latexandmore/IDB/idb_skript_greeny/Anfrageverarbeitung.tex

\section{Anfrageverarbeitung}

\subsection{Allgemein}
Eine SQL Anfrage ist ein mengenorientierter Zugriff.
D.h. diese mengenorientierten Operatoren müssen auf satzorientierte
Operatoren abgebildet werden.
\subsubsection{Phasen}
\textbf{Verarbeitungsschritte}:
\begin{itemize}
		\item Syntax überprüfen
		\item Rechte und Integritätsbedingungen (Formate) prüfen
		\item \textbf{Anfrageoptimierung} um effizient Query zu bearbeiten
		\item Code Generieung
\end{itemize}
\begin{figure}[H]
		\begin{center}
				\includegraphics[scale=0.7]{pics/anfrageverarbeitung.png}
				\caption{Phasen der Anfrageverarbeitung}
		\end{center}
\end{figure}
\textbf{Ziel}:\\
Umsetzung deskriptiver Anfragen in eine \glqq optimale\grqq Folge
interner DBS-Operationen
\subsection{Interndarstellung}
\subsubsection{Relationale Algebra}
Definition von relationalen \textbf{logischen Operatoren}:
\begin{itemize}
		\item Selektion: Auswahl von \glqq Zeilen\grqq (\textbf{where}-Klausel)
		\item Projektion Auswahl von \glqq Spalten\grqq (\textbf{select}-Klausel)
\item Kreuzprodukt: Konkatenation derjenigen Tupel aus zwei Relationen(\textbf{from})
		\item Verbund: Konkatenation derjenigen Tupel aus zwei Relationen
				die eine Bedingung erfüllen(\textbf{from-where})
		\item Mengenoperationen auf zwei Relationen:
				\begin{itemize}
						\item $R \cup S$ bzw \textbf{UNION(R,S)}
						\item $R \cap S$ bzw \textbf{INTERSECT(R,S)}
						\item $R \setminus S$ bzw \textbf{EXCEPT(R,S)}
				\end{itemize}
\end{itemize}
\subsubsection{Operatorbaum}
Beispiel:
\begin{lstlisting}
select Name, Beruf
from Abt a, Pers p,
     PM pm , Projekt pj
		 where a.ANr = p.ANr
		 and a.AOrt = "Erlangen"
		 and p.PNr = pm.PNr
		 and pm.JNr = pj.JNr
		 and pj.POrt = "Erlangen"
\end{lstlisting}

\begin{figure}[H]
		\begin{center}
				\includegraphics[scale=0.7]{pics/operatorbaum.png}
				\caption{Operatorbaum}
		\end{center}
\end{figure}
Blattknoten: Relationen\\
Gerichtete Kanten: Datenfluss\\
Knoten: Operatoren der Relationalen Algebra
\subsection{Restrukturierung}
Regeln:
\begin{enumerate}
		\item Ein n-facher Verbund kann durch eine Folge von binären Verbunden ersetzt und werden und umgekehrt
		\item Verbund ist kommutativ
		\item Verbund ist assoziativ
		\item Selektionen können zusammengefasst werden
		\item Projektionen können zusammengefasst werden
		\item Selektionen und Projektionen dürfen vertauscht werden
		\item Selektionen und Verbund dürfen vertauscht werden
		\item Selektion darf mit Vereinigung und Differenz vertauscht werden
		\item Selektion und Kreuzprodukt können zu Verbund zusammengefasst weren
\end{enumerate}
\subsubsection{Algorithmus}
\textbf{Ziel}: Kreuzprodukt vermeiden
Heuristik:
\begin{itemize}
		\item komplexe Verbundoperationen zerlegen in binäre Verbunde (Regel 1)
		\item Selektionen mit mehreren Prädikat Termen separieren in Selektionen mit jeweils einem Prädikat Term (Regel 4)
		\item Selektionen so früh wie möglich ausführen (Regel 7 und 8)
		\item Selektionen und Kreuzprodukt zu Verbund zusammenfassen, wenn
				das Selektionsprädikat Attribute aus den beiden Relationen verwendet (Regel 9)
		\item Projektionen so früh wie möglich ausführen, allerdings nicht vor Selektion und Mengenoperationen.

\end{itemize}