Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/220953

Title

Least common container of tree pattern queries and its applications

Author(s)

Wang, Junhu;  Xu Yu, Jeffrey;  Pang, Chaoyi;  Liu, Chengfei

Abstract

Tree patterns represent important fragments of XPath. In this paper, we show that some classes C of tree patterns exhibit such a property that, given a finite number of compatible tree patterns P1, . . . , Pn ∈ C, there exists another pattern P such that P1, . . . , Pn are all contained in P, and for any tree pattern Q ∈ C, P1, . . . , Pn are all contained in Q if and only if P is contained in Q.We experimentally demonstrate that the pattern P is usually much smaller than P1, . . . , Pn combined together. Using the existence of P above, we show that testing whether a tree pattern, P, is contained in another, Q ∈ C, under an acyclic schema graph G, can be reduced to testing whether PG, a transformed version of P, is contained in Q without any schema graph, provided that the distinguished node of P is not labeled *.We then show that, under G, the maximal contained rewriting (MCR) of a tree pattern Q using a view V can be found by finding the MCR of Q using VG without G, when there are no *-nodes on the distinguished path of V and no *-nodes in Q.

Publication type

Journal article

Research centre

Swinburne University of Technology

Source

Acta Informatica, Vol. 49, no. 3 (May 2012), pp. 173-202

Publication year

2012

FOR Code(s)

0802 Computation Theory and Mathematics;  0803 Computer Software;  0804 Data Format

Keyword(s)

Common containers;  Queries;  Tree patterns

Publisher

Springer

ISSN

0001-5903

Publisher URL

http://dx.doi.org/10.1007/s00236-012-0155-1

Copyright

Copyright © Springer-Verlag 2012.

Research Projects

Exploiting views in extensible markup language (XML) data processing, Australian Research Council grant number DP1093404

Peer reviewed