Indexing XML Documents Using Tree Paths Automaton
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F17%3A00314286" target="_blank" >RIV/68407700:21240/17:00314286 - isvavai.cz</a>
Výsledek na webu
<a href="http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945" target="_blank" >http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/OASIcs.SLATE.2017.10" target="_blank" >10.4230/OASIcs.SLATE.2017.10</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Indexing XML Documents Using Tree Paths Automaton
Popis výsledku v původním jazyce
An XML document can be viewed as a tree in a natural way. Processing tree data structures usually requires a pushdown automaton as a model of computation. Therefore, it is interesting that a finite automaton can be used to solve the XML index problem. In this paper, we attempt to support a significant fragment of XPath queries which may use any combination of child (i.e., /) and descendant-or-self (i.e., //) axis. A systematic approach to the construction of such XML index, which is a finite automaton called Tree Paths Automaton, is presented. Given an XML tree model T, the tree is first of all preprocessed by means of its linear fragments called string paths. Since only path queries are considered, the branching structure of the XML tree model can be omitted. For individual string paths, smaller Tree Paths Automata are built, and they are afterwards combined to form the index. The searching phase uses the index, reads an input query Q of size m, and computes the list of positions of all occurrences of Q in the tree T. The searching is performed in time O(m) and does not depend on the size of the XML document. Although the number of queries is clearly exponential in the number of nodes of the XML tree model, the size of the index seems to be, according to our experimental results, usually only about 2.5 times larger than the size of the original document.
Název v anglickém jazyce
Indexing XML Documents Using Tree Paths Automaton
Popis výsledku anglicky
An XML document can be viewed as a tree in a natural way. Processing tree data structures usually requires a pushdown automaton as a model of computation. Therefore, it is interesting that a finite automaton can be used to solve the XML index problem. In this paper, we attempt to support a significant fragment of XPath queries which may use any combination of child (i.e., /) and descendant-or-self (i.e., //) axis. A systematic approach to the construction of such XML index, which is a finite automaton called Tree Paths Automaton, is presented. Given an XML tree model T, the tree is first of all preprocessed by means of its linear fragments called string paths. Since only path queries are considered, the branching structure of the XML tree model can be omitted. For individual string paths, smaller Tree Paths Automata are built, and they are afterwards combined to form the index. The searching phase uses the index, reads an input query Q of size m, and computes the list of positions of all occurrences of Q in the tree T. The searching is performed in time O(m) and does not depend on the size of the XML document. Although the number of queries is clearly exponential in the number of nodes of the XML tree model, the size of the index seems to be, according to our experimental results, usually only about 2.5 times larger than the size of the original document.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2017
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
6th Symposium on Languages, Applications and Technologies
ISBN
978-3-95977-056-9
ISSN
—
e-ISSN
1868-8969
Počet stran výsledku
14
Strana od-do
"10:1"-"10:14"
Název nakladatele
Dagstuhl Publishing,
Místo vydání
Saarbrücken
Místo konání akce
Vila do Conde
Datum konání akce
26. 6. 2017
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—