More Web Proxy on the site http://driver.im/

Article

A framework for using materialized XPath views in XML query processing

Authors:

Kevin S. Beyer,

Roberta J. Cochrane,

Hamid PiraheshAuthors Info & Claims

VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases - Volume 30

Pages 60 - 71

Published: 31 August 2004 Publication History

Abstract

XML languages, such as XQuery, XSLT and SQL/XML, employ XPath as the search and extraction language. XPath expressions often define complicated navigation, resulting in expensive query processing, especially when executed over large collections of documents. In this paper, we propose a framework for exploiting materialized XPath views to expedite processing of XML queries. We explore a class of materialized XPath views, which may contain XML fragments, typed data values, full paths, node references or any combination thereof. We develop an XPath matching algorithm to determine when such views can be used to answer a user query containing XPath expressions. We use the match information to identify the portion of an XPath expression in the user query which is not covered by the XPath view. Finally, we construct, possibly multiple, compensation expressions which need to be applied to the view to produce the query result. Experimental evaluation, using our prototype implementation, shows that the matching algorithm is very efficient and usually accounts for a small fraction of the total query compilation time.

References

[1]

{1} ISO/IEC 9075-14:2003. Information technology - database languages - sql - part 14: Xml-related specications (sql/xml).

[2]

{2} S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Proceedings of ICDE, pages 190-200, 1995.

Digital Library

[3]

{3} B. F. Cooper, N. Sample, M. J. Franklin, G. R. Hjaltason, and M. Shadmon. A fast index for semistructured data. In Proceedings of VLDB, pages 341-350, Roma, Italy, 2001.

Digital Library

[4]

{4} A. Deutsch and V. Tannen. Containment and integrity constraints for xpath. In Proceedings of KRDB, 2001.

[5]

{5} R. Goldman and J. Widom. Dataguides:enabling query formulation and optimization in semistructured databases. In Proceedings of VLDB, pages 436-445, 1997.

Digital Library

[6]

{6} J. Goldstein and P. Larson. Optimizing queries using materialized views: A practical, scalable solution. In Proceedings of SIGMOD, Santa Barbara, CA, 2001.

Digital Library

[7]

{7} R. Kaushik, P. Bohannon, J. F. Naughton, and H. F. Korth. Covering indexes for branching path queries. In Proceedings of SIGMOD, 2002.

Digital Library

[8]

{8} A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proceedings of PODS, pages 95-104, 1995.

Digital Library

[9]

{9} Quanzhong Li and Bongki Moon. Indexing and querying xml data for regular path expressions. In Proceedings of the 27th International Conference on Very Large Databases (VLDB), pages 361-370, Roma, Italy, September 2001.

Digital Library

[10]

{10} G. Miklau and D. Suciu. Containment and equivalence for an xpath fragment. In Proceedings of PODS, pages 65-76, 2002.

Digital Library

[11]

{11} S. Nestorov, J. D. Ullman, J. L. Wiener, and S. S. Chawathe. Representative objects: Concise representations of semistructured, hierarchial data. In Proceedings of ICDE, pages 79-90, 1997.

Digital Library

[12]

{12} F. Neven and T. Schwentick. Xpath containment in the presence of disjunction, dtds and variables. In Proceedings of ICDT, 2003.

Digital Library

[13]

{13} D. Olteanu, H. Meuss, T. Furche, and F. Bry. Xpath: Looking forward. In Workshop on XML-Based Data Management, 2002.

Digital Library

[14]

{14} F. Rizzolo and A. O. Mendelzon. Indexing xml data with toxi. In Proceedings of WebDB, pages 49-54, 2001.

[15]

{15} SQL/XML. See http://www.sqlx.org.

[16]

{16} XML Path Language (XPath) Version 2.0, November 2003. W3C Working Draft, See http://www.w3.org/TR/xpath20.

[17]

{17} XQuery 1.0: An XML Query Language, November 2003. W3C Working Draft, See http://www.w3.org/TR/xquery.

[18]

{18} M. Zaharioudakis, R. Cochrane, G. Lapis, H. Pirahesh, and M. Urata. Answering complex sql queries using automatic summary tables. In Proceedings of SIGMOD, pages 105-116, 2000.

Digital Library

Cited By

Wu XTheodoratos DKementsietsidis A(2015)Configuring bitmap materialized views for optimizing XML queriesWorld Wide Web10.5555/2780035.278004918:3(607-632)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.5555/2780035.2780049
Lakshmanan LThomo A(2014)View-Based Tree-Language Rewritings for XMLProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_13(270-289)Online publication date: 3-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-04939-7_13
Bonifati AGoodfellow MManolescu ISileo D(2013)Algebraic incremental maintenance of XML viewsACM Transactions on Database Systems10.1145/2508020.250802138:3(1-45)Online publication date: 5-Sep-2013
https://dl.acm.org/doi/10.1145/2508020.2508021
Show More Cited By

Index Terms

A framework for using materialized XPath views in XML query processing

Recommendations

Efficient xpath query processing in native xml databases
Rewriting XPath queries using materialized views
VLDB '05: Proceedings of the 31st international conference on Very large data bases

As a simple XML query language but with enough expressive power, XPath has become very popular. To expedite evaluation of XPath queries, we consider the problem of rewriting XPath queries using materialized XPath views. This problem is very important ...
Answering XML queries using materialized views revisited
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Answering queries using views is a well-established technique in databases. In this context, two outstanding problems can be formulated. The first one consists in deciding whether a query can be answered exclusively using one or multiple materialized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases - Volume 30

August 2004

1380 pages

ISBN:0120884690

Sponsors

VLDB Endowment: Very Large Database Endowment

Publisher

VLDB Endowment

Publication History

Published: 31 August 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu XTheodoratos DKementsietsidis A(2015)Configuring bitmap materialized views for optimizing XML queriesWorld Wide Web10.5555/2780035.278004918:3(607-632)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.5555/2780035.2780049
Lakshmanan LThomo A(2014)View-Based Tree-Language Rewritings for XMLProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_13(270-289)Online publication date: 3-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-04939-7_13
Bonifati AGoodfellow MManolescu ISileo D(2013)Algebraic incremental maintenance of XML viewsACM Transactions on Database Systems10.1145/2508020.250802138:3(1-45)Online publication date: 5-Sep-2013
https://dl.acm.org/doi/10.1145/2508020.2508021
Thimma MTsui TLuo BConti MVaidya JSchaad A(2013)HyXACProceedings of the 18th ACM symposium on Access control models and technologies10.1145/2462410.2462424(113-124)Online publication date: 12-Jun-2013
https://dl.acm.org/doi/10.1145/2462410.2462424
Cautis BKharlamov E(2012)Answering queries using views over probabilistic XMLProceedings of the VLDB Endowment10.14778/2350229.23502355:11(1148-1159)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.14778/2350229.2350235
Liu ZChen Y(2012)Exploiting and Maintaining Materialized Views for XML Keyword QueriesACM Transactions on Internet Technology10.1145/2390209.239021212:2(1-27)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2390209.2390212
Wang JXu Yu J(2012)Revisiting answering tree pattern queries using viewsACM Transactions on Database Systems10.1145/2338626.233863137:3(1-34)Online publication date: 6-Sep-2012
https://dl.acm.org/doi/10.1145/2338626.2338631
Katsifodimos AManolescu IVassalos VCandan KChen YSnodgrass RGravano LFuxman A(2012)Materialized view selection for XQuery workloadsProceedings of the 2012 ACM SIGMOD International Conference on Management of Data10.1145/2213836.2213900(565-576)Online publication date: 20-May-2012
https://dl.acm.org/doi/10.1145/2213836.2213900
Aravogliadis PVassalos V(2011)On equivalence and rewriting of XPath queries using views under DTD constraintsProceedings of the 22nd international conference on Database and expert systems applications - Volume Part II10.5555/2033546.2033548(1-16)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.5555/2033546.2033548
Zhou RLiu CLi JWang JLiu J(2011)Evaluating contained rewritings for XPath queries on materialized viewsProceedings of the 16th international conference on Database systems for advanced applications - Volume Part I10.5555/1997305.1997350(481-495)Online publication date: 22-Apr-2011
https://dl.acm.org/doi/10.5555/1997305.1997350
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten