Re: Functional Dependencies?

Theo Clevadore wrote:
> If there is a FD that says {} -> Y what does that mean?
>
> I take from it that Y is a constant value therefore anything supplied
> for X (including nothing) will determine Y. But, I'm unsure.

FD and MVFD with empty antecedents impose
some constraints onto relation cardinality.

Indeed, assuming {X,Y,Z} being relation signature FD, then

{} -> {X,Y,Z}

says that there is no pair of tuples with 2 distinct values, or,
equivalently, that cardinality of the relation is 1 at most.

Likewise MVFD with empty antecedent, for example

{} -> {X} | {Y,Z}

claims that cardinality of the XYZ relation is the product of
cardinalities of its X and YZ projections.

Natural question is if some set of dependencies can effectively
constrain cardinality to an arbitrary integer.

I asked Ron Fagin this question some time ago, and here is his answer:

Theorem: Let S be an arbitrary set S of FDs and MVDs that does not
logically imply the FD {} -> X, where X is the set of all attributes.
Then for every positive integer n, there is a relation with n tuples
that
satisfies S.

Corollary. The cross-product constraint by
MVDs doesn't cause a problem, since one side of the cross-product can
have
size 1.

.

Quantcast