Help needed on Boyce-Codd Normal Form.

#11

"Jan Hidders" <hidders (AT) gmail (DOT) com> wrote

Quote:

On 15 dec, 11:16, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
On 2007-12-14 21:50:13 -0500, Jan Hidders <hidd... (AT) gmail (DOT) com> said:

On 15 dec, 02:16, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
On 2007-12-14 17:08:02 -0500, TroyK <cs_tr... (AT) juno (DOT) com> said:

On Dec 14, 4:42 am, Kira Yamato <kira... (AT) earthlink (DOT) net> wrote:
On 2007-12-14 06:24:06 -0500, Kira Yamato <kira... (AT) earthlink (DOT) net
said:

Suppose I want to create a schema for
S = student,
J = subject,
T = teacher,
that enforces

1) For each subject, each student taking that subject is taught by
exactly one teacher. But a student can take multiple subjects.
2) Each teacher teaches exactly one subject. But a subject can be
taught by multiple teachers.

How do you create a schema that is at least BCNF and enforces 1)
and 2)?

Your
example can be represented in pseudo-BCNF as follows:

R1(S,J,T) with candidate key {S,J}
R2(T,J) with candidate key {T}
inclusion dependencies:
- from R1(T,J) to R2(T,J)

Note that I omitted the candidate key {S,T} for R1. It is implied by
the other specified dependencies. So you see it is quite possible to
come up with a set of relations and a set of dependencies that consist
of inclusion dependencies and local functional dependencies such that
all original dependencies are implied.

What is a bit dodgy about this solution is that it pretends that the
FD T-->J does not exists for R1 and so it will only find out that this
FD has been violated by an update on R2 if the update is propagated to
R2. It is in that sense that this is usually not considered a valid
solution: not all local FDs are implied by the CKs. It is also in this
sense that the claim is correct that says that you cannot always
normalize to BCNF while being dependency preserving. Note that in
practice it could be that pseudo-BCNF is acceptable, provided that
your DBMS supports it efficiently.

Nice explanation. So, the trouble is that some constraint is needed
that must span multiple relations, like the inclusion dependency you
mentioned above.

Exactly.

So, when you say "provided that your DBMS supports it [pseudo-BCNF],"
do you mean that a DBMS that allows specifying a constraint across
multiple tables?

Almost all do. Inclusion dependencies are simply foreign keys, but as
you see in the example you need here a foreign key that does not
arrive in a candidate key. Not all DBMSs allow this.

Sorry to pick nits, but not all inclusion dependencies are foreign key
constraints. Correct me if I'm wrong, but doesn't a foreign key constraint
require that the set of referenced attributes be a superkey? An inclusion
dependency simply requires that the set of values for the set of referencing
attributes be a subset of the set of values for the set of referenced
attributes.

Quote:

Is there a way to identify when a set of FD's cannot be decomposed
into BCNF?

Yep. Determine an irreducible cover. Check if there are two different
FDs in it such that the set of all attributes mentioned in one is a
subset of that of the other. If this is the case you cannot get to
BCNF and be dependency preserving.

I am guessing that by an "irreducible cover" you mean some minimal set
of FD's such that all of its combinations will produce all of the
original FD's in question.

Close. It must also be the case that the right-hand sides all consist
of one attribute, and the left-hand sides must be as small as
possible, i.e., if you make them smaller you no longer produce all of
the orginal FDs. Google around and you will find more explanation.

So your claim is that if the procedure of getting to BCNF while being
dependency preserving cannot be met, then every irreducible cover of
the original FD's will have two distinct FD's such that the set of
attributes mentioned in one will be a subset of those in the other.

This is quite a strong claim.

Indeed it is. :-)

But you can also simply start splitting off 3NF violating dependencies
as usual and see what you end up with. If that is not in BCNF then you
cannot get there and be dependency preserving. The order in which you
pick the dependencies does not matter.

Very cool results. I will try to look up some books that prove these
assertions. Do you have a good reference to recommend?

IIRC the book by Ullman "Principles of Database & Knowledge-Base
Systems" (part 1) discusses this. Should be available in a university
library near you.

-- Jan Hidders

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Help needed on Boyce-Codd Normal Form.

comp.databases.theory comp.databases.theory

Re: Help needed on Boyce-Codd Normal Form. - 12-15-2007 , 06:42 PM