9 Auswertung von Anfrageoperatoren (S.217)

Wir haben in den voran gehenden Kapiteln gesehen, wie wir eine Datenbank strukturieren und wie wir Anfragen an sie formulieren können. Wir kennen die grundlegenden Speichertechniken und Indexstrukturen einer physischen Datenbank. In diesem Kapitel wollen wir zunächst diskutieren, wie geeignete Basisoperatoren einer Anfragesprache auf den Gegebenheiten einer physischen Datenbank effizient ausgewertet werden können.

Basisoperatoren sind primär die Operatoren der Relationenalgebra; die für SQL typischen Aggregierungsoperatoren werden wir streifen. Darüber hinaus wollen wir die grundlegenden Prinzipien eines Anfrageoptimierers kennen lernen. Damit schließt sich die letzte Lücke zwischen der Formulierung einer Anfrage und ihrer Auswertung.

Wir behandeln auch die Problematik einer effizienten Auswertung eines XPath- Ausdrucks über einem in einer relationalen Datenbank gespeicherten XMLBaum. Wir präsentieren eine für alle Achsen eines XPath-Ausdrucks anwendbare Auswertungstechnik und stellen eine Optimierung für die descendant- Achse vor.

9.1 Selektion

Beginnen wir mit einer Selektion der Form ó[A op val]R, wobei R ein Relationsschema, A ein Attribut von R und op ein arithmetischer Vergleichsoperator. Angenommen, für R existiert keine Indexstruktur zu A und die Relationen zu R seien nicht nach A sortiert gespeichert. In diesem Fall kann nur mittels vollständigem Durchsuchen der Relation die Selektion ausgewertet werden.

Liegt eine Sortierung zu A vor, dann können wir das Tupel mit Suchschlüsselwert val durch binäres Suchen lokalisieren und, sofern op nicht der Gleichheitsoperator, die restlichen die Suchbedingung erfüllenden Tupel ausgehend hiervon bestimmen. Analog, liegt eine Baum-Indexstruktur über A vor, können wir das Tupel mit Suchschlüsselwert val, bzw. seine Adresse, lokalisieren und die restlichen die Suchbedingung erfüllenden Tupel, bzw. ihre Adressen, ausgehend von diesem erreichen. Eine Hash-Indexstruktur kann hier nur helfen, wenn op der Gleichheitsoperator ist.

Angenommen, die Selektionsbedingung besteht aus einer Konjunktion atomarer Selektionsbedingungen. Sei beispielsweise (LGrad < 10 ∧ BGrad < 50) eine Bedingung über der Relation Stadt. Existiert zu keinem der beiden Attribute eine Indexstruktur, dann bleibt nur ein vollständiges Durchsuchen der Relation. Für jedes gefundene Tupel kann dann die Bedingung überprüft werden.

Existiert mindestens eine Indexstruktur zu den Attributen der Selektionsbedingung, dann können wir in Abhängigkeit dieser Bedingung auf die Tupel zugreifen und für jedes gelesene Tupel die restlichen Bedingungen überprüfen. Existieren getrennte Indexstrukturen zu beiden Attributen, dann kann alternativ zunächst der Durchschnitt der entsprechenden Adresslisten gebildet werden und danach zu den die gesamte Bedingung erfüllenden Tupeln zugegriffen werden. Steht ein geeigneter mehrdimensionaler Index über beiden Attributen zur Verfügung, dann kann mittels diesem direkt zu den die Eigenschaften erfüllenden Tupel zugegriffen werden.

Haben wir in der Selektionsbedingung Disjunktionen, dann überführen wir die Selektionsbedingung zunächst in konjunktive Normalform, d.h., eine Konjunktion von Disjunktionen. Sei beispielsweise (Einwohner > 1000 ∨ (LGrad < 10 ∧ BGrad < 50)) die ursprüngliche Bedingung, dann erhalten wir die konjunktive Normalform ((Einwohner > 1000 ∨ LGrad < 10) ∧(Einwohner > 1000 ∨ BGrad < 50)).

Für eine möglichst effizienten Auswertung werden wir zunächst versuchen, konjunktiv verknüpfte Selektionsbedingungen zur Einschränkung der zu betrachtenden Tupel auszuwerten. In unserem Beispiel werden wir zunächst eine der beiden Disjunktion auswerten und dann die andere auf der resultierenden Menge von Tupeln betrachten.