Re: thinking about UPDATE

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Thu, 22 Jul 2004 18:05:36 GMT
Message-Id: <pan.2004.07.22.18.06.23.604113@REMOVETHIS.pandora.be>

On Thu, 22 Jul 2004 15:05:20 +0000, Marshall Spight wrote:

> "x" <x-false_at_yahoo.com> wrote in message news:40feafc9_at_post.usenet.com...

>> **** Post for FREE via your newsreader at post.usenet.com ****
>>
>> "Marshall Spight" <mspight_at_dnai.com> wrote in message
>> news:YhxLc.4607$8_6.1154_at_attbi_s04...
>>
>> > Presumably one could infer the keys on the results of a relational
>> > operator.
>>
>> Try it. For project operator for example.

>
> [I'm just going to consider tables with a single key for now.]
>
> First, the case where the key is zero attributes. [...]
>
> Next the case where the key is one attribute. [...]
>
> Next the case where the key is multiple attributes. [...]
>
> If we have multiple keys and one has lost attributes and
> one hasn't, then [...]
>
> If we have multiple keys and they have all lost attributes,
> then [...]
>
> I think that covers all cases. How did I do?

Not bad, but a bit long. All you had to say was the following:

If K is the set of original candidate keys and P is the set of attribute on which we project then:
- Let K' = { k in K | k subset P }
- If K' is not empty then return K' otherwise { P }

> Also I note that my post here is simply thinking out the
> cases, and I have no formalism to back this up. Does anyone
> have any suggestions as to a formalism to apply to either
> prove or disprove the above?

Yep, normalization theory. You can translate the candidate keys to functional dependencies and these always also hold for the projection, and those that hold for the projection also hold for the original relation. So the proof of completeness goes something like this.

Suppose that in the projection we have a candidate key A that is not in K'. Then the FD A->P holds in the projection, but also in the original relation. However, the only FDs that hold in the original relation are those that are implied by its CKs so A must have already been a CK in the original relation. But then A is by definition in K' which leads to a contradiction. So the original assumption that the projection has a CK that is not in K' must be false. QED

I'm taking a few big leaps in this proof, but it should give you an idea of how it works.

• Jan Hidders

Received on Thu Jul 22 2004 - 13:05:36 CDT