ANDES : efficient evaluation of NOT-twig queries in relational databases.
|dc.contributor.author||Soh, Kheng Hong.|
|dc.contributor.author||Truong, Ba Quan.|
|dc.contributor.author||Bhowmick, Sourav S.|
|dc.identifier.citation||Soh, K. H., Truong, B. Q., & Bhowmick, S. S. (2012). ANDES: efficient evaluation of NOT-twig queries in relational databases. The VLDB Journal, 21(6), 889-914.||en_US|
|dc.description.abstract||Despite a large body of work on XPath query processing in relational environment, systematic study of queries containing not-predicates have received little attention in the literature. Particularly, several xml supports of industrial-strength commercial rdbms fail to efficiently evaluate such queries. In this paper, we present an efficient and novel strategy to evaluate not -twig queries in a tree-unaware relational environment. not -twig queries are XPath queries with ancestor–descendant and parent–child axis and contain one or more not-predicates. We propose a novel Dewey-based encoding scheme called Andes (ANcestor Dewey-based Encoding Scheme), which enables us to efficiently filter out elements satisfying a not-predicate by comparing their ancestor group identifiers. In this approach, a set of elements under the same common ancestor at a specific level in the xml tree is assigned same ancestor group identifier. Based on this scheme, we propose a novel sql translation algorithm for not-twig query evaluation. Experiments carried out confirm that our proposed approach built on top of an off-the-shelf commercial rdbms significantly outperforms state-of-the-art relational and native approaches. We also explore the query plans selected by a commercial relational optimizer to evaluate our translated queries in different input cardinality. Such exploration further validates the performance benefits of Andes.||en_US|
|dc.relation.ispartofseries||The VLDB journal||en_US|
|dc.rights||© 2012 Springer-Verlag.||en_US|
|dc.subject||DRNTU::Engineering::Computer science and engineering|
|dc.title||ANDES : efficient evaluation of NOT-twig queries in relational databases.||en_US|
|dc.contributor.school||School of Computer Engineering||en_US|
Files in this item
There are no files associated with this item.
This item appears in the following Collection(s)