Skip to main content
Springer Nature Link
Log in

A survey of some combinatorial results concerning functional dependencies in database relations

  • Published:
Save article
View saved research
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

A databaseR has some obvious and less obvious parameters such as the number of attributes, the size |r|, the maximum size of a domain, the number of some special functional dependencies (e.g. the minimal keys), and so on. The main aim of this paper is to survey some of the results giving connections and inequalities among these parameters. The methods are of a combinatorial nature. A generalization of the numerical dependency is also considered.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Netherlands)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. V.B. Alekseyev, Diskret. Mat. 1(1989)129–136.

    Google Scholar 

  2. W.W. Armstrong, Dependency structures of data base relationship, in:Information Processing 74 (North-Holland, Amsterdam) pp. 580–583.

  3. A. Békéssy, J. Demetrovics, L. Hannák, P. Frankl and G.O.H. Katona, On the number of maximal dependencies in a data base relation of fixed order, Discr. Math. 30(1980)83–88.

    Google Scholar 

  4. F.E. Bennett and Lisheng Wu, On minimum matrix representation of closure operations, Discr. Appl. Math. 26(1990)25–40.

    Google Scholar 

  5. J. Biskup, private communication.

  6. B. Bollobás, On generalized graphs, Acta Math. Hungar. 16(1965)447–452.

    Google Scholar 

  7. Yeow Meng Chee, Design-theoretic problems in perfectly (n-3)-error-correcting databases, SIAM J. Discr. Math., submitted.

  8. E.F. Codd, A relational model of data for large shared data banks, Commun. ACM 13(1970)377–387.

    Google Scholar 

  9. G. Burosch, J. Demetrovics and G.O.H. Katona, The poset of closures as a model of changing databases, Order 4(1987)127–142.

    Google Scholar 

  10. G. Burosch, J. Demetrovics, G.O.H. Katona, D.J. Kleitman and A.A. Sapozhenko, On the number of database closure operations, Theor. Comput. Sci. 78(1991)377–381.

    Google Scholar 

  11. G. Burosch, J. Demetrovics, G.O.H. Katona, D.J. Kleitman and A.A. Sapozhenko, On the number of database closure operations, II, Discr. Appl. Math., submitted.

  12. J. Demetrovics, On the equivalence of candidate keys with Sperner systems, Acta Cybern. 4(1979)247–252.

    Google Scholar 

  13. J. Demetrovics, Z. Füredi and G.O.H. Katona, Minimum matrix representation of closure operations, Discr. Appl. Math. 11(1985)115–128.

    Google Scholar 

  14. J. Demetrovics and Gy. Gyepesi, A note on minimal matrix representation of closure operations, Combinatorica 3(1983)177–180.

    Google Scholar 

  15. J. Demetrovics, G. Hencsey, L.O. Libkin and I.B. Muchnik, On the interaction between closure operations and choice functions with applications to relational databases, Acta Cybem., to appear.

  16. J. Demetrovics and G.O.H. Katona, Extremal combinatorial problems in a relational database, in:Fundamentals of Computation Theory 81, Proc. 1981 Int. FCT-Conf., Szeged, Hungary, 1981, Lecture Notes in Computer Science 117 (Springer, Berlin, 1981) pp. 110–119.

    Google Scholar 

  17. J. Demetrovics and G.O.H. Katona, Combinatorial problems of database models, in:Coll. Math. Soc. János Bolyai, 42. Algebra, Combinatorics and Logic in Computer Science, Györ, Hungary, 1983 (North-Holland, Amsterdam, 1986) pp. 331–353.

    Google Scholar 

  18. J. Demetrovics and G.O.H. Katona, Extremal combinatorial problems of databases, in:MFDBS'87, 1st Symp. on Mathematical Fundamentals of Database Systems, Dresden, Germany, Lecture Notes in Computer Science (Springer, 1987) pp. 99–127.

  19. J. Demetrovics, G.O.H. Katona and D. Miklós, Partial dependencies in relational databases and their realization, Discr. Appl. Math., to appear.

  20. J. Demetrovics, G.O.H. Katona and A. Sali, On the characterization of branching dependencies, Discr. Appl. Math., to appear.

  21. J. Demetrovics, G.O.H. Katona and A. Sali, Branching dependencies in relational databases (in Hungarian), Alkalmaz. Mat Lapok, to appear.

  22. J. Demetrovics and Son Hua Nam, Closures and Sperner families,Coll. Math. Soc. János Bolyai, Extremal Problems for Families of Subsets, Visegrád, Hungary (1991), submitted.

  23. Z. Füredi, Perfect error-correcting databases, Discr. Appl. Math. 28(1990)171–176.

    Google Scholar 

  24. J. Grant and J. Minker, Normalization and axiomatization for numerical dependencies, Inf. Contol 65(1985)1–17.

    Google Scholar 

  25. H.-O.O.F. Gronau and B. Ganter, On two conjectures of Demetrovics, Füredi and Katona concerning partitions, Discr. Math. 88(1991)149–155.

    Google Scholar 

  26. H.-O.O.F. Gronau and R.C. Mullin, Preprint.

  27. A.D. Korshunov, On the number of monotone Boolean functions, Problemy Kibernet. 38(1981)5–108, in Russian.

    Google Scholar 

  28. A.V. Kostochka, On the maximum size of a filter in then-cube, Metodi Diskretnovo Analiza 41(1984)49–61, in Russian.

    Google Scholar 

  29. D. Lubell, A short proof of Sperner's lemma, J. Combinat Theory 1(1966)299.

    Google Scholar 

  30. H. Mannila and K.-J. Räihä, On the complexity of inferring functional dependencies, Discr. Appl. Math., to appear.

  31. L.D. Meshalkin, A generalization of Sperner's theorem on the number of subsets of a finite set, Teor. Veroyatnost. i Primenen. 8(1963)219–220, in Russian.

    Google Scholar 

  32. A. Rausche, On the existence of special block designs, Rostock Math. Kolloq. 35(1985)13–20.

    Google Scholar 

  33. A. Sali, Extremal problems for finite partially ordered sets and matrices, Thesis for “kandidátus” degree, Hungarian Academy of Sciences, Budapest (1990), in Hungarian.

    Google Scholar 

  34. A. Sali, private communication.

  35. E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27(1928)544–548.

    Google Scholar 

  36. B. Thalheim, A review of research on dependency theory in relational databases I, II, Preprint, Technische Universität Dresden, Sektion Mathematik (1986).

  37. B. Thalheim, On the number of keys in relational databases, Discr. Appl. Math., to appear.

  38. B. Thalheim,Dependencies in Relational Databases (Teubner, Leipzig, 1991).

    Google Scholar 

  39. K. Yamamoto, Logarithmic order of free distributive lattices, J. Math. Soc. Japan 6(1954)347–357.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 12-17, H-1111, Budapest, Hungary

    J. Demetrovics

  2. Mathematical Institute, Hungarian Academy of Sciences, P.O. Box 127, H-1364, Budapest, Hungary

    G. O. H. Katona

Authors
  1. J. Demetrovics
    View author publications

    Search author on:PubMed Google Scholar

  2. G. O. H. Katona
    View author publications

    Search author on:PubMed Google Scholar

Additional information

This work was supported by the Hungarian National Foundation for Scientific Research, Grant No. 2575.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Demetrovics, J., Katona, G.O.H. A survey of some combinatorial results concerning functional dependencies in database relations. Ann Math Artif Intell 7, 63–82 (1993). https://doi.org/10.1007/BF01556350

Download citation

  • Issue date:

  • DOI: https://doi.org/10.1007/BF01556350

Keywords