Ronald Fagin
Abstract
A new normal form for relational databases, called domain-key normal form (DK/NF), is defined. Also, formal definitions of insertion anomaly and deletion anomaly are presented. It is shown that a schema is in DK/NF if and only if it has no insertion or deletion anomalies. Unlike previously defined normal forms, DK/NF is not defined in terms of traditional dependencies (functional, multivalued, or join). Instead, it is defined in terms of the more primitive concepts of domain and key, along with the general concept of a “constraint.” We also consider how the definitions of traditional normal forms might be modified by taking into consideration, for the first time, the combinatorial consequences of bounded domain sizes. It is shown that after this modification, these traditional normal forms are all implied by DK/NF. In particular, if all domains are infinite, then these traditional normal forms are all implied by DK/NF.
- 1 AHO, A. V., BEERI, C., AND ULLMAN, J.D. The theory of joins in relational databases. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 297-314. Google Scholar
Digital Library
- 2 AHO, A. V., SAGIV, Y., AND ULLMAN, J.D. Equivalences among relational expressions. SIAM J. Comput. 8, 2 (May 1979), 218-246.Google ScholarCross Ref
- 3 ARMSTRONG, W.W. Dependency structures of database relationships. In Proc. 1974 IFIP Congr. North-Holland, Amsterdam, 1974, pp. 580-583.Google Scholar
- 4 ARMSTRONG, W. W., AND DELOBEL, C. Decompositions and functional dependencies in relations. A CM Trans. Database Syst. 5, 4 (Dec. 1980), 404-430. Google ScholarDigital Library
- 5 ASTRAHAN, M. M., ET AL. System R: A relational approach to database management. A CM Trans. Database Syst. 1, 2 (June 1976), 97-137. Google ScholarDigital Library
- 6 BERNSTEIN, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 4 (Dec. I976), 277-298. Google ScholarDigital Library
- 7 CADIOU, J.-M. On semantic issues in the relational model of data. In Proc. Int. Syrup. Mathematical Foundations of Computer Science, Gdansk, Poland, Lecture Notes in Computer Sciences, Springer-Verlag, Heidelberg, Sept. 1975.Google Scholar
- 8 CHURCH, A. A note on the Entscheidungsproblem. J. Symbolic Logic 1, 40--41. Correction, 101- 102.Google ScholarCross Ref
- 9 CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June I970), 377-387. Google ScholarDigital Library
- 10 CODD, E.F. Further normalization of the database relational model. In Data Base Systems, Courant Computer Science Symposia 6. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.Google Scholar
- 11 CODD, E.F. Recent investigations in relational database systems. In Proc. 1974 IFIP Congr. North-Holland, Amsterdam, 1974, pp. 1017-1021.Google Scholar
- 12 CODD, E.F. Extending the database relational model to capture more meaning. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 397-434. Google ScholarDigital Library
- 13 DATE, C.J. An Introduction to Database Systems, 2nd ed. Addison-Wesley, Reading, Mass., 1977. Google ScholarDigital Library
- 14 DAYAL, U., AND BERNSTEIN, P. A. The fragmentation problem: Lossless decomposition of relations into files. Tech. Rep. CCA-78-13, Computer Corporation of America, Cambridge, Mass., Nov. 15, 1978.Google Scholar
- 15 DELOBEL, C. Contribution theorique a la conception des systemes d'information. Ph.D. Dissertation, Univ. Grenoble, Grenoble, France, 1973.Google Scholar
- 16 FA6XN, R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 262-278. Google ScholarDigital Library
- 17 FAGIN, R. Normal forms and relational database operators. In Proc. ACM SIGMOD, 1979, pp. I53-160. Google ScholarDigital Library
- 18 FA6IN, R. Horn clauses and database dependencies. In Proc. ACM SIGACT Syrup. Theory of Computation, 1980, pp. 123-I34. Google ScholarDigital Library
- 19 IBM CORPORATION.Generalized information System/Virtual Storage, User's Guide. SH20- 9036.Google Scholar
- 20 IBM CORPORATION. Information Management System~Virtual Storage Utilities Reference Manual. SH20-9029.Google Scholar
- 21 IBM CORPORATION. Query by Example, User's Guide. SH20-2078.Google Scholar
- 22 KANELLAKIS, P.C. On the computational complexity of cardinality constraints in relational databases. Inf. Process. Lett. 11, 2 (Oct. 1980), 98-101.Google ScholarCross Ref
- 23 MAIER, D., MENDELZON, A., AND SAGIV, Y. Testing implications of data dependencies. A CM Trans. Database Syst. 4, 4 {Dec. 1979), 455-469. Google ScholarDigital Library
- 24 NICOLAS, J.M. Mutual dependencies and some results on undecomposable relations. In Proc. 4th Conf. Very Large Data Bases, West Berlin, 1978, pp. 360-367.Google Scholar
- 25 RISSANEN, J. Independent components of relations. A CM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325. Google ScholarDigital Library
- 26 RISSASEN, J. Theory of relations for databases--A tutorial survey. In Proc. 7th Syrup. Mathematical Foundations of Computer Science, 1978, Lecture Notes in Computer Science, vol. 64, Springer-Verlag, pp. 537-551.Google Scholar
- 27 SAGIV, Y., DELOBEL, C., PARKER, D. S., AND FAGIN, 1:{. An equivalence between relational database dependencies and a fragment of propositional logic. J. ACM 28, 2 (April 1981), 435-453. Google ScholarDigital Library
- 28 SMITH, J.M. A normal form for abstract syntax. In Proc. 4th Conf. Very Large Data Bases, West Berlin, 1978, pp. 156-162.Google Scholar
- 29 SMITH, J. M., AND SMITH, D. C.P. Database abstractions: Aggregation. Commun. A CM 20, 6 (June I977), 405-413. Google ScholarDigital Library
- 30 SOFTWARE AG. ADABAS Introductory Manual. Software AG North America Inc., 11800 Sunrise Valley Drive, Reston, Va. 22091.Google Scholar
- 31 SPERNER, E. Ein satz fiber Untermengen einer endlichen Menge. Math. Zeitschrift 27 (1928), 544-548.Google ScholarCross Ref
- 32 STONEBRAKER, M., WONG, E., KREPS, P., AND HELD, G. The design and implementation of INGRES. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 189-222. Google ScholarDigital Library
- 33 TYMSHARE INC. MAGNUM Reference Manual, Nov, 1975,Google Scholar
- 34 ZANIOLO, C. Design of relational views over network schemas. In Proc. ACM SIGMOD, i979, pp. 179-190. Google ScholarDigital Library
Index Terms
- A normal form for relational databases that is based on domains and keys
Recommendations
Simple conditions for guaranteeing higher normal forms in relational databases
A key is simple if it consists of a single attribute. It is shown that if a relation schema is in third normal form and every key is simple, then it is in projection-join normal form (sometimes called fifth normal form), the ultimate normal form with ...
Multivalued dependencies and a new normal form for relational databases
A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is ...
Equivalence of Relational Database Schemes
We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. ...
Comments