Latha S. Colby
Abstract
The nested relational model provides a better way to represent complex objects than the (flat) relational model, by allowing relations to have relation-valued attributes. A recursive algebra for nested relations that allows tuples at all levels of nesting in a nested relation to be accessed and modified without any special navigational operators and without having to flatten the nested relation has been developed. In this algebra, the operators of the nested relational algebra are extended with recursive definitions so that they can be applied not only to relations but also to subrelations of a relation. In this paper, we show that queries are more efficient and succinct when expressed in the recursive algebra than in languages that require restructuring in order to access subrelations of relations. We also show that most of the query optimization techniques that have been developed for the relational algebra can be easily extended for the recursive algebra and that queries are more easily optimizable when expressed in the recursive algebra than when they are expressed in languages like the non-recursive algebra.
- 1 Abiteboul, S., and Bidoit, N., "Non First Normal Form Relations to Represent Hierarchically Organized Data," Proc. 3rd PODS, 1984, pp. 191-200. Google Scholar
Digital Library
- 2 Bancilhon, F., Richard, P., and Scholl, M., "On Line Processing of Compacted Relations," Proc. 8th VLDB, Mexico City, 1982, pp. 21-37. Google ScholarDigital Library
- 3 Bidoit, N., "The Verso Algebra or How to Answer Queries with Fewer Joins," Journal of Computer and System Sciences, 1987, pp. 321-364 Google ScholarDigital Library
- 4 Codd, E.F., "A Relational Model for Large Shared Data Banks, " Communications ACM Vol. 6, No. 13, June 1970, pp. 377-387. Google ScholarDigital Library
- 5 Colby, L.S., "A Recursive Algebra for Nested Relations," Technical Report, No. 259, August 1988, University of IndianaGoogle Scholar
- 6 Dadam, P., Kuespert, F., Andersen, F., Blanken, H., Erbe, R., Guenauer, J., Lure, V., Pistor, P., and Walch,G., "A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies," Proc. Annual SIGMOD Conf., Austin, 1986, pp. 356-366. Google ScholarDigital Library
- 7 Deppisch, U., Paul, H.B., and Schek, H.J., "A Storage System for Complex Objects," Proc. Int. Workshop on Object- Oriented Database Systems, Pacific Grove, 1986, pp. 183-195. Google ScholarDigital Library
- 8 Deshpande, V., and Larson, P.A., "An Algebra for Nested Relations," Tech. Report, CS-87-65, 1987, University of Waterloo.Google Scholar
- 9 Deshpande, A., and Van Gucht, D., "A Storage Structure for Unnormalized Relations," Proc. (71 Conf. on Database Systems for Office Automation, Engineering and Scientific Applications, Darmstadt, April 1987, pp. 481-486.Google Scholar
- 10 Gyssens, M. and Van Gucht, D., "The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra," Proc. Annual SIGMOD Conf., Chicago, IL, June 1988 Google ScholarDigital Library
- 11 Jaeshke, G., and Schek, H.J., "Remarks on the Algebra on Non-First Normal Form Relations," Proc. 1st PODS, Los Angeles, 1982, pp. 124-138. Google ScholarDigital Library
- 12 Linnemann, V., "Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach," Proc. 3rd IEEE Int. Conf. on Data Engineering, Los Angeles, 1987. Google ScholarDigital Library
- 13 Makinouchi, A., "A Consideration of Normal Form of Not- Necessarily-Normalized Relations in the Relational Data Model," Proc. 3rd. VLDB, Tokyo 1977, pp. 447-453.Google Scholar
- 14 Ozsoyoglu, G., Ozsoyoglu, Z.M., and Matos, V., "Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions," A CM Transactions on Database Systems, Vol. 12, No. 4, December 1987, pp. 566-592. Google ScholarDigital Library
- 15 Paul, H.B., Schek, H.J., Scholl, M.H., Weikum, G., and Deppisch, U., "Architecture and Implementation of the Darmstadt Database Kernel System," Proc., Annual SIGMOD Conf., San Francisco, 1987, pp. 196-207. Google ScholarDigital Library
- 16 Pistor, P., and Andersen, F., "Designing a generalized NF2 model with an SQL-Type Language Interface," Proc. 12th VLDB, Kyoto, Japan, 1986, pp. 278-288. Google ScholarDigital Library
- 17 Pistor, P., and Traunmueller, R., "A Database Language for Sets, Lists and Tables," Information Sys. tems, Vol 11, No. 4, 1986, pp. 323-336. Google ScholarDigital Library
- 18 Roth, M.A., Korth, H.F., and Batory, D.S., "SQL/- NF: A Query Language for ~INF Relational Databases," Information Systems, Vol 12, No. 1, 1987, pp. 99-114. Google ScholarDigital Library
- 19 Roth, M.A., Korth, H.F., and Silberschatz, A., "Theory of Non-First-Normal-Form Relational Databases," Tech. Report TR-84-36 (Revised January 1986), University of Texas at Austin, 1984.Google Scholar
- 20 Roth, M.A., Korth, H.F., and Silberschatz, A., "Extended Algebra and Calculus for -~INF Relational Databases," Tech. Report TR.85.19, University of Texas at Austin, 1985. Google ScholarDigital Library
- 21 Roth, M.A., Korth, H.F., and Silberschatz, A., "Null Values in --1NF Relational Databases," Tech. Report TR-85-32, University of Texas at Austin, December, 1985. Google ScholarDigital Library
- 22 Schek, H.J., and Scholl, M.H., "The Relational Model with Relation-Valued Attributes," Information Systems, Vol. 11, No. 2, 1986, pp. 137-147. Google ScholarDigital Library
- 23 Scholl, M.H., "Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations," Proceedings of the International Conference on Database Theory, September, 1986, Rome, Italy, pp. 380-396 Google ScholarDigital Library
- 24 Scholl, M.tt., Paul, tt.B., and Schek, H.J., "Supporting Flat Relations by a Nested Relational Kernel," Proc. 13th VLDB, London, 1987. Google ScholarDigital Library
- 25 Thomas, S.J., and Fischer, P.C., "Nested Relational Structures," Advances in Computing Research III, The Theory of Databases, P.C. Kanellakis, ed., JAIpress, 1986, pp. 269-307.Google Scholar
- 26 Van Gueht, D., "Theory of Unnormalized Relational Structures," Ph.D. Dissertation, Vanderbilt University, 1985. Google ScholarDigital Library
- 27 Van Gucht, D., "On the Expressive Power of the Extended Relational Algebra for the Unnormalized Relational Model," Proc. 6th PODS, San Diego, CA, March 1987, pp. 302-312. Google ScholarDigital Library
- 28 Van Gucht, D., and Fischer, P.C., "Multilevel Nested Relational Structures," Journal of Computer and System Sciences, Vol. 36, No. 1, February 1988, pp. 77-105 Google ScholarDigital Library
Index Terms
- A recursive algebra and query optimization for nested relations
Recommendations
A recursive algebra and query optimization for nested relations
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of dataThe nested relational model provides a better way to represent complex objects than the (flat) relational model, by allowing relations to have relation-valued attributes. A recursive algebra for nested relations that allows tuples at all levels of ...
SQL query optimization through nested relational algebra
Most research work on optimization of nested queries focuses on aggregate subqueries. In this article, we show that existing approaches are not adequate for nonaggregate subqueries, especially for those having multiple subqueries and certain comparison ...
Converting nested algebra expressions into flat algebra expressions
Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive ...
Comments