Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F0573" target="_blank" >GAP202/10/0573: Zpracování XML dat v heterogenních a dynamických prostředích</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

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ů

Název periodika

VLDB Journal

ISSN

1066-8888

e-ISSN

—

Svazek periodika

22

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

25

Strana od-do

369-393

Kód UT WoS článku

000319276000005

EID výsledku v databázi Scopus

—