Re: Help needed on Boyce-Codd Normal Form.
Date: Sun, 16 Dec 2007 00:42:32 GMT
Message-ID: <Yv_8j.53665$eY.21970_at_newssvr13.news.prodigy.net>
"Jan Hidders" <hidders_at_gmail.com> wrote in message news: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. >
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.
>> >> 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. :-) >>> > cannot get there and be dependency preserving. The order in which you
>> > 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
>> > 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 HiddersReceived on Sun Dec 16 2007 - 01:42:32 CET