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

\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{shapes}

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

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

\tikzstyle{xml}=[draw=green!50,fill=green!20,thick]
\tikzstyle{relation}=[draw=blue!50,fill=blue!20,thick]
\tikzstyle{wichtig}=[circle,draw=blue!50,fill=blue!20,thick]
\tikzstyle{pfeil}=[->,thick]
\tikzstyle{pfeilwichtig}=[->,draw=red!50,thick]
\tikzstyle{xmltag}=[rectangle,draw]
\tikzstyle{xmltext}=[ellipse,draw]
\tikzstyle{xmlbeschr}=[above]

\newcommand{\xmltag}[1]{$\langle${#1}$\rangle$}
\newcommand{\xmltext}[1]{#1}

\title{Effiziente XPath-Ausführung}
\author{Volker Grabsch \and Christine Janischek}
\date{10. Dezember 2007}

\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-sa/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}
        Improving the Efficiency of XPath Execution
        on Relational Systems
        \end{quote}
    von Haris Georgiadis und Vasilis Vassalos.
\end{frame}

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

\section{Einleitung}

\begin{frame}
    \frametitle{Einleitung}

    \begin{tikzpicture}[node distance=2.2cm,thick]
        \node[wichtig]     (DB)                               {RDBMS};

        \node[relation]    (Daten)   [above left of=DB]       {Relationen-Tupel}
            edge [pfeil] (DB);
        \node[xml]         (XML)     [above left of=Daten]    {XML-Dokumente}
            edge [pfeil] (Daten);

        \node[relation]    (RSchema) [below left of=DB]       {Relationenschema}
            edge [pfeil] (DB);
        \node[xml]         (XSD)     [below left of=RSchema]  {XML-Schema}
            edge [pfeil] (RSchema);

        \node[relation]    (SQL)     [right of=DB]            {SQL}
            edge [pfeil] (DB);
        \node[xml]         (XPath)   [right of=SQL]           {XPath}
            edge [pfeil] (SQL);
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Einleitung}

    \begin{tikzpicture}[node distance=2.2cm,thick]
        \node[wichtig]     (DB)                               {RDBMS};

        \node[relation]    (Daten)   [above left of=DB]       {Relationen-Tupel}
            edge [pfeil] (DB);
        \node[xml]         (XML)     [above left of=Daten]    {XML-Dokumente}
            edge [pfeil] (Daten);

        \node[relation]    (RSchema) [below left of=DB]       {Relationenschema}
            edge [pfeil] (DB);
        \node[xml]         (XSD)     [below left of=RSchema]  {XML-Schema}
            edge [pfeilwichtig] (RSchema);

        \node[relation]    (SQL)     [right of=DB]            {SQL}
            edge [pfeil] (DB);
        \node[xml]         (XPath)   [right of=SQL]           {XPath}
            edge [pfeilwichtig] (SQL);
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Grundidee}

    \begin{itemize}
    \item<1-> Ziel
        \begin{itemize}
        \item schnelle XPath-Anfragen
        \item einfacherer SQL-Code
        \item weniger Joins
        \end{itemize}
    \item<2-> Strategie
        \begin{itemize}
        \item speichere mehr Informationen über die Hierarchie
        \item 1 Join = mehrere XPath-Schritte
        \end{itemize}
    \end{itemize}
\end{frame}

\section{XML-Schema $\rightarrow$ Relationenschema}

\subsection{Aufbau der Relationen}

\begin{frame}
    \frametitle{Relationenschema}

    \begin{itemize}
    \item<1-> je "`Complex Type"' eine Relation
    \item<2-> Attribute:
        \begin{itemize}
        \item<1,2-> ID
        \item<1,3-> Eltern-IDs pro Eltern-Typ
        \item<1,4-> Dewey-Position
        \item<1,5-> Pfad
        \item<1,6-> "`Simple Type"'-Elemente, Attribute, Text
        \end{itemize}
    \end{itemize}
\end{frame}

\subsection{Beispiel}

\begin{frame}
    \frametitle{Beispiel: XML-Schema und XML-Dokument}

    (entnommen aus dem Paper)

    \resizebox{\textwidth}{!}{%
        \includegraphics{Scherz-Skizze}}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: XML-Schema und XML-Dokument}

    \begin{center}
    \Large
    Nur ein Scherz!
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: XML-Schema}

    \begin{center}
    \begin{tikzpicture}
        \tikzstyle{level 1}=[sibling distance=2.5cm]
        \node[xmltag]{\xmltag{report}}
            child{node[xmltag]{\xmltag{author}}
                edge from parent node[left]{*}}
            child{node[xmltag]{\xmltag{date}}}
            child{node[xmltag](section){\xmltag{section}}
                edge from parent node[right]{*}}
            ;
        \path (section) edge [loop below] node{*} (section);
    \end{tikzpicture}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: XML-Dokument (mit Dewey-Positionen)}

    \begin{tikzpicture}
        \tikzstyle{level 1}=[sibling distance=2.5cm]
        \tikzstyle{level 2}=[sibling distance=2.2cm]
        \tikzstyle{every label}=[red!70]
        \node(root)[xmltag,label=below:1]{\xmltag{report}}
            [level distance=1.5cm]
            child{node[xmltag,label=below left:1.1]{\xmltag{author}}
                child{node[xmltext,label=below:1.1.1]{\xmltext{Christine}}}}
            child{node[xmltag,label=below left:1.2]{\xmltag{author}}
                child{node[xmltext,label=below:1.2.1]{\xmltext{Volker}}}}
            child{node[xmltag,label=below left:1.3]{\xmltag{date}}
                child{node[xmltext,label=below:1.3.1]{\xmltext{Dez 2007}}}}
            child{node[xmltag,label=below left:1.4]{\xmltag{section}}
                [level distance=2.5cm]
                child{node[xmltag,label=below left:1.4.1]{\xmltag{section}}
                    [level distance=1.5cm]
                    child{node[xmltext,label=below:1.4.1.1]{\xmltext{blabla}}}}
                child{node[xmltag,label=below left:1.4.2]{\xmltag{section}}
                    [level distance=1.5cm]
                    child{node[xmltext,label=below:1.4.2.1]{\xmltext{sülzsülz}}}}}
            ;
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: Relation \xmltag{report}}

    \begin{tabular}{|ccll|}
    \hline
    ID &
    Dewey-Pos &
    Pfad &
    date \\
    \hline
    1 & 1 & /report & Dez 2007 \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: Relation \xmltag{author}}

    \begin{tabular}{|cccll|}
    \hline
    ID &
    \xmltag{report} &
    Dewey-Pos &
    Pfad &
    text \\
    \hline
    1 & 1 & 1.1 & /report/author & Christine \\
    2 & 1 & 1.2 & /report/author & Volker \\
    \hline
    \end{tabular}
\end{frame}

\begin{frame}
    \frametitle{Beispiel: Relation \xmltag{section}}

    \begin{tabular}{|ccccll|}
    \hline
    ID &
    \xmltag{report} &
    \xmltag{section} &
    D-Pos &
    Pfad &
    text \\
    \hline
    1 & 1 & & 1.4   & /report/section         & \\
    2 & & 1 & 1.4.1 & /report/section/section & blabla \\
    3 & & 1 & 1.4.2 & /report/section/section & sülzsülz \\
    \hline
    \end{tabular}
\end{frame}

\subsection{Reservierte Dewey-Positionen}

\begin{frame}
    \frametitle{Reservierte Dewey-Positionen}

    \begin{itemize}
        \item<1-> höchster Index (hier: 9) darf nicht verwendet werden
            \begin{itemize}
            \item<2-> \texttt{1.4.9} ist nicht erlaubt
            \item<3-> maximal 8 (statt 9) direkte Kindknoten
            \item<4-> $x < 1.5 \Leftrightarrow x < 1.4.9$
            \end{itemize}
    \end{itemize}
\end{frame}

\section{XPath $\rightarrow$ SQL}

\subsection{Grundregeln}

\begin{frame}
    \frametitle{Einfache Pfadfragmente (PPFs)}

    \uncover<1,6->{Welche Teile eines XPath können wir mit einem Schlag abarbeiten?}

    \begin{itemize}
    \item<2,5,6-> einfache Abwärts-Pfade
    \item<3,6->   einfache Aufwärts-Pfade
    \item<4,6->   Einzelschritte entlang der Seitenachsen
    \item<5,6->   ... jeweils mit abschließendem Prädikat
        \begin{itemize}
        \item kann komplexe XPath-Ausdrücke enthalten ($\rightarrow$ Rekursion!)
        \end{itemize}
    \end{itemize}

    \bigskip

    \textcolor{blue}{\texttt{%
        \uncover<1,2,6->{/report/date}%
        \uncover<1,3,6->{/..}%
        \uncover<1,5,6->{//section[.='blabla']}%
        \uncover<1,4,6->{/following::*}}}
\end{frame}

\begin{frame}
    \frametitle{Einfacher Abwärts-Pfad}

    \textcolor{blue}{\texttt{%
        \uncover<1-2,3,8->{/}%
        \uncover<1-2,4,8->{*}%
        \uncover<1-2,5,8->{/section}%
        \uncover<1-2,  6->{//section}}}

    $\rightarrow$

    \textcolor{blue}{\texttt{%
        \uncover<  8->{WHERE REGEX('}%
        \uncover<3,8->{\^{}/}%
        \uncover<4,8->{[\^{}/]+}%
        \uncover<5,8->{/section}%
        \uncover<  6->{/}%
        \uncover<  7->{(}%
        \uncover<  6->{.+/}%
        \uncover<  7->{)?}%
        \uncover<  6->{section\$}%
        \uncover<  8->{', Rel.Pfad)}}}
\end{frame}

\begin{frame}
    \frametitle{Einfacher Aufwärts-Pfad}

    \textcolor{blue}{\texttt{%
        \uncover<2,3->{/parent::section}%
        \uncover<1,3->{/ancestor::*}}}

    $\rightarrow$

    \textcolor{blue}{\texttt{%
        \uncover<  3->{WHERE REGEX('}%
        \uncover<1,3->{\^{}/.+/}%
        \uncover<2,3->{section/[\^{}/]+\$}%
        \uncover<  3->{', VorherigeRel.Pfad)}}}

    \uncover<4->{%
        Alternativ:

        \textcolor{blue}{\texttt{%
            WHERE REGEX('%
            \^{}/.+/section\$%
            ', VorherigeElternRel.Pfad)}}
    }
\end{frame}

\begin{frame}
    \frametitle{Einzelschritte entlang der Seitenachsen}

    \textcolor{blue}{\texttt{/preceding-sibling::author}}

    $\rightarrow$

    \textcolor{blue}{\texttt{%
        WHERE REGEX('%
        \^{}.*/author\$%
        ', Rel.Pfad)}}
\end{frame}

\begin{frame}
    \frametitle{Prädikate}

    \begin{itemize}
    \item<1> einfaches Prädikat:
        \begin{itemize}
        \item[]
        \textcolor{blue}{\texttt{//*[date='Dez 2007']}}

        $\rightarrow$

        \textcolor{blue}{\texttt{WHERE ... AND date='Dez 2007'}}
        \end{itemize}

    \item<2> Prädikat mit komplexem Teilpfad:
        \begin{itemize}
        \item[]
        \textcolor{blue}{\texttt{//*[section/section='blabla']}}

        $\rightarrow$

        \textcolor{blue}{\texttt{... AND EXISTS (SELECT ... WHERE ... AND text='blabla')}}
        \end{itemize}

    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Zusammenführen der PPFs mittels Dewey-Positionen}

    \textcolor{blue}{\texttt{//A/ancestor::B}}

    $\rightarrow$

    \textcolor{blue}{\texttt{WHERE A.Dewey-Pos > B.Dewey-Pos\\\ \ AND A.Dewey-Pos < B.Dewey-Pos || '.9'}}
\end{frame}

\begin{frame}
    \frametitle{Zusammenführen von Vorwärts-Pfaden}

    \begin{itemize}
    \item<1-> Join über Dewey-Positionen
    \item<2-> Pfad des bisherigen Elements
              in die Regex des nächsten Elements einbauen!
        \begin{itemize}
        \item<3->[]
        \textcolor{blue}{\texttt{//A[@x=0]//*/B}}

        $\rightarrow$

        \textcolor{blue}{\texttt{WHERE ... AND REGEX('\^{}' || A.Pfad || '/.+/B\$', B.Pfad)}}
        \end{itemize}
    \end{itemize}
\end{frame}

\subsection{Optimierungen}

\begin{frame}
    \frametitle{Binärkodierung der Dewey-Positionen}

    \begin{itemize}
    \item<1-> Dewey-Positionen binär kodieren
    \item<2-> Verzicht auf Trennzeichen
    \item<3-> Beispiel:
        \begin{itemize}
        \item<1-2,3-> 3 Bytes je Position
        \item<1-2,4-> Bereich: \texttt{000000} -- \texttt{feffff}
        \item<1-2,5-> Reservierter Bereich: \texttt{ff....}
        \item<1-2,6-> \texttt{dewey\_pos || '$\backslash{}$xff'}
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{LIKE statt Regex}

    \begin{itemize}
    \item<1-> Einfache reguläre Ausdrücke mit LIKE formulieren
        \begin{itemize}
        \item[]<2->
        \textcolor{blue}{\texttt{WHERE REGEX('\^{}/report/{}.+/section\$', Rel.Pfad)}}

        $\rightarrow$

        \textcolor{blue}{\texttt{Rel.Pfad LIKE '/report/\%/section'}}
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Zusätzliches Attribut für Elementnamen}

    \begin{itemize}
    \item<1-> Neues Attribut: Elementname
        \begin{itemize}
        \item[]<2->
        \textcolor{blue}{\texttt{WHERE REGEX('\^{}.*/section\$', Rel.Pfad)}}

        $\rightarrow$

        \textcolor{blue}{\texttt{WHERE Rel.Elementname = 'section'}}
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Pfad-ID}

    \begin{itemize}
    \item<1-> Pfade wiederholen sich oft
    \item<2-> Neue Relation: (Pfad-ID, Pfad)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Unnötige Pfadfilterungen}

    \begin{itemize}
    \item<1-> Zu jeder Relation ("`Complex Type"'):
        \begin{itemize}
        \item<1-> Welche Pfade sind laut Schema möglich?
        \end{itemize}
    \item<2-> Zu jeder Regex:
        \begin{itemize}
        \item<1,2-> Erlaubt die Regex all diese Pfade?
        \item<1,3-> Erlaubt die Regex keinen der Pfade?
        \end{itemize}
    \item<4-> Falls ja:
        \begin{itemize}
        \item<1-3,4->Regex-Vergleich weglassen
        \item<1-3,5->Join mit Pfad-ID-Relation weglassen
        \end{itemize}
    \end{itemize}
\end{frame}

\section{Kritik}

\begin{frame}
    \frametitle{Kritik}

    \begin{itemize}
    \item<1-> Mehrere Rückwärtsschritte dürfen nicht einfach zusammengefasst werden!
        \begin{itemize}
        \item[]<2->
        \textcolor{blue}{\texttt{//F/parent::B/parent::*/ancestor::B}}

        $\rightarrow$

        \textcolor{blue}{\texttt{WHERE REGEX('\^{}.*/B/.+/B/F\$', F.Pfad)}}
        \end{itemize}
    \end{itemize}
\end{frame}

\end{document}