# CS145 Final Exam Solutions

### Index

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

### Problem 1: (c)

R INTERSECT R is R, with duplicates eliminated.

### Problem 2: (b)

Q1 asks for the topics of classes that have any two students with different names. Q2 asks for the same, but produces the topic of the class once for every pair of students in the class that have different names.

### Problem 3: (a)

In both queries, the condition in the if-clause asks whether the sequence \$a/B is empty.

### Problem 4: (a)

Q2 is the direct translation of Q1 from Datalog to recursive SQL. Note that Datalog produces sets, and the UNION operator in SQL also produces sets as a default.

### Problem 5: (d)

There is no relationship between the tuples in S and the tuples referred to by R.d.

### Problem 6: (c)

Q1 produces all pairs of a first component from some tuple r of R paired with the second component of some tuple s from from S. Q2 produces that pair if and only if r has a second component that agrees with the first component of s.

### Problem 7: (c)

The projection of R onto AB is the three tuples {12, 12, 32}. The projection onto BC is {23, 23, 21}. After renaming, the join asks for pairs where the second component of tuples in the first group is less than the second component of the second group. Thus, each of the three tuples of the first group joins with the first two tuples of the second group, {23, 23}, but not with the third tuple, 21, of the second group. Thus, the result is {1223, 1223, 1223, 1223, 3223, 3223}.

### Problem 8: (a)

The database schema is E(a,b,c), F(c,d), G(a,c,e), H(g,h), and S(a,c,f,g).

### Problem 9: (a)

There are only two Cars (as opposed to Trucks) manufactured by Toyota. (b) produces the three Model elements for the Azera, Camry, and Tundra. (c) produces three copies of the string "Toyota," for the three Cars and Trucks with manf="Toyota".

### Problem 10: (b)

The problem with (b) is that there can be only one Car element after the Truck elements, and the document has two Car elements after the Truck element.

### Problem 11: (a)

Since there are no curly braces in the return-clause, the result has literal strings like \$c/@manf. "Toyota" does not appear at all.

### Problem 12: (b)

The first line of the where-clause produces student C, and the second line of the where-clause produces student A. Since both parts of the where-clause compare cs145_grade with a value, student B, with NULL in that component, cannot be returned.

### Problem 13: (a)

The relation satisfies A->->BC, because it is a trivial dependency for any relation with schema ABC. It does not satisfy A->->B, because if we swap B's in the two tuples, we get tuples that are not in relation (a). (b) and (d) cannot be counterexamples, because they satisfy A->->B, and (c) cannot be a counterexample because it doesn't satisfy A->->BC.

### Problem 14: (a)

Since there is no FD with only A on the left, we never get started when trying to compute A+.

### Problem 15: (c)

II was a challenge-problem exercise, and III is a consequence of Algorithm 3.26 (synthesis for 3NF). I does not hold, as discussed in Example 3.25.

### Problem 16: (d)

Algorithm 3.20 is a lossless-join decomposition into BCNF (and thus into 3NF as well, although Algorithm 3.26 can also serve for that purpose. Algorithm 3.33 is a lossless-join decomposition into 4NF.

### Problem 17: (b)

For II, the two tuples inserted join to give the desired tuple in the view. However, in I, the two tuples both have NULL in the join attributes, and so cannot join with any tuple. Neither affects the view at all.

### Problem 18: (a)

I is false; a many-many relationship is represented by a diamond and no arrows. II is true. III is nonsense. There are many examples of many-one relationships that do not support a weak entity set, e.g., the "favorite-beer" relationship discussed in class.

### Problem 19: (d)

An A can consist of one C followed by one or more B's, or zero or more B's and one C. The latter clearly leads to documents with the fewest elements, an A with one C-child and no B-children.

### Problem 20: (c)

We may be "trying" to count cars, but the query only counts tuples. Since counting an attribute ignores tuples that have NULL in that component, the result of the query is 3.

### Problem 21: (b)

A course has 0-10 remote students and 1-30 local students. Every student is exactly one of these. Thus, there must be at least one student, and there can be at most 40 students.

### Problem 22: (c)

The problem with (c) is that the tuples for RemoteStudent and LocalStudent don't have a name, and thus names cannot be related to years or the other attributes that remote or local students have.

### Problem 23: (a)

S(a,d) is never part of the database schema, because supporting relationships without attributes of their own are never part of the translation. D(a,c) is also part of neither translation, because the key for D is a, d, and f.

### Problem 24: (d)

In the E/R approach, it's D(a,c,d); in the OO approach it's D(a,b,c,d). In the nulls approach, there is one relation for R and all its subclasses, which includes all attributes: R(a,b,c,d,e).

### Problem 25: (d)

T2 must appear to be executed either completely before or completely after T1. If before, T2 produces the average of 40, 50, and 60 = 50. If after, T2 produces the average of 38, 50, 60, and 0 = 37.

### Problem 26: (a)

Singly quoted strings in PHP are treated literally, and there is no substitution for apparent variable names.

### Problem 27: (c)

First the delete statement causes all occurrences of B1 in Sells.Beer to be set to NULL. Then, the update statement causes the occurrences of B3 in Sells.Beer to be set to B4. Then, the query computes the sum of the Price values in the third, fourth, and fifth tuples of Sells --- those tuples where Beer is not NULL. This sum is 3+4+6 = 13.

### Problem 28: (b)

The outer subquery must be empty, which means that every Cars tuple must satisfy name=name OR price=price. The only way that condition is not satisfied is if name and price are both NULL.

### Problem 29: (c)

When we insert (3,4), the trigger causes the insertion of (2,5). Since 2*5 is not greater than 10, there is no third tuple inserted. On the other hand, the other choices to result in exactly three tuples. For example, inserting (3,5) triggers the insertion of (2,6), which triggers the insertion of (1,7), and nothing more.

### Problem 30: (d)

Choice (d) says that values must be strictly bigger than 1000 and strictly less than 99999. Both conditions are violated, by the first and third Cart_ID elements, respectively. Even one violation would be enough to make (d) the correct answer.

### Problem 31: (b)

Anything can appear in an aggregation, so I is OK. II is also OK, because both A and B are grouping attributes. But III is not OK, because C and D are neither aggregated nor grouping attributes.

### Problem 32: (a)

A+ = ABCDE, so A is a key. AB is not a key, since there is a proper subset (A) that is a key. Neither is CD a key. Even though CD+ = ABCDE, there is a proper subset, D, that is a key.

### Problem 33: (c)

R has sets at both ends, so it is many-many. T has sets at neither end, so it is 1-1. The same is true for U, which is self-inverse. Finally, S has a set at one end, but not the other, so it is many-1.

### Problem 34: (d)

If the first three FD's, A->BCD, BC->A, and CD->B hold, then A, BC, and CD are all keys, so R is in BCNF. Moreover, the fourth FD, D->C must not hold, or else BCNF is violated. If A->BCD, BC->A, and D->C hold, then A and BD are keys. If so, CD->B would violate BCNF if it held. Similar reasoning rules out the other two possibilities.

### Problem 35: (c)

The grants leave us with a grant diagram that looks like:

```     CP<---DP*<---AP**--->BP*<-->CP*
```
The double-arrow line between BP* and CP* represents arcs in both directions. The first Revoke severs the arc from AP** to BP*, which cuts off that node and CP* as well. The second Revoke has no effect, because D has granted P to C. Thus, AP** reaches DP* and CP, resulting in privilege P being held by A, C, and D.