Equivalence of nested queries with mixed semantics

ABSTRACT

We consider the problem of deciding query equivalence for a conjunctive language in which queries output complex objects composed from a mixture of nested, unordered collection types. Using an encoding of nested objects as flat relations, we translate the problem to deciding the equivalence between encodings output by relational conjunctive queries. This encoding equivalence cleanly unifies and generalizes previous results for deciding equivalence of conjunctive queries evaluated under various processing semantics. As part of our characterization of encoding equivalence, we define a normal form for encoding queries and contend that this normal form offers new insight into the fundamental principles governing the behaviour of nested aggregation.

REFERENCES

• 1: Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
• 2: Vasilis Aggelis , Stavros S. Cosmadakis, Optimization of Nested SQL Queries by Tableau Equivalence, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.31-42, September 01-03, 1999
• 3: N. Bidoit, The Verso algebra or how to answer queries with fewer joins, Journal of Computer and System Sciences, v.35 n.3, p.321-364, Dec. 1987 [doi>10.1016/0022-0000(87)90019-5]
• 4: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 5: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 6: Surajit Chaudhuri , Moshe Y. Vardi, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
• 7: Sara Cohen, Equivalence of queries combining set and bag-set semantics, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142362]
• 8: Sara Cohen , Werner Nutt , Yehoshua Sagiv, Deciding equivalences among conjunctive aggregate queries, Journal of the ACM (JACM), v.54 n.2, p.5-es, April 2007 [doi>10.1145/1219092.1219093]
• 9: Sara Cohen , Yehoshua Sagiv , Werner Nutt, Equivalences among aggregate queries with negation, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.328-360, April 2005 [doi>10.1145/1055686.1055691]
• 10: Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
• 11: David DeHaan. Equivalence of nested queries with mixed semantics. Technical Report CS-2009-12, D.R. Cheriton School of Computer Science, University of Waterloo, 2009. Available at http://www.cs.uwaterloo.ca/research/tr/2009/.
• 12: David DeHaan , Per-Ake Larson , Jingren Zhou, Stacked indexed views in microsoft SQL server, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066179]
• 13: Xin Dong , Alon Y. Halevy , Igor Tatarinov, Containment of nested XML queries, Proceedings of the Thirtieth international conference on Very large data bases, p.132-143, August 31-September 03, 2004, Toronto, Canada
• 14: Hector Garcia-Molina , Jeffrey D. Ullman , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall Press, Upper Saddle River, NJ, 2008
• 15: Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303994]
• 16: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 17: Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
• 18: Yannis E. Ioannidis , Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Transactions on Database Systems (TODS), v.20 n.3, p.288-324, Sept. 1995 [doi>10.1145/211414.211419]
• 19: D.S. Johnson and A. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1):167--189, 1984.
• 20: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 21: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 22: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 23: Alon Y. Levy , Inderpal Singh Mumick, Reasoning with Aggregation Constraints, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.514-534, March 25-29, 1996
• 24: Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv, Query Optimization by Predicate Move-Around, Proceedings of the 20th International Conference on Very Large Data Bases, p.96-107, September 12-15, 1994
• 25: Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263665]
• 26: Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182609]
• 27: Hong-Cheu Liu , Jeffery X. Yu, Algebraic equivalences of nested relational operators, Information Systems, v.30 n.3, p.167-204, May 2005 [doi>10.1016/j.is.2003.12.001]
• 28: Sergey Melnik , Atul Adya , Philip A. Bernstein, Compiling mappings to bridge applications and databases, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-50, November 2008 [doi>10.1145/1412331.1412334]
• 29: Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.314-330, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298584]
• 30: G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
• 31: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 32: Kenneth A. Ross , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Foundations of aggregation constraints, Theoretical Computer Science, v.193 n.1-2, p.149-179, Feb. 28, 1998 [doi>10.1016/S0304-3975(97)00011-X]
• 33: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 34: Marc H Scholl, Theoretical foundation of algebraic optimization utilizing unnormalized relations, Proceedings on International conference on database theory, p.380-396, December 1986, Rome, Italy
• 35: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 36: Stan J. Thomas and Patrick C. Fischer. Nested relational structures. In Paris C. Kanellakis, editor, Advances in Computing Research: The Theory of Databases, pages 269--307. JAI Press, 1986.
• 37: F. W. Tompa , J. A. Blakeley, Maintaining materialized views without accessing base data, Information Systems, v.13 n.4, p.393-406, Oct. 1, 1988 [doi>10.1016/0306-4379(88)90005-1]
• 38: Jan Van den Bussche , Dirk Van Gucht , Stijn Vansummeren, Well-definedness and semantic type-checking for the nested relational calculus, Theoretical Computer Science, v.371 n.3, p.183-199, February 2007 [doi>10.1016/j.tcs.2006.11.007]
• 39: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
• 40: Weipeng P. Yan , Per-Åke Larson, Performing Group-By before Join, Proceedings of the Tenth International Conference on Data Engineering, p.89-100, February 14-18, 1994
• 41: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Theory

Keywords:
aggregation, bag-set semantics, conjunctive queries, normalized bags, query equivalence, set semantics