XPath Node Selection over Grammar-Compressed Trees

Sebastian Maneth; Tom Sebastian

doi:10.4204/EPTCS.134.5

XPath Node Selection over Grammar-Compressed Trees

Sebastian Maneth, Tom Sebastian

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.

Original language	English
Title of host publication	Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19/10/2013.
Publisher	Cornell University Press
Pages	38-48
Number of pages	11
DOIs	https://doi.org/10.4204/EPTCS.134.5
Publication status	Published - 2013

Access to Document

10.4204/EPTCS.134.5

Maneth Sebastian 2013 XPath Node Selection over Grammar Compressed TreesFinal published version, 107 KB

http://dx.doi.org/10.4204/EPTCS.134.5

Cite this

@inproceedings{33dab85de435411e96aee1cf22010e11,

title = "XPath Node Selection over Grammar-Compressed Trees",

abstract = "XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.",

author = "Sebastian Maneth and Tom Sebastian",

year = "2013",

doi = "10.4204/EPTCS.134.5",

language = "English",

pages = "38--48",

booktitle = "Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19/10/2013.",

publisher = "Cornell University Press",

}

TY - GEN

T1 - XPath Node Selection over Grammar-Compressed Trees

AU - Maneth, Sebastian

AU - Sebastian, Tom

PY - 2013

Y1 - 2013

N2 - XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.

AB - XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.

U2 - 10.4204/EPTCS.134.5

DO - 10.4204/EPTCS.134.5

M3 - Conference contribution

SP - 38

EP - 48

BT - Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19/10/2013.

PB - Cornell University Press

ER -

XPath Node Selection over Grammar-Compressed Trees

Abstract

Access to Document

Fingerprint

Cite this