en>Monkbot: /* References */Task 3: Fix CS1 deprecated coauthor parameter errors

2014-05-07T01:43:12Z

References: Task 3: Fix CS1 deprecated coauthor parameter errors

en>Sodin: added Category:Probability theorems using HotCat

2011-10-13T16:57:16Z

added Category:Probability theorems using HotCat

New page

In [[database theory]], a '''conjunctive query''' is a restricted form of [[first-order logic|first-order]] queries. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on [[relational database]]s 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 simply the fragment of (domain independent) [[first-order logic]] given by the set of
formulae that can be constructed from [[atomic formula]]e using [[Logical conjunction|conjunction]] <math>\wedge</math> and
[[existential quantification]] <math>\exists</math>, but not using [[disjunction]] <math>\lor</math>, [[negation]] <math>\neg</math>,
or [[universal quantification]] <math>\forall</math>.
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:

:<math>(x_1, \ldots, x_k).\exists x_{k+1}, \ldots x_m. A_1 \wedge \ldots \wedge A_r</math>,

with the [[Free variables and bound variables|free variables]] <math>x_1, \ldots, x_k</math> being called distinguished variables, and the [[Free variables and bound variables|bound variables]] <math>x_{k+1}, \ldots, x_m</math> being called undistinguished variables. <math>A_1, \ldots, A_r</math> are [[atomic formula]]e. Conjunctive queries without distinguished variables are called [[boolean conjunctive query|boolean conjunctive queries]].

As an example of why the restriction to domain independent first-order logic is important, consider <math>x_1.\exists x_2. R(x_2)</math>, 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 part of queries, which are frequently issued on [[relational database]]s. To give an example, imagine a relational database for storing information about students, their address, the courses they visit 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:

<code>
(student, address) . <math>\exists</math>(student2, course) .
attends(student, course) <math>\wedge</math> gender(student, 'male') <math>\wedge</math>
attends(student2, course) <math>\wedge</math>
gender(student2, 'female') <math>\wedge</math> lives(student, address)
</code>

Note that since the only entity of interest is the male student and his address, these are the only distinguished variables, while the variables <code>course</code>, <code>student2</code> are only [[existential quantification|existentially quantified]], i.e. undistinguished.

==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
<code>
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';
</code>

==Conjunctive queries and datalog==
Besides their logical notation, conjunctive queries can also be written as [[datalog]] rules. Many authors in fact prefer the following datalog notation for the query above:

<code>
result(student, address) :- attends(student, course), gender(student, male),
attends(student2, course), gender(student2, female),
lives(student, address).
</code>

Although there are no quantifiers in this notation, variables appearing in the head of the rule are still implicitly [[universal quantification|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 [[recursion|nonrecursive program]] (corresponding to a positive relational algebra query, or, equivalently, a formula of positive existential [[first-order logic]], or, as a special case, a conjunctive query) is known as the [[datalog boundedness]] problem and is undecidable.<ref>[[Gerd G. Hillebrand]], [[Paris C. Kanellakis]], [[Harry G. Mairson]], [[Moshe Y. Vardi]]: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190 (1995)</ref>

==Extensions of conjunctive queries==
Extensions of conjunctive queries capturing more [[expressive power]] include unions of conjunctive queries, which are equivalent to positive (i.e., [[negation]]-free) [[relational algebra]], conjunctive queries extended by union and [[negation]], which by [[Codd's theorem]] correspond to [[relational algebra]] and [[first-order logic]], conjunctive queries with built-in predicates and conjunctive queries with [[aggregate function]]s. The formal study of all of these extensions is justified by their application in [[relational databases]] and is in the realm of [[database theory]].

==Complexity of conjunctive queries==
For the study of the [[computational complexity]] 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'''.<ref>{{Citation | last=Vardi | first=Moshe Y. | authorlink=Moshe Y. Vardi | contribution=The Complexity of Relational Query Languages (Extended Abstract) | series=STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing | year=1982 | pages=137–146 | contribution-url=http://www.cs.rice.edu/~vardi/papers/stoc82.pdf.gz | doi=10.1145/800070.802186}}</ref>

Conjunctive queries are [[NP-complete]] with respect to combined complexity,<ref>[[Ashok K. Chandra]] and [[Philip M. Merlin]], 1977. ''Optimal Implementation of Conjunctive Queries in Relational Data Bases''. STOC '77: Proceedings of the ninth annual ACM symposium on Theory of computing [http://portal.acm.org/citation.cfm?id=803397&coll=portal&dl=ACM]</ref> 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]]. The [[NP-hard]]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.

==Formal properties of conjunctive queries==
Conjunctive queries are one of the great success stories of [[database theory]] in that many interesting problems that are computationally hard or [[undecidability|undecidable]] for larger classes of queries are feasible for conjunctive queries.<ref name="AHV">[[Serge Abiteboul]], [[Richard B. Hull]], [[Victor Vianu]]: Foundations of Databases. Addison-Wesley, 1995.</ref> For example, consider the query containment problem. We write <math>R \subseteq S</math> for two [[database relation]]s <math>R, S</math> of the same [[database schema|schema]] if and only if each tuple occurring in <math>R</math> also occurs in <math>S</math>. Given a query <math>Q</math> and a [[relational database]] instance <math>I</math>, we write the result relation of evaluating the query on the instance simply as <math>Q(I)</math>. Given two queries <math>Q_1</math> and <math>Q_2</math> and a [[database schema]], the query containment problem is the problem of deciding whether for all possible database instances <math>I</math> over the input database schema, <math>Q_1(I) \subseteq Q_2(I)</math>. 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]] 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.<ref name="AHV"/> Since queries tend to be small, [[NP-completeness]] here is usually considered acceptable. The query containment problem for conjunctive queries is also equivalent to the [[constraint satisfaction problem]].<ref>{{Citation
| last = Kolaitis
| first = Phokion G.
| last2 = Vardi
| first2 = Moshe Y.
| title = Conjunctive-Query Containment and Constraint Satisfaction
| journal = Journal of Computer and System Sciences
| volume = 61
| pages = 302–332
| year = 2000
| doi = 10.1006/jcss.2000.1713}}</ref>

An important class of conjunctive queries that have polynomial-time combined complexity are the '''acyclic''' conjunctive queries.<ref>[[Mihalis Yannakakis]]: Algorithms for Acyclic Database Schemes . Proc. VLDB 1981: 82-94.</ref> The query evaluation, and thus query containment, is [[LOGCFL]]-complete and thus in [[polynomial time]].<ref>[[Georg Gottlob]], [[Nicola Leone]], and [[Francesco Scarcello]] (2001). "The complexity of acyclic conjunctive queries". Journal of the ACM (JACM) 48 (3): 431–498. {{doi|10.1145/382780.382783}}.</ref> Acyclicity of conjunctive queries is a structural property of queries that is defined with respect to the query's [[hypergraph]]:<ref name="AHV"/> 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 <math>\{x,y\}</math> between two variables if and only if there is an atomic formula <math>R(x,y)</math> or <math>R(y,x)</math> in the query) and the conjunctive query is acyclic if and only if its dependency graph is [[Graph (mathematics)|acyclic]].

An important generalization of acyclicity is the notion of [[hypertree decomposition|bounded hypertree-width]], which is a measure of how close to acyclic a hypergraph is, analogous to bounded [[treewidth]] in [[graph (mathematics)|graphs]]. Conjunctive queries of bounded tree-width have [[LOGCFL]] combined complexity.<ref>[[Georg Gottlob]], [[Nicola Leone]], and [[Francesco Scarcello]]: Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci. 64(3): 579-627 (2002)</ref>

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.<ref>[[Georg Gottlob]], [[Christoph Koch]], [[Klaus U. Schulz]]: Conjunctive queries over trees. J. ACM 53(2): 238-272 (2006)</ref>

==References==
{{Reflist}}

==External links==
*[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-43G4RRN-2&_user=5423704&_coverDate=05/28/2000&_rdoc=2&_fmt=summary&_orig=browse&_srch=doc-info(%23toc%235674%232000%23997609997%23255297%23FLP%23display%23Volume)&_cdi=5674&_sort=d&_docanchor=&_ct=8&_acct=C000007438&_version=1&_urlVersion=0&_userid=5423704&md5=adc35b17aaf28963cc6925a017813785 Ullman, J. D. ''Information integration using logical views Theoretical Computer Science'', 2000, 239, 189-210]

*[[Georg Gottlob]], [http://www.dis.uniroma1.it/~lenzerin/homepagine/didattica/viewbasedqueryprocessing/ConjunctiveQueries.pdf Presentation on structural decomposition methods for the efficient evaluation of conjunctive queries (PDF)]

[[Category:Database theory]]

Contraction principle (large deviations theory) - Revision history

en>Monkbot: /* References */Task 3: Fix CS1 deprecated coauthor parameter errors

en>Sodin: added Category:Probability theorems using HotCat