Complexity of First Order Queries
So far:
1. Reconsider the term of query.
2. Used the Recognation Problem to define the complexity of individual query.
3. Establish a correspondence between class of queries expressible by a language L and a complexity class QC of queries.
Now it's time to discuss the complexity of a specific language - CALC. We will show that CALC can be evaluated in LOGSPACE. This means that every CALC query can be evaluated in polylogarithmic time, using a polynomial number of processors.
The mentioned above fact explains the success of relational database systems: Relational queries can be evaluated efficiently.