dc.contributor.authorSoh, Kheng Hong.
dc.contributor.authorTruong, Ba Quan.
dc.contributor.authorBhowmick, Sourav S.
dc.identifier.citationSoh, 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.abstractDespite 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.ispartofseriesThe VLDB journalen_US
dc.rights© 2012 Springer-Verlag.en_US
dc.subjectDRNTU::Engineering::Computer science and engineering
dc.titleANDES : efficient evaluation of NOT-twig queries in relational databasesen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Computer Engineeringen_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record