Normal forms and conservative properties for query languages over collection types

ABSTRACT

Strong normalization results are obtained for a general language for collection types. An induced normal form for sets and bags is then used to show that the class of functions whose input has height (that is, the maximal depth of nestings of sets/bags/lists in the complex object) at most i and output has height at most o definable in a nested relational query language without powerset operator is independent of the height of intermediate expressions used. Our proof holds regardless of whether the language is used for querying sets, bags, or lists, even in the presence of variant types. Moreover, the normal forms are useful in a general approach to query optimization. Paredaens and Van Gucht proved a similar result for the special case when i = o = 1. Their result is complemented by Hull and Su who demonstrated the failure of independence when powerset operator is present and i = o = 1. The theorem of Hull and Su was generalized to all i and o by Grumbach and Vianu. Our result generalizes Paredaens and Van Gucht's to all i and o, providing a counterpart to the theorem of Grumbach and Vianu.

REFERENCES

• 1: Serge Abiteboul , Catriel Beeri , Marc Gyssens , Dirk Van Gucht, An introduction to the completeness of languages for complex objects and nested relations, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 2: S. Abiteboul and C. Beeri. On the Power of Languages for the Manipulation of Complex Objects. In Proceedings of international Workshop on Theory and Applications of Nested Relations and Complex Objects, Darmstadt, 1988.
• 3: Serge Abiteboul , Richard Hull, IFO: a formal semantic database model, ACM Transactions on Database Systems (TODS), v.12 n.4, p.525-565, Dec. 1987 [doi>10.1145/32204.32205]
• 4: Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.9-19, April 1992, Nafplion, Greece
• 5: Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
• 6: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• 7: Stéphane Grumbach , Victor Vianu, Playing games with objects, Proceedings of the third international conference on database theory on Database theory, p.25-38, November 1990, Paris, France
• 8: Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
• 9: Marc Gyssens , Dirk Van Gucht, A comparison between algebraic query languages for flat and nested databases, Theoretical Computer Science, v.87 n.2, p.263-286, Sept. 23, 1991 [doi>10.1016/0304-3975(91)90327-X]
• 10: P. Hudak and P. Wadler. Report on the Programming Language Haskell. Technical Report 90/?, Glasgow University, Glasgow G12 8QQ, Scotland, April 1990.
• 11: Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Journal of Computer and System Sciences, v.43 n.1, p.219-267, Aug. 1991 [doi>10.1016/0022-0000(91)90036-5]
• 12: Richard Hull , Chee K. Yap, The Format Model: A Theory of database Organization, Journal of the ACM (JACM), v.31 n.3, p.518-544, July 1984 [doi>10.1145/828.832]
• 13: G. Jaeschke , H. J. Schek, Remarks on the algebra of non first normal form relations, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588133]
• 14: Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
• 15: Jan Paredaens , Dirk Van Gucht, Possibilities and limitations of using flat operators in nested algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.29-38, March 1988, Austin, Texas, United States [doi>10.1145/308386.308402]
• 16: Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
• 17: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• 18: S. J. Thomas and P. C. Fischer. Nested Relational Structures. In P. C. Kanellakis, editor, Advances in Computing Research: The Theory of Databases, pages 269-307. JAI Press, 1986.
• 19: Phil Trinder, Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.55-68, April 1992, Nafplion, Greece
• 20: P. W. Trinder and P. L. Wadler. List Comprehensions and the Relational Calculus. In C. V. Hall, editor, Proceedings of 1988 Glasgow Workshop on Functional Programming, pages 187-202, Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, 1989.
• 21: D. Tumer. Recursion Equations as a Programming Language. In J. Darlington, P. Henderson, and David Turner, editors, Functional Programming and its Applications. Cambridge University Press, 1982.
• 22: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• 23: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• 24: Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
• 25: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
• 26: D. A. Watt and P. Trinder. Towards a Theory of Bulk Types. Fide Technical Report 91/26, Glasgow University, Glasgow G12 8QQ, Scotland, July 1991.
• 27: L. Wong. A Conservative Property of a Nested Relational Query Language. Technical Report MS-CIS-92-59/L&C 48, University of Pennsylvania, Philadelphia, Pensylvania, PA 19104, July 1992.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

General Terms:
Languages, Theory