imported>Invisigoth67: typo, form

2024-07-09T14:20:00Z

typo, form

Neue Seite

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

== Definition ==

Die Klasse der konjunktiven Anfragen entspricht der [[Prädikatenlogik]] ohne [[Allquantor]]en <math>\forall</math>, [[Disjunktion]] <math>\vee</math>, [[Negation]]<math>\neg</math>, also eingeschränkt auf atomare Formeln, [[Konjunktion (Logik)|Konjunktion]] <math>\wedge</math> und
[[Existenzquantor]]en <math>\exists</math>.

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:

<math>(x_1, \ldots, x_k).\exists x_{k+1}, \ldots x_m. A_1 \wedge \ldots \wedge A_r</math>

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

Da nur nach den Studenten und ihren Adressen gefragt ist, sind <code>student</code> und <code>adresse</code> die einzigen ausgezeichneten Variablen in obiger Anfrage, wohingegen die Variablen <code>kurs</code> und <code>student2</code> 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 <code><nowiki><Spaltenname>=Konstante and <Spaltenname1>=<Spaltenname2> and ...</nowiki></code> sein. Insbesondere dürfen hier keine [[Aggregation (Informatik)|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 ==

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.<ref>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.</ref>

== Einzelnachweise ==
<references />

[[Kategorie:Datenbanktheorie]]

Konjunktive Anfrage - Versionsgeschichte

imported>Invisigoth67: typo, form