Minimum covers in the relational database model (Extended Abstract)

ABSTRACT

Numerous algorithms concerning relational databases use a cover for a set of functional dependencies as all or part of their input. Examples are Bernstein and Beeri's synthesis algorithm [BB] and the tableau modification algorithm of Aho, Beeri, and Ullman [ABU]. The performance of these algorithms may depend both on the number of functional dependencies in the cover and the total size of the cover. Starting with a smaller cover will make such algorithms run faster. After Bernstein [Be75], many researchers believe the problem of finding a minimum cover is NP-complete. We show that minimum covers can be found in polynomial time, using the notion of direct determination. The proof details the structure of minimum covers, refining the structure Bernstein and Beeri show for non-redundant covers [BB]. The kernel algorithm of Lewis, Sekino, and Ting [LST] is improved using these results.

REFERENCES

• 1: A.V. Aho, C. Beeri, and J.D. Ullman. The theory of joins in relational databases. Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, 1977 pages 107-113.
• 2: A.V. Aho, M.R. Garey, and J.D. Ullman. The transitive reduction of a directed graph. Siam Journal of Computing, Vol. 1, No. 2, June 1972, pages 131-137.
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: W.W. Armstrong. Dependency structures of data base relationships. Proceedings IFIP 1974, North Holland, pages 580-583.
• 5: Philip Alan Bernstein, Normalization and functional dependencies in the relational data base model., 1975
• 6: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 7: P.A. Bernstein and C. Beeri. An algorithmic approach to normalization of relational database schemes. Technical report CSRG-73, Computer Systems Research Group, University of Toronto, September 1976.
• 8: 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]
• 9: E.F. Codd. Further normalization of the data base relational model. In Data Base Systems, R. Rustin ed., Prentice-Hall, 1972, pages 33-64.
• 10: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: E.A. Lewis, L.C. Sekino, and P.D. Ting. A canonical representation for the relational schema and logical data independence. IEEE COMPSAC '77 Conference, November 1977.
• 12: C.L. Lucchesi and S.L. Osborne. Candidate keys for relations. Unpublished manuscript, University of Waterloo, 1976. Cited in Beeri and Bernstein {BB}.
• 13: J. Paredaens. About functional dependencies in a data base structure and their coverings. Report R 342, Philips Laboratories, Belgium, March 1977.
• 14: S. Sahni. Some related problems from network flows, game theory and integer programming. Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, 1972, pages 130-138.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Management, Measurement, Theory