\begin{document}

\title{Implementierung von Subqueries im SECONDO Optimierer}
\author{Burkart Poneleit}
\maketitle
\section{Einleitung}
**Beschreibung SECONDO**
\section{Problembeschreibung}
Der SECONDO Optimierer soll um die Fähigkeit zur Übersetzung von geschachtelten Abfragen erweitert werden. Grundlagen zur Übersetzung liefert \cite{319745} und \cite{38723} Soweit möglich werden Queries mit Subqueries in äquivalente nicht geschachtelte Abfragen überführt werden. Grundsätzlich lassen sich geschachtelte Abfragen mit der 'nested-iteration' Methode ausführen, d.h. die Subquery wird für jedes Tupel der äußeren Abfrage ausgeführt. 

\begin{flushleft}
\subsection{Typ-A Queries}
\begin{math}
\text{select } A_{1},\dotsc,A_n \linebreak
\text{from } R_1,\dotsc,R_m \linebreak
\text{where } P_1,\dotsc,P_l \linebreak
A_i \theta (\text{select } \text{AGGR}(T_i.B) \linebreak
\text{from } T_1,\dotsc,T_s \linebreak
\text{where } Q_1,\dotsc,Q_r) \linebreak
\end{math}

\begin{math}
\text{select} A_{1},\dotsc,A_n \linebreak
\text{from } R_1,\dotsc,R_m \linebreak
\text{where } P_1,\dotsc,P_l \linebreak
A_i \theta C \linebreak
\end{math}

\begin{math}
C\text{ ist die durch Auswertung von } 
\text{select } \text{AGGR}(T_i.B) 
\text{ from } T_1,\dotsc,T_s
\text{where } Q_1,\dotsc,Q_r \linebreak
\text{gewonnene Konstante.}
\end{math}

\subsection{Algorithm NEST-N-J}
select $A_1 ,\ldots,A_n$ \linebreak 
from $R_1 ,\ldots,R_m$ \linebreak 
where $P_1,\ldots,P_l,$ \linebreak 
$X \theta ($select $T_i.B$ \linebreak 
from $T_1 ,\ldots,T_s$ \linebreak 
where $Q_1 ,\ldots,Q_r)$ \linebreak

select $A_1,\ldots,A_n$ \linebreak
from $R_1,\ldots,R_m,T_1,\ldots,T_s$ \linebreak
where $P_1,\ldots,P_l,Q_1,\ldots,Q_r$ \linebreak
X $\theta^{'} B$ \linebreak

X $\subset\{A_1,\ldots,A_n\}$ \linebreak
$\theta \in $\{IN,NOT IN,$=,\not=,>,\geq,<,\leq$\} \linebreak
$\theta^{'} = \begin{cases}
=& \text{falls }\theta = \text{IN} \\
\not=& \text{falls }\theta = \text{NOT IN} \\
\theta& \text{sonst}
\end{cases}$\linebreak

\subsection{Algorithm NEST-JA2}
select $A_1 ,\ldots,A_n$ \linebreak 
from $R_1 ,\ldots,R_m$ \linebreak 
where $P_1 (R_1 ),\ldots,P_k (R_1 ),P_1 ,\ldots,P_l,$ \linebreak 
$R_i.X \theta ($select AGGR($T_j.A$) \linebreak 
from $T_1 ,\ldots,T_s$ \linebreak 
where pred$[R_1.Y,T_1.Z],Q_1 ,\ldots,Q_r)$ \linebreak

let Temp1 = select $R_1.Y$ \linebreak
from $R_1$ \linebreak
where $P_1(R_1),\ldots,P_k(R_1)$ \linebreak

let Temp2 = select $T_j.A,T_1.Z$ \linebreak
from $T_1,\ldots,T_s$ \linebreak
where $Q_1,\ldots,Q_r$ \linebreak

let Temp3 = Temp1 feed {t1} \linebreak
Temp2 feed \linebreak
outerjoin$[$pred$[R_1.Y,T_1.Z]]$ \linebreak
sortby$[Z$ asc$]$ \linebreak
groupby$[Z$; AggrResult: group AGGR$]$ \linebreak
consume \linebreak

select $A_1,\ldots,A_n$ \linebreak
from $R_1,\ldots,R_m,Temp3$ \linebreak
where $P_1,\ldots,P_l,$ \linebreak
$R_i.X \theta Temp3.AggrResult,$\linebreak 
$R_1.Y=Temp3.Z$ \linebreak

$\theta \in\{=,\not=,>,\geq,<,\leq\}$

\subsection{Algorithm NEST-D}
\begin{math}
\text{select } A_1 \linebreak
\text{from } R \linebreak
\text{where } P_1,\dotsc,P_k \linebreak
(\text{select } B_1,\dotsc,B_n \linebreak
\text{ from } T \linebreak
\text{ where } B_2=A_2,\dotsc,B_n=A_n) \linebreak
op \linebreak
(\text{select } C_1,\dotsc,C_m \linebreak
\text{ from } U \linebreak
\text{ where } C_2=A_2,\dotsc,C_m=A_m) \linebreak
\end{math}

\begin{math}
\text{let }Temp1 = \text{select } C_2,\dotsc,C_m \linebreak
\text{from } U \linebreak
\end{math}

\begin{math}
\text{let }Temp2 = \text{select }  B_2,\dotsc,B_n \linebreak
\text{from } T \linebreak
\end{math}

\begin{math}
\text{let }Temp3 = Temp2 \text{ feed sort } Temp2 \text{ feed sort mergediff consume }\linebreak
\end{math}

\begin{math}
\text{select } A_1 \linebreak
\text{from } R,Temp3 \linebreak
\text{where } P_1,\dotsc,P_k \linebreak
Temp3.C_{m+1}=A_{m+1},\dotsc,Temp3.C_n=A_n \linebreak
\end{math}
\end{flushleft}


\nocite{*}
\bibliographystyle{acm}
\bibliography{Diplomarbeit}
\end{document}