Please use this identifier to cite or link to this item:
Title: ANDES : efficient evaluation of NOT-twig queries in relational databases
Authors: Soh, Kheng Hong.
Truong, Ba Quan.
Bhowmick, Sourav S.
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2012
Source: 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.
Series/Report no.: The VLDB journal
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.
ISSN: 1066-8888
DOI: 10.1007/s00778-012-0275-9
Rights: © 2012 Springer-Verlag.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Google ScholarTM



Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.