Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F13%3A86088950" target="_blank" >RIV/61989100:27240/13:86088950 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00778-012-0295-5" target="_blank" >http://dx.doi.org/10.1007/s00778-012-0295-5</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00778-012-0295-5" target="_blank" >10.1007/s00778-012-0295-5</a>
Alternative languages
Result language
angličtina
Original language name
Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings
Original language description
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 Stack which introduced a linear output enumeration time with respect to the result size. In this article,we introduce a holistic algorithm called GTPStack 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
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F10%2F0573" target="_blank" >GAP202/10/0573: Handling XML Data in Heterogeneous and Dynamic Environments</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
VLDB Journal
ISSN
1066-8888
e-ISSN
—
Volume of the periodical
22
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
25
Pages from-to
369-393
UT code for WoS article
000319276000005
EID of the result in the Scopus database
—