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
BearbeitenDie Klasse der konjunktiven Anfragen entspricht der Prädikatenlogik ohne Allquantoren , Disjunktion , Negation , also eingeschränkt auf atomare Formeln, Konjunktion und Existenzquantoren .
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:
Hierbei werden ausgezeichnete Variablen genannt, dagegen als nicht ausgezeichnet. 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) . (student2, kurs) . besucht(student, kurs) geschlecht(student, 'männlich') besucht(student2, kurs) geschlecht(student2, 'weiblich') 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
BearbeitenKonjunktive 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 und Datalog
BearbeitenKonjunktive 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]
Einzelnachweise
Bearbeiten- ↑ 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.