Complexity of queries
Objective: Find a framework for measuring the complexity of queries.
Tools: Classical complexity classes defined using the TM model.
2 main possibilities to measure the complexity of queries:
1. Data complexity – the complexity of evaluating a fixed query for variable database inputs. The complexity is with respect to the database input and the query is considered constant.
2. Expression complexity – the complexity of evaluating, on a fixed database instance, the verious queries specifiable in a given query language. The complexity is with respect to the size of the query expression and the database input is fixed.
In most cases the size of the database input dominates by far the the size of the query, therefor when we use the term complexity we will refer to the term data complexity.