| A First Course in Database Systems |
|
| A First Course in Database Systems |
Customers(ssNo, name, address, phone, acctNumber) Accounts(number, type, balance)Notice that if we had started from the E/R diagram of Exercise 2.2.1, we would separate out the ownership relationship into its own relation, as:
Customers(ssNo, name, address, phone) Accounts(number, type, balance) Owns(ssNo, number)Unlike the ODL-to-relation conversion, this approach avoids redundantly saying the address, phone, and so on, of the customers who have more than one account.
Person(name, mother, father, childrenOfFemale, childrenOfMale, children, parentsOf)However, in general, we only need to represent one direction of each pair of inverse relationships, so we should pick one direction only. The natural choice is to pick the simple concepts mother, father, and children. That gives us the preferred relation:
Person(name, mother, father, children)Incidentally, if we worked from the E/R diagram of Exercise 2.2.7(a) we would get the relations:
Person(name) Family(personName, motherName, fatherName)The first relation represents the entity set People. Its attributes are the key
name and any other attributes
that we might have about people.
The relation Family represents the relationship and consists of the keys
for People in its three roles: the person, the mother, and the father.
We need to distinguish these attributes by giving them names that
reflect their roles.Note: if People really had only the attribute name, then the relation People would be unnecessary. We could get the set of people from Family.
The design from an E/R diagram again avoids redundancy in the case that a person has several children, but it does divide information about people into two relations.
Customers(ssNo, name, address, phone) Flights(number, day, aircraft) Bookings(ssNo, number, day, row, seat)Being a weak entity set, Bookings' relation has the keys for Customers and Flights and Bookings' own attributes.
Notice that the relations obtained from the toCust and
toFlt relationships are unnecessary.
They are:
toCust(ssNo, ssNo1, number, day) toFlt(ssNo, number, day, number1, day1)That is, for toCust, the key of Customers is paired with the key for Bookings. Since both include
ssNo, this attribute is repeated with
two different names, ssNo and ssNo1.
A similar situation exists for toFlt.
Ships(name, yearLaunched) SisterOf(name, sisterName)
Depts(name, chair)
Courses(number, deptName, room)
LabCourses(number, deptName, allocation)
For part (b), LabCourses gets all the attributes of Courses, as:
Depts(name, chair)
Courses(number, deptName, room)
LabCourses(number, deptName, room, allocation)
And for (c), Courses and LabCourses are combined, as:
Depts(name, chair)
Courses(number, deptName, room, allocation)
Ship(name, displacement, type)
Gunship(name, displacement, type, numberOfGuns, bore)
Carrier(name, displacement, type, deckLength, airGroup)
Submarine(name, displacement, type, maxSafeDepth)
Battlecarrier(name, displacement, type, numberOfGuns, bore,
deckLength, airGroup)
Ship(name, displacement, type) Gunship(name, numberOfGuns, bore) Carrier(name, deckLength) Submarine(name, maxSafeDepth) AirGroupOf(name, airGroup)Note that the relation AirGroupOf connects carriers to their air groups. There would be another relation for the unseen entity set AirGroups.
Also note that there is no relation for battlecarriers. Their information would be obtained from Ship, Gunship, Carrier, and AirGroupOf.
For the single attributes we have A+ = A, B+ = B, C+ = ACD, and D+ = AD. Thus, the only new dependency we get with a single attribute on the left is C->A.
Now consider pairs of attributes. AB+ = ABCD, so we get new dependency AB->D. AC+ = ACD, and AC->D is nontrivial. AD+ = AD, so nothing new. BC+ = ABCD, so we get BC->A, and BC->D. BD+ = ABCD, giving us BD->A and BD->C. CD+ = ACD, giving CD->A.
For the triples of attributes, ACD+ = ACD, but the closures of the other sets are each ABCD. Thus, we get new dependencies ABC->D, ABD->C, and BCD->A.
Since ABCD+ = ABCD, we get no new dependencies.
The collection of 11 new dependencies mentioned above is: C->A, AB->D, AC->D, BC->A, BC->D, BD->A, BD->C, CD->A, ABC->D, ABD->C, and BCD->A.
| A | B |
|---|---|
| 0 | 2 |
| 1 | 2 |
We also learned that the three keys were AB, BC, and BD. Thus, any dependency above that does not have one of these pairs on the left is a BCNF violation. These are: C->A, C->D, D->A, AC->D, and CD->A.
One choice is to decompose using C->D. That gives us ABC and CD as decomposed relations. CD is surely in BCNF, since any two-attribute relation is. ABC is not in BCNF, since AB and BC are its only keys, but C->A is a dependency that holds in ABCD and therefore holds in ABC. We must further decompose ABC into AC and BC. Thus, the three relations of the decomposition are AC, BC, and CD.
Since all attributes are in at least one key of ABCD, that relation is already in 3NF, and no decomposition is necessary.
One possible BCNF decomposition is AB and BCD. AB is the only key for AB, and B is the only key for BCD.
Since there is only one key for ABCD, the 3NF violations are the same, and so is the decomposition.
For the singletons, A+ = A, B+ = B, and C+ = ACE. Thus, we discover the nontrivial dependency C->A for ABC.
For the pairs, we have AB+ = ABCDE, AC+ = ACE, and BC+ = ABCDE. That gives us AB->C and BC->A for ABC.
The nontrivial dependencies for ABC are thus C->A, AB->C, and BC->A. Of course BC->A can be inferred from C->A, so it is sufficient to take C->A and AB->C as the dependencies for ABC.
First, people have unique Social Security numbers and unique birthdates. Thus, we expect the functional dependencies ssNo->name and ssNo->birthdate hold. The same applies to children, so we expect childSSNo->childname and childSSNo->childBirthdate. Finally, an automobile has a unique brand, so we expect autoSerialNo->autoMake.
There are two multivalued dependencies that do not follow from these functional dependencies. First, the information about one child of a person is independent of other information about that person. That is, if a person with social security number s has a tuple with cn,cs,cb, then if there is any other tuple t for the same person, there will also be another tuple that agrees with t except that it has cn,cs,cb in its components for the child name, Social Security number, and birthdate. That is the multivalued dependency
Similarly, an automobile serial number and make are independent of any of the other attributes, so we expect the multivalued dependency
ssNo -> name birthdate childSSNo -> childName childBirthdate autoSerialNo -> autoMake ssNo ->-> childSSNo childName childBirthdate ssNo ->-> autoSerialNo autoMake
{ssNo, name, birthdate}
{ssNo, childSSNo}
{childSSNo, childName childBirthdate}
{ssNo, autoSerialNo}
{autoSerialNo, autoMake}
An initial decomposition based on the two multivalued dependencies would
give us
{ssNo, name, birthDate}
{ssNo, childSSNo, childName, childBirthdate}
{ssNo, autoSerialNo, autoMake}
Functional dependencies force us to decompose the second and third of
these.
In conclusion, we started with tuples xyzw and xy'z'w' and showed that xyzw' and xy'z'w must also be in the relation. That is exactly the statement of the MVD X ->-> Y-union-Z. Note that the above statements all make sense even if there are attributes in common among X, Y, and Z.