Re: Help needed on Boyce-Codd Normal Form.

From: Jan Hidders <hidders_at_gmail.com>
Date: Sat, 15 Dec 2007 03:14:45 -0800 (PST)
Message-ID: <5e4baf55-ed8c-46ba-9d7d-6c3c73f226ca_at_e23g2000prf.googlegroups.com>


On 15 dec, 11:16, Kira Yamato <kira..._at_earthlink.net> wrote:
> On 2007-12-14 21:50:13 -0500, Jan Hidders <hidd..._at_gmail.com> said:
>
>
>
> > On 15 dec, 02:16, Kira Yamato <kira..._at_earthlink.net> wrote:
> >> On 2007-12-14 17:08:02 -0500, TroyK <cs_tr..._at_juno.com> said:
>
> >>> On Dec 14, 4:42 am, Kira Yamato <kira..._at_earthlink.net> wrote:
> >>>> On 2007-12-14 06:24:06 -0500, Kira Yamato <kira..._at_earthlink.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.

> >> 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
Received on Sat Dec 15 2007 - 12:14:45 CET

Original text of this message