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

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

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)

Manf(name, addr)

PianoType(name, height, length, width)

PianoModel(ManfName, TypeName, price)

Electronic(ManfName, TypeName, power, processor)

Traditional(ManfName, TypeName, wood)

(c)

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:

• 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:

Relation	Basis
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

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)

     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);
     Answer(ID) := PROJ_ID(R5);

Part (d)

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

Part (e)

     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)

     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.