Cost-sensitive reordering of navigational primitives

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.
4. N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: optimal XML pattern matching. In ACM SIGMOD, pages 310--321, 2002.
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.
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.
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.
10. G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In VLDB Conf., pages 95--106, 2002.
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.
13. T. Grust. Accelerating XPath location steps. In SIGMOD Conference, pages 109--120, 2002.
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.
16. A. Kemper and D. Kossmann. Dual-buffering strategies in object bases. In VLDB Conf., pages 427--438, March 1994.
17. A. Kemper and G. Moerkotte. Advanced query processing in object bases using access support relations. In VLDB Conf., pages 290--301, 1990.
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
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.
20. D. Olteanu, H. Meuss, T. Furche, and F. Bry. XPath: Looking forward. In EDBT Workshop on XML Data Management, 2002.
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.
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.
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.
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.
25. Z. Xie and J. Han. Join index hierarchies for supporting efficient navigations in object-oriented databases. In VLDB Conf., pages 522--533, 1994.

• Information systems

  • Data management systems

    • Database management system engines

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory