Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Acta Informatica

01-08-2016 | Original Article

Optimal covers in the relational database model

Published in: Acta Informatica | Issue 5/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The problem of finding an optimal cover which has possible fewest attributes is NP-complete. It is shown here that an optimal cover can be found, using the notion of mini cover. The minimum Boolean expression of the first Delobel–Casey transform of a set of functional dependencies can be converted into corresponding mini cover, refining classic canonical cover. The relationship between optimal cover and Boolean expression minimization is built, and all theory of Boolean expression minimization can be used to find an optimal cover.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
2.
3.
Bernstein, P.A.: Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 277–298 (1976)CrossRef
4.
Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13, 377–387 (1970)CrossRefMATH
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)MathSciNetCrossRefMATH
7.
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)
9.
10.
11.
Maier, D.: The Theory of Relational Databases, pp. 42–70. Computer Science Press, Rockville, MD (1983)
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)MathSciNetCrossRefMATH
13.
McCluskey, E.J.: Minimization of Boolean functions. Bell Syst. Tech. J. 35, 1417–1444 (1956)
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)
Metadata
Title
Optimal covers in the relational database model
Publication date
01-08-2016
Published in
Acta Informatica / Issue 5/2016
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-015-0247-9

Premium Partner

    Image Credits