Re: BCNF

From: Brian Selzer <brian_at_selzer-software.com>
Date: Tue, 12 Aug 2008 07:44:58 -0400
Message-ID: <%Ieok.18359$jI5.6033_at_flpi148.ffdc.sbc.com>


<aarklon_at_gmail.com> wrote in message news:5cdb3bb4-b2be-468e-bd9a-f8854dcc51ae_at_k36g2000pri.googlegroups.com...
> On Aug 8, 4:11 pm, "Brian Selzer" <br..._at_selzer-software.com> wrote:
> > <aark..._at_gmail.com> wrote in message
> >
> > news:57725ea6-edc0-4dd4-a0bd-6c3ec629a1bc_at_r15g2000prh.googlegroups.com...
> >
> >
> >
> >
> >
> >
> >
> > > On Aug 2, 1:10 pm, "Brian Selzer" <br..._at_selzer-software.com> wrote:
> > > > <aark..._at_gmail.com> wrote in message
> >
> > > >news:3a1e04e9-e65f-469f-8357-f36486009e72_at_b38g2000prf.googlegroups.com...
> >
> > > > > Hi all,
> >
> > > > > BCNF
> >
> > > > > the following is the definition is the definition of BCNF , which
> > > > > i
> > > > > saw in a schaum series book
> >
> > > > > 1) The relation is 1 N.F
> >
> > > > > 2) for every functional dependency of the form X -> A , we have
> > > > > either A C X or X is a super key of r. in other words,
> > > > > every functional dependency is either a trivial dependency or in
> > > > > the case that the functional dependency is not trivial then X must
> > > > > be a super key.
> >
> > > > > now my questions are as follows
> >
> > > > > 1)
> >
> > > > > we know that 2-ND normal form is all about separating partial
> > > > > dependencies and full dependencies.third normal form is all about
> > > > > removing transitive dependencies, in these lines can any one give
> > > > > simple/ easy to understand method/explanation for converting a
> > > > > relation in 3rd normal form to BCNF
> >
> > > > A relation schema is in 3NF iff for every functional dependency the
> > > > determinant is a superkey or the dependent is prime; a relation
> > > > schema
> > > > is in
> > > > BCNF iff every determinant is a superkey. A schema that is in 3NF
> > > > but
> > > > not
> > > > in BCNF will have one or more determinants that are not superkeys.
> > > > Find
> > > > them and eliminate them.
> >
> > > > > 2) how correct is the following definition of transitive
> > > > > dependencies
> >
> > > > > transitive dependencies
> >
> > > > > assume that A,B, and C are the set of attributes of a relation(R).
> > > > > further assume that the following
> > > > > functional dependencies are satisfied simultaneously : A -> B ,
> > > > > B -/-
> > > > >> A, B -> C , and C -/-> A and A -> C
> > > > > observe that C -> B is neither prohibited nor required. if all
> > > > > these
> > > > > conditions are true, we will say that attribute C is transitively
> > > > > dependent on attribute on A
> >
> > > > It is not correct: what if B = C or C is a subset of B?
> >
> > > this is what the the reply i got from the authors of the book
> >
> > > The condition for having a transitive dependency is as follows:
> >
> > > A -> B B-> C from this you will infer that A ->C provided that B
> > > does not determine A and C does not determine A. The reason for
> > > requiring that B does not determine A is because we are assuming that
> > > A is the only key. If B were to determine A then B will also be a key.
> > > Same thing applies to C. Remember that you are going from 1NF to 2NF.
> > > This latter form requires that you do not have any partial
> > > dependencies on any primary or candidate key. That is no subset of A
> > > can determine B if A is a key or candidate key.
> >
> > Bunk! Suppose that R has attributes {V, W, X, Y},
> > that A is the set of attributes {V, W, X, Y},
> > that B is the set of attributes {W, X, Y}
> > and that C is the set of attributes {X, Y}.
> >
> > R is in 2NF.
> > Clearly A --> B, B -/-> A, B --> C, A --> C, and C -/-> A,
> > but C is not /transitively/ dependent on A: C is /trivially/ dependent
> > on A.
> >
> > > If B=C then they are
> > > the same attribute and every attribute determines itself. That is what
> > > the reflexivity axiom is all about. Remember that 2NF requires that
> > > there cannot be partial dependencies on the key. It does not talk
> > > about partial dependencies among the other attributes if these
> > > attribute are not primary key or candidate key. Just make sure that
> > > before you guarantee that a set of relationships are in 2NF you find
> > > ALL keys. From this set you will choose a primary key. There got to be
> > > only one primary key. The other possible keys are candidate. Tell your
> > > friends that they are not correct the definition in the book is the
> > > original and only definition that there is about transitivity.
> >
> > Assuming that you copied the definition from the book word for word, the
> > definition in the book is wrong because it does not exclude trivial
> > functional dependencies. Here is a definition that appears in a paper by
> > Carlo Zaniolo, "A New Normal Form for the Design of Relational Database
> > Schemata", ACM Transactions on Database Systems, Vol. 7, No. 3,
> > September
> > 1982:
> >
> > Let R be a relation with attribute set U, let X be a subset of U (not
> > necessarily proper), and let A be a member of U. A is /transitively/
> > dependent on X if there exists a Y which is a subset of U (not
> > necessarily
> > proper) such that X --> Y, Y -/-> X, Y --> A, and A is not a member of
> > Y.
> > [Zaniolo's definition used symbols instead of 'be a subset of ... (not
> > necessarily proper)' and 'is/is not a member of'. Sometimes I've found
> > that
> > the symbols for 'is a subset of' and 'is a proper subset of' are not
> > used
> > consistently. This may be one case of that because clearly, in order for
> > there to be a transitive dependency, both X and Y must both be /proper/
> > subsets of U, since A can't be a member of Y, so if Y were a subset of X
> > which would be the case when X = U, then A couldn't be a member of X.]
> >
> > Note that the final condition, 'A is not a member of Y,' excludes the
> > trivial case.
> >
> > > Just
> > > remember that in the book we are assuming that A is the PK. If as your
> > > friends say B -> A and A is a key then B is a key. As I mentioned
> > > before this applies also to C. If A, B, and C were all keys then the
> > > definition of 2NF and 3NF are moot because there cannot be partial or
> > > transitive dependencies because these definitions require that there
> > > exist other attributes that are not primary or candidate keys. You
> > > need to be careful when you go to 3NF if you have PK that overlap.
> > > Then you have to move to BC normal form.
> >
> > > Thanks for reading the book and reading it carefully. If you find any
> > > mistakes please let me know, Pauline and I are in the process of
> > > getting ready for the 2nd. Ed.
> > > Ramon A. Mata-Toledo

>
>
>

> this again is the reply i got from authors of the book
>

> I am glad that you are taking databases seriously. With regard to your
> question. Assume you have the relation R with the attributes that you
> have defined. The relation R is in 2NF if, first, it is in 1NF. We can
> assume that none of the attributes V, W, X, and Y have attributes of
> their own. Therefore, the relation is in 1NF. Now, the 2NF requires
> that you have a key but it also assume that there are non prime
> attributes. These non prime attributes cannot be partially dependent
> on the key. Yes, you have a key. It is obvious from the reflexivity
> axiom that the key determines all other attributes. In fact, {V, W, X,
> Y} -> V; {V, W, X, Y}-> W; {V, W, X, Y} -> X; {V, W, X, Y} ->Y. You
> also have that {V, W, X, Y} -> {W,X,Y} by the axiom of augmentation.
> Finally, {V, W, X, Y} -> {X,Y} by the same axiom. The apparent
> contradiction that you have found to the definition of 3NFcomes from
> not having nonprime attributes which are not partially dependent upon
> ANY key. Take into account also that the def of 3NF requires that the
> relation be previously in 2NF (no nonprime attribute can be partially
> dependent upon any key).Remember the definitions (2NF, 3NF) assume
> that the key A determines every other attribute but it also assumes
> the existence of nonprime attributes which are not partially dependent
> upon the key.

Perhaps his sloppy definitions do. A relation can be in 2NF or 3NF and not have any nonprime attributes.

> All the attributes that you have here, B and C are
> partially dependent upon the key. In the def of transitive dependence
> (refer to the graph in the book) A is assumed to be a single key. B
> is a nonprime attribute and it cannot be partially dependent upon the
> key. Finally, C must also be a nonprime attribute. In case, you
> forgot, nonprime attributes are those attributes that do no
> participate in any key.

>

> If there are no partial dependencies you are in 2NF. If you do not
> have transitive dependencies you are in 3NF. Obviously, I am assuming
> that we have a key for the relation as determined by the set of given
> FDs. Finally, if you have a relation with attributes A, B, and C and
> they all can be used as key and they do not overlap then you are
> already in 3NF.
>

> By the way, in the book all attributes A,B, and C are assumed to be
> simple attributes unless defined otherwise. This is to simplify the
> explanations.
>

> If you want to take a more formal book, take a look at The Theory of
> Relational Databases by David Maier. It is heavy in mathematics.
>
>
>

> Before, I forgot, Trivial FDs are those that are determined by the
> Axiom of Reflexivity. A comment about the use of notations. In the DB
> world, there are definitions and definitions. Zaniolo is top expert in
> DB but if you read some of his papers you will find that the same
> concept may have more than one interpretation. This is typical of DB.
> That is, why it is very important to know what definitions you are
> using. Take for example, the word set, I believe that the last time I
> checked there were more than 200 definitions of this word in different
> DBMSs alone. When working with FD and non redundant FDs you need to
> exclude trivial FDs.
>

This author sounds almost as slippery as Osama Obama (Wait! I can't say that! I'm not Teddy Kennedy! I must be a xenophobic hatemonger clinging to my guns and my religion!).

> The Definition that I used in the book is the same as Maier which in
> turn is the definition that Date uses. I do a lot of consulting in DB
> across the world in ORACLE. It is fun to work with set of FDs
> developed by the designers who are using the IBM concepts and
> notations and sometimes notations and definitions of their own. Take
> into account that the same thing happens sometimes in mathematics. One
> author considers the set of natural numbers beginning with one. Others
> may assume that it includes zero. That is, sometimes you need to check
> what the definitions are to be consistent. Hope this helps ;if not I
> hope to hear from you again soon.
>

"I did not have sex with that woman!" --William Jefferson Clinton

> I have enjoyed the discussion across the ocean.
> Be well,
>

Sloppy definitions yield sloppy results. Sloppy definitions are indicative of sloppy thinking. Received on Tue Aug 12 2008 - 13:44:58 CEST

Original text of this message