Konjunktive Anfrage

Konjunktive Anfragen sind eine Einschränkung von Anfragen der Prädikatenlogik und haben eine Reihe an wünschenswerten Eigenschaften, die in der Datenbanktheorie intensiv untersucht worden sind. Viele Anfragen an relationale Datenbanken -- und damit auch viele SQL-Anfragen -- sind konjunktive Anfragen.

Definition

Die Klasse der konjunktiven Anfragen entspricht der Prädikatenlogik ohne Allquantoren $\forall$, Disjunktion $\vee$, Negation$\neg$, also eingeschränkt auf atomare Formeln, Konjunktion $\wedge$ und Existenzquantoren $\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:

$(x_1, \ldots, x_k).\exists x_{k+1}, \ldots x_m. A_1 \wedge \ldots \wedge A_r$

Hierbei werden $x_1, \ldots, x_k$ ausgezeichnete Variablen genannt, $x_{k+1}, \ldots x_m$ dagegen als nicht ausgezeichnet. $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) . $\exists$(student2, kurs) .
    besucht(student, kurs) $\wedge$ geschlecht(student, 'männlich') $\wedge$ 
    (student2, kurs) $\wedge$
    gender(student2, 'weiblich') $\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 versus Relationale Algebra

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 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 Anfragen und Datalog

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 allgemneinen 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].

Einzelnachweise

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