Optimal covers in the relational database model
Functional dependencies (FD) belong to very important integrity constraints of the relational database model. Their theoretical problems were studied mainly in the 80s and they are still a challenge for some researches. The paper is focused on finding an optimal cover for a set of FDs, which is an NP-complete problem. The authors of the paper show that an optimal cover can be found, using the notion of mini-cover. The paper's content is divided into five sections. Section 1 presents some important concepts and background concerning FDs and optimal covers. Section 2 introduces the notions of mini-cover and minimum Boolean expression. The latter contributes to finding mini-covers using the transformation of the output of a Boolean expression minimization algorithm. Section 3 introduces the notion of minimum cover, defined by \textit{D. Maier} in [J. Assoc. Comput. Mach. 27, 664--674 (1980; Zbl 0466.68085)], including an algorithm, \(\mathrm{MINIMIZE}(G)\), to compute a minimum cover of a set \(G\) of FDs. Section 4 starts with introducing the notion of derivation sequence [\textit{D. Maier}, The theory of relational databases. London: Pitman Publishing Limited (1983; Zbl 0519.68082)], which allows one to prove that an optimal cover can be found using the mini-cover as the input of \(\mathrm{MINIMIZE}(G)\). The theoretical analysis of the algorithm's complexity is not conducted in this paper. Section 5 presents some conclusions. The paper is written at a sufficiently formal level, it is completed by many examples illustrating the used notions. It gives a meaningful contribution to extending the theory of FDs.
- scientific article; zbMATH DE number 4110179
- Computing the minimum cover of functional dependencies
- The synthesis approach for relational database design: An expanded perspective
- On the size of nonredundant FD-covers
- scientific article; zbMATH DE number 4057065
- scientific article; zbMATH DE number 1453046
- scientific article; zbMATH DE number 4215353
- scientific article; zbMATH DE number 1755716
- Publication:4733444
- A relational model of data for large shared data banks
- Candidate keys for relations
- Decomposition of a Data Base and the Theory of Boolean Switching Functions
- Functional Dependencies in a Relational Database and Propositional Logic
- Graph Algorithms for Functional Dependency Manipulation
- scientific article; zbMATH DE number 3823168 (Why is no real title available?)
- Minimal Representation of Directed Hypergraphs
- Minimum Covers in Relational Database Model
- On the relationship of minimum and optimum covers for a set of functional dependencies
- Computing the minimum cover of functional dependencies
- On the size of nonredundant FD-covers
- Computing premises of a minimal cover of functional dependencies is intractable
- scientific article; zbMATH DE number 4016958 (Why is no real title available?)
- scientific article; zbMATH DE number 3843178 (Why is no real title available?)
- scientific article; zbMATH DE number 4057065 (Why is no real title available?)
- scientific article; zbMATH DE number 4110179 (Why is no real title available?)
- Autonomous sets for the hypergraph of all canonical covers
- scientific article; zbMATH DE number 4116030 (Why is no real title available?)
- scientific article; zbMATH DE number 4119675 (Why is no real title available?)
- scientific article; zbMATH DE number 883940 (Why is no real title available?)
- Computing unique canonical covers for simple FDs via transitive reduction
This page was built for publication: Optimal covers in the relational database model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q303689)
