along/secondo
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
secondo/Optimizer/Subqueries/kapitel/review.tex

390 lines
39 KiB
TeX
Raw Permalink Normal View History

firs commit
2026-01-23 17:03:45 +08:00
%
% Review
%
%
\chapter{Review}\label{chp:Review}
Dieses Kapitel gibt einen <20>berblick <20>ber die f<>r die Umsetzung dieser Arbeit verwendeten Technologien und deren theoretische Grundlagen. Anschlie<69>end werden die in der Literatur bekannten Ans<6E>tze zur Optimierung geschachtelter Abfragen dargestellt.
\section{<EFBFBD>berblick}\label{sct:<3A>berblick}
Ein Datenbanksystem ist eine Sammlung zusammenh<6E>ngender Dateien und Programme, die es einem Benutzer erlauben auf diese Dateien zuzugreifen und diese zu <20>ndern. Eine Hauptaufgabe eines Datenbanksystems ist es, dem Benutzer eine abstrakte Sicht auf die Daten zu erm<72>glichen. Die physikalische Ablage und der eigentliche Zugriff auf die Daten werden dabei vor dem Benutzer verborgen. Dabei k<>nnen drei Abstraktionsebenen unterschieden werden.
Die interne Ebene beschreibt, wie die Daten physikalisch abgelegt werden. Mit Hilfe von systemnahen komplexen Datenstrukturen wird die physische Ablage der Daten beschrieben.
Die konzeptuelle Ebene umfasst die Beschreibung der Art der Daten und der Beziehungen zwischen den Daten. In ihr wird die gesamte Datenbank auf der Basis von vergleichsweise einfachen Strukturen beschrieben. Bei der Realisierung der Strukturen auf der konzeptuellen Ebene kann auf die Strukturen der physischen Ebene zur<75>ckgegriffen werden. F<>r einen Benutzer der logischen Ebene, z.B. einen Datenbankadministrator, muss dies jedoch nicht sichtbar sein.
Auf der h<>chsten Abstraktionsebene, der externen Ebene, wird nur ein Teil der Datenbank beschrieben. Obwohl die konzeptuelle Ebene mit einfacheren Strukturen arbeitet, bleibt eine gewisse Komplexit<69>t wegen der Unterschiedlichkeit der in einer gro<72>en Datenbank gespeicherten Informationen. Viele Benutzer eines Datenbanksystems ben<65>tigen nicht alle Informationen; stattdessen brauchen sie nur einen Teil der Datenbank. Die externe Ebene dient der Vereinfachung beim Zugriff auf das System. Es k<>nnen beliebig viele Sichten auf eine Datenbank existieren.
Jedem Datenbanksystem liegt ein Datenmodell zugrunde. Das Datenmodell beschreibt die konzeptuellen Einheiten und Werkzeuge, um Daten, Beziehungen zwischen den Daten, die Semantik der Daten und Konsistenzeinschr<68>nkungen zu beschreiben. Verbreitete Datenmodelle f<>r Datenbanken sind das relationale und das objektorientierte Datenbankmodell.
Die Grundelemente des relationalen Datenmodells sind Attribute, Tupel und Relationen. Eine Relation wird durch ihr Relationenschema eindeutig beschrieben. Ein Relationenschema ist eine Menge von Attributen. Durch einen zugeordneten Datentyp und einen Namen bestimmt ein Attribut die m<>glichen Werte, die die Auspr<70>gungen des Attributs annehmen k<>nnen. Ein Tupel ist eine konkrete Auspr<70>gung, d.h. eine Zeile einer Relation (Tabelle). Damit ist eine Relation eine Menge von Tupeln.
Die Relationenalgebra l<>sst sich durch folgende Konstruktionsvorschriften eindeutig beschreiben.
Es seien $E_1$ und $E_2$ Ausdr<64>cke <20>ber der Relationenalgebra, dann lassen sich alle Ausdr<64>cke der Relationenalgebra mit den folgenden Operationen bilden:
\begin{itemize}
\item $E_1 \cup E_2$
\item $E_1 - E_2$
\item $E_1 \times E_2$
\item $\sigma_P(E_1)$, wobei P ein Pr<50>dikat <20>ber Attributen von $E_1$ ist.
\item $\pi_S(E_1)$, wobei S eine Teilmenge der Attribute von $E_1$ ist.
\item $\rho_x(E_1)$, wobei $x$ ein neuer Name f<>r das Ergebnis von $E_1$ ist.
\end{itemize}
(\cite{DBLP:books/mg/SilberschatzKS01})
Die Vereinigung ($\cup$) hat als Ergebnis die Vereinigung der Ergebnisse der beiden Ausdr<64>cke $E_1$ und $E_2$. Voraussetzung f<>r die Vereinigung ist die <20>bereinstimmung der beiden Ausdr<64>cke in ihrem Relationenschema.
Die Mengendifferenz (-) ermittelt alle Tupel, die im ersten Ausdruck enthalten sind, nicht aber im zweiten.
Das Kreuzprodukt zweier relationaler Ausdr<64>cke, bezeichnet mit ($\times$), liefert die Verkettung jedes Tupels des ersten Ausdrucks mit jedem Tupel des zweiten Ausdrucks. Hat $E_1$ $n_1$ Tupel und $E_2$ $n_2$ Tupel, so hat das Kreuzprodukt $n_1 * n_2$ Tupel.
Mit der Selektionsoperation ($\sigma$) werden nur die Tupel ermittelt, die das angegebene Pr<50>dikat erf<72>llen.
Die Projektion ($\pi$) schr<68>nkt das Ergebnisschema auf die angegebenen Attribute ein.
W<EFBFBD>hrend Relationen und Attribute <20>ber einen Namen spezifiziert sind, sind die Ergebnisse relationaler Ausdr<64>cke ohne Bezeichnung. Mit der Umbenennungsoperation ($\rho$) wird dem Ergebnis eines relationalen Ausdrucks eine Bezeichnung zugeordnet. Dies kann auf Relationenebene geschehen, d.h. das Ergebnis bekommt einen Namen zugeordnet. Es ist aber auch m<>glich, die Attribute des Ergebnisses umzubenennen.
\subsection{SQL}
Relationale Datenbanken beruhen auf der von E.F. Codd vorgeschlagenen Relationenalgebra und dem ebenfalls von Codd vorgestellten Relationenkalk<6C>l \cite{DBLP:books/mg/SilberschatzKS01}. Ein grunds<64>tzlicher Vorteil des relationalen Datenbankmodells ist die M<>glichkeit, die gew<65>nschten Ergebnisse einer Abfrage auf einem hohen Abstraktionsniveau formulieren zu k<>nnen. Die Zugriffspfade auf die Daten m<>ssen hier nicht mit angegeben werden. Die Relationenalgebra ist abgeschlossen, d.h. das Ergebnis jedes Ausdrucks ist ebenfalls wieder eine Relation. Da die mathematischen Grundlagen der Relationenalgebra und des Relationenkalk<6C>ls f<>r nicht-technische Benutzer einer Datenbank nicht einfach zu verstehen sind, wurde viel Arbeit in die Entwicklung einer Datenbanksprache gesteckt, die genauso m<>chtig ist wie das Relationenkalk<6C>l und die Relationenalgebra, sich aber leichter erlernen l<>sst. Eines der interessantesten Merkmale von SQL ist die M<>glichkeit, Abfragebl<62>cke beliebig zu schachteln. Eine geschachtelte Abfrage enth<74>lt einen weiteren Abfrageblock als Teilausdruck. Die Syntax f<>r geschachtelte Abfragen wird weiter unten dargestellt. Die Begriffe innerer Abfrageblock und Unterabfrage werden im Folgenden synonym verwendet.
Eine Abfrage ohne geschachtelte Pr<50>dikate hat die Schachtelungstiefe 1. Enth<74>lt eine Abfrage mindestens einen weiteren Abfrageblock der maximalen Schachtelungstiefe n, so hat sie die Schachtelungstiefe n + 1. Die Schachtelungstiefe gibt also an, auf wie vielen Ebenen die Abfragebl<62>cke geschachtelt sind.
SQL ist eine auf dem relationalen Datenbankmodell beruhende Datenbanksprache. Mit ihr k<>nnen in relationalen Datenbanken die Metadaten der Relationen angelegt und ge<67>ndert werden. Au<41>erdem erlaubt sie die Manipulation der Daten. Auch die granulare Vergabe von Berechtigungen wurde in SQL standardisiert.
%\begin{itemize}
% \item Datenbanksprache
% \subitem Datendefinition (DDL)
% \subitem Datenmanipulation (DML)
% \subitem Rechtevergabe (DCL)
Ein typischer Abfrageblock hat die Form
\begin{lstlisting}
select <20>$A_1,A_2,\cdots,A_n$<EFBFBD>
from <20>$r_1,r_2,\cdots,r_m$<EFBFBD>
where P
\end{lstlisting}
Grunds<EFBFBD>tzlich besteht eine SQL-Abfrage aus den drei Klauseln \sql{select}, \sql{from} und \sql{where}. Diese bilden einen sogenannten Abfrageblock. In der \sql{select}-Klausel werden die Attribute der Ergebnisrelation angegeben. Die \sql{from}-Klausel gibt die Quellrelationen an, aus denen das Ergebnis ermittelt wird. Die optionale \sql{where}-Klausel gibt schlie<69>lich Einschr<68>nkungen an, denen die Ergebnistupel gen<65>gen m<>ssen.
Die \sql{select}-Klausel entspricht der Projektions-Operation der Relationenalgebra. In ihr werden alle Attribute der Ergebnisrelation angegeben. Um alle Attribute der beteiligten Relationen zu erhalten gibt es die spezielle Notation \enquote{*}. Mit Ihr wird also das Schema der Ergebnisrelation festgelegt.
Die \sql{from}-Klausel entspricht dem kartesischen Produkt in der Relationenalgebra. Hier werden alle in der Abfrage verwendeten Relationen aufgef<65>hrt.
Die \sql{where}-Klausel entspricht der Selektions-Operation der Relationenalgebra. Das Pr<50>dikat P ist ein boolescher Ausdruck <20>ber den Attributen der in der \sql{from}-Klausel angegebenen Relationen. Ist der Ausdruck die Konjunktion mehrerer Terme, so spricht man auch bei den einzelnen Termen von einem Pr<50>dikat der Abfrage.
Es gibt in SQL zwei Konstrukte, die sich nicht mit der Relationenalgebra ausdr<64>cken lassen. D.h. SQL ist echt m<>chtiger als die Relationenalgebra. Die Konstrukte sind \sql{null}-Werte und Aggregationsfunktionen.
\sql{null}-Werte sind spezielle Attributwerte, die die Abwesenheit eines Werts anzeigen. Boolesche-Ausdr<64>cke mit \sql{null}-Werten entsprechen einer dreiwertigen Logik, da als Ergebnis die Werte \sql{true}, \sql{false} und \sql{null} auftreten k<>nnen.
Aggregationsfunktionen berechnen Werte <20>ber allen Tupeln einer Relation. Die im SQL-Standard definierten Aggregationsfunktionen sind
\begin{itemize}
\item \sql{count} -- Anzahl der Tupel
\item \sql{sum} -- Summe eines Attributwerts
\item \sql{avg} -- Durchschnitt eines Attributwerts
\item \sql{min} -- Minimum eines Attributwerts
\item \sql{max} -- Maximum eines Attributwerts
\end{itemize}.
Als Parameter wird ein Attribut angegeben, <20>ber dessen Werten die Aggregation berechnet wird. Dabei kann jede der Aggregationsfunktionen in einer mengenbasierten und einer multimengenbasierten Variante aufgerufen werden. Mit dem Zusatz \sql{distinct} wird die strikt mengenbasierte Variante gew<65>hlt, mit dem impliziten Parameter \sql{all} die multimengenbasierte. Implizit bedeutet in diesem Fall, ein Aggregationsausdruck ohne Zusatz wird berechnet wie ein Ausdruck, bei dem \sql{all} explizit angegeben wurde. Ein \sql{count}-Ausdruck hat z.B. die Form \sql{count(distinct $C$)} bzw. \sql{count($C$)} f<>r die multimengenbasierte Semantik. Der Operator \sql{count} existiert auch noch in einer tupelbasierten Variante: \sql{count(*)}. Diese unterscheidet sich nur in Bezug auf die Behandlung von \sql{null}-Werten vom spaltenbasierten Operator.
\sql{group by\dots having}-Klausel. Die Eingabemenge der Aggregationsfunktion wird in Gruppen mit gleichen Attributwerten in den angegebenen Attributen partitioniert; die Aggregationsfunktion wird dann jeweils separat f<>r jede Gruppe berechnet. Die optionale \sql{having}-Klausel erlaubt die Selektions-Operation auf den Ergebnissen der Aggregationsfunktion(en). Hierzu wird ein Pr<50>dikat angegeben, das auf das Ergebnis der Aggregation angewandt wird. Nur Ergebnistupel, f<>r die dieses Pr<50>dikat zu \sql{true} auswertet, werden in die Ergebnisrelation <20>bernommen.
In der \sql{order by}-Klausel werden die Ergebnisattribute angegeben, nach welchen das Ergebnis sortiert werden soll. Mit dem Zusatz \sql{asc} bzw. \sql{desc} hinter dem Attributnamen kann zwischen auf- und absteigender Sortierung f<>r das entsprechende Attribut gew<65>hlt werden. Die Reihenfolge der Attribute in der \sql{order by}-Klausel gibt die Rangfolge bei der Sortierung an.
% \item geschachtelte Abfragen
%
% \subitem in der \sql{select}-Klausel.
% \subitem in der \sql{from}-Klausel
% \subitem in der WHERE Klausel
% \subitem in der \sql{group by}\dots \sql{having}-Klausel (nicht implementiert) Die \sql{group by}\dots \sql{having}-Klausel erlaubt die Angabe eines Pr<50>dikats, das auf das Ergebnis einer Aggregation angewandt wird.
Der SQL-Standard unterscheidet in
\begin{enumerate}
\item scalar subqueries -- Ergebnis der Abfrage ist ein einzelner Wert. Diese Form der Unterabfrage darf an jeder Stelle in einem Abfrageblock verwendet werden, an dem auch eine skalare Konstante zul<75>ssig w<>re.
\item row subqueries -- Ergebnis der Abfrage ist eine Liste bzw. Menge von Werten.
\item table subqueries -- Ergebnis der Abfrage ist eine Relation.
\end{enumerate}.
Zus<EFBFBD>tzlich kann man die Unterabfrage nach dem Ort ihres Auftretens unterscheiden.
%\begin{itemize}
% \item SQL-Standard unterscheidet in
% \subitem \enquote{scalar subqueries} (Ergebnis der Abfrage ist ein einzelner Wert). Diese Form der Unterabfrage darf an jeder Stelle in einem Abfrageblock verwendet werden, an dem auch eine skalare Konstante zul<75>ssig w<>re.
% \subitem \enquote{row subqueries} (Ergebnis der Abfrage ist eine Liste/Menge von Werten)
% \subitem \enquote{table subqueries} (Ergebnis der Abfrage ist eine Relation)
% \item nach Korrelation
% \subitem nicht-korreliert (trivial, Ergebnis ist Konstante/Liste von Konstanten)
% \subitem korrelierte geschachtelte Abfrage
% \subsubitem ohne Aggregation
% \subsubitem mit Aggregation
% \item Ort des Auftretens
%\end{itemize}
\begin{enumerate}
\item In der \sql{select}-Klausel -- Das Ergebnis der Auswertung der geschachtelten Abfrage wird in die Ergebnisrelation aufgenommen. In der \sql{select}-Klausel sind nur skalare Unterabfragen zul<75>ssig.
\item In der \sql{from}-Klausel -- Komplexe Abfragen <20>ber mehrere Relationen lassen sich oft verst<73>ndlicher formulieren, wenn in einem ersten Schritt die notwendigen Daten zu einer Relation zusammengefasst werden. Im darauf folgenden Schritt wird dann die eigentliche Abfrage <20>ber dieser neuen Relation formuliert. Diese Form der Strukturierung l<>sst sich durch Unterabfragen in der \sql{from}-Klausel bewerkstelligen. Die Unterabfrage liefert die Zusammenfassung der Daten, auf deren Basis die Abfrage formuliert wird.
\item In der \sql{where}-Klausel -- Geschachtelte Abfragen in der \sql{where}-Klausel bieten die M<>glichkeit, das Ergebnis einer Abfrage in einer Bedingung zu verwenden. Hierzu k<>nnen die Operatoren \sql{in}, \sql{exists}, \sql{all}, \sql{any} und skalare Vergleichsoperatoren benutzt werden. Die Semantik dieser Operatoren wird in den nachfolgenden Abs<62>tzen kurz skizziert.
\item In der \sql{group by}\dots \sql{having}-Klausel -- Auch in den Pr<50>dikaten der \sql{having}"=Klau"-sel kann auf Unterabfragen zur<75>ckgegriffen werden. Allerdings kann nur auf die Attribute der Ergebnisrelation der zuvorstehenden Abfrage zugegriffen werden. D.h. die Ausdr<64>cke in einem Pr<50>dikat beziehen sich auf ein \sql{group by}-Attribut oder ein Aggregationsergebnis.
\begin{lstlisting}
select <20>$A_i$<EFBFBD>, <20>$avg(A_j)$<EFBFBD>
from <20>$R_n$<EFBFBD> as R
group by <20>$A_i$<EFBFBD>
having <20>$avg(A_j)$<EFBFBD> >
(select <20>$avg(A_j)$<EFBFBD>
from <20>$R_n$<EFBFBD>
where <20>$R.A_i$<EFBFBD> = <20>$A_i$<EFBFBD>)
\end{lstlisting}
\end{enumerate}
Der \sql{in}-Operator pr<70>ft das Enthaltensein eines Werts in einer Menge. Die Menge kann durch Auflistung oder durch eine Abfrage spezifiziert werden. Ein geschachteltes Pr<50>dikat mit dem \sql{in}-Operator ist genau dann wahr, wenn der Wert auf der linken Seite (Attribut oder Zeile) im Ergebnis der Unterabfrage enthalten ist.
\begin{lstlisting}
<EFBFBD>$A_i$<EFBFBD> in (select <20>$A_j$<EFBFBD> from <20>$R_n$<EFBFBD> where P)
\end{lstlisting}
Mit dem \sql{exists}-Operator wird die Ergebnisrelation darauf <20>berpr<70>ft, ob sie mindestens ein Ergebnistupel enth<74>lt. In nicht-korrelierten Pr<50>dikaten ist die Verwendung von \sql{exists} meist nicht relevant, da das Pr<50>dikat in diesem Fall zu der Konstant \sql{TRUE} bzw. \sql{FALSE} auswertet. Bei korrelierten Pr<50>dikaten lassen sich mit \sql{exists} komplexe Bedingungen pr<70>fen.
\begin{lstlisting}
exists(select <20>$A_j$<EFBFBD> from <20>$R_n$<EFBFBD> where P)
\end{lstlisting}
Die Operatoren \sql{any} und \sql{all} entsprechen den Quantoren $\exists$ und $\forall$ der Pr<50>dikatenlogik erster Stufe. Das Ergebnis eines Pr<50>dikats mit dem \sql{any}-Operator ist genau dann wahr, wenn mindestens ein Tupel der Ergebnisrelation den Vergleich $\theta$ erf<72>llt. Als Vergleichsoperator sind die skalaren Operatoren $<, <=, =, >, >=$ mit ihrer <20>blichen Semantik und der Operator <> mit der Bedeutung \enquote{ungleich} zul<75>ssig. Um den semantischen Unterschied des Operators \sql{any} zu der Verwendung des Wortes \enquote{any} in der englischen Sprache zu betonen und Missverst<73>ndnisse zu vermeiden, wurde mit SQL92 der Operator \sql{some} mit identischer Semantik eingef<65>hrt.
\begin{lstlisting}
<EFBFBD>$A_i$<EFBFBD> <20>$\theta$<EFBFBD> any(select <20>$A_j$<EFBFBD> from <20>$R_n$<EFBFBD> where P)
\end{lstlisting}
Der \sql{all}-Operator wertet zu \sql{TRUE} aus, wenn der Vergleich f<>r alle Ergebnistupel positiv ausf<73>llt. Die zul<75>ssigen Vergleichsoperatoren sind dieselben wie beim Operator \sql{any}.
\begin{lstlisting}
<EFBFBD>$A_i$<EFBFBD> <20>$\theta$<EFBFBD> all(select <20>$A_j$<EFBFBD> from <20>$R_n$<EFBFBD> where P)
\end{lstlisting}
\subsection{TPC-D Benchmark}
TPC \footnote{TPC = Transaction Processing Performance Council} ist eine Vereinigung von IT-Unternehmen. Ziel des TPC ist es, standardisierte Benchmarks zur Bewertung von Transaktionssystemen zur Verf<72>gung zu stellen. Mit diesen Benchmarks k<>nnen herstellerunabh<62>ngig Datenbanksysteme verglichen werden. Je nach Anwendungsgebiet werden verschiedene Metriken zum Vergleich von real verf<72>gbaren Systemen bereitgestellt. Der in dieser Arbeit f<>r den Vergleich herangezogene Benchmark TPC-D ist ein Entscheidungshilfe-Benchmark. In dem Benchmark sind 22 Abfragen zusammengefasst, die Antworten auf betriebswirtschaftliche Fragestellungen geben. Insgesamt 14 dieser Abfragen haben geschachtelte Abfragebl<62>cke und eignen sich daher als Anschauungsobjekt f<>r die Optimierung geschachtelter Anfragen. In Kapitel \ref{chp:Leistungsbewertung} findet sich eine Gegen<65>berstellung der geschachtelten und der optimierten Ausf<73>hrung dieser Abfragen. Ziel des Benchmarks ist der Vergleich von Datenbanksystemen <20>ber Metriken, die sowohl die Performance, gemessen <20>ber die Antwortzeiten der Abfragen, als auch die Kosten f<>r die verwendete Hardware mit einbeziehen. Die Ergebnisse eines solchen Benchmarks k<>nnen nach einer <20>berpr<70>fung durch den TPC auf der Website \url{http://www.tpc.org/} ver<65>ffentlicht werden.
\subsection{Beschreibung SECONDO}\label{sct:Beschreibung SECONDO}
\textsc{Secondo} ist ein modular aufgebautes, erweiterbares Datenbanksystem. Es k<>nnen sowohl das zugrundeliegende Datenmodell, als auch die verf<72>gbaren Datentypen und Operatoren beliebig erweitert und ausgebaut werden.
<EFBFBD>ber den Formalismus der Signaturen zweiter Ordnung (\textbf{SECOND} \textbf{O}rder Signatures) lassen sich die Datentypen und Operationen auf den Datentypen beschreiben. Signaturen zweiter Ordnung sind zwei gekoppelte Signaturen. Die Sorten der ersten Signatur werden \secondo{KIND} genannt, die Operationen Typ-Konstruktoren. Die im System verf<72>gbaren Datentypen sind genau die Ausdr<64>cke dieser Signatur. Die zweite Signatur beschreibt Operationen auf diesen Datentypen. <20>ber die Implementierung von Algebramodulen l<>sst sich \textsc{Secondo} um beliebige Datentypen und Operationen auf diesen Datentypen erweitern. Zu den bereits verf<72>gbaren Datentypen geh<65>ren neben den <20>blichen Basisdatentypen, wie z.B. \secondo{integer}, unter anderem auch r<>umliche (spatiale) und raum-zeitliche (spatio-temporale) Datentypen, die z.B. in Geoinformationssystemen verwendet werden k<>nnen.
\textsc{Secondo} besteht aus den drei Komponenten Kernel, Optimierer und grafischer Benutzeroberfl<66>che (GUI). Diese drei Komponenten k<>nnen getrennt, aber auch im Zusammenspiel genutzt werden.
Der Kernel ist in C++ geschrieben und bietet die M<>glichkeit Ausdr<64>cke in der \textsc{Secondo}-eigenen Syntax auszuf<75>hren. Hierzu gibt es eine Kommandozeilen-Schnittstelle, <20>ber die mit dem Kernel kommuniziert werden kann. Zus<75>tzlich kann der Kernel auch im Client/Server-Betriebsmodus gestartet werden. Er bietet dann anderen Komponenten die M<>glichkeit, auf den Kernel zuzugreifen. Abfragen <20>ber Relationen werden mit Tupelstr<74>men realisiert, d.h. zur Ausf<73>hrungszeit wird einem Operator auf Anforderung das n<>chste Tupel bereitgestellt oder das Ende des Stroms signalisiert. Dadurch ist es nicht notwendig die beteiligten Relationen vollst<73>ndig im Speicher vorhalten zu m<>ssen bzw. <20>ber Paging-Mechanismen bereitzustellen.
Mit dem Optimierer k<>nnen SQL-<2D>hnliche Ausdr<64>cke in ausf<73>hrbare Pl<50>ne <20>bersetzt werden. Dies kann losgel<65>st von den anderen Komponenten <20>ber die Kommandozeile erfolgen. Zus<75>tzlich gibt es auch beim Optimierer die M<>glichkeit, ihn im Client/Server-Modus zu starten.
Der Optimierer bietet die M<>glichkeit, conjunctive query optimization durchzuf<75>hren. D.h. es werden f<>r die Optimierung alle Konjunktionsterme des Pr<50>dikats betrachtet. Basis des Optimierers ist ein in \cite{G<EFBFBD>ting02,DBLP:conf/ideas/DiekerG00} vorgestellter Optimierungsalgorithmus der auf k<>rzesten Pfaden in einem predicate order graph (pog) beruht. Ein pog zu einer Liste von n Pr<50>dikaten ist ein n-dimensionaler Hyperw<72>rfel mit zwei ausgezeichneten Knoten maximaler Entfernung, die mit 0 bzw. $2^n$ bezeichnet werden. Hierbei stellen die Pfade die Permutationen der Konjunktionsterme des Pr<50>dikats dar. Jeder Knoten gibt durch seine Nummer die ausgewerteten Pr<50>dikate an. Die ausgewerteten Pr<50>dikate werden in Bits kodiert. Beim Knoten mit der Nummer 5 (bin<69>r 101) sind also die Pr<50>dikate 1 und 3 bereits ausgewertet. Jede Kante steht f<>r einen booleschen Ausdruck. F<>r jede <20>bersetzungsm<73>glichkeit dieses Ausdrucks wird eine \enquote{ausf<EFBFBD>hrbare Kante} erzeugt. Durch die Bewertung der Kanten mit Kosten (die sich aus der Selektivit<69>t und den Ausf<73>hrungskosten des Ausdrucks zusammensetzen) entspricht ein bez<65>glich der Kosten k<>rzester Pfad einer optimalen Reihenfolge der Pr<50>dikatsauswertung.
Die Implementierung des Optimierers ist in Prolog geschrieben. Da die vom Optimierer erkannte SQL-<2D>hnliche Sprache aus g<>ltigen Prolog-Ausdr<64>cken besteht, werden das Parsen und <20>bersetzen in entsprechende Datenstrukturen von der Prolog-Laufzeitumgebung <20>bernommen. Die <20>bersetzung der SQL-<2D>hnlichen Ausdr<64>cke in die ausf<73>hrbare \textsc{Secondo}-Syntax besteht aus den im Folgenden beschriebenen Phasen. In der ersten Phase wird der Ausdruck umgeschrieben. Abh<62>ngig von den gew<65>hlten Optionen des Optimierers werden z.B. enthaltene Makros ausgewertet, redundante Pr<50>dikate entfernt oder der Ausdruck so umstrukturiert, dass an mehreren Stellen verwendete Teilausdr<64>cke nur einmal ausgef<65>hrt werden m<>ssen (CSE -- common subexpression elimination). In diese Phase integrieren sich die Ent\-schach\-te\-lungs\-al\-go\-rith\-men, die im Rahmen dieser Arbeit implementiert wurden. Im zweiten Schritt werden die Schema-Daten der an der Abfrage beteiligten Datenbankobjekte (Attribute, Relationen und konstante Objekte) ermittelt und als Prolog-Fakten gespeichert. Sie werden zum Aufbau des predicate order graphs ben<65>tigt. Im n<>chsten Schritt wird der optimale Plan mit dem oben beschriebenen Optimierungsalgorithmus ermittelt. Im letzten Schritt wird aus dem Plan, der immer noch ein g<>ltiger Prolog-Term ist, ein Ausdruck in der ausf<73>hrbaren Syntax des \textsc{Secondo}-Kernels generiert. Falls vom Benutzer gew<65>nscht, kann die Abfrage direkt aus dem Optimierer heraus an den \textsc{Secondo}-Kernel gestellt werden. Das Ergebnis wird dann ebenfalls im Optimierer ausgegeben.
Die vom Optimierer unterst<73>tzte SQL-Syntax ist in Anhang \ref{apd:Secondo SQL-Dialekt} angegeben, inklusive der in dieser Arbeit implementierten Erweiterungen. Grunds<64>tzlich wird eine SQL-Abfrage durch folgende Struktur abgebildet, wobei kursiv dargestellte Knoten optionale Teile einer Abfrage sind.
% Set the overall layout of the tree
\tikzstyle{level 1}=[level distance=2cm, sibling distance=4cm]
\tikzstyle{level 4}=[level distance=2cm, sibling distance=2cm]
% Define styles for bags and leafs
\tikzstyle{bag} = [text width=4em, text centered]
%\tikzstyle{end} = [circle, minimum width=3pt,fill, inner sep=0pt]
\tikzstyle{end} = [text width=4em, text centered]
\begin{tikzpicture}[grow=down]
\node[bag] {\optional{first/last}}
child {
node[end, label=below:
{}]{\optional{Limit}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{groupby}}
child {
node[end, label=below:
{}]{\optional{grouping Attribute}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{sortby}}
child {
node[end, label=below:
{}]{\optional{Sortierungs Attribute}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {from}
child{
node[bag] {select}
child {
node[end, label=below:
{}] {\optional{Selektions Attribute}}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
child{
node[end, label=below:
{}] {Relationen}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{where}}
child {
node[end, label=below:
{}] {\optional{Pr<EFBFBD>dikate}}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
};
\end{tikzpicture}
Die grafische Benutzeroberfl<66>che ist in Java implementiert. Mit ihr k<>nnen Abfragen sowohl an den Optimierer als auch an den Kernel gestellt werden. Zus<75>tzlich ist sie in der Lage z.B. raum-zeitliche Datentypen darzustellen. Es wird eine zweidimensionale Projektion der Daten dargestellt, die <20>ber die Zeitachse abgespielt werden kann. Hierbei kann die Geschwindigkeit variiert werden. Durch Erweiterungen kann die GUI um die Darstellung beliebiger Datentypen erg<72>nzt werden. Da die GUI die M<>glichkeit bietet, das Ergebnis einer Abfrage in einem eigenen Format zu speichern, kann man ihre Darstellungsm<73>glichkeiten auch ohne Kernel und Optimierer benutzen.
%\begin{itemize}
% \item Erweiterbares Datenbanksystem
% \item Second-Order-Signatures
% \item Kernel/Algebren
% \item Optimierer
% \item GUI
% \item Client/Server Betrieb
%\end{itemize}
\section{Ausf<EFBFBD>hrungsstrategien}
\subsection{Geschachtelte Iteration}
%\cite{375748,1247598,ISO:1992:IITa}
Die Semantik der Auswertung von geschachtelten Abfragen wird im SQL-Standard \cite{ISO:1992:IITa} definiert. Das Ergebnis einer geschachtelten Abfrage erh<72>lt man, indem der innere Abfrageblock f<>r jedes Tupel des <20>u<EFBFBD>eren Abfrageblocks ausgewertet wird. Enth<74>lt die Unterabfrage korrelierte Pr<50>dikate, d.h. Pr<50>dikate, die sich auf Attribute der Relationen des <20>u<EFBFBD>eren Abfrageblocks beziehen, so werden die entsprechenden Werte aus dem Tupel des <20>u<EFBFBD>eren Abfrageblocks als Konstanten in die Pr<50>dikate der Unterabfrage <20>bernommen. Diese Form der Auswertung ist f<>r gro<72>e <20>u<EFBFBD>ere Relationen nicht sehr performant. Bei Unterabfragen mit Aggregationsfunktion muss die Aggregation f<>r jedes Tupel der <20>u<EFBFBD>eren Relation neu berechnet werden. In \cite{319745, 38723} werden Kostenberechnungen f<>r Beispiele durchgef<65>hrt, die eine Verbesserung der notwendigen I/O-Operationen f<>r eine Abfrage um ein bis zwei Gr<47><72>enordnungen zeigen.
\subsection{Entschachtelung}
Es wurde schon fr<66>h beobachtet, dass es zu bestimmten geschachtelten Abfragen inhaltlich <20>quivalente Abfragen gibt, die ohne Schachtelung auskommen. In \cite{319745} wurde erstmals die Formalisierung dieser <20>quivalenz untersucht, um geschachtelte Abfragen durch Optimierung der Ausf<73>hrungspl<70>ne beschleunigen zu k<>nnen. Ebd. wird ein Verfahren vorgestellt, eine geschachtelte Abfrage durch Transformation in eine inhaltlich <20>quivalente, nicht geschachtelte Abfrage zu optimieren. Die dort vorgestellten Algorithmen ben<65>tigen nur die erweiterten Standard-Operationen der Relationenalgebra. Ziel der Entschachtelungen ist die <20>berf<72>hrung geschachtelter Abfragebl<62>cke in eine inhaltlich <20>quivalente Form. Zwei Abfragebl<62>cke sind inhaltlich <20>quivalent, wenn f<>r jede beliebige Interpretation (Belegung mit Werten) der Variablen (in diesem Fall Relationen, Attribute und Konstanten), das Ergebnis der Abfrage <20>bereinstimmt. Grunds<64>tzlich haben die Entschachtelungsans<6E>tze gemeinsam, dass <20>quivalenzen aufgestellt werden, die die Transformation einer Abfrage in eine strukturell anders aufgebaute Abfrage erlauben. Dabei unterscheiden sich die verschiedenen Ans<6E>tze in der f<>r die Optimierung genutzten Notation der Abfrage. Die Relationenalgebra wird je nach Ansatz um verschiedene Operatoren erweitert. Dabei wird die Relationenalgebra zwar funktional erweitert, es findet jedoch keine Erweiterung der Ausdrucksst<73>rke statt. D.h. die eingef<65>hrten Operatoren lassen sich grunds<64>tzlich durch komplexe Ausdr<64>cke <20>ber den Standardoperatoren darstellen. Vorteil der Einf<6E>hrung der neuen Operatoren ist die M<>glichkeit, mit Hilfe dieser Operatoren Transformationen zu formulieren, die eine optimierte Formulierung einer geschachtelten Abfrage zulassen. Dienen die Operatoren nur der algebraischen Optimierung und k<>nnen sie durch algebraische Transformationen immer aus einem Ausdruck entfernt werden, so ist keine Implementierung notwendig. Andernfalls ist eine effiziente Implementierung erforderlich. W<>hrend in \cite{319745,38723,671634} die Abfrage in SQL-Notation transformiert wird, wird die Abfrage in \cite{375748,756653} in Ausdr<64>cke einer erweiterten Relationenalgebra <20>bersetzt und algebraisch transformiert.
In \cite{375748} wird die SQL-Abfrage erst einmal in eine algebraische Darstellung <20>bersetzt. Um die Transformationen leisten zu k<>nnen, wird die relationale Algebra um einige Operatoren erweitert, mit deren Hilfe sich der Term, der durch die <20>bersetzung entsteht, in eine entschachtelte Variante <20>berf<72>hren l<>sst. Die Ans<6E>tze zur Entschachtelung korrelierter Unterabfragen mit Aggregationsfunktion werden in die Vorgehensweisen Nested-Iteration, erst Outer-Join, dann Aggregation, erst Aggregation, dann Outer-Join und in orthogonale Optimierung unterschieden. Die orthogonale Optimierung geht in folgenden Schritten vor: Zerlegung der Abfrage in einen Operatorbaum auf der Basis des \sql{apply}-Operators. \sql{Apply} ist ein relationaler Operator zweiter Ordnung, der die parametrierte Ausf<73>hrung von Teilausdr<64>cken abstrahiert. Im zweiten Schritt wird \sql{apply} in andere Operatoren umgeschrieben, wie z.B. \sql{outer join}. Die Vorgehensweise zur Entfernung der Korrelation beruht auf den gleichen Mechanismen wie in \cite{671634}. Anschlie<69>end wird, sofern m<>glich, der Outer-Join noch vereinfacht. So l<>sst sich Outer-Join in Gegenwart von \sql{null}-verwerfenden Pr<50>dikaten in Join umwandeln. Zus<75>tzlich werden \sql{group-by}-Ausdr<64>cke m<>glichst sp<73>t ausgewertet. Nachteil dieser Vorgehensweise ist die m<>gliche Einf<6E>hrung gemeinsamer Teilausdr<64>cke (CSEs) bei der Entschachtelung.
Apply ist eine Auspr<70>gung des Generalized-Projection Operators wie er z.B. in \cite{DBLP:books/mg/SilberschatzKS01} f<>r die erweiterte Relationenalgebra vorgestellt wird. Der Generalized-Projection-Operator erlaubt nicht nur die Projektion auf Attribute der Ursprungsrelation, sondern auch auf Funktionsergebnisse, die <20>ber den Attributen dieser Relation formuliert werden. SegmentApply ist eine Variante des Apply-Operators, die nicht auf einzelne Zeilen sondern auf Gruppen von Zeilen angewandt wird. \sql{null}-rejecting Outer-Join: Ein Outer-Join hei<65>t \sql{null}-verwerfend, wenn das Join-Pr<50>dikat \sql{null}-verwerfend ist und die Menge A der Attribute Teilmenge des Schemas der zweiten Relation. Ist ein Outer-Join-Pr<50>dikat \sql{null}-verwerfend, so ist es <20>quivalent zu einem Join-Pr<50>dikat mit der gleichen Join-Bedingung. Diese <20>quivalenz erm<72>glicht, die Ausf<73>hrungsreihenfolge zumindest f<>r gewisse Outer-Joins und Joins zu vertauschen. \sql{null}-verwerfend hei<65>t, dass das Pr<50>dikat \sql{null} auf den Wert \sql{false} abbildet.
In \cite{1066180} wird ein Algorithmus zur Optimierung geschachtelter Abfragen auf der Basis einer geschachtelten Relationenalgebra vorgestellt. Der vorgestellte Algorithmus ist jedoch nur f<>r geschachtelte Abfragen ohne Aggregationsfunktion zul<75>ssig. Eine geschachtelte Relationenalgebra ist die konsequente Erweiterung der Relationenalgebra um die Zul<75>ssigkeit von Relationen als Attributwerte, d.h. eine Relation kann ihrerseits bereits geschachtelt sein. Die Grundoperationen der relationalen Algebra werden um zwei Operatoren erweitert. Die Operatoren nest und unnest <20>berf<72>hren eine Menge von Relationen in eine geschachtelte Relation respektive entfernen die Schachtelung aus einer geschachtelten Relation. Pr<50>dikate, die in der geschachtelten Relationenalgebra Schachtelungsebenen verbinden, werden \emph{linking} (verbindende) Pr<50>dikate genannt. Es wird ein Operator \emph{linking selection} eingef<65>hrt, dieser erweitert die Selektionsoperation der Relationenalgebra, die ja nur auf flachen Relationen definiert ist. Die Selektion mit einem \emph{linking} Pr<50>dikat entspricht daher der \emph{linking selection}. Der Algorithmus zur Entschachtelung baut in einer depth-first Vorgehensweise eine flache Relation aus der geschachtelten Abfrage mit Hilfe von Join und Outer-Join auf. In einer optimierten Variante wird die Entschachtelung durch Pipelining, d.h. die Verzahnung der Rechenschritte der einzelnen Entschachtelungen noch einmal beschleunigt. Bei einer prototypischen Implementierung in einem kommerziellen DBMS\footnote{Database Management System = Datenbankverwaltungssystem} mit gespeicherten Prozeduren wurden zum Teil Beschleunigungen um mehrere Gr<47><72>enordnungen erreicht.
%\begin{itemize}
% \item G-Aggregation (Generalized-Aggregation)
% \item G-Join (Generalized-Join)
% \item G-Restriction (Generalized-Restriction)
% \item G-Outerjoin (Generalized-Outer-Join)
%\end{itemize}
\section{Klassifikation geschachtelter Abfragen}
SQL Pr<50>dikate lassen sich in verschiedene Klassen einteilen. Abh<62>ngig von der Semantik der Operation, kann man in \emph{einfache} Pr<50>dikate, \emph{Join}-Pr<50>dikate und \emph{geschachtelte} Pr<50>dikate unterscheiden.
\emph{Einfache} Pr<50>dikate sind solche Pr<50>dikate, die zu ihrer Berechnung nur auf Konstanten und Attribute einer Relation zugreifen. Ein Beispiel f<>r ein solches Pr<50>dikat ist \textbf{$C_m = 10$}. Die entsprechende Operation der Relationenalgebra ist die Selektion.
\emph{Join}-Pr<50>dikate ben<65>tigen zu ihrer Berechnung Attribute aus zwei oder mehr Relationen. Sie \emph{verbinden} (to join -- engl. verbinden) die verwendeten Relationen. In der Relationenalgebra entspricht diese Operation der Kombination von Kreuzprodukt und Selektion.
\begin{lstlisting}
select * from <20>$R_i, R_j$<EFBFBD> where <20>$R_i.C_n=R_j.C_m$<EFBFBD>
\end{lstlisting}
entspricht in der Relationenalgebra dem Ausdruck
\begin{math}
\sigma_{R_i.C_n=R_j.C_m}(R_i \times R_j)
\end{math}
\emph{Geschachtelte} Pr<50>dikate enthalten eine Unterabfrage in ihrem Ausdruck. Abh<62>ngig von der Ergebnism<73>chtigkeit der Unterabfrage spricht der SQL-Standard von skalaren Unterabfragen, deren Ergebnis genau ein Wert ist; Zeilen-Unterabfragen (row subqueries), Ergebnis dieser Abfragen ist ein Tupel, das aus mehreren Attributen bestehen kann, sowie von Tabellen-Unterabfragen, deren Ergebnis eine Relation ist. Je nach Ergebnistyp ist die Verwendung von Unterabfragen an verschiedenen Stellen eines Abfrageblocks zul<75>ssig. Skalare Unterabfragen sind an jeder Stelle zul<75>ssig, an der auch Literale erlaubt sind. Zeilen- und Tabellen-Abfragen unterliegen einigen Einschr<68>nkungen, was ihre Verwendung in Views betrifft (siehe \cite{ISO:1992:IITa}), k<>nnen aber an fast jeder Stelle eingesetzt werden, an der ihr Ergebnistyp zul<75>ssig ist. Der SQL-Standard erlaubt die Schachtelung von Abfragebl<62>cken in beliebiger Tiefe. Tabellen-Unterabfragen k<>nnen z.B. in der \sql{from}-Klausel eingesetzt werden.
%Klassifikation von Pr<50>dikaten in
%einfache(Vergleich mit Konstante(n)),
%Nested,
%Join und
%Divisionspr<70>dikat,\\
%Einschr<68>nkung bei Join-Pr<50>dikaten auf =-Operator, \\
%nur eine Spalte in der Select-Klausel erlaubt in Subquery, \\
%keine \sql{group by}\dots \sql{having}-Klausel in Subquery \cite{671658}, \\
%Innerer und und <20>u<EFBFBD>erer Abfrageblock, \\
%Klassifikation in
%N =(kein Join-Pr<50>dikat, dass auf Relationen im <20>u<EFBFBD>eren Abfrageblock verweist, keine Aggregationsfunktion in Select-Klausel, ergibt eine Liste von Konstanten),
%A =(kein Join-Pr<50>dikat, dass auf Relationen im <20>u<EFBFBD>eren Abfrageblock verweist, Aggregationsfunktion in Select-Klausel, kann vollkommen unabh<62>ngig vom <20>u<EFBFBD>eren Abfrageblock ausgewertet werden, Ergebnis ist immer eine Konstante,
%J =(hat Join-Pr<50>dikat das die/eine Relation aus dem <20>u<EFBFBD>eren Abfrageblock referenziert, keine Aggregationsfunktion in Select-Klausel),
%JA =(hat Join-Pr<50>dikat mit Verweis auf Relation im <20>u<EFBFBD>eren Abfrageblock, Aggregationsfunktion),
%D =(ein Divisions-Pr<50>dikat, dass in einer der beiden Abfragebl<62>cke ein Join-Pr<50>dikat mit Verweis auf eine Relation im <20>u<EFBFBD>eren Abfrageblock, dr<64>ckt die relationale Divisionsoperation aus), \\
%\emph{nested-iteration method}, vollst<73>ndige Auswertung des inneren Abfrageblocks f<>r jedes Tupel des <20>u<EFBFBD>eren Blocks
Grunds<EFBFBD>tzlich lassen sich geschachtelte Abfragen in unabh<62>ngige Abfragen und korrelierte Abfragen unterscheiden. Unabh<62>ngige Abfragen lassen sich ohne den <20>u<EFBFBD>eren Abfrageblock auswerten. Ist eine unabh<62>ngige Auswertung nicht m<>glich, spricht man von korrelierten Abfragen, da das Ergebnis der inneren Abfrage vom Wert des Tupels des <20>u<EFBFBD>eren Abfrageblocks abh<62>ngt. Kim stellt in \cite{319745} eine Klassifikation geschachtelter Abfragen auf, auf deren Basis seine ebendort vorgestellten Entschachtelungsalgorithmen arbeiten.
\subsection{Typ A}
Eine geschachtelte Abfrage mit Aggregationsfunktion, die keine Attribute aus den <20>u<EFBFBD>eren Relationen referenziert, hei<65>t vom Typ A. Solche Abfragen k<>nnen unabh<62>ngig vom <20>u<EFBFBD>eren Abfrageblock ausgewertet werden. Ihr Ergebnis ist ein skalarer Wert, z.B. der Ort mit der h<>chsten Postleitzahl aus der Relation PLZ.
\begin{lstlisting}
select ort
from plz
where
plz = (select max(p:plz) from plz as p)
\end{lstlisting}
\subsection{Typ N}
Eine geschachtelte Abfrage ist vom Typ N, genau dann wenn die innere Abfrage keine Aggregationsfunktion enth<74>lt und alle Pr<50>dikate entweder simple Pr<50>dikate oder Join-Pr<50>dikate <20>ber Attributen der Relationen des inneren Abfrageblocks sind. Pr<50>dikate vom Typ N k<>nnen unabh<62>ngig vom <20>u<EFBFBD>eren Abfrageblock ausgewertet werden; ihr Ergebnis ist eine Liste von Konstanten. Beispiel: Alle St<53>dte mit einer Postleitzahl > 5000
\begin{lstlisting}
select sname
from staedte
where sname in (select ort from plz where plz > 5000)
\end{lstlisting}
\subsection{Typ J}
Eine Abfrage hat den Typ J, wenn mindestens ein Attribut der <20>u<EFBFBD>eren Relation im Pr<50>dikat verwendet wird, aber keine Aggregationsfunktion in der \sql{select}-Klausel vorkommt. Beispiel: Finde alle St<53>dte, deren Bev<65>lkerung gr<67><72>er als die Postleitzahl ist.
\begin{lstlisting}
select sname
from staedte
where sname in (select ort from plz where plz < bev)
\end{lstlisting}
\subsection{Typ JA}
Korrelierte Abfragen mit Aggregationsfunktion in der \sql{select}-Klausel hei<65>en vom Typ JA. Das Ergebnis der Unterabfrage h<>ngt vom Wert eines Attributs der <20>u<EFBFBD>eren Relationen ab. Beispiel: Alle Orte mit ihrer maximalen Postleitzahl. Der Wert des Maximums ist vom gerade betrachteten Ort abh<62>ngig.
\begin{lstlisting}
select ort
from plz
where plz = (select max(p:plz) from plz as p where ort = p:ort)
\end{lstlisting}
%
% EOF
%
%
Reference in New Issue Copy Permalink