Re: ADR's Normalization question

From: Mr. Scott <do_not_reply_at_noone.com>
Date: Fri, 13 Nov 2009 23:54:20 -0500
Message-ID: <QrKdnXcTCq9gqmPXnZ2dnUVZ_hmdnZ2d_at_giganews.com>


"paul c" <toledobythesea_at_oohay.ac> wrote in message news:JqmLm.51902$Db2.37119_at_edtnps83...
> In his 'Writings' series, this time from the 2006 edition, chapter 13,
> 'More on Normalization', Date examines a suggestion by one his
> correspondents, known only as 'ADR'. This suggestion intrigued me, here's
> a longish quote for some context:
>
> (start quote)
> '... Note. Just to remind you, let me summarize those principles here:
> 1. A relvar that's not in fifth normal form (5NF) should be decomposed
> into a set of 5NF projections.
> 2. The original relvar should be reconstructable by joining those
> projections back together again.
> 3. The decomposition process should preserve dependencies.
> 4. Every projection should be needed in the reconstruction process.
>
> 'On the basis of this example I claimed that normalization by itself
> wasn't enough: we needed something else to tell us what's wrong - what's
> formally wrong, I mean - with this decomposition. In fact, I claimed that
> what we needed was another principle (and later in the chapter I claimed
> that the principle in question was essentially The Principle of Orthogonal
> Design). ADR commented:
>
> (ADR): "How about a principle stating that no attribute of the relvar
> being decomposed is to appear as a nonkey attribute in more than one
> projection? But I would not elevate such a simple and obvious rule to the
> status of a principle; I would just add it to the definition of the
> decomposition procedure. (That said, I admit that at the moment I'm still
> wondering if there are pathological cases that my suggested wording
> doesn't cater for.)"
>
> (Date): 'There are several things I want to say ...
> (snip)
> 'But my major concern is that I think the proposed rule is too strong ...
> 'By way of example, suppose suppliers are partitioned into classes (C1,
> C2, etc.), so that the supplier relvar has an additional attribute CLASS.
> Suppose also that (a) each class has just one associated status, and (b)
> each city has just one associated status as well, but (c) classes and
> cities are otherwise quite independent of each other. Then the relvar
> satisfies these two functional dependencies (FDs):
>
> { CLASS } -> { STATUS }
> { CITY } -> { STATUS }
>
> ...(snip)
>
> 'it should be apparent that the following is a valid nonloss decomposition
> for this revised suppliers relvar (I ignore attribute SNAME for
> simplicity):
>
> SCC ( S#, CLASS, CITY}
> KEY { S# }
>
> CLS { CLASS, STATUS}
> KEY { CLASS }
>
> CTS { CITY, STATUS}
> KEY { CITY }
>
> 'Observe in particular that attribute STATUS appears here as a nonkey
> attribute in more than one projection, and the decomposition thus violates
> ADR's proposed rule. Yet, to repeat, the decomposition is surely valid,
> and the proposed rule is thus not quite right.
>
> (end quote)
>
> I think that Date might be using a strawman argument here, ie., he shoots
> down an example which is a violation of ADR's suggestion.
>
> If I'm not mistaken Armstrong's axioms can be applied to show that
>
> { CITY, CLASS } -> { STATUS },
>
> so the CTS relation isn't needed if the CLS relation is replaced by
>
> CLS { CITY, CLASS, STATUS }
> KEY { CITY, CLASS }
>
> Have I got this right? If so, I think ADR's suggested rule does apply to
> Date's example.
>

Sorry, you've got it wrong. {CITY,CLASS,STATUS} satisfies the multi-valued dependency,

    STATUS ->-:> CITY | CLASS which is not implied by the key

    {CITY,CLASS} {CITY,CLASS,STATUS} is therefore not in 4NF let alone 5NF. The projections, {CITY,STATUS} and {CLASS,STAUTS}, are in 5NF, though.

While AB -> C can be inferred from A -> C and B -> C, that is, a table that satisfies A -> C and B -> C also satisfies AB -> C, but A -> C and B -> C cannot be inferred from AB -> C.

The table,

(Boston, C1, S1),
(Boston, C2, S2),
(Chicago, C1, S2),
(Chicago, C2, S1),

satisfies the functional dependency

{CITY,CLASS} -> STATUS but it is easy to see that neither

CITY -> STATUS or CLASS -> STATUS

are satisfied. Received on Fri Nov 13 2009 - 22:54:20 CST

Original text of this message