Re: Functional Dependencies?

From: paul c <toledobythesea_at_oohay.ac>
Date: Sat, 01 Oct 2005 18:33:43 GMT
Message-ID: <bEA%e.26826$1i.11256@pd7tw2no>

Mikito Harakiri wrote:
> 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.
>

I presume this is the same as saying that the attribute set, {}, is a key. I wonder if the FD {X} -> {} means anything?

> 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.
> ...

If we *don't* have the FD {} -> X but we let n = 1 then must this refer to a relation whose attributes are the empty set?

p Received on Sat Oct 01 2005 - 13:33:43 CDT