Efficient evaluation of high-selective XML twig patterns with parent child edges in tree-unaware rdbms

SS Bhowmick, E Leonardi, H Sun - … of the sixteenth ACM conference on …, 2007 - dl.acm.org
Proceedings of the sixteenth ACM conference on Conference on information and …, 2007dl.acm.org
Recent study showed that native twig join algorithms and tree-aware relational framework
significantly outperform tree-unaware approaches in evaluating structural relationships in
XML twig queries. In this paper, we present an efficient strategy to evaluate high-selective
twig queries containing only parent-child relationships in a tree-unaware relational
environment. Our scheme is built on top of our S UCXENT++ system. We show that by
exploiting the encoding scheme of S UCXENT++, we can devise efficient strategy for …
Recent study showed that native twig join algorithms and tree-aware relational framework significantly outperform tree-unaware approaches in evaluating structural relationships in XML twig queries. In this paper, we present an efficient strategy to evaluate high-selective twig queries containing only parent-child relationships in a tree-unaware relational environment. Our scheme is built on top of our SUCXENT++ system. We show that by exploiting the encoding scheme of SUCXENT++, we can devise efficient strategy for evaluating such twig queries. Extensive performance studies on various data sets and queries show that our approach performs better than a representative tree-unaware approach (GLOBAL-ORDER) and a state-of-the-art native twig join algorithm (TJFAST) on all benchmark queries with the highest observed gain factors being 243 and 95, respectively. Additionally, our approach reduces significantly the performance gap between tree-aware and tree-unaware approaches and even outperforms a tree-aware approach(MONETDB/XQUERY) for certain high-selective twig queries. We also report our insights to the plan choices a relational optimizer made during twig query evaluation by visually characterizing its behavior over the relational selectivity space.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果