Conjunctive query

Conjunctive queries are a restriction of queries of predicate logic and have a number of desirable properties which have been extensively studied in database theory. Many queries to relational databases - and thus many SQL queries - are conjunctive queries.

Definition

The class of conjunctive queries corresponding to the predicate logic without universal quantifiers, disjunction, negation, ie restricted to atomic formulas, conjunction and existential quantifiers.

Each conjunctive query can be easily rewritten in Pränexnormalform, which is often implicitly assumed. Conjunctive queries in Pränexnormalform have the following general form:

These are called distinguished variables, on the other hand not awarded. are atomic formulas. Conjunctive queries without excellent variable called Boolean conjunctive queries.

A lot of the widespread SQL queries to relational databases may be formulated as conjunctive queries. For example, consider a database of students with addresses, they attended lectures and gender. With the following conjunctive query can be found all those students who attend lectures, in which at least one female participant:

( student, address ). ( student2, course ).      attended ( student, course ) gender ( student, ' male ')      visited ( student2, course ) gender ( student2, ' female ')      lives ( student, address ) There is only asked for the students and their addresses, the only variables are excellent student and address in the above request, whereas the variable rate and are only existentially quantified student2, not excellent.

Conjunctive queries versus Relational Algebra

Conjunctive queries correspond selection -projection -join queries in relational algebra and Select -From -Where queries in SQL, which may occur only conjunctions of atomic equality conditions in the Where clause. So the Where clause must be of the form = constant and = and ... be. In particular, no aggregations and Subanfragen may occur here. The above query could be written in SQL as follows:

Select l.student, l.adresse   from visits b1, g1 gender,        visited b2, g2 gender,        lives l   where a1.student = g1.student   and a2.student = g2.student   and l.student = g1.student   and a1.kurs = a2.kurs   and g1.gender = ' male '   and g2.gender = ' female '; Konjunkive queries and Datalog

Conjunctive queries can be written as Datalog rules. So above query corresponds to the following Datalog rule.

Income ( student, address): - visited ( student, course ), gender ( student, male)                               visited ( student2, course ), gender ( student2, female),                               lives ( student, address ). In Datalog rules no quantifiers are specified, the variables in the head of the rule, however, implicitly quantified as universal, the variables which occur adopted as existentially quantified only in the fuselage.

It may indeed any conjunctive query can be written as a rule in Datalog, but not every Datalog program as a conjunctive query. Specifically, few rules on extensional predicates in conjunctive queries can be rewritten. In general it is not decidable whether an equivalent non- recursive program for a Datalogprogramm - in other words, a positive request of the relational algebra or a formula of the positive existential predicate logic exists. This problem is referred to as the Datalog boundedness problem.