A uniform approach toward handling atomic and structured information in the nested relational database model

ABSTRACT

The algebras and query languages for nested relations defined thus far do not allow us to “flatten” a relation scheme by disregarding the internal representation of data. In real life, however, the degree in which the structure of certain information, such as addresses, phone numbers, etc., is taken into account depends on the particular application and may even vary in time. Therefore, an algebra is proposed that does allow us to simplify relations by disregarding the internal structure of a certain class of information. This algebra is based on a careful manipulation of attribute names. Furthermore, the key operator in this algebra, called “copying,” allows us to deal with various other common queries in a very uniform manner, provided these queries are interpreted as operations on classes of semantically equivalent relations rather than individual relations. Finally, it is shown that the proposed algebra is complete in the sense of Bancilhon and Paredaens.

REFERENCES

• 1: ABITEBOUL, S., AND BEERI, C. On the power of languages for the manipulation of complex objects. INRIA Tech. Rep. 846. INRIA, Paris, France, May 1988.
• 2: Serge Abiteboul , Nicole Bidoit, Non first normal form relations to represent hierarchically organized data, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588038]
• 3: BANCILHON, F. On the completeness of query languages for relational data bases. In Proceedings of the 7th Symposium on Mathematical Foundations of Composition Science (Zakopane, Poland). In Lecture Notes in Computer Science, vol. 64, Springer-Verlag, Berlin, 1978, pp. 112-123.
• 4: CHANDRA, A. K., AND HAREL, D. Computable queries for relational databases. J. Comput. Syst. Sci. 21, 2 (Oct. 1980), 156-178.
• 5: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 6: CODt~, E. F. Further normalizations of the relational data base model. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
• 7: CODD, E.F. Relational completeness of database sublanguages. In Data Base Systems, Ft. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.
• 8: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 9: DESHPANDE, V., AND LARSON, P. An algebra for nested relational databases. Tech. Rep. CS-87- 65. Univ. of Waterloo, Waterloo, Ont., Canada, Dec. 1987.
• 10: GYSSENS, M., AND VAN GUCHT, D. The powerset operator as an algebraic tool for understanding least fixpoint semantics in the context of nested relations. Tech. Rep. 233. Computer Science Department, Indiana Univ., Bloomington, Ind., Oct. 1987.
• 11: Marc Gyssens , Dirk van Gucht, The powerset algebra as a result of adding programming constructs to the nested relational algebra, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.225-232, June 01-03, 1988, Chicago, Illinois, United States
• 12: 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]
• 13: Henry F. Korth , Abraham Silberschatz, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986
• 14: Gabriel M. Kuper , Moshe Y. Vardi, A new approach to database logic, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588026]
• 15: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 16: MAKINOUCHI, A. A consideration of normal form of not-necessarily-normalized relations in the relational data model. In Proceedings of the 3rd VLDB Conference (Tokyo), 1977, pp. 445'-453.
• 17: 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]
• 18: PAREDAENS, J. On the expressive power of the relational algebra. Inf. Proc. Lett. 7, 2 (Feb. 1978), 107-111.
• 19: Jan Paredaens , Paul De Bra , Marc Gyssens , Dirk Van Gucht, The structure of the relational database model, Springer-Verlag New York, Inc., New York, NY, 1989
• 20: 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]
• 21: Peter Pistor , F. Andersen, Designing A Generalized NF2 Model with an SQL-Type Language Interface, Proceedings of the 12th International Conference on Very Large Data Bases, p.278-285, August 25-28, 1986
• 22: Mark A. Roth , Henry F. Korth , Don S. Batory, SQL/NF: a query language for ¬ 1NF relational databases, Information Systems, v.12 n.1, p.99-114, Jan. 1987 [doi>10.1016/0306-4379(87)90021-4]
• 23: Mark A. Roth , Henry F. Korth , Avi Silberschatz, Null Values in ~1NF Relational Databases, University of Texas at Austin, Austin, TX, 1985
• 24: Mark A. Roth , Herry F. Korth , Abraham Silberschatz, Extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.389-417, Dec. 1988 [doi>10.1145/49346.49347]
• 25: H J Schek , M H Scholl, The relational model with relation-valued attributes, Information Systems, v.11 n.2, p.137-147, 1986 [doi>10.1016/0306-4379(86)90003-7]
• 26: THOMAS, S. J., AND FISCHER, P.C. Nested relational structures. In The Theory of Databases, P. C. Kanellakis, Ed. JAI Press, Greenwich, Conn., 1986, pp. 269-307.
• 27: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 28: D. Van Gucht, On the expressive power of the extended relational algebra for the unnormalized relational model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.302-312, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28692]
• 29: ZANIOLO, C. Database relations with null values. J. Comput. Syst. Sci. 28, 1 (Feb. 1984), 142-166.

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: Data models

General Terms:
Design, Languages, Performance, Theory