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.||URI:||https://hdl.handle.net/10356/84485
|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|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.