Subjunctive inquiry

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

definition

The class of the conjunctive queries corresponds to the predicate logic without universal quantifiers , disjunction , negation , i.e. restricted to atomic formulas, conjunction and existential quantifiers . ${\displaystyle \forall }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$ ${\displaystyle \wedge }$ ${\displaystyle \exists }$

Every conjunctive query can easily be rewritten in prenex normal form , which is often taken implicitly. Subjunctive queries in prenex normal form have the following general form:

${\displaystyle (x_{1},\ldots ,x_{k}).\exists x_{k+1},\ldots x_{m}.A_{1}\wedge \ldots \wedge A_{r}}$

Excellent variables are named here, but not marked as such . are atomic formulas. Subjunctive queries without a distinctive variable are called Boolean conjunctive queries. ${\displaystyle x_{1},\ldots ,x_{k}}$ ${\displaystyle x_{k+1},\ldots x_{m}}$ ${\displaystyle A_{1},\ldots ,A_{r}}$

A large part of the widespread SQL queries to relational databases can be formulated as conjunctive queries. As an example, consider a database of students with addresses, lectures they attended, and gender. The following conjunctive query can be used to find all those students who attend lectures in which at least one female participant is:

 (student, adresse) .  ${\displaystyle \exists }$(student2, kurs) .
    besucht(student, kurs)   ${\displaystyle \wedge }$ geschlecht(student, 'männlich')  ${\displaystyle \wedge }$
    besucht(student2, kurs)  ${\displaystyle \wedge }$ geschlecht(student2, 'weiblich')  ${\displaystyle \wedge }$
    wohnt(student, adresse)

There is only asked for the students and their addresses are student, and adressethe only outstanding variables in the above request, whereas the variables kursand student2are quantified only existentially, not excellent.

Conjunctive queries versus relational algebra

Conjunctive queries correspond to selection-projection-join queries in relational algebra and select-from-where queries in SQL , whereby only conjunctions of atomic equality conditions may occur in the where condition. The where condition must therefore be of the form <Spaltenname>=Konstante and <Spaltenname1>=<Spaltenname2> and .... In particular, no aggregations and sub-queries may occur here. The above query could be written in SQL like this:

 select l.student, l.adresse
 from besucht b1, geschlecht g1,
      besucht b2, geschlecht g2,
      wohnt 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';

Subjunctive queries and datalog

Conjunctive queries can also be written as data log rules. The above request corresponds to the following data log rule.

 ergebnis(student, address) :- besucht(student, kurs),  geschlecht(student, männlich),
                             besucht(student2, kurs), geschlecht(student2, weiblich),
                             wohnt(student, adresse).

In Datalog rules no quantifiers are given, but the variables in the head of the rule are implicitly quantified as universal, the variables that only appear in the body are assumed to be existentially quantified.

Every conjunctive query can be written as a rule in Datalog, but not every Datalog program as a conjunctive query. More precisely, only individual rules can be rewritten into conjunctive queries using extensional predicates. In general, it cannot be decided whether an equivalent non-recursive program exists for a datalog program - in other words a positive query of relational algebra or a formula of positive existential predicate logic. This problem is known as the Datalog Boundedness Problem.

Individual evidence

1. ^ Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. In: J. Log. Program. Volume 25, No. 2, 1995, pp. 163-190.