Three Cases for Query Decorrelation in XQuery | SpringerLink
Skip to main content
Springer Nature Link
Log in

Three Cases for Query Decorrelation in XQuery

  • Conference paper
Database and XML Technologies (XSym 2003)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2824))

Included in the following conference series:

Abstract

We present algebraic equivalences that allow to unnest nested algebraic expressions for order-preserving algebraic operators. We illustrate how these equivalences can be applied successfully to unnest nested queries given in the XQuery language. Measurements illustrate the performance gains possible our approach.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Astrahan, M.M., Chamberlin, D.D.: Implementation of a structured English query language. Communications of the ACM 18(10), 580–588 (1975)

    Article  MATH  Google Scholar 

  2. Beeri, C., Tzaban, Y.: SAL: An algebra for semistructured data and XML. In: ACM SIGMOD Workshop on the Web and Databases (WebDB) (1999)

    Google Scholar 

  3. Bhargava, G., Goel, P., Iyer, B.: Hypergraph based reorderings of outer join queries with complex predicates. In: Proc. of the ACM SIGMOD Conf. on Management of Data, pp. 304–315 (1995)

    Google Scholar 

  4. Chaudhuri, S., Shim, K.: Optimizing queries with aggregate views. In: Apers, P.M.G., Bouzeghoub, M., Gardarin, G. (eds.) EDBT 1996. LNCS, vol. 1057, pp. 167–182. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  5. Cluet, S., Moerkotte, G.: Nested queries in object bases. In: Proc. Int. Workshopon Database Programming Languages (1993)

    Google Scholar 

  6. Cluet, S., Moerkotte, G.: Classification and optimization of nested queries in object bases. Technical Report 95-6, RWTH Aachen (1995)

    Google Scholar 

  7. Dayal, U.: Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In: VLDB, pp. 197–208 (1987)

    Google Scholar 

  8. Fegaras, L., Elmasri, R.: Query engines for Web-accessible XML data. In: Apers, P.M.G., Atzeni, P., Ceri, S., Paraboschi, S., Ramamohanarao, K., Snodgrass, R.T. (eds.) Proceedings of the 27th International Conference on Very Large Data Bases: Roma, Italy, Los Altos, CA 94022, USA, pp. 251–260. Morgan Kaufmann Publishers, San Francisco (2001)

    Google Scholar 

  9. Fegaras, L., Levine, D., Bose, S., Chaluvadi, V.: Query processing of streamed XML data. In: Proceedings of the 2002 ACM CIKM International Conference on Information and Knowledge Management, McLean, VA, USA, pp. 126–133. ACM, New York (2002)

    Google Scholar 

  10. Fegaras, L., Maier, D.: Optimizing object queries using an effective calculus. ACM Transactions on Database Systems 25(4), 457–516 (2000)

    Article  MATH  Google Scholar 

  11. Fiebig, T., Helmer, S., Kanne, C.-C., Moerkotte, G., Neumann, J., Schiele, R., Westmann, T.: Anatomy of a Native XML Base Management System. VLDB Journal 11(4), 292–314 (2002)

    Article  MATH  Google Scholar 

  12. Fiebig, T., Moerkotte, G.: Algebraic XML construction and its optimization in Natix. World Wide Web Journal 4(3), 167–187 (2002)

    Article  Google Scholar 

  13. Galindo-Legaria, C., Rosenthal, A.: Outerjoin simplification and reordering for query optimization. ACM Trans. on Database Systems 22(1), 43–73 (1997)

    Article  Google Scholar 

  14. Ganski, R., Wong, H.: Optimization of nested SQL queries revisited. In: Proc. of the ACM SIGMOD Conf. on Management of Data, pp. 23–33 (1987)

    Google Scholar 

  15. Gottlob, G., Koch, C., Pichler, R.: Xpath query evaluation: Improving time and space efficiency. In: Proc. IEEE Conference on Data Engineering (2003) (to appear)

    Google Scholar 

  16. Hasan, W., Pirahesh, H.: Query rewrite optimization in starburst. Research Report RJ6367, IBM (1988)

    Google Scholar 

  17. Helmer, S., Kanne, C.-C., Moerkotte, G.: Optimized translation of xpath expressions into algebraic expressions parameterized by programs containing navigational primitives. In: Proc. Int. Conf. on Web Information Systems Engineering (WISE), pp. 215–224 (2002)

    Google Scholar 

  18. Kiessling, W.: SQL-like and Quel-like correlation queries with aggregates revisited. In: ERL/UCB Memo 84/75. University of Berkeley, Berkeley (1984)

    Google Scholar 

  19. Kim, W.: On optimizing an SQL-like nested query. ACM Trans. on Database Systems 7(3), 443–469 (1982)

    Article  MATH  Google Scholar 

  20. Klug, A.: Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM 29(3), 699–717 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  21. Leung, C., Pirahesh, H., Seshadri, P.: Query rewrite optimization rules in IBM DB2 universal database. Research Report RJ 10103 (91919), IBM Almaden Research Division (January 1998)

    Google Scholar 

  22. May, N., Helmer, S., Moerkotte, G.: Nested queries and quantifiers in an ordered context. Technical Report TR-03-002, Lehrstuhl für Praktische Informatik III, Universität Mannheim (2003)

    Google Scholar 

  23. Muralikrishna, M.: Optimization and dataflow algorithms for nested tree queries. In: Proc. Int. Conf. on Very Large Data Bases (VLDB) (1989)

    Google Scholar 

  24. Muralikrishna, M.: Improved unnesting algorithms for join aggregate SQL queries. In: Proc. Int. Conf. on Very Large Data Bases (VLDB), pp. 91–102 (1992)

    Google Scholar 

  25. Paparizos, S., Al-Khalifa, S., Jagadish, H.V., Lakshmanan, L.V.S., Nierman, A., Srivastava, D., Wu, Y.: Grouping in XML. In: Chaudhri, A.B., Unland, R., Djeraba, C., Lindner, W. (eds.) EDBT 2002. LNCS, vol. 2490, pp. 128–147. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  26. Pirahesh, H., Hellerstein, J., Hasan, W.: Extensible/rule-based query rewrite optimization in Starburst. In: Proc. of the ACM SIGMOD Conf. on Management of Data, pp. 39–48 (1992)

    Google Scholar 

  27. Rosenthal, A., Galindo-Legaria, C.: Query graphs, implementing trees, and freely-reorderable outerjoins. In: Proc. of the ACM SIGMOD Conf. on Management of Data, pp. 291–299 (1990)

    Google Scholar 

  28. Seshadri, P., Pirahesh, H., Leung, T.: Complex query decorrelation. In: Proc. IEEE Conference on Data Engineering, pp. 450–458 (1996)

    Google Scholar 

  29. Steenhagen, H., Apers, P., Blanken, H.: Optimization of nested queries in a complex object model. In: Jarke, M., Bubenko, J., Jeffery, K. (eds.) EDBT 1994. LNCS, vol. 779, pp. 337–350. Springer, Heidelberg (1994)

    Google Scholar 

  30. Steenhagen, H., Apers, P., Blanken, H., de By, R.: From nested-loop to join queries in oodb. In: Proc. Int. Conf. on Very Large Data Bases (VLDB), pp. 618–629 (1994)

    Google Scholar 

  31. Steenhagen, H., de By, R., Blanken, H.: Translating OSQL queries into efficient set expressions. In: Apers, P.M.G., Bouzeghoub, M., Gardarin, G. (eds.) EDBT 1996. LNCS, vol. 1057, pp. 183–197. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Mannheim, D7, 27, Mannheim, Germany

    Norman May, Sven Helmer & Guido Moerkotte

Authors
  1. Norman May
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sven Helmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guido Moerkotte
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LIRMM - UMR 5506 CNRS / Université Montpellier 2, 161 Rue Ada, F-34392, Montpellier Cedex 5

    Zohra Bellahsène

  2. IBM developerWorks 6 New Square, Bedfont Lakes, TW14 8HA, Feltham, Middlesex, UK

    Akmal B. Chaudhri

  3. Dept. of Computer Science, University of Leipzig,  

    Erhard Rahm

  4. Microsoft Corporation, One Microsoft Way, 98052, Redmond, WA, USA

    Michael Rys

  5. Universität Duisburg-Essen,  

    Rainer Unland

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

May, N., Helmer, S., Moerkotte, G. (2003). Three Cases for Query Decorrelation in XQuery. In: Bellahsène, Z., Chaudhri, A.B., Rahm, E., Rys, M., Unland, R. (eds) Database and XML Technologies. XSym 2003. Lecture Notes in Computer Science, vol 2824. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39429-7_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-39429-7_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20055-0

  • Online ISBN: 978-3-540-39429-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation