Article

Cost-sensitive reordering of navigational primitives

Authors:

Carl-Christian Kanne,

Matthias Brantner,

Guido MoerkotteAuthors Info & Claims

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

Pages 742 - 753

https://doi.org/10.1145/1066157.1066242

Published: 14 June 2005 Publication History

Abstract

We present a method to evaluate path queries based on the novel concept of partial path instances. Our method (1) maximizes performance by means of sequential scans or asynchronous I/O, (2) does not require a special storage format, (3) relies on simple navigational primitives on trees, and (4) can be complemented by existing logical and physical optimizations such as duplicate elimination, duplicate prevention and path rewriting.We use a physical algebra which separates those navigation operations that require I/O from those that do not. All I/O operations necessary for the evaluation of a path are isolated in a single operator, which may employ efficient I/O scheduling strategies such as sequential scans or asynchronous I/O.Performance results for queries from the XMark benchmark show that reordering the navigation operations can increase performance up to a factor of four.

References

[1]

C. Beeri and Y. Tzaban. SAL: An algebra for semistructured data and xml. In WebDB (Informal Proceedings), pages 37--42, 1999.

[2]

S. Boag, D. Chamberlin, M. Fernandez, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery 1.0: An XML query language. Technical report, World Wide Web Consortium, 2002. W3C Working Draft 30 April 2002.

[3]

M. Brantner, S. Helmer, C.-C. Kanne, and G. Moerkotte. Full-fledged algebraic xpath processing in natix. In ICDE, 2005. to appear.

Digital Library

[4]

N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: optimal XML pattern matching. In ACM SIGMOD, pages 310--321, 2002.

Digital Library

[5]

P. Buneman, B. Choi, W. Fan, R. Hutchison, R. Mann, and S. Viglas. Vectorizing and querying large xml repositories. In ICDE, 2005. to appear.

Digital Library

[6]

J. Clark. XSL transformations (XSLT) version 1.0. Technical report, World Wide Web Consortium (W3C), November 1999.

[7]

J. Clark and S. DeRose. XML path language (XPath) version 1.0. Technical report, World Wide Web Consortium (W3C) Recommendation, 1999.

[8]

A. Deutsch, M. Fernandez, and D. Suciu. Storing semistructured data with STORED. In SIGMOD Conf., pages 431--442, Philadelphia, Pennsylvania, USA, June 1999.

Digital Library

[9]

T. Fiebig, S. Helmer, C.-C. Kanne, G. Moerkotte, J. Neumann, R. Schiele, and T. Westmann. Anatomy of a Native XML base management system. VLDB Journal. 11(4):292--314, 2003.

Digital Library

[10]

G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In VLDB Conf., pages 95--106, 2002.

Digital Library

[11]

G. Gottlob, C. Koch, and R. Pichler. Xpath query evaluation Improving time and space efficiency. In ICDE, pages 379--390, 2003.

[12]

G. Graefe. Query evaluation techniques for large databases ACM Computing Surveys, 25(2):73--170, 1993.

Digital Library

[13]

T. Grust. Accelerating XPath location steps. In SIGMOD Conference, pages 109--120, 2002.

Digital Library

[14]

J. Hidders and P. Michiels. Avoiding unnecessary ordering operations in xpath. In DBLP, pages 54--74, 2003.

[15]

T. Keller, G. Graefe, and D. Maier. Efficient assembly of complex objects. In J. Clifford and R. King, editors, SIGMOD Conf., pages 148--157. ACM Press, 1991.

Digital Library

[16]

A. Kemper and D. Kossmann. Dual-buffering strategies in object bases. In VLDB Conf., pages 427--438, March 1994.

Digital Library

[17]

A. Kemper and G. Moerkotte. Advanced query processing in object bases using access support relations. In VLDB Conf., pages 290--301, 1990.

Digital Library

[18]

C. Koch. Efficient processing of expressive node-selecting queries on xml data in secondary storage: A tree automata-based approach. In VLDB Conf., pages 249--260, 2003

Digital Library

[19]

J. E. B. Moss. Working with persistent objects: To swizzle or not to swizzle. IEEE Transactions on Software Engineering. 18(8):657--673, August 1992.

Digital Library

[20]

D. Olteanu, H. Meuss, T. Furche, and F. Bry. XPath: Looking forward. In EDBT Workshop on XML Data Management, 2002.

Digital Library

[21]

P. E. O'Neil, E. J. O'Neil, S. Pal, I. Cseri, G. Schaller, and N. Westbury. Ordpaths: Insert-friendly xml node labels. In ACM SIGMOD, pages 903--908, 2004.

Digital Library

[22]

A. Schmidt, F. Waas, M. Kersten, M. J. Carey, I. Manolescu, and R. Busse. Xmark: A benchmark for xml data management. In VLDB Conf., pages 974--985, 2002.

Digital Library

[23]

J. Shanmugasundaram, K. Tufte, C. Zhang, G. He, D. J. DeWitt, and J. F. Naughton. Relational databases for querying xml documents: Limitations and opportunities. In VLDB Conf, pages 302--314, 1999.

Digital Library

[24]

S. A.-K. Shurug, H. V. Jagadish, J. M. Patel, Y. Wu, N. Koudas, and D. Srivastava. Structural joins: A primitive for efficient xml query pattern matching. In ICDE, pages 141--152, 2003.

Digital Library

[25]

Z. Xie and J. Han. Join index hierarchies for supporting efficient navigations in object-oriented databases. In VLDB Conf., pages 522--533, 1994.

Digital Library

Cited By

Cong GFan WKementsietsidis ALi JLiu X(2012)Partial Evaluation for Distributed XPath Query Processing and BeyondACM Transactions on Database Systems10.1145/2389241.238925137:4(1-43)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2389241.2389251
Kling PÖzsu MDaudjee K(2011)Scaling XML query processingDistributed and Parallel Databases10.1007/s10619-011-7085-829:5-6(445-490)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10619-011-7085-8
Kling PÖzsu MDaudjee K(2010)Generating efficient execution plans for vertically partitioned XML databasesProceedings of the VLDB Endowment10.14778/1880172.18801734:1(1-11)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.14778/1880172.1880173
Show More Cited By

Cost-sensitive reordering of navigational primitives
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Navigational Path Expressions on XML Schemas
DEXA '08: Proceedings of the 19th international conference on Database and Expert Systems Applications

XML Schema is employed for describing the type and structure of information contained in valid XML documents. As for a document, a schema can be navigated and its components can be identified through a path language. In this paper we discuss the ...
Navigational control of several mobile robotic agents using Petri-potential-fuzzy hybrid controller

In this paper, a Petri-potential-fuzzy hybrid controller (PFHC) for obstacle avoidance and target seeking navigational behaviour of multiple mobile robots in unknown cluttered environments is presented. Based upon a reference motion, direction; ...
Computing Semantic Relatedness from Human Navigational Paths: A Case Study on Wikipedia

In this article, the authors present a novel approach for computing semantic relatedness and conduct a large-scale study of it on Wikipedia. Unlike existing semantic analysis methods that utilize Wikipedia's content or link structure, the authors ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

June 2005

990 pages

ISBN:1595930604

DOI:10.1145/1066157

Conference Chair:
Fatma Ozcan
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS05

Sponsor:

SIGMOD/PODS05: International Conference on Management of Data and Symposium on Principles Database and Systems

June 14 - 16, 2005

Maryland, Baltimore

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
456
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cong GFan WKementsietsidis ALi JLiu X(2012)Partial Evaluation for Distributed XPath Query Processing and BeyondACM Transactions on Database Systems10.1145/2389241.238925137:4(1-43)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2389241.2389251
Kling PÖzsu MDaudjee K(2011)Scaling XML query processingDistributed and Parallel Databases10.1007/s10619-011-7085-829:5-6(445-490)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10619-011-7085-8
Kling PÖzsu MDaudjee K(2010)Generating efficient execution plans for vertically partitioned XML databasesProceedings of the VLDB Endowment10.14778/1880172.18801734:1(1-11)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.14778/1880172.1880173
Bhadkamkar MFarfan FHristidis VRangaswami R(2009)Storing semi-structured data on disk drivesACM Transactions on Storage10.1145/1534912.15349155:2(1-35)Online publication date: 12-Jun-2009
https://dl.acm.org/doi/10.1145/1534912.1534915
Peng MYang LZhao WXiong N(2008)Wireless Service Attributes Classification and Matching Mechanism Based on Decision TreeProceedings of the 22nd International Conference on Advanced Information Networking and Applications - Workshops10.1109/WAINA.2008.43(12-17)Online publication date: 25-Mar-2008
https://dl.acm.org/doi/10.1109/WAINA.2008.43
Cong GFan WKementsietsidis AZhou LLing TOoi B(2007)Distributed query evaluation with performance guaranteesProceedings of the 2007 ACM SIGMOD international conference on Management of data10.1145/1247480.1247537(509-520)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1247480.1247537

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.

Media

Figures

Other

Tables

View Table of Contents