HOME

TheInfoList



OR:

In database theory, a conjunctive query is a restricted form of first-order queries using the
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational databases can be expressed in this way. Conjunctive queries also have a number of desirable theoretical properties that larger classes of queries (e.g., the relational algebra queries) do not share.


Definition

The conjunctive queries are the fragment of (domain independent)
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
given by the set of formulae that can be constructed from atomic formulae using conjunction ∧ and existential quantification ∃, but not using
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
∨,
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
¬, or universal quantification ∀. Each such formula can be rewritten (efficiently) into an equivalent formula in prenex normal form, thus this form is usually simply assumed. Thus conjunctive queries are of the following general form: :(x_1, \ldots, x_k).\exists x_, \ldots x_m. A_1 \wedge \ldots \wedge A_r, with the free variables x_1, \ldots, x_k being called distinguished variables, and the bound variables x_, \ldots, x_m being called undistinguished variables. A_1, \ldots, A_r are atomic formulae. As an example of why the restriction to domain independent first-order logic is important, consider x_1.\exists x_2. R(x_2), which is not domain independent; see Codd's theorem. This formula cannot be implemented in the select-project-join fragment of relational algebra, and hence should not be considered a conjunctive query. Conjunctive queries can express a large proportion of queries that are frequently issued on relational databases. To give an example, imagine a relational database for storing information about students, their address, the courses they take and their gender. Finding all male students and their addresses who attend a course that is also attended by a female student is expressed by the following conjunctive query: (student, address) . ∃ (student2, course) . attends(student, course) ∧ gender(student, 'male') ∧ attends(student2, course) ∧ gender(student2, 'female') ∧ lives(student, address) Note that since the only entity of interest is the male student and his address, these are the only distinguished variables, while the variables course, student2 are only
existentially quantified In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, whe ...
, i.e. undistinguished.


Fragments

Conjunctive queries without distinguished variables are called boolean conjunctive queries. Conjunctive queries where all variables are distinguished (and no variables are bound) are called equi-join queries, because they are the equivalent, in the
relational calculus The relational calculus consists of two calculi, the tuple relational calculus and the domain relational calculus, that are part of the relational model The relational model (RM) is an approach to managing data using a Structure (mathematical ...
, of the
equi-join A join clause in SQL – corresponding to a Join (relational algebra), join operation in relational algebra – combines column (database), columns from one or more table (database), tables into a new table. Informally, a join stitches two tables a ...
queries in the relational algebra (when selecting all columns of the result).


Relationship to other query languages

Conjunctive queries also correspond to select-project-join queries in relational algebra (i.e., relational algebra queries that do not use the operations union or difference) and to select-from-where queries in SQL in which the where-condition uses exclusively conjunctions of atomic equality conditions, i.e. conditions constructed from column names and constants using no comparison operators other than "=", combined using "and". Notably, this excludes the use of aggregation and subqueries. For example, the above query can be written as an SQL query of the conjunctive query fragment as select l.student, l.address from attends a1, gender g1, attends a2, gender g2, lives l where a1.student = g1.student and a2.student = g2.student and l.student = g1.student and a1.course = a2.course and g1.gender = 'male' and g2.gender = 'female';


Datalog

Besides their logical notation, conjunctive queries can also be written as
Datalog Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
rules. Many authors in fact prefer the following Datalog notation for the query above: result(student, address) :- attends(student, course), gender(student, male), attends(student2, course), gender(student2, female), lives(student, address). Although there are no quantifiers in this notation, variables appearing in the head of the rule are still implicitly universally quantified, while variables only appearing in the body of the rule are still implicitly existentially quantified. While any conjunctive query can be written as a Datalog rule, not every Datalog program can be written as a conjunctive query. In fact, only single rules over extensional predicate symbols can be easily rewritten as an equivalent conjunctive query. The problem of deciding whether for a given Datalog program there is an equivalent nonrecursive program (corresponding to a positive relational algebra query, or, equivalently, a formula of positive existential
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
, or, as a special case, a conjunctive query) is known as the
Datalog boundedness Datalog is a Declarative programming, declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different ...
problem and is undecidable.


Extensions

Extensions of conjunctive queries capturing more expressive power include: * unions of conjunctive queries, which are equivalent to positive (i.e.,
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
-free) relational algebra * conjunctive queries extended by union and
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
, which by Codd's theorem correspond to relational algebra and
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
* conjunctive queries with built-in predicates, e.g., arithmetic predicates * conjunctive queries with
aggregate function In database management, an aggregate function or aggregation function is a function where the values of multiple rows are grouped together to form a single summary value. Common aggregate functions include: * Average (i.e., arithmetic mean) * ...
s. The formal study of all of these extensions is justified by their application in
relational databases A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
and is in the realm of database theory.


Complexity

For the study of 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 evaluating conjunctive queries, two problems have to be distinguished. The first is the problem of evaluating a conjunctive query on a relational database where both the query and the database are considered part of the input. The complexity of this problem is usually referred to as combined complexity, while the complexity of the problem of evaluating a query on a relational database, where the query is assumed fixed, is called data complexity. Conjunctive queries are
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
with respect to combined complexity, while the data complexity of conjunctive queries is very low, in the parallel complexity class AC0, which is contained in LOGSPACE and thus in
polynomial time In 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 performed by ...
. The
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
ness of conjunctive queries may appear surprising, since relational algebra and SQL strictly subsume the conjunctive queries and are thus at least as hard (in fact, relational algebra is PSPACE-complete with respect to combined complexity and is therefore even harder under widely held complexity-theoretic assumptions). However, in the usual application scenario, databases are large, while queries are very small, and the data complexity model may be appropriate for studying and describing their difficulty. The problem of listing all answers to a non-Boolean conjunctive query has been studied in the context of enumeration algorithms, with a characterization (under some computational hardness assumptions) of the queries for which enumeration can be performed with
linear time In 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 performed by t ...
preprocessing and constant delay between each solution. Specifically, these are the acyclic conjunctive queries which also satisfy a ''free-connex'' condition.


Formal properties

Conjunctive queries are one of the great success stories of database theory in that many interesting problems that are computationally hard or undecidable for larger classes of queries are feasible for conjunctive queries. Serge Abiteboul,
Richard B. Hull Richard is a male given name. It originates, via Old French, from Old Frankish and is a compound of the words descending from Proto-Germanic ''*rīk-'' 'ruler, leader, king' and ''*hardu-'' 'strong, brave, hardy', and it therefore means 'stron ...
, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
For example, consider the query containment problem. We write R \subseteq S for two
database relation In database theory, a relation, as originally defined by E. F. Codd, is a set of tuples (d1, d2, ..., dn), where each element dj is a member of Dj, a data domain. Codd's original definition notwithstanding, and contrary to the usual ...
s R, S of the same
schema The word schema comes from the Greek word ('), which means ''shape'', or more generally, ''plan''. The plural is ('). In English, both ''schemas'' and ''schemata'' are used as plural forms. Schema may refer to: Science and technology * SCHEMA ...
if and only if each tuple occurring in R also occurs in S. Given a query Q and a relational database instance I, we write the result relation of evaluating the query on the instance simply as Q(I). Given two queries Q_1 and Q_2 and a
database schema The database schema is the structure of a database described in a formal language supported by the database management system (DBMS). The term " schema" refers to the organization of data as a blueprint of how the database is constructed (divid ...
, the query containment problem is the problem of deciding whether for all possible database instances I over the input database schema, Q_1(I) \subseteq Q_2(I). The main application of query containment is in query optimization: Deciding whether two queries are equivalent is possible by simply checking mutual containment. The query containment problem is undecidable for relational algebra and SQL but is decidable and
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
for conjunctive queries. In fact, it turns out that the query containment problem for conjunctive queries is exactly the same problem as the query evaluation problem. Since queries tend to be small,
NP-completeness In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
here is usually considered acceptable. The query containment problem for conjunctive queries is also equivalent to the constraint satisfaction problem. An important class of conjunctive queries that have polynomial-time combined complexity are the acyclic conjunctive queries. The query evaluation, and thus query containment, is LOGCFL-complete and thus in
polynomial time In 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 performed by ...
. Acyclicity of conjunctive queries is a structural property of queries that is defined with respect to the query's
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...
: a conjunctive query is acyclic if and only if it has hypertree-width 1. For the special case of conjunctive queries in which all relations used are binary, this notion corresponds to the treewidth of the dependency graph of the variables in the query (i.e., the graph having the variables of the query as nodes and an undirected edge \ between two variables if and only if there is an atomic formula R(x,y) or R(y,x) in the query) and the conjunctive query is acyclic if and only if its dependency graph is acyclic. An important generalization of acyclicity is the notion of bounded hypertree-width, which is a measure of how close to acyclic a hypergraph is, analogous to bounded treewidth in graphs. Conjunctive queries of bounded tree-width have LOGCFL combined complexity. Unrestricted conjunctive queries over tree data (i.e., a relational database consisting of a binary child relation of a tree as well as unary relations for labeling the tree nodes) have polynomial time combined complexity. Georg Gottlob,
Christoph Koch Christoph is a male given name and surname. It is a German variant of Christopher. Notable people with the given name Christoph * Christoph Bach (1613–1661), German musician * Christoph Büchel (born 1966), Swiss artist * Christoph Dientzenhofe ...
,
Klaus U. Schulz Klaus is a German, Dutch and Scandinavian given name and surname. It originated as a short form of Nikolaus, a German form of the Greek given name Nicholas. Notable persons whose family name is Klaus *Billy Klaus (1928–2006), American baseba ...
: Conjunctive queries over trees. J. ACM 53(2): 238-272 (2006)


References


External links


Ullman, J. D. ''Information integration using logical views Theoretical Computer Science'', 2000, 239, 189-210
{cbignore, bot=medic * Georg Gottlob
Presentation on structural decomposition methods for the efficient evaluation of conjunctive queries (PDF)
Database theory