\documentclass{beamer} \mode{\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 2 3 Der moderne Dieb 4 5
6 7 Unterwegs 8 9 10 11 Gerade zu Weihnachten ... 12 13
... 22
23
... 32
33 34
35 \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}