TY - GEN
T1 - A holistic algorithm for efficiently evaluating xtwig joins
AU - Ning, Bo
AU - Wang, Guoren
AU - Yu, Jeffrey Xu
PY - 2008
Y1 - 2008
N2 - More and more XML data have been generated and used in the data exchange. XML employs a tree-structure data model, but lots of queries submitted by users are not like the tree-structure. Those queries contain ancestor axis in predicates, and specify the pattern of selection predicates on multiple elements from descendants to ancestors. Efficiently finding all occurrences of such an xtwig pattern in an XML database is crucial for XML query processing. A straightforward method is to rewrite an xtwig pattern to equivalent reverse-axis-free one. However, this method needs scanning the element streams several times and is rather expensive to evaluate. In this paper, we study the xtwig pattern, and propose two basic decomposing methods, VertiDec and HoriDec, and a holistic processing method, XtwigStack, for processing xtwig queries. The experiments show that the holistic algorithm is much more efficient than the rewriting and decomposition approaches.
AB - More and more XML data have been generated and used in the data exchange. XML employs a tree-structure data model, but lots of queries submitted by users are not like the tree-structure. Those queries contain ancestor axis in predicates, and specify the pattern of selection predicates on multiple elements from descendants to ancestors. Efficiently finding all occurrences of such an xtwig pattern in an XML database is crucial for XML query processing. A straightforward method is to rewrite an xtwig pattern to equivalent reverse-axis-free one. However, this method needs scanning the element streams several times and is rather expensive to evaluate. In this paper, we study the xtwig pattern, and propose two basic decomposing methods, VertiDec and HoriDec, and a holistic processing method, XtwigStack, for processing xtwig queries. The experiments show that the holistic algorithm is much more efficient than the rewriting and decomposition approaches.
UR - https://www.scopus.com/pages/publications/47249102910
U2 - 10.1007/978-3-540-78568-2_48
DO - 10.1007/978-3-540-78568-2_48
M3 - Conference contribution
AN - SCOPUS:47249102910
SN - 3540785671
SN - 9783540785675
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 571
EP - 579
BT - Database Systems for Advanced Applications - 13th International Conference, DASFAA 2008, Proceedings
PB - Springer Verlag
T2 - 13th International Conference on Database Systems for Advanced Applications, DASFAA 2008
Y2 - 19 March 2008 through 21 March 2008
ER -