\documentclass{beamer}
\mode<presentation>{\usetheme{Frankfurt}}
\setbeamercovered{transparent}

\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{dcolumn}

\usepackage{tikz}
\usetikzlibrary{shapes}
\tikzstyle{ed}=[thick]
\tikzstyle{map}=[<-,dashed,>=latex]

\usepackage{listings}
\lstset{showstringspaces=false}

\newcommand{\ignore}[1]{}
\newcommand{\uw}[1]{\textcolor{black!40}{#1}} % \uw{} = unwichtig (ausgegraut)

\newcommand{\s}[1]{section$_#1$}
\renewcommand{\c}[1]{content$_#1$}
\renewcommand{\t}[1]{text$_#1$}
\newcommand{\x}{$\rightarrow$}
\newcommand{\pathstack}[2]{%
\begin{frame}
    \frametitle{Vorführung: PathStack}

    \small

    \texttt{//section//content//text}
    \hspace{-2cm}
    \hfill
    \begin{tikzpicture}[level distance=0.8cm]
        \tikzstyle{level 1}=[sibling distance=0cm]
        \tikzstyle{level 2}=[sibling distance=2cm]
        \tikzstyle{level 3}=[sibling distance=2.5cm]
        \tikzstyle{level 4}=[sibling distance=1.2cm]
        \node {$\cdots$}
            child {node {\s0}
                child {node {$\cdots$}}
                child {node {\c0}
                    child {node {\t0}}
                    child {node {\s1}
                        child {node {$\cdots$}}
                        child {node {\c1}
                            child {node {\t1}}}}
                    child {node {\s2}
                        child {node {$\cdots$}}
                        child {node {\c2}
                            child {node {\t2}}}}}}
            ;
    \end{tikzpicture}

    \bigskip

    {#1}

    \bigskip

    Ausgabe:\textcolor{white}{/}{#2}
\end{frame}
}

\newcommand{\p}[9]{%
    \begin{tabular}{|rlll|}
    \hline
    $q_{min}$ & $q$     & Dok-Knoten \hspace{0.1cm} & Stack \hspace{4.8cm} \\
    \hline
    #1        & section & #2         & #3    \\
    #4        & content & #5         & #6    \\
    #7        & text    & #8         & #9    \\
    \hline
    \end{tabular}}

\AtBeginSection[]
{
    \begin{frame}
        \frametitle{Übersicht}
        \tableofcontents[currentsection]
    \end{frame}
}

\AtBeginSubsection[]
{
    \begin{frame}
        \frametitle{Übersicht}
        \tableofcontents[currentsection,currentsubsection]
    \end{frame}
}

\title{Optimale Bearbeitung von XML-Anfragen}
\author{Volker Grabsch \and Christine Janischek}
\date{4. Februar 2008}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

\begin{frame}
    \frametitle{Allgemeines}

    \begin{itemize}
    \item veröffentlicht unter \\
        \url{http://www.profv.de/uni/}

    \vfill

    \item lizensiert unter \\
        \href{http://creativecommons.org/licenses/by/3.0/deed.de}{%
        % CC-Icons heruntergeladen von:
        % http://creativecommons.org/presskit
        \includegraphics{by-sa} \\
        Creative Commons BY-SA 3.0}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Quelle}

    Dieser Vortrag basiert auf dem Paper
        \begin{quote}
        Holistic Twig Joins:
        Optimal XML Pattern Matching
        \end{quote}
    von Nicolas Bruno, Nick Koudas und Divesh Srivastava.
\end{frame}

\begin{frame}
    \frametitle{Übersicht}
    \tableofcontents
\end{frame}

\section{Einleitung}

\begin{frame}
    \frametitle{Einleitung}

    \begin{itemize}
    \item Ziel: Bessere Algorithmen zur XML-Anfragenabarbeitung
    \item XPath-Anfragen auf XML-Datenbank 
    \item Problem: unverhältnismässig viele Teilergebnisse bei stark einschränkenden Anfragen
    \end{itemize}
\end{frame}

\section{XML-Darstellung}

\begin{frame}
    \frametitle{XML-Darstellung}

    \begin{itemize}
    \item bisher
        \begin{itemize}
        \item ParentID
        \item Dewey-Pos
        \item OrdPath
        \item Preorder : Postorder
        \item usw.
        \end{itemize}
    \pause
    \item jetzt
        \begin{itemize}
        \item (DocID, LeftPos : RightPos, LevelNum)
        \item sehr ähnlich zu Preorder : Postorder
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{LeftPos : RightPos}

    \begin{tabular}{ll}
\begin{lstlisting}[language=XML,basicstyle=\tiny]
 1  <report>
 2      <title>
 3          Der moderne Dieb
 4      </title>
 5      <section>
 6          <title>
 7              Unterwegs
 8          </title>
 9          <content>
10              <text>
11                  Gerade zu Weihnachten ...
12              </text>
13              <section>
                    ...
22              </section>
23              <section>
                    ...
32              </section>
33          </content>
34      </section>
35  </report>
\end{lstlisting}
        &
        \small
        \begin{tabular}{|D{:}{:}{2}l|}
        \hline
        \multicolumn{2}{|c|}{LeftPos : RightPos} \\
        \hline
         1:35    & $<$report$>$     \\
         2:4     & $<$title$>$      \\
         3:3     & Der moderne ...  \\
         5:34    & $<$section$>$    \\
         6:8     & $<$title$>$      \\
         7:7     & Unterwegs        \\
         9:33    & $<$content$>$    \\
        10:12    & $<$text$>$       \\
        11:11    & Gerade zu W...   \\
        13:22    & $<$section$>$    \\
        ...      &                  \\
        23:32    & $<$section$>$    \\
        ...      &                  \\
        \hline
        \end{tabular}
    \end{tabular}
\end{frame}

\begin{frame}
    \frametitle{Achsen mit (LeftPos : RightPos)}

    \tikzstyle{knoten}=[draw]

    \begin{tabular}{ccc}
        \begin{tikzpicture}[auto,node distance=2cm]
            \node[knoten] (AL)                                      {ancestor.L};
            \node[knoten] (DL) [below right of=AL]                  {descendant.L};
            \node[knoten] (DR) [below of=DL,node distance=1.5cm]    {descendant.R}
                edge (DL);
            \node[knoten] (AR) [below left of=DR]                   {ancestor.R}
                edge (AL);
        \end{tikzpicture}
    &
    \hspace{1cm}
    &
        \begin{tikzpicture}[auto,node distance=1.5cm]
            \node[knoten] (PL)                      {preceding.L};
            \node[knoten] (PR) [below of=PL]        {preceding.R}
                edge (PL);
            \node[knoten] (FL) [below right of=PR]  {following.L};
            \node[knoten] (FR) [below of=FL]        {following.R}
                edge (FL);
        \end{tikzpicture}
    \\
    \\
    ancestor.L $<$ descendant.L & & preceding.R $<$ following.L \\
    ancestor.R $>$ descendant.R & &
    \end{tabular}
\end{frame}

\section{PathStack}

\begin{frame}[fragile]
    \frametitle{Grundlagen}

    \begin{itemize}
    \item Anfrage-Baum (XPath-Achsen)
    \item<2-> Filter auf Anfrage-Knoten (Tagname, XPath-Prädikate)
    \item<3-> Eingabe: Kandidaten für Anfrage-Knoten (in preorder)
    \item[] ~
    \end{itemize}

    \bigskip

    \verb,//section//title[text()!=''],

    \bigskip

    \hspace{2cm}
    \begin{tikzpicture}[node distance=1.4cm]
        \node (section)
            {section};
        \node (title) [below of=section]
            {title}
            edge[ed] node[label=right:descendant] {} (section);
        \node (text) [below of=title]
            {text()}
            edge[ed] node[label=right:child] {} (title);
        \uncover<3>{
        \node (section stream) [right of=section,node distance=2cm,
                                label=right:{section$_0$, section$_1$, section$_2$}] {}
            edge[map] (section);
        \node (title stream)   [below of=section stream,
                                label=right:{title$_{rep}$, title$_0$, title$_1$, title$_2$}] {}
            edge[map] (title);
        \node (text stream)    [below of=title stream,
                                label=right:{"`Der moderne Dieb"', $\ldots$}] {}
            edge[map] (text);
        }
    \end{tikzpicture}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Grundlagen}

    \begin{itemize}
    \item Anfrage-Baum (XPath-Achsen)
    \item Filter auf Anfrage-Knoten (Tagname, XPath-Prädikate)
    \item Eingabe: Kandidaten für Anfrage-Knoten (in preorder)
    \item Ausgabe: Zuordnungen Dokument-Baum $\rightarrow$ Anfrage-Baum
    \end{itemize}

    \bigskip

    \verb,//section//title[text()!=''],

    \bigskip

    \hspace{2cm}
    \begin{tikzpicture}[node distance=1.4cm]
        \node (section)
            {section};
        \node (title) [below of=section]
            {title}
            edge[ed] node[label=right:descendant] {} (section);
        \node (text) [below of=title]
            {text()}
            edge[ed] node[label=right:child] {} (title);
        \node (section stream) [right of=section,node distance=2cm,
                                label=right:section$_0$] {}
            edge[map] (section);
        \node (title stream)   [below of=section stream,
                                label=right:title$_1$] {}
            edge[map] (title);
        \node (text stream)    [below of=title stream,
                                label=right:"`Jackentaschen"'] {}
            edge[map] (text);
    \end{tikzpicture}
\end{frame}

\begin{frame}[fragile]
    \frametitle{root-to-leaf $\leftrightarrow$ leaf-to-root}

    \verb,//section//title[text()!=''],

    \bigskip
    \small

    \begin{tabular}{|D{:}{:}{2}D{:}{:}{2}D{:}{:}{2}l|}
    \hline
    \multicolumn{1}{|c}{section} &
    \multicolumn{1}{c}{title} &
    \multicolumn{1}{c}{text()} &
    \\
    \hline
     5:34   &  6:8  &  7:7    & \uw{/r./}section$_0$/title$_0$/"`Unterwegs"'                          \\
     5:34   & 14:16 & 15:15   & \uw{/r./}section$_0$\uw{/c./section$_1$/}title$_1$/"`Jackentaschen"'  \\
     5:34   & 24:26 & 25:25   & \uw{/r./}section$_0$\uw{/c./section$_2$/}title$_2$/"`Handtaschen"'    \\
    13:22   & 14:16 & 15:15   & \uw{/r./section$_0$/c./}section$_1$/title$_1$/"`Jackentaschen"'       \\
    23:32   & 24:26 & 25:25   & \uw{/r./section$_0$/c./}section$_2$/title$_2$/"`Handtaschen"'         \\
    \hline
    \end{tabular}

    \pause
    \bigskip

    \begin{tabular}{|D{:}{:}{2}D{:}{:}{2}D{:}{:}{2}l|}
    \hline
    \multicolumn{1}{|c}{section} &
    \multicolumn{1}{c}{title} &
    \multicolumn{1}{c}{text()} &
    \\
    \hline
     5:34   &  6:8  &  7:7    & \uw{/r./}section$_0$/title$_0$/"`Unterwegs"'                          \\
     5:34   & 14:16 & 15:15   & \uw{/r./}section$_0$\uw{/c./section$_1$/}title$_1$/"`Jackentaschen"'  \\
    13:22   & 14:16 & 15:15   & \uw{/r./section$_0$/c./}section$_1$/title$_1$/"`Jackentaschen"'       \\
     5:34   & 24:26 & 25:25   & \uw{/r./}section$_0$\uw{/c./section$_2$/}title$_2$/"`Handtaschen"'    \\
    23:32   & 24:26 & 25:25   & \uw{/r./section$_0$/c./}section$_2$/title$_2$/"`Handtaschen"'         \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Erkenntnis}

    \begin{itemize}
    \item Reihenfolge leaf-to-root effizienter erzeugbar
    \pause
    \item pro Dokumenten-Blatt
        \begin{itemize}
        \item alle möglichen Matches seines Pfads durchlaufen
        \item kompakte Kodierung durch Stacks
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Primitive Stacks}

    \verb,//section//title[text()!=''],

    \bigskip
    \small

    \begin{tabular}{|D{:}{:}{2}D{:}{:}{2}D{:}{:}{2}l|}
    \hline
    \multicolumn{1}{|c}{section} &
    \multicolumn{1}{c}{title} &
    \multicolumn{1}{c}{text()} &
    \\
    \hline
     5:34   &  6:8  &  7:7    & \uw{/r./}section$_0$/title$_0$/"`Unterwegs"'                          \\
    \uncover<2->{
     5:34   & 14:16 & 15:15   & \uw{/r./}section$_0$\uw{/c./section$_1$/}title$_1$/"`Jackentaschen"'} \\
    \uncover<2->{
    13:22   & 14:16 & 15:15   & \uw{/r./section$_0$/c./}section$_1$/title$_1$/"`Jackentaschen"'}      \\
    \uncover<3->{
     5:34   & 24:26 & 25:25   & \uw{/r./}section$_0$\uw{/c./section$_2$/}title$_2$/"`Handtaschen"'}   \\
    \uncover<3->{
    23:32   & 24:26 & 25:25   & \uw{/r./section$_0$/c./}section$_2$/title$_2$/"`Handtaschen"'}        \\
    \hline
    \end{tabular}

    \bigskip

    \begin{tabular}{|l|lll|}
    \hline
            & \uncover<1>{Stack}       & \uncover<2>{Stack}                    & \uncover<3>{Stack} \\
    \hline
    section & \uncover<1>{section$_0$} & \uncover<2>{section$_1$, section$_0$} & \uncover<3>{section$_2$, section$_0$} \\
    title   & \uncover<1>{title$_0$}   & \uncover<2>{title$_1$}                & \uncover<3>{title$_2$} \\
    text()  & \uncover<1>{Unterwegs}   & \uncover<2>{Jackentaschen}            & \uncover<3>{Handtaschen} \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Primitive Stacks - Problemfall}

    \verb,//section//content//text[text()='Jacken werden...'],

    \bigskip
    \small

    \begin{tabular}{|D{:}{:}{2}D{:}{:}{2}l|l}
    \cline{1-3}
    \multicolumn{1}{|c}{section} &
    \multicolumn{1}{c}{content} &
    \\
    \cline{1-3}
     5:34   &  9:33 & \uw{/r./}section$_0$/content$_0$\uw{/section$_1$/content$_1$/}text$_1$ \\
    13:22   &  9:33 & \uw{/r./section$_0$/}content$_0$/section$_1$\uw{/content$_1$/}text$_1$ & ?! \\
     5:34   & 17:21 & \uw{/r./}section$_0$\uw{/content$_0$/section$_1$/}content$_1$/text$_1$ \\
    13:22   & 17:21 & \uw{/r./section$_0$/content$_0$/}section$_1$/content$_1$/text$_1$ \\
    \cline{1-3}
    \end{tabular}

    \bigskip

    \begin{tabular}{|l|l|}
    \hline
            & Stack \\
    \hline
    section & section$_1$, section$_0$ \\
    content & content$_1$, content$_0$ \\
    text    & text$_1$ \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Erkenntnis}

    \begin{itemize}
    \item Stacks bisher zu primitiv
    \pause
    \item Lösungen:
    \pause
        \begin{itemize}
        \item prüfe vor Ausgabe auf \texttt{ancestor}-\texttt{descendant} (ineffizient)
        \pause
        \item Hierarchie-Info im Stack notieren
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Stacks mit Hierarchie-Info}

    \verb,//section//content//text[text()='Jacken werden...'],

    \bigskip
    \small

    \begin{tabular}{|D{:}{:}{2}D{:}{:}{2}l|l}
    \cline{1-3}
    \multicolumn{1}{|c}{section} &
    \multicolumn{1}{c}{content} &
    \\
    \cline{1-3}
     5:34   &  9:33 & \uw{/r./}section$_0$/content$_0$\uw{/section$_1$/content$_1$/}text$_1$ \\
     5:34   & 17:21 & \uw{/r./}section$_0$\uw{/content$_0$/section$_1$/}content$_1$/text$_1$ \\
    13:22   & 17:21 & \uw{/r./section$_0$/content$_0$/}section$_1$/content$_1$/text$_1$ \\
    \cline{1-3}
    \end{tabular}

    \bigskip

    \begin{tabular}{|l|l|}
    \hline
            & Stack \\
    \hline
    section & section$_1$, section$_0$ \\
    content & content$_1$(section$_1$), content$_0$(section$_0$) \\
    text    & text$_1$(content$_1$) \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}
    \frametitle{PathStack-Algorithmus}

    \begin{itemize}
    \item $q_{min} :=$ Anfrage-Knoten mit minimalem Dok-Knoten $d_{min}$
        \begin{itemize}
        \item gibt es mehrere $q_{min}$, wähle kleinsten
        \end{itemize}
    \pause
    \item säubere alle Stacks
        \begin{itemize}
        \item entferne alle \texttt{precedings} (d.h. nicht-\texttt{ancestors}) von $d_{min}$
        \end{itemize}
    \pause
    \item $d_{min}$ $\rightarrow$ $q_{min}$-Stack
    \pause
    \item nächster Dok-Knoten für $q_{min}$
    \pause
    \item Wenn $q_{min}$ ein Blatt:
        \begin{itemize}
        \item Ausgabe der in den Stacks kodierten Lösungen
        \end{itemize}
    \pause
    \item wiederhole von vorn
    \end{itemize}
\end{frame}

%             >section                     >content                               >text
\pathstack{\p{  }{\s0, ...     }{        }{  }{\c0, ...     }{                  }{  }{\t0, ...     }{        }}{}
\pathstack{\p{\x}{\s0, ...     }{        }{  }{\c0, ...     }{                  }{  }{\t0, ...     }{        }}{}
\pathstack{\p{\x}{     \s1, ...}{     \s0}{  }{\c0, ...     }{                  }{  }{\t0, ...     }{        }}{}
\pathstack{\p{  }{     \s1, ...}{     \s0}{\x}{\c0, ...     }{                  }{  }{\t0, ...     }{        }}{}
\pathstack{\p{  }{     \s1, ...}{     \s0}{\x}{     \c1, ...}{          \c0(\s0)}{  }{\t0, ...     }{        }}{}
\pathstack{\p{  }{     \s1, ...}{     \s0}{  }{     \c1, ...}{          \c0(\s0)}{\x}{\t0, ...     }{        }}{}
\pathstack{\p{  }{     \s1, ...}{     \s0}{  }{     \c1, ...}{          \c0(\s0)}{\x}{     \t1, ...}{\t0(\c0)}}{}
\pathstack{\p{  }{     \s1, ...}{     \s0}{  }{     \c1, ...}{          \c0(\s0)}{\x}{     \t1, ...}{\t0(\c0)}}
    {\uw{/report/}\s0/\c0/\t0}
\pathstack{\p{\x}{     \s1, ...}{     \s0}{  }{     \c1, ...}{          \c0(\s0)}{  }{     \t1, ...}{\t0(\c0)}}{}
\pathstack{\p{\x}{     \s1, ...}{     \s0}{  }{     \c1, ...}{          \c0(\s0)}{  }{     \t1, ...}{        }}{}
\pathstack{\p{\x}{          \s2}{\s1, \s0}{  }{     \c1, ...}{          \c0(\s0)}{  }{     \t1, ...}{        }}{}
\pathstack{\p{  }{          \s2}{\s1, \s0}{\x}{     \c1, ...}{          \c0(\s0)}{  }{     \t1, ...}{        }}{}
\pathstack{\p{  }{          \s2}{\s1, \s0}{\x}{          \c2}{\c1(\s1), \c0(\s0)}{  }{     \t1, ...}{        }}{}
\pathstack{\p{  }{          \s2}{\s1, \s0}{  }{          \c2}{\c1(\s1), \c0(\s0)}{\x}{          \t2}{\t1(\c1)}}{}
\pathstack{\p{  }{          \s2}{\s1, \s0}{  }{          \c2}{\c1(\s1), \c0(\s0)}{\x}{          \t2}{\t1(\c1)}}
    {\uw{/report/}\s0\uw{/\c0/\s1}/\c1/t1}
\pathstack{\p{  }{          \s2}{\s1, \s0}{  }{          \c2}{\c1(\s1), \c0(\s0)}{\x}{          \t2}{\t1(\c1)}}
    {\uw{/report/\s0/\c0/}\s1/\c1/t1}
\pathstack{\p{  }{          \s2}{\s1, \s0}{  }{          \c2}{\c1(\s1), \c0(\s0)}{\x}{          \t2}{\t1(\c1)}}
    {\uw{/report/}\s0/\c0\uw{/\s1/\c1}/t1}
\pathstack{\p{\x}{          \s2}{\s1, \s0}{  }{          \c2}{\c1(\s1), \c0(\s0)}{  }{          \t2}{\t1(\c1)}}{}
\pathstack{\p{\x}{          \s2}{     \s0}{  }{          \c2}{          \c0(\s0)}{  }{          \t2}{        }}{}
\pathstack{\p{\x}{             }{\s2, \s0}{  }{          \c2}{          \c0(\s0)}{  }{          \t2}{        }}{}
\pathstack{\p{  }{             }{\s2, \s0}{\x}{          \c2}{          \c0(\s0)}{  }{          \t2}{        }}{}
\pathstack{\p{  }{             }{\s2, \s0}{\x}{             }{\c2(\s2), \c0(\s0)}{  }{          \t2}{        }}{}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{          \t2}{        }}{}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{             }{\t2(\c2)}}{}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{             }{\t2(\c2)}}
    {\uw{/report/}\s0\uw{/\c0/\s2}/\c2/t2}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{             }{\t2(\c2)}}
    {\uw{/report/\s0/\c0/}\s2/\c2/t2}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{             }{\t2(\c2)}}
    {\uw{/report/}\s0/\c0\uw{/\s2/\c2}/t2}
\pathstack{\p{  }{             }{\s2, \s0}{  }{             }{\c2(\s2), \c0(\s0)}{\x}{             }{\t2(\c2)}}{}

\begin{frame}
    \frametitle{Nach PathStack -- Kritik am Paper}

    \begin{itemize}
    \item PathStack arbeitet nur auf Zweigen des Anfragebaums ?
    \item<2-> Wende PathStack auf Zweige an, dann Merge der Ausgaben
    \item<3-> vorher: leaf-to-root $\rightarrow$ root-to-leaf ?
        \begin{itemize}
        \item<4-> Sortierung: ineffizient
        \item<5-> verzögerte, gepufferte Ausgabe
        \end{itemize}
    \end{itemize}

    \bigskip

    \begin{center}
    \begin{tikzpicture}[level distance=1cm]
        \tikzstyle{level 1}=[sibling distance=0cm]
        \tikzstyle{level 2}=[sibling distance=1.5cm]
        \node (tree) {section}
            child {node (content) {content}
                child {node {text}}
                child {node {section}
                    child {node (title) {title}}}}
            ;
        \uncover<2->{
        \node (twig1) [right of=tree,node distance=5cm] {section}
            child {node (content1) {content}
                child {node {text}}}
            ;
        \node (twig2) [right of=twig1,node distance=2cm] {section}
            child {node {content}
                child {node {section}
                    child {node {title}}}}
            ;
        \draw[map,->] ([xshift=1cm]title |- content) -- ([xshift=-1.5cm]content1 |- content1);
        }
    \end{tikzpicture}
    \end{center}
\end{frame}

\section{Algorithmen}

\begin{frame}
    \frametitle{Algorithmen}
	%Stack: Wird von oben befüllt (LIFO); PUSH: packt auf den Stack; POP: holt vom Stack
    \begin{itemize}
    \item Multi-Predicate Merge Join (MPMGJN) 
        \begin{itemize}
        \item arbeitet Ancestor/Descendant-Achsen effizient ab
        %Besonderheit: Speicherung der einzelnen Knotenpositionen in Index (s.o.).
	%Folge: Übertrifft den Standard RDBMS-Join-Algorithmus leistungsmäßig
        % um mehr als eine Zehnerpotenz (order of magnitude?).
        \end{itemize}
    \item PathMPMJ
        \begin{itemize}
	\item Optimierter MPMGJN
        \item arbeitet aufeinanderfolgende A/D-Achsen besser ab
        %Besonderheit: Optimierter MPMGJN.
        %Nicht jeder Anfrage-Knoten hat eine Markierung in der "`Knotenliste"' (T).
        %Jede Markierung zeigt auf eine frühere Position in der "`Knotenliste"'.
	%Folge: noch nicht asymtotisch optimal zur Anfrage.
	\end{itemize}
    \item PathStack
        \begin{itemize}
	\item benutzt zusätzliche Datenstruktur (PathStack)
        \item arbeitet aufeinanderfolgende A/D-Achsen optimal ab
        \end{itemize}
    \item TwigStack
        \begin{itemize}
        \item basiert auf PathStack
        \item arbeitet auch nebeneinander liegende A/D-Achsen optimal ab
        \end{itemize}
    \item TwigStackXB
        \begin{itemize}
        \item basiert auf TwigStack
        \item sublinear bezüglich der Eingangsdaten
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Beispiel(Multi-Predicate Merge Join -- MPMGJN/1)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report00.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(Multi-Predicate Merge Join -- MPMGJN/2)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report01.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(Multi-Predicate Merge Join -- MPMGJN/3)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report02.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(Multi-Predicate Merge Join -- MPMGJN/4)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report03.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathMPMJ)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report03a.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/1)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report10.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/2)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report11.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/3)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report11a.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/4)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report11b.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/5)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report11c.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/6)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report12.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/7)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report13.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/8)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report13a.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(PathStack/9)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report13b.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/1)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report10.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/2)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report11.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/3)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report12.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/4)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report13.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/5)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report14.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
\frametitle{Beispiel(TwigStack/6)}
\begin{center}
\includegraphics[bb=0 0 192 157]{grafiken_praesi/report15.jpg}
% report00.jpg: 400x327 pixel, 150dpi, 6.77x5.54 cm, bb=0 0 192 157
\end{center}
\end{frame}

\begin{frame}
    \frametitle{PathStack}
    %Idee:
	%Die wiederholte Generierung von Positionsrepräsentationen (DocId, LeftPos:RightPos, LevelNum) für Zwischen- und Endergebnisse, bei Abarbeitung der Anfrage. Dabei wird (via LeftPos) durch die sortierten Knoten eines Datenstroms iteriert.
    \begin{itemize}
    \item Vorteile
        \begin{itemize}
	\item prüft Zweige von der Wurzel bis zum Blatt
	\item hält erfolgreiche und nur teilweise erfolgreiche Anfragepfade im Speicher 
        \end{itemize}
    \item Nachteile
        \begin{itemize}
	\item ineffizient bei stark einschränkenden Anfragen %(unnötige Zwischenergebnisse, Prädikate )
	\item lange Anfrage-Pfade brauchen Zeit %(Teilpfade müssen trotzdem alle geprüft werden)) 
	\item ist somit nicht asymtotisch optimal zur Anfrage
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{TwigStack}
	%Phase1: erweiterter PathStack
	%Phase2: zusammenfügen der gefundenen Ergebnisse
    \begin{itemize}
    \item Vorteile
        \begin{itemize}
        \item löscht im Speicher gehaltene Teilpfade der Anfrage, wenn sie nicht erfolgreich sind
	\item somit Linearität bezüglich Anfrage %Zwischenergebnisse sind maximal so groß, wie die Summe der (1) Eingabegrößen (Teilpfade der Anfrage) und der (2) Ausgabegrößen (Antworten der auf das Anfragemuster)
        \end{itemize}
    \item Nachteile
        \begin{itemize}
	\item lange Anfrage-Pfade brauchen Zeit %(Teilpfade müssen trotzdem alle geprüft werden)
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{TwigStackXB}
	%XB Tree, ist Variante des B Trees [Unterschied enthält eine Begrenzung (Bounding Segment: N.L, N.R, N= interne Seiten, L= LeftPos, R=RightPos] und erstellt den Index in gewohnter Form (DocID, LeftPos:RightPos, LevelNum) für alle Elemente des XML Baums. R muß nach oben bekannt gemacht (propagiert) werden. P.parent (act = Pointer der auf das Elternseite zeigt)
    \begin{itemize}
    \item Vorteile
        \begin{itemize}
	\item Sub-Linearität bezüglich der Anfrage
	\item beste Ergebnisse bei [4,64] Knoten
	\item bei komplexen Anfragen bessere Ergebnisse wie zuvor  
        \end{itemize}
    \item Nachteile
        \begin{itemize}
	\item viele interne Zwischenergebnisse notwendig (internal pages)
	\item einfache Anfragen sind schlechter gestellt %muss tief gehen
        \end{itemize}
    \end{itemize}
\end{frame}

\end{document}
