# Re: Functional Dependencies?

Date: 30 Sep 2005 11:04:24 -0700

Message-ID: <1128103464.250032.292400_at_g44g2000cwa.googlegroups.com>

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