From: Kim Nguyễn Date: Mon, 29 Sep 2014 20:15:54 +0000 (+0200) Subject: . X-Git-Url: http://git.nguyen.vg/gitweb/?p=hacks%2FsimpleWebSlides.git;a=commitdiff_plain;h=00a1f062a9f255b188f15b1d5373b5d73901c675 . --- diff --git a/pres-typex/01.xhtml b/pres-typex/01.xhtml new file mode 100644 index 0000000..2e104f0 --- /dev/null +++ b/pres-typex/01.xhtml @@ -0,0 +1,240 @@ + +â"> + â"> + +] + > + + + Tatoo : the path forward + + + + + + + + + + + + + + + + + + + +

+

Tatoo : the path forward

+

TYPEX meeting, Grenoble April 14-16 2014

+ kn@lri.fr
+ http://www.lri.fr/~kn +

+ +

XPath in nutshell

+

+

XPath

+

W3C query (sub-)language. Allows one to + denote a set of nodes in a document

+


+   /descendant::M/ancestor::A[ descendant::P  or parent::Q ]/child::*

+

A path is made of several + steps steps
A step is made of : +
- An axis amongst + : self, child, parent, descendant, ancestor, descendant-or-self, ancestor-or-self, following-sibling, preceding-sibling, + â¦
- A node test : label + name, *, text(), node(), â¦
- An optional filter : an XPath expression whose + truth value determine is the node is kept
+

+ + +

+

+

Filters (or predicates)

+

An arbitrary expression whose value is cast into a + Boolean (true keeps the selected node, false + discards it)

+

Example :

+


+   //A[ child::B and .//* = count(/descendant::X) mod 12 ]
+

+

* is an alias for child::*
// is an alias for /descendant-or-self::node()/
. is an alias for self::node()

+

BTW: XPath semantics + is crazy rich. In + the example we want all A nodes (ok) that have + a B child (ok) and that have a + descendant (humâ¦ ) + for which the (string) concatenation + of its text descendants (?) is equal to the number + of X elements in the document mod 12 + (whaaat ?) +

+

+

Tatoo : what is it ? how does it work ?

+

+

SXSI

+

Succint XML Self-Index: (limited) XPath query engine developped during my + postdoc at Nicta. It uses: +

+

Self-Index developped by MÃ¤kinen, SirÃ©n, Valimaki : + stores a text T of N characters (in an + alphabet of size σ) in NÂ·H_k(T) + + o(NÂ·log σ) bits.
+ Can answer queries like Â« first position after i that + matches a constant string s Â» in O(|s|Â·log σ) +
Succinct tree index of Arroyuello, Claude, Navarro : + stores a tree of size M with labels in an alphabet of + size θ in 4M(2 + log θ) + o(M) bits.
+ Full navigation + jumping from a node to the next one with a + given label (and also LCA of two nodes) in O(1). +
Non det. alternating tree-automata of Maneth and + myself, on the + fly determinization and approximation of the sets of relevant + nodes (worst case O(MÂ·|A|) to evaluate an automaton + of size A). +

+

Can answer downward (no ancestor, parent, â¦) XPath with text + expressions of the form (f(., constant), + with f ∈ { contains, starts-with, ends-with, =, <, > , + <=, >= }). Translation from XPath to automata is + linear in size

+

+

+

Pros and cons of SXSI

+

Pros

+

For the considered subset: much faster than state of the + art optimized XML DB
Very small space overhead
Theoreticall sound formalism, proven worst-case + bounds

+

Cons

+

The subset is ~~too restricted~~ (no upward axes, no + arbitrary joins)
Encoding was ~~wrong~~ in subtle ways (e.g. in some corner + cases with double negations in filters) +

+ +

+

+

Tree Automata TOOlkit

+

RÃ©-implmentation of the automata part of SXSI

+

Supports full navigational XPath (upward axis)
Retain polynomial (combined complexity) running + time, i.e. O(|Doc|Â·|Q|) for an XPath + query Q. +

+

+

+

How does it work ?

+

Sample document: alphabet.xml +

+