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.

Index and Graders
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

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:

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

Manf(name, addr)
PianoType(name, height, length, width)
PianoModel(ManfName, TypeName, price)
Electronic(ManfName, TypeName, power, processor)
Traditional(ManfName, TypeName, wood)

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

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

Problem 2

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

There are 21 superkeys.
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},

The basis for decomposed relations is:
R1(A, B) {B->A, A->B}
R2(A, C, D, E){A->C, C->A, D->E, E->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:
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.
         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);
     Answer(ID) := PROJ_ID(R5);

Part (d)

     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);
     Answer(author) = AllAuthors - MiloAuthors;

Notice how important it is that you subtract sets of authors. If you subtract before projecting onto authors, you get only authors whose every article had only keyword ``Milosevic'' or something like that.

Part (g)

Modification in SQL refers only to insertion, deletion, and update, not to altering the schema. In this case, you had to use an update.
     UPDATE Articles
     SET text = headline
     WHERE text IS NULL;

One of the saddest things was people who came up with some really clever ways to detect that a tuple had NULL text, and lost significant amounts of credit for violating the requirement that their solutions be as simple as possible. The fact is that there is a straightforward way, given above, for testing whether a value is NULL.