ANDES : efficient evaluation of NOT-twig queries in relational databases
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 queri...
Saved in:
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2013
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/84485 http://hdl.handle.net/10220/11745 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-84485 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-844852020-05-28T07:17:16Z ANDES : efficient evaluation of NOT-twig queries in relational databases Soh, Kheng Hong. Truong, Ba Quan. Bhowmick, Sourav S. School of Computer Engineering DRNTU::Engineering::Computer science and engineering 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. 2013-07-17T06:41:01Z 2019-12-06T15:46:00Z 2013-07-17T06:41:01Z 2019-12-06T15:46:00Z 2012 2012 Journal Article 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. 1066-8888 https://hdl.handle.net/10356/84485 http://hdl.handle.net/10220/11745 10.1007/s00778-012-0275-9 en The VLDB journal © 2012 Springer-Verlag. |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Engineering::Computer science and engineering |
spellingShingle |
DRNTU::Engineering::Computer science and engineering Soh, Kheng Hong. Truong, Ba Quan. Bhowmick, Sourav S. ANDES : efficient evaluation of NOT-twig queries in relational databases |
description |
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. |
author2 |
School of Computer Engineering |
author_facet |
School of Computer Engineering Soh, Kheng Hong. Truong, Ba Quan. Bhowmick, Sourav S. |
format |
Article |
author |
Soh, Kheng Hong. Truong, Ba Quan. Bhowmick, Sourav S. |
author_sort |
Soh, Kheng Hong. |
title |
ANDES : efficient evaluation of NOT-twig queries in relational databases |
title_short |
ANDES : efficient evaluation of NOT-twig queries in relational databases |
title_full |
ANDES : efficient evaluation of NOT-twig queries in relational databases |
title_fullStr |
ANDES : efficient evaluation of NOT-twig queries in relational databases |
title_full_unstemmed |
ANDES : efficient evaluation of NOT-twig queries in relational databases |
title_sort |
andes : efficient evaluation of not-twig queries in relational databases |
publishDate |
2013 |
url |
https://hdl.handle.net/10356/84485 http://hdl.handle.net/10220/11745 |
_version_ |
1681056391044792320 |