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. Received on Fri Sep 30 2005 - 20:04:24 CEST