Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/47700

Title

Filtering techniques for rewriting XPath queries using views

Author(s)

Zhou, Rui;  Liu, Chengfei;  Li, Jianxin;  Wang, Junhu

Abstract

In this paper, we propose several filtering techniques for rewriting XPath queries using views. The work is motivated by scenarios dealing with large quantities of queries and views, such as semantic query caching and data integration. Considerable rewriting computation could be saved if we manage to efficiently discover that, given a query Q and a view V, there does not exist a rewriting for Q using V. In contrast to O(|Q||V|) (O(|Q||V|2)) time complexity to compute an equivalent rewriting (contained rewriting) for XP {/,//,[] } , we devise linear algorithms running in O(|Q|) to filter queries for both equivalent rewriting and contained rewriting. Our filtering algorithms can be extended to support queries and views in XP {/,//,[],*} , where the equivalent (or contained) rewriting existence problem is still coNP-hard.

Publication type

Conference paper

Source

Lecture Notes in Computer Science: Proceedings of the 9th International Conference on Web Information Systems Engineering (WISE 2008) Auckland, New Zealand, 01-03 September 2008 / James Bailey, David Maier, Klaus-Dieter Schewe, Bernhard Thalheim, Xiaoyang Sean Wang (eds.), Vol. 5175 LNCS, pp. 307-320

Publication year

2008

FOR Code(s)

080404 Markup Languages;  080604 Database Management

Keyword(s)

Data integrations;  Dynamic programming;  Filtering techniques;  Industrial engineering;  Information science;  Information systems;  Information theory;  Integration;  Semantic queries;  Systems engineering;  Web information systems;  World Wide Web;  Xpath queries

Publisher

Springer

ISSN

0302-9743 (series ISSN)

ISBN

9783540854807, 3540854800

Publisher URL

http://dx.doi.org/10.1007/978-3-540-85481-4_24

Copyright

Copyright © 2008 Springer-Verlag Berlin Heidelberg.

Peer reviewed