# CS145 Midterm Solutions

If, after reading the solutions and error keys, you want to discuss the grading, you should give your exam, with a note, to the relevant person. Ms. Bharwada can deliver these notes and exams if you like.

Part 1(a)Mayank
Parts 1(b) & 1(c)Calvin
Parts 2(a) & 2(b)Karen
Parts 2(c) & 2(d)Grace
Problem 3Jeff

### Problem 1

(a)
No, it is not possible to represent the fact that Steinway makes two different models of baby-grand piano. This is because PianoModel has as its key (Manf.name, PianoType.name). Thus, there can be only one entity with key as (Steinway, baby-grand piano).

The following are acceptable ways of modifying the ER diagram to make it possible:

• Add an attribute "modelNumber" to the entity set PianoModel, and make it part of the key.
• Assume that "price" for a model is unique across pianos of the same type and by the same manufacturer, and make it part of the key.

The following were some of the common errors, and the penalties thereof:

• Making price a part of the key without stating the assumption: -1 point
• Introducing "modelNumber" as an attribute of the PianoType entity set, and making it part of the key of the PianoType entity set. However, by doing so, the other attributes of the piano type would have to be duplicated for each different model of the same type: -2 points
• Introducing a 3-way relationship between Manf, PianoType, PianoModel: -3 points
• Introducing a 2-way relationship between Manf and PianoType: -3 points
• Making some other attribute of PianoType a part of its key: -3 points

(b)
PianoType(name, height, length, width)
PianoModel(ManfName, TypeName, price)
Electronic(ManfName, TypeName, power, processor)

(c)
PianoType(name, height, length, width)
PianoModel(ManfName, TypeName, price)
Electronic(ManfName, TypeName, price, power, processor)
ElectronicTraditional(ManfName, TypeName, price, power, processor, wood)

The following are keys to the error codes, as indicated on the corrected answer sheets:

• A1: missing ElectronicTraditional class (to represent pianos that are both electronic and traditional (OO approach): -2 points
• A2: missing "price" attribute in subclasses (OO approach): -2 points
• A3: missing keys, or incorrect keys: -1 for each occurance, -2 maximum
• A4: redundant attributes: -1 for each occurance, -2 maximum
• A5: missing relations: -1 for each occurance, -2 maximum
• A6: missing attributes: -1 for each occurance, -2 maximum
• A7: redundant relations: -1 for each occurance, -2 maximum

### Problem 2

(a)
The keys are {A,D}, {A,E}, {B,D}, {B,E}, {C,D}, {C,E}.

(b)
There are 21 superkeys.
Justification:
Each superkey has at least one attribute from {A,B,C} (2^3-1 = 7 ways), and at least one attribute from {D,E} (2^2-1 = 3 ways). Thus there are 7 x 3 superkeys. Note that keys are also superkeys.

Thus, enumerating the superkeys, we have:
{A,D}, {A,E}, {B,D}, {B,E}, {C,D}, {C,E},
{A,B,D}, {A,C,D}, {A,D,E}, {A,B,E}, {A,C,E}, {B,D,E}, {B,C,D}, {C,D,E}, {B,C,E},
{A,B,C,D}, {A,B,D,E}, {A,C,D,E}, {A,B,C,E}, {B,C,D,E},
{A,B,C,D,E}.

(c)
The basis for decomposed relations is:
RelationBasis
R1(A, B) {B->A, A->B}
R2(A, C, D, E){A->C, C->A, D->E, E->D}

(d)
A legal counterexample must follow all the functional dependencies of R, and violate AB->->CD. A counterexample could be the following instance of R:
A B C D E
1 1 1 1 1
1 1 1 0 0

### Problem 3

#### Error Codes

In general, syntax errors (e.g., missing parentheses) were worth -1; logic errors were worth a deduction of 2 or more, and if the query really didn't work for reasons that could not be explained by a single mistake, you got no credit. If you produced something slightly more complicated than needed, you lost 1 point, and the abbreviation MTC (-3) stands for ``much too complicated.'' Here are the other codes used:

A1: Checking all pairs, rather than just the inserted tuple against those previously in the relation (-3).

A2: Using an assertion rather than a tuple-based check (-5).

B1: Missing join term (-3).

C1: Forgetting that renaming requires atttributes as well as a new relation name (-1).

C2: Including Articles in the join (-1).

E1: No HAVING clause (-2).

E2: Failing to group by both author and keyword (-2).

E3: Putting an attribute that isn't in the GROUP BY into the SELECT list (-2).

F1: same as C1.

G1: Using = NULL instead of IS NULL (-1).

G2: Using ALTER instead of UPDATE (-3).

G3: Using a trigger (-5).

#### Part (a)

Because ID is a key for Articles, it is sufficient to check that the relation before the insertion or update does not have a tuple with the same dateline and author as the new tuple. Here is one way to do it.
```     CHECK(NOT EXISTS(
SELECT *
FROM Articles aa
WHERE dateline = aa.dateline AND author = aa.author
))
```

#### Part (b)

```     SELECT headline
FROM Articles, Keywords
WHERE Articles.ID = Keywords.ID AND keyword = 'Arafat';
```

#### Part (c)

```     R1(ID,k1) := Keywords;
R2(ID,k2) := Keywords;
R3(ID,k3) := Keywords;
R4(ID,k1,k2,k3) := R1 NATURALJOIN R2 NATURALJOIN R3;
R5(ID,k1,k2,k3) := SIGMA_{k1!=k2 AND k2!=k3 AND k1!=k3}(R4);
```

#### Part (d)

```     SELECT ID
FROM Articles
WHERE text LIKE '%Pol Pot%';
```

#### Part (e)

This question, although it appeared difficult, is actually a direct application of the definition of grouping and ``having.''
```     SELECT author, keyword, MIN(dateline)
FROM Articles, Keywords
WHERE Articles.ID = Keywords.ID
GROUP BY author, keyword
HAVING COUNT(*) >= 3;
```

#### Part (f)

```     R1(ID) = PROJ_{ID}(SIGMA_{keyword="Milosevic"}(Keywords);
MiloAuthors(author) = PROJ_{author}(R1 NATURALJOIN Articles);
AllAuthors(author) = PROJ_{author}(Articles);
```     UPDATE Articles