Normal Forms and Conservative Extension Properties for Query Languages over Collection Types
✍ Scribed by Limsoon Wong
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 557 KB
- Volume
- 52
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 (ACM Trans on Database Systems 17, No. 1 (1992), 65 93), proved a similar result for the special case when i=o=1. Their result is complemented by Hull and Su (J. Comput. Systems Sci. 43 (1991), 219 261) 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 (in ``Proceedings of the 3rd International Conference on Database Theory,'' Lecture Notes in Computer Science, Vol. 470, Springer-Verlag, Berlin, 1990). Our result generalizes Paredaens and Van Gucht's to all i and o, providing a counterpart to the theorem of Grumbach and Vianu.