database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...

, the query evaluation problem is the

problem Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from simple personal tasks (e.g. how to turn on an appliance) to complex issues in business an ...

of determining the answers to a query on a database. Research in database theory aims at determining the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

of answering different kinds of queries over databases, in particular over

relational database A relational database (RDB) is a database based on the relational model of data, as proposed by E. F. Codd in 1970. A Relational Database Management System (RDBMS) is a type of database management system that stores data in a structured for ...

Formal definition

The query evaluation problem takes two inputs: the query to be answered, and the database on which to answer it. The output of the problem is the set of answers to the query on the database. If the queries are ''Boolean queries'', i.e., queries have a yes or no answer (for example, Boolean conjunctive queries) then the query evaluation problem is a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

. The query evaluation problem is usually posed for a specific class of queries and databases. For instance, one example of the query evaluation problem would be the problem of evaluating a

conjunctive query In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational ...

on a

. The computational complexity of the problem can be measured in different ways, to account for the fact that the two inputs of the problem are different: * The combined complexity of the query evaluation problem is its

when measured as a function of the two inputs, i.e., the query and the database, as usual in computational complexity. * The data complexity is the computational complexity when the query is fixed and when the input is just the database. For instance, we say that query evaluation has

polynomial-time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

data complexity for a class of queries if, for every fixed query ''Q'' in that class, given a database ''D'', we can compute the answers to ''Q'' on ''D'' in polynomial time. * Less commonly, we can study the query complexity, which is the computational complexity when the database is fixed and when the input is just the query. This is also called expression complexity.

Query classes

The complexity of query evaluation can be studied for several query classes, for instance acyclic queries, conjunctive queries, unions of conjunctive queries, Datalog, regular path queries, etc., up to logical formalisms like

first-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...

monadic second-order logic In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's ...

. For instance, for Boolean conjunctive queries, the complexity of query evaluation is polynomial in data complexity: it even falls in the class AC0. By contrast, the query complexity and combined complexity are

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

by a reduction from 3-colorability.

Boolean versus non-Boolean queries

The complexity of query evaluation can be studied for queries that return answers, or for Boolean queries (yes/no queries). However, we can often reduce to the case of Boolean queries. More specifically, if the number of answers to the query is always polynomial in the database size, and if we can rewrite the query to a Boolean query for each answer, then we can reduce query evaluation for a non-Boolean query to polynomially many Boolean query evaluation problems.

References

{{reflist Database theory