git clone
Log | Files | Refs

commit 901a0bf733d26761bd47f2034bf62d86e3fb3f2c
parent 6a7a49d6fa0a03f61c14f34ff0c34911dbd9ba09
Author: a3nm <>
Date:   Sun, 17 Jun 2018 02:20:07 +0200

non-boolean, etc.

Query | 18++++++++++++++++++
1 file changed, 18 insertions(+), 0 deletions(-)

diff --git a/Query b/Query @@ -0,0 +1,17 @@ +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](). + +# Complexity measures + +TODO: combined complexity, data complexity, query complexity + +# Basic results + +TODO + +# Non-Boolean queries + +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. + +A different perspective on non-Boolean queries is to write the query in [relational algebra]() and consider the evaluation of relational algebra instead. + +Yet another perspective is to study the complexity of producing the query results in succession: see [Enumeration algorithms]().+ \ No newline at end of file