Languages and Complexity
Untill now we defined the complexity of an individual query.
How can we measure the complexity of query language L?
Establish a correspondence between:
1. The class of queries expressible by L.
2. A complexity class QC of queries.
Expressivness and Completeness:
The most straightforward connection between L and the class of queries QC is when L and QC are precisely the same, i.e. each query in L has complexity C, and L can express every query of complexity C. In this case, we say that L expresses QC.
Eureka!
For a given class QC, let’s design a language expressing precisely QC.
Unfortunately, this is not always possible - no such results for the pure relational model for complexity classes of polynomial time or below.
In general, classes of queries of low complexity can not be expressed by any known languages. Therefore we are led to consider a less straightforward way to match languages to complexity classes.