Re: Fails Relational, Fails Third Normal Form

In article <7e4c6cec-6534-4187-bc75-2fe09ea5cdb1_at_googlegroups.com>,  Derek Asirvadem <derek.asirvadem_at_gmail.com> wrote:

> > For instance (from H. Koehler):
> >
> > CourseSchedule(Course, Lecturer, Room, Time)
> >
> > where a course has only one lecturer, each class has a fixed duration,
> > and the obvious constraints hold, such as teachers do not have the gift
> > of ubiquity.
>
> I couldn't find that.

I've borrowed it from his PhD thesis, but it's discussed in the paper "Finding Faithful Boyce-Codd Normal Form Decompositions", too.

> From what I can /see/, it looks too simple anyway.

Good for you. So, let's move on to the next example, which is slightly more interesting.

> I found Köhler's DNF paper, it has an example that is very similar, with one
> more element ("non-simple" in Relational terms), and it is quite fine for me.
> If you are happy to go with that, I have one tiny question. Given:
>
> >>>>
> Domination Normal Form - Decomposing Relational Database Schemas (sic),
> Henning Köhler
>
> 5 An Example
>
> A (sic) university has oral examinations at the end of each semester, and
> wants to manage related data using a relational database. The relevant
> attributes to be stored are
>
> ____R = {Student, Course, Chapter, Time, Room}
>
> Here Chapter denotes a chapter from the course textbook the student will be
> examined about. Every student can get examined about multiple chapters, and
> chapters may vary for each student. Multiple students can get examined at the
> same time in the same room, but the course must be the same. Further
> constraints are that a student gets examined for a >course<chapter> only
> once, and can't be in multiple rooms at the same time. Those conditions can
> be expressed through functional dependencies as follows:
> <<<<
>
> 1. Is the strike-out and substitution correct ? Otherwise the facts given
> are incoherent.

Usually, students take an exam for a course, not for a chapter, so "course" intuitively make more sense. Let me see if I can spot some contradiction. I will go through the requirements (not in the same order) and try to provide an example of sets of values compatible with each requirement and the previous ones.

1. "Every student can get examined about multiple chapters" (for the same course or for different courses):

Student Course Chapter Time Room

s1      c1     1       ...
s1      c1     2       ...
s1      c2     1       ...
s1      c2     2       ...

2. "chapters may vary for each student" (also for the same course):

Student Course Chapter Time Room

s1      c1     1       ...
s1      c1     2       ...
s1      c2     1       ...
s1      c2     2       ...
s2      c1     3       ...  <-- different from s1
s2      c1     4       ...  <-- different from s1
s2      c2     3       ...  <-- different from s2

3. "a student gets examined for a *course* only once and can't be in multiple rooms at the same time": this says that given a student and a course, there is only one exam, hence time and room are fixed (an exam takes place at one time in one room):

Student Course Chapter Time Room

s1      c1     1       t1   r1
s1      c1     2       t1   r1   <-- cannot be t2 or r2

4. "Multiple students can get examined at the same time in the same room, but the course must be the same". So:

Student Course Chapter Time Room

s1      c1     1       t1   r1
s1      c1     2       t1   r1
s1      c2     1       t2   r1   <-- cannot be t1
s1      c2     2       t2   r1
s2      c1     2       t1   r1
s2      c1     3       t1   r1
s2      c2     3       t3   r2   <-- cannot be t1

I don't see any contradictory facts (there is redundancy, of course).

For the theoreticians among us, let me express the same requirements formally ( "->" means "functionally determines" and "-/->" means "does not functionally determines"):

1. {Student,Course} -/-> {Chapter}
2. Well, this states that the multi-valued dependency {Course} ->> {Chapter} does not hold.
3. {Student,Course} -> {Time,Room} and {Student,Time} -> {Room}
4. {Time,Course,Room} -/-> {Student}, but {Time,Room} -> {Course}

So, we have the following constraints:

{Student,Course} -> {Time,Room}
{Student,Time} -> {Room}
{Time,Room} -> {Course}

"Room" in the first dependency can be removed without loss of information (SC -> R descends from SC -> T and ST -> R by transitivity).

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---