Extended algebra and calculus for nested relational databases

ABSTRACT

Relaxing the assumption that relations are always in First-Normal-Form (1NF) necessitates a reexamination of the fundamentals of relational database theory. In this paper we take a first step towards unifying the various theories of ¬1NF databases. We start by determining an appropriate model to couch our formalisms in. We then define an extended relational calculus as the theoretical basis for our ¬1NF database query language. We define a minimal extended relational algebra and prove its equivalence to the ¬1NF relational calculus. We define a class of ¬1NF relations with certain “good” properties and extend our algebra operators to work within this domain. We prove certain desirable equivalences that hold only if we restrict our language to this domain.

REFERENCES

• 1: 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]
• 2: Hiroshi Arisawa , Kunihiko Moriya , Takao Miura, Operations and the Properties on Non-First-Normal-Form Relational Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.197-204, October 31-November 02, 1983
• 3: BANCILHON, F., FORTIN, D., GAMERMAN, S., LAUBIN, J. M., RICHARD, P., SCHOLL, M., TUSERA, D., AND VERROUST, A. VERSO: A relational backend database machine. In Advanced Database Machine Architecture, D. K. Hsiao, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1983, pp. 1-18.
• 4: 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]
• 5: CODD, E.F. Relational completeness of data base sublanguages. In Courant Computer Science Symposium 6 on Data Base Systems. R. Rustin, Ed., 1971, 65-98.
• 6: EPSTEIN, R. Techniques for processing of aggregates in relational database systems. Memorandum UCB/ERL M79/8, Electronics Research Laboratory, University of California, Berkeley, 1979.
• 7: P C Fischer , L V Saxton , S J Thomas , D Van Gucht, Interactions between dependencies and nested relational structures, Journal of Computer and System Sciences, v.31 n.3, p.343-354, December 1985 [doi>10.1016/0022-0000(85)90057-1]
• 8: FISCHER, P. C., AND THOMAS, S. Operators for non-first-normal-form relations. In Proceedings of the 7th International Computer Software Applications Conference (Chicago, Nov. 1983), pp. 464-475.
• 9: Patrick C. Fischer , Dirk Van Gucht, Weak multivalued dependencies, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588050]
• 10: P C Fischer , D Van Gucht, Structure of relations satisfying certain families of dependencies, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.131-142, December 1985, Saarbru:9Aicken, Germany
• 11: A. L. Furtado, Horizontal decomposition to improve a non-BCNF scheme, ACM SIGMOD Record, v.12 n.1, p.26-32, October 1981 [doi>10.1145/984497.984500]
• 12: Antonio L. Furtado , Larry Kerschberg, An algebra of quotient relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509406]
• 13: 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]
• 14: Barry E. Jacobs, On Database Logic, Journal of the ACM (JACM), v.29 n.2, p.310-332, April 1982 [doi>10.1145/322307.322310]
• 15: JAESCHKE, G. Nonrecursive algebra for relations with relation valued attributes. Tech. Rep. 84.12.001, Heidelberg Scientific Center, IBM Germany, 1984.
• 16: JAESCHKE, G. Recursive algebra for relations with relation valued attributes. Tech. Rep. 84.01.003, Heidelberg Scientific Center, IBM Germany, 1984.
• 17: 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]
• 18: KAMBAYASHI, Y., TANAKA, K., AND TAKEDA, K. Synthesis of unnormalized relations incorporating more meaning. Inf. Sci. 29 (1983), 201-247.
• 19: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• 20: KORTH, H. F., AND SILBERSCHATZ, A. A user-friendly operating system interface based on the relational data model. In International Symposium on New Directions in Computing (Trondheim Aug. 1985), pp. 302-310.
• 21: 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]
• 22: MAK{NOUCH{, A. A consideration on normal form of not-necessarily-normalized relation in the relational data model, in Proceedings of the Third International Conference on Very Large Data Bases (Tokyo, Oct. 1977), pp. 447-453.
• 23: ORMAN, L. Semantics of indexed data sets. Working Paper 81-05, Graduate School of Management, Cornell University, Ithaca, N.Y., Feb. 1981.
• 24: Z. Meral Özsoyoglu , Gultekin Özsoyoglu, An extension of relational algebra for summary tables, Proceedings of the 2nd international workshop on Proceedings of the Second International Workshop on Statistical Database Management, p.202-211, September 27-29, 1983, Los Altos, California
• 25: Z. Meral Ozsoyoglu , Li-Yan Yuan, A new normal form for nested relations, ACM Transactions on Database Systems (TODS), v.12 n.1, p.111-136, March 1987 [doi>10.1145/12047.13676]
• 26: Mark Aron Roth, Theory of non-first normal form relational databases (null values, nesting), 1986
• 27: Mark A. Roth , Henry F. Korth, The design of ¬ 1NF relational databases into nested normal form, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.143-159, May 27-29, 1987, San Francisco, California, United States
• 28: 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]
• 29: Mark A. Roth , Henry F. Korth , Avi Silberschatz, Null Values in ~1NF Relational Databases, University of Texas at Austin, Austin, TX, 1985
• 30: SCHEK, H. Towards a basic relational NF~ algebra processor. In Proceedings q{ the International Conference on Foundations of Data Organization (Kyoto, May 1985), pp. 173-182.
• 31: Hans-Jörg Schek , Peter Pistor, Data Structures for an Integrated Data Base Management and Information Retrieval System, Proceedings of the 8th International Conference on Very Large Data Bases, p.197-207, September 08-10, 1982
• 32: 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]
• 33: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 34: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

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

General Terms:
Languages, Theory