--- /dev/null
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
+[
+ <!ENTITY in "<small style='font-size:small'>∈</small>">
+ <!ENTITY notin "<small style='font-size:small'>∉</small>">
+ <!ENTITY mapsto "↦">
+]
+ >
+<html xmlns="http://www.w3.org/1999/xhtml" >
+ <head>
+ <title>Tatoo : the path forward</title>
+
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=utf-8" />
+ <meta name="copyright"
+ content="Copyright © 2013 Kim Nguyễn" />
+
+ <!-- Load jQuery -->
+ <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
+ <script src="../libs/raphael-min.js" type="text/javascript" ></script>
+ <!-- Load the library -->
+ <script src="../simpleWebSlides.js" type="text/javascript" ></script>
+
+ <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
+ <!-- Load a custom Theme, the class-element marks this style-sheet
+ a "theme" that can be swtiched dynamicaly -->
+ <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
+
+ <!-- Customize some templates and initialize -->
+
+ <script type="text/javascript">
+ SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
+ SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
+ SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
+
+ //Ensures that we load SWS at the very end, after MathJax has
+ //been initialized
+
+ $(window).load(SWS.Presentation.init);
+ </script>
+ </head>
+ <body>
+ <div class="sws-slide sws-cover sws-option-nofooter">
+ <h1>Tatoo : the path forward</h1>
+ <h3>TYPEX meeting, Grenoble April 14-16 2014</h3>
+ <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
+ <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
+ </div>
+
+ <h1>XPath in nutshell</h1>
+ <div class="sws-slide">
+ <h1>XPath</h1>
+ <p>W3C <em>query</em> (sub-)language. Allows one to
+ denote a <em>set of nodes</em> in a document</p>
+ <code class="xpath">
+ /<span class="step"><span class="axis">descendant</span>::<span class="test">M</span></span>/<span class="step"><span class="axis">ancestor</span>::<span class="test">A</span><span class="filter">[ <span class="axis">descendant</span>::<span class="test">P</span> or <span class="axis">parent</span>::<span class="test">Q </span>]</span></span>/<span class="step"><span class="axis">child</span>::<span class="test">*</span></span></code>
+ <ul>
+ <li class="sws-pause">A path is made of several
+ steps <span style="color:green;">steps</span></li>
+ <li > A step is made of :
+ <ul>
+ <li class="sws-pause">An <span style="color:orange;">axis</span> amongst
+ : <tt>self</tt>, <tt>child</tt>, <tt>parent</tt>, <tt>descendant</tt>, <tt>ancestor</tt>, <tt>descendant-or-self</tt>, <tt>ancestor-or-self</tt>, <tt>following-sibling</tt>, <tt>preceding-sibling</tt>,
+ … </li>
+ <li class="sws-pause">A <span style="color:purple">node test</span> : label
+ name, <tt>*</tt>, <tt>text()</tt>, <tt>node()</tt>, …</li>
+ <li class="sws-pause"> An optional <span style="color:#88f">filter</span> : an XPath expression whose
+ truth value determine is the node is kept</li>
+ </ul>
+ </li>
+ </ul>
+ <script type="text/javascript">
+ <![CDATA[
+ var col_change = function (sel, col) {
+ return function (canvas) {
+ canvas.find(".xpath *").css("color","");
+ var objs = canvas.find(sel);
+ objs.css("color", col);
+ };
+ };
+ var reg = SWS.Presentation.registerCallback;
+ reg ("0", col_change(".xpath *",""));
+ reg ("1", col_change(".step","green"));
+ reg ("2", col_change(".axis","orange"));
+ reg ("3", col_change(".test","purple"));
+ reg ("4", col_change(".filter","#88f"));
+ ]]>
+ </script>
+
+ </div>
+ <div class="sws-slide">
+ <h1>Filters (or predicates)</h1>
+ <p>An <em>arbitrary expression</em> whose value is cast into a
+ Boolean (<tt>true</tt> keeps the selected node, <tt>false</tt>
+ discards it)</p>
+ <p>Example :</p>
+ <code>
+ //A[ child::B and .//* = count(/descendant::X) mod 12 ]
+ </code>
+ <ul>
+ <li><tt>*</tt> is an alias for <tt>child::*</tt></li>
+ <li><tt>//</tt> is an alias for <tt>/descendant-or-self::node()/</tt></li>
+ <li><tt>.</tt> is an alias for <tt>self::node()</tt></li>
+ </ul>
+ <p class="sws-pause" style="background:white">BTW: XPath semantics
+ is <span style="text-decoration:line-through">crazy</span> <em>rich</em>. In
+ the example we want all <tt>A</tt> nodes (ok) that have
+ a <tt>B</tt> child (ok) and <span class="sws-pause">that have a
+ descendant (hum… )
+ </span><span class="sws-pause">for which the (string) concatenation
+ of its text descendants (?) is equal to the number
+ of <tt>X</tt> elements in the document <tt>mod 12</tt>
+ (whaaat ?)</span>
+ </p>
+ </div>
+ <h1>Tatoo : what is it ? how does it work ?</h1>
+ <div class="sws-slide">
+ <h1>SXSI</h1>
+ <p>Succint XML Self-Index: (limited) XPath query engine developped during my
+ postdoc at Nicta. It uses:
+ </p>
+ <ul><li><em>Self-Index</em> developped by Mäkinen, Sirén, Valimaki :
+ stores a text <tt>T</tt> of <tt>N</tt> characters (in an
+ alphabet of size <tt>σ</tt>) in <tt>N·H<sub>k</sub>(T)
+ + o(N·log σ) bits</tt>.<br/>
+ Can answer queries like « <i>first position after i that
+ matches a constant string <tt>s</tt></i> » in <tt>O(|s|·log σ)</tt>
+ </li>
+ <li><em>Succinct tree index</em> of Arroyuello, Claude, Navarro :
+ stores a tree of size <tt>M</tt> with labels in an alphabet of
+ size <tt>θ</tt> in <tt>4M(2 + log θ) + o(M) bits</tt>. <br/>
+ Full navigation + jumping from a node to the next one with a
+ given label (and also LCA of two nodes) in O(1).
+ </li>
+ <li><em>Non det. alternating tree-automata</em> of Maneth and
+ myself, on the
+ fly determinization and approximation of the sets of relevant
+ nodes (worst case <tt>O(M·|A|)</tt> to evaluate an automaton
+ of size <tt>A</tt>).
+ </li>
+ </ul>
+ <p style="background:white">Can answer downward (no ancestor, parent, …) XPath with text
+ expressions of the form (<tt>f(., <i>constant</i>)</tt>,
+ with <tt>f ∈ { contains, starts-with, ends-with, =, <, > ,
+ <=, >= }</tt>). Translation from XPath to automata is
+ linear in size</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Pros and cons of SXSI</h1>
+ <p>Pros</p>
+ <ul><li>For the considered subset: <em>much faster</em> than state of the
+ art optimized XML DB</li>
+ <li>Very <em>small space overhead</em></li>
+ <li>Theoreticall sound formalism, <em>proven worst-case
+ bounds</em></li>
+ </ul>
+ <p>Cons</p>
+ <ul><li>The subset is <s>too restricted</s> (no upward axes, no
+ arbitrary joins)</li>
+ <li> Encoding was <s>wrong</s> in subtle ways (e.g. in some corner
+ cases with double negations in filters)
+ </li>
+ </ul>
+
+ </div>
+ <div class="sws-slide">
+ <h1>Tree Automata TOOlkit</h1>
+ <p>Ré-implmentation of the automata part of SXSI</p>
+ <ul>
+ <li>Supports <em>full navigational XPath</em> (upward axis)</li>
+ <li>Retain polynomial (combined complexity) running
+ time, <i>i.e.</i> <tt>O(|Doc|·|Q|)</tt> for an XPath
+ query <tt>Q</tt>.
+ </li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>How does it work ?</h1>
+ <p>Sample document: <tt>alphabet.xml</tt>
+ </p>
+ <iframe src="alphabet.xhtml" style="width:99%;height:320pt;border-style:none;"
+ />
+ </div>
+ <div class="sws-slide">
+ <h1>Example 1 : <tt>/descendant::M</tt></h1>
+ <iframe src="ex1.html" style="margin:0pt 5% 0pt 5%;width:90%;height:320pt;border-style:none;"
+ />
+ </div>
+ <div class="sws-slide">
+ <h1>Example 2 </h1>
+ <code> /descendant::M/ancestor::A[ descendant::P or parent::Q ]/child::*</code>
+ <iframe src="ex2.html" style="margin:0pt 5% 0pt 5%;width:90%;height:320pt;border-style:none;"
+ />
+ </div>
+
+ <h1>Open problems, todos and future directions</h1>
+ <div class="sws-slide">
+ <h1>Todos/open problems</h1>
+ <ul>
+ <li>Update the analysis of <em>relevant nodes</em> to automata
+ with upward moves to deduce nodes that can be skipped</li>
+ <li>Use the succinct index</li>
+ <li>Add joins (automata product ?)</li>
+ <li>Prove the correctness of the translation (with Matthieu,
+ in Coq)</li>
+ <li>Polynomial complexity relies on the fact that the
+ automaton is <em>ranked</em> (vague notion, only implemented
+ not formalized )</li>
+ <li>Automata now looks like <em>μ-calculus</em> formulæ
+ (historically, I chose automata because I did not know much
+ about logics and automata <i>felt</i>
+ more <em>execution-oriented</em>)</li>
+ <li>Implement static analysis through decision procedure:
+ emptiness, non-reachability etc.</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Future directions</h1>
+ <ul>
+ <li>Probably want to ditch automata and used formula
+ instead</li>
+ <li>see if cycle-freeness of formula implies the ranking
+ property (I think so) </li>
+ <li>Like for formula, use dedicated moves/modalities for
+ attributes instead of poluting the automaton with the tree
+ encoding
+ </li>
+ <li>Implement decision procédure using automata techniques,
+ use performances of the super-solver™ as a goal
+ </li>
+ <li>Define aproximate, lineartime (on the fly) analyses to
+ perform more efficient evaluation
+ </li>
+ <li class="sws-pause">Your item of choice here</li>
+ </ul>
+ </div>
+
+ </body>
+</html>
projects / hacks / simpleWebSlides.git / blobdiff