Efficient evaluation of high-selective xml twig patterns with parent child edges in tree-unaware rdbms
Sourav Saha Bhowmick, Erwin Leonardi, Hongmei Sun · 2007
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-theart 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. 2 1