Conjunctive query

From Wikipedia, the free encyclopedia

This article or section needs to be wikified to meet Wikipedia's quality standards.
Please help improve this article with relevant internal links. (September 2007)

All or part of this article may be confusing or unclear.
Please help clarify the article. Suggestions may be on the talk page. (September 2007)

In database theory, a conjunctive query is a restricted form of first-order queries, which are said to be particularly easy to grasp for novice users. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first-order queries can be written as conjunctive queries.

Conjunctive queries are of the general form $(x_1, \ldots, x_k). \exists x_{k+1}, \ldots x_m. A_1 \wedge \ldots \wedge A_r$ , with the variables $x_1, \ldots, x_k$ being called distinguished variables, and the variables $x_{k+1}, \ldots, x_m$ being called undistinguished variables. $A_1, \ldots, A_r$ are atomic formulae. Conjunctive queries without distinguished variables are called boolean conjunctive queries.

Conjunctive queries can express a large part of queries, which are frequently issued on relational data bases. To give an example, imagine a relational data base 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:

(student, address) . (student2, course) .

attends(student, course) gender(student, 'male') attends(student2, course)

gender(student2, 'female') lives(student, address)

Note that since the only entities we are interested in is the male student and his address, these are the only distinguished variables, while the variables course, student2 are only existentially quantified, i.e. undistinguished.

1 Conjunctive Queries and Datalog
2 Extensions of Conjunctive Queries
3 References
4 External links

[edit] 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:

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 implicitely universally quantified, while variables only appearing in the body of the rule are still implicitely 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 rewritten as an equivalent conjunctive query.

[edit] Extensions of Conjunctive Queries

Extensions of conjunctive queries capturing more expressive power include conjunctive queries with negation, conjunctive queries with built-in predicates and conjunctive queries with aggregate functions. The formal study of all of these extensions is justified by their application in relational databases.

[edit] References

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 [1]