W. W. Armstrong
Abstract
A general study is made of two basic integrity constraints on relations: functional and multivalued dependencies. The latter are studied via an equivalent concept: decompositions. A model is constructed for any possible combination of functional dependencies and decompositions. The model embodies some decompositions as unions of relations having different schemata of functional dependencies. This suggests a new, stronger integrity constraint, the degenerate decomposition. More generally, the theory demonstrates the importance of using the union operation in database design and of allowing different schemata on the operands of a union. Techniques based on the union lead to a method for solving the problem of membership of a decomposition in the closure of a given set of functional dependencies and decompositions. The concept of antiroot is introduced as a tool for describing families of decompositions, and its fundamental importance for database design is indicated.
- 1 ARMSTRONG, W.W. Dependency structures of database relationships, In Proc. IFIP 74, North- Holland Pub. Co., Amsterdam, 1974, pp. 580-583.Google Scholar
- 2 BEERI, C. Unpublished manuscript.Google Scholar
- 3 BEERI, C., FAGIN, R., AND HOWARD, J.H. A complete axiomatization for functional and multivalued dependencies in database relations. In Proc. ACM SIGMOD Int. Conf. Management of Data, Toronto, 1977, pp. 47-61. Google ScholarDigital Library
- 4 B~RNSTEIS, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 4 (Dec. 1976), 277-298. Google ScholarDigital Library
- 5 BERNSTEIN, P.A., AND BEERI, C. An algorithmic approach to normalization of relational database schemas. TR CSRG-73, Computer Systems Research Group, Univ. Toronto, Sept. 1976.Google Scholar
- 6 CObb, E.F. Recent investigations in relational database systems. In Proc. IFIP 74, North- Holland Pub. Co., Amsterdam, 1974, pp. 1017-1021.Google Scholar
- 7 CODD, E.F. Further normalization of the data base relational model. In Data Base Systems, Courant Institute Computer Science Symposia Series 6. Prentice-Hall, Englewood Cliffs, N.J., 1971, pp. 33-64.Google Scholar
- 8 DATE, C.J. An Introduction to Database Systems, 2nd ed. Addison-Wesley, Reading, Mass., 1977. Google ScholarDigital Library
- 9 DELOBEL, C. Normalization and hierarchical dependencies in the relational data model. ACM Trans. Database Syst. 3, 3 (Sept. I978), 201-222. Google ScholarDigital Library
- 10 DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. and Develop. 17, 5 (Sept. 1973), 374-386.Google ScholarDigital Library
- 11 DZLOB~.L, C., AND PARKER, D.S. Functional and multivalued dependencies in a relational database and the theory of Boolean switching functions. Rapport de Recherche no. 142, Laboratoire d'informatique et de mathdmatiques appliqu~es de Grenoble, Nov. 1978.Google Scholar
- 12 FAGIN, R. Multivalued dependencies and a new normal form for relational databases. A CM Trans. Database Syst. 2, 3 {Sept. 1977), 262-278. Google ScholarDigital Library
- 13 MZRRETT, T.H. Multidimensional paging for efficient data base querying. In Proc. Int. Conf. Data Base Management Systems (ICMOD 78), Milano, June 1978, pp. 277-290.Google Scholar
- 14 PAREDAENS, J. The interaction of integrity constraints in an information system. Rep. R-372, M.B.L.E. Research Labs., Brussels, 1978.Google Scholar
- 15 SAGIV, Y., AND FAGIN, R. An equivalence between relational database dependencies and a subclass of propositional logic. IBM Res. Rep. RJ 2500 {32750), March 1979. (References 11 and 15 have been combined into one paper: SAGIV, Y., DELOBEL, C., PARKER, D.S., AND FAGIN, R. An equivalence between relational database dependencies and a subclass of propositional logic. To appear in J. ACM.)Google Scholar
- 16 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
- 17 ZANIOLO, C., AND MELKANOFF, M.A. On the design of relational database schemas. To appear in A CM Trans. Database Syst. Google ScholarDigital Library
Index Terms
- Decompositions and functional dependencies in relations
Recommendations
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 ...
On the menbership problem for functional and multivalued dependencies in relational databases
The problem of whether a given dependency in a database relation can be derived from a given set of dependencies is investigated. We show that the problem can be decided in polynomial time when the given set consists of either multivalued dependencies ...
Appropriate inferences of data dependencies in relational databases
We study inference systems for the combined class of functional and full hierarchical dependencies in relational databases. Two notions of implication are considered: the original notion in which a dependency is implied by a given set of dependencies ...
Comments