×

Optimal covers in the relational database model. (English) Zbl 1347.68112

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 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 [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.

MSC:

68P15 Database theory
03G05 Logical aspects of Boolean algebras
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ausiello, G., D’Atri, A., Sacc, D.: Minimal representation of directed hypergraphs. SIAM J. Comput. 15, 418-431 (1986) · Zbl 0602.68056 · doi:10.1137/0215029
[2] Ausiello, G., D’Atri, A., Sacca, D.: Graph algorithm for functional dependency manipulation. J. ACM 30, 752-766 (1983) · Zbl 0624.68089 · doi:10.1145/2157.322404
[3] Bernstein, P.A.: Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 277-298 (1976) · doi:10.1145/320493.320489
[4] Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13, 377-387 (1970) · Zbl 0207.18003 · doi:10.1145/362384.362685
[5] Cotelea, V.: Problem decomposition method to compute an optimal cover for a set of functional dependencies. Database Syst. J. 2, 17-30 (2011)
[6] Delobel, C., Casey, R.G.: Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Dev. 17, 374-386 (1973) · Zbl 0259.68016 · doi:10.1147/rd.175.0374
[7] Fagin, R.: Functional Dependencies in a Relational Database and Propositional Logic. IBM J. Res. Dev. 21, 533-544 (1977) · Zbl 0366.68022 · doi:10.1147/rd.216.0534
[8] Jain, T.K., Kushwaha, D.S., Misra, A.K.: Optimization of the Quine-McCluskey method for the minimization of the Boolean expressions. In: Fourth International Conference on Autonomic and Autonomous Systems, pp. 165-168. (2008) · Zbl 0259.68016
[9] Lucchesi, C.L., Osborn, S.L.: Candidate keys for relations. J. Comput. Syst. Sci. 17, 270-279 (1978) · Zbl 0395.68025 · doi:10.1016/0022-0000(78)90009-0
[10] Maier, D.: Minimum covers in the relational database model. J. ACM 27, 664-674 (1980) · Zbl 0466.68085 · doi:10.1145/322217.322223
[11] Maier, D.: The Theory of Relational Databases, pp. 42-70. Computer Science Press, Rockville, MD (1983) · Zbl 0519.68082
[12] Mannila, H., Raiha, K.-J.: On the relationship of minimum and optimal covers for a set of functional dependencies. Acta Informatica 20, 143-158 (1983) · Zbl 0504.68060 · doi:10.1007/BF00289412
[13] McCluskey, E.J.: Minimization of Boolean functions. Bell Syst. Tech. J. 35, 1417-1444 (1956) · Zbl 0395.68025
[14] McGeer, Patrick C., Sanghavi, Jagesh V., Brayton, Robert K., Sangiovanni-vincentelli, Alberto L.: ESPRESSO-SIGNATURE: A new exact minimizer for logic functions. IEEE Trans. Very Large Scale Integr. Syst. 1, 1-14 (1996)
[15] Peng, X., Xiao, Z.: Comments on problem decomposition method to compute an optimal cover for a set of functional dependencies. Database Syst. J. 4, 50-51 (2013)
[16] Wakerly, J.F.: Digital Design: Principles and Practices, pp. 222-228. Higher Education Press, Beijing (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.