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

Download PDF (Accepted manuscript) (Adobe Acrobat PDF, -1 bytes)

Title

Evaluating contained rewritings for XPath queries on materialized views

Author(s)

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

Abstract

In this paper, we study the problem how to efficiently evaluate a set of contained rewritings on materialized views. Previous works focused on how to find a set of contained rewritings given a view and a query, but did not address how to evaluate the rewritings on materialized views. To evaluate a potential exponential number of contained rewritings, we design two algorithms, a basic algorithm and an optimized algorithm. Both algorithms are built on the observation that the exponential number of contained rewritings are actually composed by a linear number of component patterns. In the optimized algorithm, we further design four important pruning rules and several heuristic rules that can effectively reduce the number of component patterns we need to evaluate. The experiments demonstrate the efficiency of our algorithms.

Publication type

Conference paper

Research centre

Swinburne University of Technology

Source

Lecture notes in computer science: Proceedings of the 16th International Conference on Database Systems for Advanced Applications (DASFAA 2011), Hong Kong, China, 22-25 April 2011 / Jeffrey Xu Yu, Myoung Ho Kim and Rainer Unland (eds.), Vol. 6587, pp. 481-495

Publication year

2011

FOR Code(s)

0804 Data Format

Keyword(s)

Algorithms;  Materialised views;  Rewritings

Publisher

Springer

ISSN

0302-9743 (series ISSN)

ISBN

9783642201486, 3642201482

Publisher URL

http://dx.doi.org/10.1007/978-3-642-20149-3_35

Copyright

Copyright © Springer-Verlag Berlin Heidelberg 2011. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher. The definitive version of the publication is available at www.springer.com.

Research Projects

Exploiting views in extensible markup language (XML) data processing, Australian Research Council grant number DP1093404
XML views of relational databases: semantics and update problems, Australian Research Council grant number DP878405

Full text

Peer reviewed