Summary
Most algorithms in relational database theory use a set of functional dependencies as their input. The efficiency of the algorithms depends on the size of the set. The notions of a minimum set (with as few dependencies as possible) and an optimum set (which is as short as possible) were introduced by Maier. He showed that while a minimum cover for a given set of dependencies can be found in polynomial time, obtaining an optimum cover is an NP-complete problem. Here the relationship of these covers is explored further. It is shown that the length of a minimum set (i) cannot be bounded by a linear function on the length of an optimum cover, and (ii) is bounded by the square of the length of an optimum cover. It is also shown that the NP-completeness of the optimization problem is somewhat surprisingly caused solely by the difficulty of optimizing a single class of dependencies having equivalent left sides, not by the globality of the optimality condition. This result has some practical significance, since the equivalence classes appearing in practice are short. The problem of optimizing an equivalence class is studied and left and right sides of a dependency are shown to behave differently. A new representation for equivalence classes based on this observation is suggested. The optimization of single dependencies is shown to be NP-complete, and a method to produce good approximations is given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho, A.V., Beeri, C., Ullman, J.D.: The theory of joins in relational databases. ACM Trans. Database Syst. 4, 3, 297–314 (1979)
Beeri, C., Bernstein, P.A.: Computational problems related to the design of normal form relational databases. ACM Trans. Database Syst. 4, 1, 30–59 (1979)
Bernstein, P.A.: Normalization and functional dependencies in the relational data base model. Tech. Rep. CSRG-60, Computer Systems Research Group, Univ. of Toronto 1975
Bernstein, P.A.: Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 4, 277–298 (1976)
Biskup, J., Dayal, U., Bernstein, P.A.: Synthesizing independent database schemas. Proc. ACM-SIGMOD Int. Conf. on Management of Data, pp. 143–151, 1979
Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13, 6, 377–387 (1970)
Codd, E.F.: Further normalization of the data base relational model. In: Data Base Systems. Rustin, R. (ed.). Englewood Cliffs: Prentice-Hall, pp. 33–64, 1972
da Silva, A.: The decomposition of relations based on relational dependencies. Ph.D. Dissertation, Univ. of California, Los Angeles 1980
Jou, J.H.: Theory of functional relation schemes in relational databases. Ph.D. Dissertation, Dept. of Computer Science, The Pennsylvania State University 1980
Kambayashi, Y., Tanaka, K., Yajima, S.: Problems of relational database design. In: Data Base Design Techniques I: Requirements and Logical Structures. Yao, S.B., Narathe, S.B., Weldon, J.L., Kunii, T.L. (eds.). Berlin, Heidelberg, New York: Springer, pp. 172–218, 1982
Ling, T.-W., Tompa, F.W., Kameda, T.: An improved third normal form for relational databases. ACM Trans. Database Syst. 6, 2, 329–346 (1981)
Lucchesi, C.L., Osborne, S.L.: Candidate keys for relations. J. Comput. Syst. Sci. 17, 2, 270–279 (1978)
Maier, D.: Minimum covers in the relational database model. J. ACM 27, 4, 664–674 (1980)
Tsou, D.-M., Fischer, P.C.: Decomposition of a relation scheme into Boyce-Codd normal form. Proc. ACM Annual Conf., pp.411–417, 1980
Ullman, J.D.: Principles of Database Systems. Potomac, MD: Computer Science Press 1980
Author information
Authors and Affiliations
Additional information
This work was supported by the Academy of Finland
Rights and permissions
About this article
Cite this article
Mannila, H., Räihä, KJ. On the relationship of minimum and optimum covers for a set of functional dependencies. Acta Informatica 20, 143–158 (1983). https://doi.org/10.1007/BF00289412
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00289412