Re: BCNF
Date: Tue, 12 Aug 2008 01:50:58 -0700 (PDT)
Message-ID: <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. 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.
I have enjoyed the discussion across the ocean. Be well, Received on Tue Aug 12 2008 - 10:50:58 CEST