Optimal covers in the relational database model (Q303689)

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.