# tcswiki

wiki-style
git clone https://a3nm.net/git/tcswiki/
Log | Files | Refs

Query evaluation.page (1125B)

      1 The task of **query evaluation** is concerned with the complexity of determining whether a database satisfies a logical formula. In other words, it is the analogue of the logical problem of [model checking]().
2
3 # Complexity measures
4
5 TODO: combined complexity, data complexity, query complexity
6
7 # Basic results
8
9 TODO
10
11 # Non-Boolean queries
12
13 It is often most convenient to assume that queries are Boolean, so query evaluation returns a YES/NO answer. If a query $Q(\mathbf{x})$ is non-Boolean, we can always reduce to the Boolean case by considering all possible results of the query, i.e., all tuples $\mathbf{a}$ of the active domain of the database instance, and solving query evaluation for each of the Boolean queries $Q(\mathbf{a})$. Note that this reduction is in [PTIME](Complexity classes) if the arity of the query is fixed.
14
15 A different perspective on non-Boolean queries is to write the query in [relational algebra]() and consider the evaluation of relational algebra instead.
16
17 Yet another perspective is to study the complexity of producing the query results in succession: see [Enumeration of query results]().