Konjunktive Anfrage

Die Klasse der konjunktiven Anfragen entspricht der Prädikatenlogik ohne Allquantoren ${\displaystyle \forall }$, Disjunktion ${\displaystyle \vee }$, Negation${\displaystyle \neg }$, also eingeschränkt auf atomare Formeln, Konjunktion ${\displaystyle \wedge }$ und Existenzquantoren ${\displaystyle \exists }$.

Jede konjunktive Anfrage kann leicht in Pränexnormalform umgeschrieben werden, welche oftmals implizit angenommen wird. Konjunktive Anfragen in Pränexnormalform haben die folgende allgemeine Form:

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

Hierbei werden ${\displaystyle x_{1},\ldots ,x_{k}}$ ausgezeichnete Variablen genannt, ${\displaystyle x_{k+1},\ldots x_{m}}$ dagegen als nicht ausgezeichnet. ${\displaystyle A_{1},\ldots ,A_{r}}$ sind atomare Formeln. Konjunktive Anfragen ohne ausgezeichnete Variable heißen boolesche konjunktive Anfragen.

Ein großer Teil der weit verbreiteten SQL Anfragen an relationale Datenbanken können als konjunktive Anfragen formuliert werden. Betrachten wir als Beispiel eine Datenbank über Studenten mit Adressen, von ihnen besuchten Vorlesungen und Geschlecht. Mit der folgenden konjunktiven Anfrage kann man all diejenigen Studenten finden, welche Vorlesungen besuchen, in der mindestens eine weibliche Teilnehmerin ist:

 (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)

Da nur nach den Studenten und ihren Adressen gefragt ist, sind student und adresse die einzigen ausgezeichneten Variablen in obiger Anfrage, wohingegen die Variablen kurs und student2 nur existentiell quantifiziert sind, also nicht ausgezeichnet.

Konjunktive Anfragen entsprechen Selektions-Projektions-Join-Anfragen in der Relationenalgebra und Select-From-Where-Anfragen in SQL, wobei in der Where-Bedingung nur Konjunktionen atomarer Gleichheitsbedingungen vorkommen dürfen. Die Where-Bedingung muss also von der Form <Spaltenname>=Konstante and <Spaltenname1>=<Spaltenname2> and ... sein. Insbesondere dürfen hier keine Aggregationen und Subanfragen vorkommen. Die obige Anfrage könnte in SQL wie folgt geschrieben werden:

 select l.student, l.adresse
 from besucht b1, geschlecht g1,
      besucht b2, geschlecht g2,
      wohnt l
 where b1.student=g1.student
 and   b2.student=g2.student
 and   l.student=g1.student
 and   b1.kurs=b2.kurs
 and   g1.gender='male'
 and   g2.gender='female';

Konjunktive Anfragen können auch als Datalog-Regeln geschrieben werden. So entspricht obige Anfrage folgender Datalog-Regel.

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

In Datalog Regeln werden keine Quantoren angegeben, die Variablen im Kopf der Regel werden jedoch implizit als universell quantifiziert, die Variablen welche nur im Rumpf vorkommen als existentiell quantifiziert angenommen.

Es kann zwar jede konjunktive Anfrage als Regel in Datalog geschrieben werden, aber nicht jedes Datalog Programm als konjunktive Anfrage. Genauer gesagt können nur einzelne Regeln über extensionale Prädikate in konjunktive Anfragen umgeschrieben werden. Im Allgemeinen ist es nicht entscheidbar, ob für ein Datalogprogramm ein äquivalentes nicht-rekursives Programm -- in anderen Worten eine positive Anfrage der relationalen Algebra oder eine Formel der positiven existentiellen Prädikatenlogik existiert. Dieses Problem wird als das Datalog Boundedness Problem bezeichnet.[1]

1. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. In: J. Log. Program. Band 25, Nr. 2, 1995, S. 163–190.