Minimum Covers in Relational Database Model
- 1 October 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 27 (4) , 664-674
- https://doi.org/10.1145/322217.322223
Abstract
Numerous algonthms concernmg relahonal databases use a cover for a set of funcUonal dependencies as all or part of their input Examples are Been and Bernsteln's synthesis algorithm and the tableau modtfication algorithm of Aho et al The performance of these algorahms may depend on both the number of funcuonal dependencies m the cover and the total size of the cover Starting with a smaller cover wdl make such algorithms run faster After Bernstem, many researchers beheve that the problem of finding a minimum cover is NP- complete It as shown here that minimum covers can be found m polynomial time, using the nouon of dwect determmatwn The proofdetads the structure ofmmtmum covers, refining the structure Bernstem and Been show for nonredundant covers The kernel algorithm of Lewis, Sekino, and TIng is improved using these resultsKeywords
This publication has 4 references indexed in Scilit:
- The theory of joins in relational databasesACM Transactions on Database Systems, 1979
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979
- Synthesizing third normal form relations from functional dependenciesACM Transactions on Database Systems, 1976
- A relational model of data for large shared data banksCommunications of the ACM, 1970