Re: thinking about UPDATE

On Wed, 28 Jul 2004 10:54:13 +0300, x wrote:
> "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> news:pan.2004.07.27.17.33.30.451062_at_REMOVETHIS.pandora.be...
>

>> Of course, but I'm not starting with *any* relation. To show the type
>> of completeness that we are dealing with here it is sufficient to show
>> that for every set A of attributes that is not derived by the algorithm
>> there is a relation that satisifies the initial set of candidate keys and
>> in whose projection A is not a candidate key. Since the only restriction
>> is that it satisfies the original set of candidate keys I'm free to assume
>> that the only FDs that hold for it are those that are implied by these
>> candidate keys.

It's the only one that really makes sense here: every CK that logically follows from the original set of CKs is derived. The algorithm cannot be expected to derive what cannot be derived.

> It would have been easier if you stated that one need to know all the
> constraints on the relation to determine the candidate keys (not a
> superkey).

That should have been rather obvious because if you don't know all the constraints then not all CKs in the projection will logically follow.

> Are you aware of any algorithm that solve this problem ? What is
> the complexity of it ?

Which problem exactly? To derive the CKs in the projection given a set of CKs in the original relation? That algorithm I already gave in this thread. Or do you want to start from a set of FDs?

• Jan Hidders