Let L be a query language that does not correspond precisely to any natural complexity class of queries.
Can we say something about the complexity of queries in L?
We will want to be able to guarantee that all queries in L are in some complexity class C, even though L may not express all queries in QC.
But the bound should be meaningful – C should be a tight upper bound for the complexity of the queries in L, i.e. L should be able to express at least some queries that are among the “hardest” in C. The property of a problem being one of the hardest in a complexity class is known from complexity theory – completeness.
By extension to languages we will get the follow:
Definition: A language L is complete in respect to a complexity class c if:
a. Each query in L is also in QC.
b. There exists a query in L for which the associated recognition problem is complete with respect to the complexity class C.
In order to show completeness of a language we can use reduction in a similar way as in complexity theory.
Completeness without expressiveness - looks like a contradiction: L can express queries that are as hard as any query in QC, and can not express queries that are easier.
But there is no contradiction. The reduction of the “easy” queries to the complete one may be computationally easy, but nevertheless not expressable in L.