Answers for some exercises from Chapter 6

6.3. Referential-integrity constraints as defined in chapter 6 involve exactly two relations. Consider a database that includes the following relations:
salaried-worker(name,office,phone,salary)
hourly-worker(name,hourly-wage)
address(name,street,city)

Suppose that we wish to require that every name that appears in address appear in either salaried-worker or hourly-worker, but not necessarily in both.

a. Propose a syntax for expressing such constraints.
b. Discuss the actions that the system must take to enforce a constraint of this form.

Answer:

a. For simplicity, we present a variant of the SQL syntax. As part of the create table expression for address we include:
foreign key (name) references salaried-worker or hourly-worker
b. To enfore this constraint, whenever a tuple is inserted into the address relation, a lookup on the name value must be made on the slaried-worker relation and (if that lookup failed) on the hourly-worker relation (or vice-versa).

6.5. Suppose there are two relations r and s, such that the foreign key B of r references the primary key A of s. Describe how the trigger mechanism can be used to implement the on delete cascade option, when a tuple is deleted from s.

Answer:

We define triggers for each relation whose primary-key is referred to by the foreign-key of some other relation. The trigger would be activated whenever a tuple is deleted from the referred-to relation. The action performed by the trigger would be to visit all the referring relations, and delete all the tuples in them whose foreign-key attribute value is the same as the primary-key attribute value of the deleted tuple in the referred-to relation. These set of triggers will take care of the on delete cascade operation.

6.6. Write an assertion for the bank database to ensure that the asset value for the Perryridge branch is equal to the sum of all the amounts lent by the Perryridge branch.

Answer:

create assertion perryridge check
(not exist (select *
     from branch
     where branch-name = "Perryridge" and
        assets != (select sum (amount)
          from loan
          where branch-name = "Perryridge")))

6.8. List all functional dependencies satisfied by the following relation:

A B C

a1 b1 c1

a1 b1 c2

a2 b1 c1

a2 b1 c3

A	B	C
a1	b1	c1
a1	b1	c2
a2	b1	c1
a2	b1	c3

Answer:

The nontrivial functional dependencies are: A->B and C-> B, and a dependency they logically imply: AC->B. There are 19 trivial functional dependencies of the form a->b, where b in a. C does not functionally determine A because the first and third tuples have the same C but different A values. The same tuples also show B does not functionally determine A. Likewise, A does not functionally determine C because the first two tuples have the same A value and different C values. The same tuples also show B does not functionally determine C.

Answers for some exercises from Chapter 7

7.5.Show that the decomposition in exercise 7.2 is not a dependency-preserving decomposition.

Answer:

The dependency B->D is not preserved.
F1, the restriction of F to (A,B,C) is: A->ABC, A->AB, A->AC, A->BC, A->B, A->C, A->A, B->B, C->C, AB->AC, AB->ABC, AB->BC, AB->AB,AB->A, AB->B, AB->C, AC(same as AB), BC(same as AB), ABC(same as AB). F2, the restriction of F to (C,D,E) is:A->ADE, A->AD, A->AE, A->DE, A->A, A->D, A->E, D->D, E(same as A), AD, AE, DE, ADE(same as A). (F1 union F2)⁺ is easily seen not to contain B->D since the only functional dependency in F1 union F2 with B as the left side is B->B, a trivial functional dependency.

7.6. Show that it is possible to ensure that a dependency-preserving decomposition into 3NF is a lossless-join decomposition by guaranteeing that at least one schema contains a candidate key for the schema being decomposed. (Hint: Show that the join of all the projections onto the schemas decomposition cannot have more tuples that the original relation.)

Answer:

Let F be a set of functional dependencies that hold on a schema R. Let sigma={R₁,R₂,...,R_n} be a dependency-preserving 3NF decomposition of R. Let X be a candidate key for R.
Consider a legal instance r of R. Let j=Project_X(r) join Project_R₁(r) join Project_R₂(r) ... Join Project_{R_n}(r). We want to prove that r=j
We claim that if t₁ and t₂ are two tuples in j such that t₁[X]=t₂[X], then t₁=t₂. To prove this claim, we use the following inductive argument.
Let F'=F₁ union F₂ union ... union F_n, where each F_i is the restriction of F to the schema R_i in sigma. Consider the use of the algorithm given in figure 6.7 in the textbook to compute the closure of X under F'. We use induction on the number of times that the for loop in this algorithm is executed.

Basis: In the first step of the algorithm, result is assigned to X, and hence given that t₁[X]=t₂[X], we know that t₁[result]=t₂[result] is true.
Induction Step: Le t₁[result]=t₂[result] be true at the end of the k^th execution of the for loop.
Suppose the functional dependency considered in the k+1^th execution of the for loop is beta->gamma, and beta in result. beta in results implies that t₁[beta]=t₂[beta] is true. The fact that beta->gamma holds for some attribute set R_i in sigma, and that t₁[R_i] and t₂[R_i] are in Project_{R_i}(r) imply that t₁[gamma]=t₂[gamma] is also true. Since gamma is now added to result by the algorithm, we know that t₁[result]=t₂[result] is true at the end of k+1^th execution of the for loop.

Since sigma is dependency-preserving and X is a key for R, all attributes in R are in result when the algorithm terminates. Thus, t₁[R]=t₂[R] is true, that is, t₁=t₂ as claimed earlier.
Our claim implies that the size of Project_X(j) is equal to the size of j. Note also that Project_X(j) = Project_X(r) = r (since X is a key for R). Thus we have proved that the size of j equals that of r. We know that r in j. Hence we conclude that r=j.
Note that since X is trivially in 3NF, sigma union {X} is a dependency-preserving lossless-join decomposition into 3NF.

7.8.Give a lossless-join decomposition into BCNF of the schema R=(A,B,C,D,E) of exercise 7.2.

Answer:

From exercise 6.15 (solved in class), we know that B->D is nontrivial and the left hand side is not a superkey. By the algorithm 7.6 of the textbook (page 226), we derive the relations {(A,B,C,E), (B,D)}. This is in BCNF.

7.14. A functional dependency alpha->beta is called a partial dependency if there is a proper subset gamma of alpha such that gamma->beta. We say that beta is partially dependent on alpha. A relation schema R is in second normal form if each attribute A in R meets one of the following criteria:

it appears in a candidate key;
it is not partially dependent on a candidate key.

Show that every #NF schema is in 2NF. (Hint: Show that every partial dependency is a transitive dependency).

Answer:

Referring to the definitions given in exercise 7.13, a relation schema R is said to be in 3NF if there is no non-prime attribute A in R for which A is transitively dependent on a key for R. We can also rewrite the definition of 2NF given here as:
"A relation schema R is in 2NF if no non-prime attribute A is partially dependent on any candidate key for R."
To prove that every 3NF schema is in 2NF, it suffices to show that a non-prime attribute A is partially dependent on a candidate key alpha, then A is also transitively dependent on the key alpha.
Let A be non-prime attribute in R. Let alpha be a candidate key for R. Suppose A is partially dependent on alpha.

from the definition of a partial dependency, we know that for some proper subset beta of alpha, beta->alpha.
since beta in alpha, alpha->beta. Also beta->alpha does not hold, since alpha is a candidate key.
finally, since A is non-prime, it cannot be in either beta or alpha.

Thus we conclude that alpha->A is transitive dependency. Hence we have proved that every 3NF schema is also in 2NF.