Mark A. Roth
Abraham Silberschatz
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.
- 1 ABITEBOUL, S., AND BIDOIT, N. Non first normal form relations to represent hierarchically organized data. In Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles o/ Database Systems (Waterloo, Apr. 1984), ACM, New York, 1984, pp. 191-200. Google Scholar
Digital Library
- 2 ARlSAWA, H., MORIYA, K., AND MIURA, T. Operations and the properties on non-first-normalform relational databases. In Proceedings of the Ninth International Conference on Very Large Data Bases (Florence, Oct. 1983), pp. 197-204. Google ScholarDigital Library
- 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.Google Scholar
- 4 CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 7 FXSCHER, P. C., SAXTON, L. V., THOMAS, S. J., AND VAN GUCHT, D. Interactions between dependencies and nested relational structures. J. Comput. Syst. Sci. 31, 3 {Dec. 1985), 343-354. Google ScholarDigital Library
- 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.Google Scholar
- 9 FISCHER, P. C., AND VAN GUCHT, D. Weak multivalued dependencies. In Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Waterloo, Apr. 1984), ACM, New York, 1984, pp. 266-274. Google ScholarDigital Library
- 10 FISCHER, P. C., AND VAN GUCHT, D. Structure of relations satisfying certain families of dependencies. In Proceedings of the 2nd Symposium on Theoretical Aspects of Computer Science ~Lecture Notes in Computer Science 182), Springer-Verlag, New York, 1985. Google ScholarDigital Library
- 11 FURTADO, A.L. Horizontal decomposition to improve a non-BCNF scheme. ACM SIGMOD Record 12, I (Oct. 1981), 26-32. Google ScholarDigital Library
- 12 FURTADO, A. L., AND KERSCHBERG, L. An algebra of quotient relations. In Proceedings of ACM- SIGMOD 1977 International Conference on Management of Data (Toronto, 1977), ACM, New York, 1977, pp. 1-8. Google ScholarDigital Library
- 13 HULL, R., AND YAP, C.K. The format model: A theory of database organization. J. ACM 31, 3 {July 1984), 518-537. Google ScholarDigital Library
- 14 JACOBS, B.E. On database logic. J. ACM 29, 2 (Apr. 1982), 310-332. Google ScholarDigital Library
- 15 JAESCHKE, G. Nonrecursive algebra for relations with relation valued attributes. Tech. Rep. 84.12.001, Heidelberg Scientific Center, IBM Germany, 1984.Google Scholar
- 16 JAESCHKE, G. Recursive algebra for relations with relation valued attributes. Tech. Rep. 84.01.003, Heidelberg Scientific Center, IBM Germany, 1984.Google Scholar
- 17 JAESCHKE, G., AND SCHEK, H. Remarks on the algebra of non first normal form relations. In Proceedings of the ACM SIGA CT-SIGMOD Symposium on Principles of Database Systems (Los Angeles, March 1982). Awrvz, r~ew York, 1982, pp. 124-138. Google ScholarDigital Library
- 18 KAMBAYASHI, Y., TANAKA, K., AND TAKEDA, K. Synthesis of unnormalized relations incorporating more meaning. Inf. Sci. 29 (1983), 201-247.Google ScholarCross Ref
- 19 KLUGA. Equivalence of relational algebra and relational calculaus query languages having aggregate functions. J. ACM 29, 3 (July 1982), 699-717. Google ScholarDigital Library
- 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.Google Scholar
- 21 KUPER, G. M., AND VARDZ, M.Y. A new approach to database logic. In Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Waterloo, Apr. 1984), ACM, New York, 1984, pp. 86-96. Google ScholarDigital Library
- 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.Google Scholar
- 23 ORMAN, L. Semantics of indexed data sets. Working Paper 81-05, Graduate School of Management, Cornell University, Ithaca, N.Y., Feb. 1981.Google Scholar
- 24 OZSO~O~LU, G., AND OZSOYO(~LU, Z.M. An extension of relational algebra for summary tables. In Proceedings of the 2nd International (LBL) Conference on Statistical Database Management (Los Angeles, Sept. 1983), pp. 202-211. Google ScholarDigital Library
- 25 OZSOYOGLU, Z. M., AND YUAN, L. A new normal form for nested relations. ACM Trans. Database Syst. 12, 1 (March 1987), 111-136. Google ScholarDigital Library
- 26 ROTH, M.A. Theory of non-first normal form relational databases. Ph.D. dissertation, The University of Texas at Austin, Austin, Texas, May 1986. Google ScholarDigital Library
- 27 ROTH, M. A., AND KORTH, H.F. The design of -~INF relational databases into nested normal form. In Proceedings o/ACM-SIGMOD 1987 Annual Conference (San Francisco, May 1987), ACM, New Yrok, 1987, pp. 143-159. Google ScholarDigital Library
- 28 ROTH, M. A., KORTH, H. F., AND BATORY, D.S. SQL/NF: A query language for ~INF relational databases. Inf. Syst. 12, 1 (1987), 99-114. Google ScholarDigital Library
- 29 ROTH, M.A., KORTH, H.F., AND SILBERSCHATZ, A. Null values in -1nf realtional databases Tech. Rep. TR-85-32, Department of Computer Science, University of Texas at Austin, Dec. 1985. Google ScholarDigital Library
- 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.Google Scholar
- 31 SCHEK, H., AND PISTOR, P. Data structures for an integrated data base management and information retrieval system. In Proceedings of the Eighth International Conference on Very Large Data Bases (Mexico City, Sept. 1982), 197-207. Google ScholarDigital Library
- 32 SCHEK, H., AND SCHOLL, M.H. The relational model with relation-valued attributes. Inf. Syst. 11, 2 (1986), 137-147. Google ScholarDigital Library
- 33 SMITH, J. M., AND SMITH, D. C.P. Database abstractions: Aggregation and generalization. ACM Trans. Database Syst. 2, 2 (June 1977), 105-133. Google ScholarDigital Library
- 34 ULLMAN, J.D. Principle of Database Systems, 2nd ed. Computer Science Press, Potomac, Md., Google ScholarDigital Library
Index Terms
- Extended algebra and calculus for nested relational databases
Recommendations
Extending relational algebra and relational calculus with set-valued attributes and aggregate functions
In commercial network database management systems, set-valued fields and aggregate functions are commonly supported. However, the relational database model, as defined by Codd, does not include set-valued attributes or aggregate functions. Recently, ...
On Roth, Korth, and Silberschatz's extended algebra and calculus for nested relational databases
We discuss the issues encountered in the extended algebra and calculus languages for nested relations defined by Roth, Korth, and Silberschatz.[4]. Their equivalence proof between algebra and calculus fails because of the keying problems and the use of ...
An Extended Algebra for Constraint Databases
Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, ...
Reviews
Don Goelman
Intended primarily for the research community, this interesting paper on theoretical principles of database systems will also interest those concerned with applications. A basic familiarity with the relational model is necessary, and familiarity with the relational algebra and calculus, normal forms, and functional dependencies as presented by Ullman [1] would also be helpful. The authors consider relations that are not in first normal form (1NF), that is, relations whose fields are not necessarily atomic. Although Codd foresaw the importance of studying these relations [2], their first formal treatment is generally attributed to Makinouchi [3]. This treatment was motivated by the relational database needs of certain applications, such as text processing and computer-aided design. This paper presents a model for ¬1NF relational structures. The authors define a particular class of these, the partitioned normal form (PNF) relations, to generalize 1NF. They also generalize both the relational algebra and the (safe) tuple relational calculus to apply to ¬1NF relations. Then the authors prove several important results. They show that the class of PNF relations is closed under the generalized query languages and also satisfies certain desirable algebraic identities, and they prove that the extended algebra and safe calculus are equivalent. The proofs are mathematically sound. The authors also provide several examples that help illustrate the ideas. Sample translations of natural language queries into the extended algebra and calculus (in the spirit of Ullman [1]) would have been useful. In this regard, note that two of the authors of this paper have presented an extended SQL for ¬1NF relations [4]. A discussion of the relationships among various types of normalization for ¬1NF relations—such as the authors' PNF, the nested normal form [5,6], and Makinouchi's normal form [3]—would also have been helpful. The bibliography is quite good, although as in the body of the paper some references used alphabetic notation (e.g., “[FT]”), while most used numbers (e.g., “[8]”).
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments