Solutions for Section 3.6

Exercise 3.6.1(a)

In the solution to Exercise 3.5.1 we found that there are 14 nontrivial dependencies, including the three given ones and 11 derived dependencies. These are: C->A, C->D, D->A, AB->D, AB-> C, AC->D, BC->A, BC->D, BD->A, BD->C, CD->A, ABC->D, ABD->C, and BCD->A.

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.

Exercise 3.6.1(b)

(Revised 1/19/02) The only key is AB. Thus, B->C and B->D are both BCNF violations. The derived FD's BD->C and BC->D are also BCNF violations. However, any other nontrivial, derived FD will have A and B on the left, and therefore will contain a key.

One possible BCNF decomposition is AB and BCD. It is obtained starting with any of the four violations mentioned above. 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.

Solutions for Section 3.7

Exercise 3.7.1

Since A->->B, and all the tuples have the same value for attribute A, we can pair the B-value from any tuple with the value of the remaining attribute C from any other tuple. Thus, we know that R must have at least the nine tuples of the form (a,b,c), where b is any of b1, b2, or b3, and c is any of c1, c2, or c3. That is, we can derive, using the definition of a multivalued dependency, that each of the tuples (a,b1,c2), (a,b1,c3), (a,b2,c1), (a,b2,c3), (a,b3,c1), and (a,b3,c2) are also in R.

Exercise 3.7.2(a)

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

ssNo->->childSSNo childName childBirthdate

Similarly, an automobile serial number and make are independent of any of the other attributes, so we expect the multivalued dependency ssNo->->autoSerialNo autoMake The dependencies are summarized below: ssNo -> name birthdate

childSSNo -> childName childBirthdate autoSerialNo -> autoMake

ssNo ->-> childSSNo childName childBirthdate ssNo ->-> autoSerialNo autoMake

Exercise 3.7.2(b)

We suggest the relation schemas

{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.

Exercise 3.7.3(a)

Since there are no functional dependencies, the only key is all four attributes, ABCD. Thus, each of the nontrvial multivalued dependencies A->->B and A->->C violate 4NF. We must separate out the attributes of these dependencies, first decomposing into AB and ACD, and then decomposing the latter into AC and AD because A->->C is still a 4NF violation for ACD. The final set of relations are AB, AC, and AD.

Exercise 3.7.7(a)

Let W be the set of attributes not in X, Y, or Z. Consider two tuples xyzw and xy'z'w' in the relation R in question. Because X ->-> Y, we can swap the y's, so xy'zw and xyz'w' are in R. Because X ->-> Z, we can take the pair of tuples xyzw and xyz'w' and swap Z's to get xyz'w and xyzw'. Similarly, we can take the pair xy'z'w' and xy'zw and swap Z's to get xy'zw' and xy'z'w. 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.

Exercise 3.7.8(a)

Consider a relation R with schema ABCD and the instance with four tuples abcd, abcd', ab'c'd, and ab'c'd'. This instance satisfies the MVD A ->-> BC. However, it does not satisfy A ->-> B. For example, if it did satisfy A ->-> B, then because the instance contains the tuples abcd and ab'c'd, we would expect it to contain abc'd and ab'cd, neither of which is in the instance.

Database Systems: The Complete Book

Solutions for Chapter 4

Solutions for Section 4.2

Exercise 4.2.1

class Customer {

attribute string name; attribute string addr; attribute string phone; attribute integer ssNo;

relationship Set ownsAccts inverse Account::ownedBy; }

class Account {

attribute integer number; attribute string type; attribute real balance;

relationship Set ownedBy inverse Customer::ownsAccts }

Exercise 4.2.4

class Person {

attribute string name;

relationship Person motherOf

inverse Person::childrenOfFemale relationship Person fatherOf inverse Person::childrenOfMale relationship Set children

inverse Person::parentsOf

relationship Set childrenOfFemale inverse Person::motherOf

relationship Set childrenOfMale inverse Person::fatherOf relationship Set parentsOf inverse Person::children

}

Notice that there are six different relationships here. For example, the inverse of the relationship that connects a person to their (unique) mother is a relationship that connects a mother (i.e., a female person) to the set of her children. That relationship, which we call childrenOfFemale, is different from the children relationship, which connects anyone -- male or female -- to their children.

Exercise 4.2.7

A relationship R is its own inverse if and only if for every pair (a,b) in R, the pair (b,a) is also in R. In the terminology of set theory, the relation R is ``symmetric.'' Solutions for Section 4.3

Exercise 4.3.1

We think that Social Security number should me the key for Customer, and account number should be the key for Account. Here is the ODL solution with key and extent declarations. class Customer

(extent Customers key ssNo) {

attribute string name; attribute string addr; attribute string phone;

attribute integer ssNo;

relationship Set ownsAccts inverse Account::ownedBy; }

class Account

(extent Accounts key number) {

attribute integer number; attribute string type; attribute real balance;

relationship Set ownedBy inverse Customer::ownsAccts }

Solutions for Section 4.4

Exercise 4.4.1(a)

Since the relationship between customers and accounts is many-many, we should create a separate relation from that relationship-pair.

Customers(ssNo, name, address, phone) Accounts(number, type, balance) CustAcct(ssNo, number)

Exercise 4.4.1(d)

Ther is only one attribute, but three pairs of relationships from Person to itself. Since motherOf and fatherOf are many-one, we can store their inverses in the relation for Person. That is, for each person, childrenOfMale and childrenOfFemale will indicate that persons's father and mother. The children relationship is many-many, and requires its own relation. This relation actually turns out to be redundant, in the sense that its tuples can be deduced from the relationships stored with Person. The schema:

Persons(name, childrenOfFemale, childrenOfMale) Parent-Child(parent, child)

Exercise 4.4.4

You get a schema like:

Studios(name, address, ownedMovie)

Since name -> address is the only FD, the key is {name, ownedMovie}, and the FD has a left side that is not a superkey.

Exercise 4.4.5(a,b,c)

(a) Struct Card { string rank, string suit }; (b) class Hand {

attribute Set theHand;

};

For part (c) we have:

Hands(handId, rank, suit)

Notice that the class Hand has no key, so we need to create one: handID. Each hand has, in the relation Hands, one tuple for each card in the hand.

Exercise 4.4.5(e)

Struct PlayerHand { string Player, Hand theHand }; class Deal {

attribute Set theDeal; }

Alternatively, PlayerHand can be defined directly within the declaration of attribute theDeal. Exercise 4.4.5(h)

Since keys for Hand and Deal are lacking, a mechanical way to design the database schema is to have one relation connecting deals and player-hand pairs, and another to specify the contents of hands. That is:

Deals(dealID, player, handID) Hands(handID, rank, suit)

However, if we think about it, we can get rid of handID and connect the deal and the player directly to the player's cards, as: Deals(dealID, player, rank, suit)

Exercise 4.4.5(i)