Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
Home
Discussion Groups
Database Servers
DB2InformixIngresMS SQLOraclePervasive.SQLPostgreSQLProgressSybase
Desktop Databases
FileMakerFoxProMS AccessParadox
General
General DB TopicsDatabase Theory
Related Topics
Java Development.NET DevelopmentVB DevelopmentMore Topics ...

Database Forum / General DB Topics / DB Theory / August 2008

Tip: Looking for answers? Try searching our database.

BCNF

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
aarklon@gmail.com - 01 Aug 2008 10:44 GMT
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

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
Brian Selzer - 02 Aug 2008 09:10 GMT
> Hi all,
>
[quoted text clipped - 20 lines]
> 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
[quoted text clipped - 8 lines]
> 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?
aarklon@gmail.com - 08 Aug 2008 10:38 GMT
> <aark...@gmail.com> wrote in message
>
[quoted text clipped - 45 lines]
>
> 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.  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. 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
Brian Selzer - 08 Aug 2008 12:11 GMT
> > <aark...@gmail.com> wrote in message
> >
[quoted text clipped - 60 lines]
> 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
[quoted text clipped - 7 lines]
> 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
[quoted text clipped - 10 lines]
> getting ready for the  2nd. Ed.
> Ramon A. Mata-Toledo
aarklon@gmail.com - 12 Aug 2008 09:50 GMT
> <aark...@gmail.com> wrote in message
>
[quoted text clipped - 122 lines]
> > 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.

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.

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 have enjoyed the discussion across the ocean.
Be well,
Brian Selzer - 12 Aug 2008 12:44 GMT
> > <aark...@gmail.com> wrote in message
> >
[quoted text clipped - 157 lines]
> 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
[quoted text clipped - 28 lines]
> 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
[quoted text clipped - 6 lines]
> 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.
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.