Can I read Optimal and Efficient Generalized Twig Pattern Processing: a Combination of Preorder and Postorder Filterings on EtoBox?

Optimal and Efficient Generalized Twig Pattern Processing: a Combination of Preorder and Postorder Filterings by Radim Bača; Michal Krátký; Tok Wang Ling; Jiaheng Lu is a Computer Science article available to read on EtoBox.

What is Optimal and Efficient Generalized Twig Pattern Processing: a Combination of Preorder and Postorder Filterings about?

Searching for occurrences of a twig pattern query (TPQ) in an XML document is a core task of all XML database query languages. The generalized twig pattern (GTP) extends the TPQ model to include semantics related to output nodes, optional nodes, and boolean expressions which are part of the XQuery language. Preorder filtering holistic algorithms such as TwigStack represent a significant class of TPQ processing approaches with a linear worst-case I/O complexity with respect to the sum of the input and output sizes for some query classes. Another important class of holistic approaches is represented by postorder filtering holistic algorithms such as Twig 2 Stack which introduced a linear output enumeration time with respect to the result size. In this article, we introduce a holistic algorithm called GTP-Stack which is the first approach capable of processing a GTP with a linear worst-case I/O complexity with respect to the GTP result size. This is achieved by using a combination of the preorder and postorder filterings before storing nodes in an intermediate storage. Additionally, another contribution of this article is an introduction of a new perspective of holistic algorithm opti

Who reads Optimal and Efficient Generalized Twig Pattern Processing: a Combination of Preorder and Postorder Filterings?

Author

Radim Bača; Michal Krátký; Tok Wang Ling; Jiaheng Lu

Publisher

Springer Science and Business Media LLC

Published

2012

Language

EN

Field

Computer Science (Physical Sciences)