On the number of independent functional dependencies. In: Dix J, Hegner SJ, editors. Lecture notes in computer science. Vol 3861.; 2006. p. 83-91. Abstract
On the number of independent functional dependencies
We will investigate the following question: what can be the maximum number of independent functional dependencies in a database of n attributes, that is the maximum cardinality of a system of dependencies which which do not follow from the Armstrong axioms and none of them can be derived from the remaining ones using the Armstrong axioms. An easy and for long time believed to be the best construction is the following: take the maximum possible number of subsets of the attributes such that none of them contains the other one (by the wellknown theorem of Sperner [8] their number is (n / n/2)) and let them all determine all the further values. However, we will show ( n by a specific construction that it is possible to give more than (n / n/2) independent dependencies (the construction will give (I + 1 / n(2))(n / n/2) of them) and – on the other hand – the upper bound is 2(n) – 1, which is roughly root n(n / n/2).
Some contributions to the minimum representation problem of key systems. In: Dix J, Hegner SJ, editors. Lecture Notes in Computer Science. Vol 3861.; 2006. p. 240-57. Abstract
Some contributions to the minimum representation problem of key systems
Some new and improved results on the minimum representation problem for key systems will be presented. By improving a lemma of the second author we obtain better or new results on badly representable key systems, such as showing the most badly representable key system known, namely of size 2(n(1-c.log n/ log n)), where n is the number of attributes. We also make an observation on a theorem of J. Demetrovics, Z. Furedi and the first author and give some new well representable key systems as well.