Name
Abstract | ||
|---|---|---|
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 by a specific construction that it is possible to give more than ($^{~~n}_{n/2}$) independent dependencies (the construction will give (1 + $\frac{1}{n^2}$) ($^{~~n}_{n/2}$) of them) and — on the other hand — the upper bound is 2n–1, which is roughly $\sqrt{n}(^{~~n}_{n/2})$. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11663881_6 | FoIKS |
Keywords | Field | DocType |
independent functional dependency,independent dependency,maximum possible number,best construction,long time,armstrong axiom,maximum cardinality,following question,maximum number,specific construction,functional dependency,upper bound | Discrete mathematics,Relational database,Computer science,Upper and lower bounds,Cardinal number,Cardinality,Algorithm,Functional dependency,Theoretical computer science,Armstrong's axioms | Conference |
Volume | ISSN | ISBN |
3861 | 0302-9743 | 3-540-31782-1 |
Citations | PageRank | References |
6 | 0.46 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Demetrovics | 1 | 414 | 163.60 |
| Gyula O. H. Katona | 2 | 264 | 66.44 |
| Dezső Miklós | 3 | 6 | 1.13 |
| Bernhard Thalheim | 4 | 1811 | 442.28 |