Note that the second to last is actually not needed, since we have courseName → teacherName, teacherName → roomName. This set, the set of given FDs, is called F.
To find possible keys for the full relation, we need to compute the closures of all attributes. A trick is that we don't need to look at attributes that never appear on the left-hand side of a FD, since these can never give anything new. Another trick is that we only need to look at attribute sets that are supersets of some left-hand side for some FD, since if the set was not a superset of some left-hand side then there would be no FDs to follow!
We get:
From this we see that weekday and hour, together with any one of courseName, roomName and teacherName, forms a key for the relation. We never need to check anything that is a superset of a key, so we are done here.
The full set of FDs for this relation, i.e. the closure of F (F+), is thus:
(Note that we also have dependencies like teacherName, roomName → teacherTitle, but since we have already listed teacherName → teacherTitle we don't list the one with the extra attribute on the left-hand side.)
First we need to find the violations, considering all FDs including the ones that we got from computing closures above. One violation is courseName → teacherName, so we shall do the first step of decomposition on this. We get
R2 is now fine, but we still have violations in R1, for instance roomName → #seats, so we get
R11 is now fine, but we still have violations in R12, for instance teacherName → teacherTitle, so we get
There are now no violations left in either, so we are done. With some clever renaming, by looking at what the relations actually represent, we have the following relations:
This solution is on BCNF, so we are (almost, see 4NF) guaranteed to have no redundancy. If you compare this solution to the one we got from the E-R diagram in the previous exercise, you will see that by doing a BCNF decomposition, we got rid of the redundancy that could cause problems. But if you compare with the solutions from the first exercise, you will see that this corresponds to the first one, and it can be "fooled" by adding two classes from different courses in the same room at the same time. The reason for this is that during decomposition, we broke the dependency roomName, weekday, hour → courseName. Recall that BCNF guarantees no redundancy, but not dependency preservation. (As an aside, it could matter in which order we resolve violations when doing BCNF decomposition, but in this case we would get the same result no matter what we started with).
It's not in the exercise, but we'll tell you anyway. The first step of a 3NF decomposition is to compute the so called minimal basis, which means we can remove from our set of dependencies A → C if we already have A → B and B → C (note that we have already removed those on the form AB → C if we already have A → C, as noted above). Do this for the full closure (F+) and we retain the following FDs:
(The trickiest one to remove might be teacherName, weekday, hour → courseName. It is removed since we have teacherName → roomName and roomName, weekday, hour → courseName).
The next step of 3NF decomposition is to create one relation for each of the FD groups above (groups since we have listed FDs with the same left-hand side together, like courseName → teacherName and courseName → #students). Thus we get
The references can be gotten by looking at the FDs we removed when computing the minimal basis. If we had A → B and B → C and thus removed A → C, we must have a reference between the two Bs in the middle, pointing in the same direction the arrows do, otherwise we couldn't recreate A → C from our relations. In this case that means the following references:
In this simple example we could simply have guessed the correct references, we always refer to keys and anything named the same as a key in some other relation should refer to it.
If you compare with the answers to the first exercise, we have the same solution as the third one given there. It suffers from the same kind of redundancy as the one gotten from the E-R diagram, which we can see since courseName → roomName holds for Classes but courseName is not a key. Recall that 3NF decomposition guarantees that all dependencies are preserved (so we can no longer put two letures at the same place and time), but not that we are free from redundancy.
FDs which violate 3NF: B → F and E → F
To decompose to 3NF, compute the minimal basis:
Remove E → F since we have E → B and B → F
Group together FDs with the same LHS:
E → BD
For each group, create a relation with the LHS as the key:
R1(_A,_B,C) R2(_C,_D,E) R3(B,_E,D) R4(_B,F)
If no relation contains a key of R, add one relation containing only a key of R:
R5(_A,_E)
Now we extend the domain a bit, and first we are asked to find FDs and MVDs for the larger domain. We get the same as above (except no #students), but we also add the following into the mix:
Recall that a MVD requires the set on the right-hand side to be independent of any other attributes for that left-hand side. As an example, the books used on a course does not depend on what students read that course. On the other hand, we would not have for instance courseName → → book since the book used is not independent of the authors that have written some book used in the course, thus we need courseName → → book, author together.
With these we are asked to do a BCNF translation. We shall not repeat all the steps here, we have Teachers, Rooms and Courses as above, and we'll get a relation Students(studentName, studentHouse, studentYear). We are then left with
There are no FDs that hold on this relation, so it fulfills BCNF. But obviously there's still plenty of redundancy here, for instance for each student reading the course we list the books, the authors, and the lectures!
The last step then is to do the decomposition to 4NF. We can continue from where we are (since there are no MVDs that hold for any of the other relations), and list the MVDs that hold for this relation R:
The first one is trivial, since the left- and right-hand sides together form the entire relation R. The rest are violations since the left-hand side is not a key in any of them. We choose one to decompose on, for instance courseName → → studentName, so we get:
Note that for MVDs there is no closure in the way there is for FDs. What about references then? There are two cases: either we have some inherited reference for the left-hand side to some other table, like in this case there is one that refers from R.courseName to Courses.courseName. Then both of the new relations now refer to Courses.courseName (there is no reference between them since they are independent!). The other case is that we don't have another table to refer to. In that case we could either simply skip the reference (easiest), or create a separate relation containing only that left-hand side (most correct, but can be overkill some times). As noted, in this case we have the references R1.courseName → Courses.courseName and R2.courseName → Courses.courseName.
R1 now fulfills 4NF. We have both courseName → → studentName and studentName → → courseName, but both are trivial (left and right form the whole relation).
For R2 we need to decompose further, so we choose courseName → → book, author to get:
(Since all the relations that come from courseName on the left-hand side are independent, we could have taken them in one step, i.e. create R1, R21 and R22 in one decomposition step).
R22 is now on 4NF, but for R21 we have book → → author and author → → book. We choose book → → author and get
Here we have nowhere to let book refer to. We could then create a relation Books(book) and let both R211 and R212 refer to it (not doing it means we have a possible deletion anomaly, what if there are no authors for a book? Not likely, but…).
We are now done, and with some renaming we get:
No redundancy anywhere, but just like for BCNF we cannot guarantee to preserve dependencies with 4NF, we have again broken roomName, weekday, hour → courseName.