CS145 Midterm Solutions

Note: Problems 1, 2, 3, and 4 were graded by Jeff, Claire, Edwina, and Ankur, respectively. 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. Winkler can deliver these notes and exams if you like.

Problem 1

Part A

I had in mind a solution in which Crimes had subclasses Felonies and Misdemeanors, but Fines and Jail Sentences did not have a superclass punishments. While Crimes provides a key for its subclasses, Punishments has no attributes and is therefore pointless. In fact, people who used such a class usually wound up violating one or more rules, e.g., they created an entity set with no key. See the Error-Codes key, below. Here was my solution:

interface Crime (key (name, degree)) {
	attribute string name;
	attribute int degree;
}

interface Misdemeanor:Crime {
	relationship Fine fine inverse Fine::forMis;
}

interface Felony:Crime {
	relationship Fine fine inverse Fine::forFel;
	relationship Jail:jail inverse Jail::forFel;
}

interface Fine (key amount) {
	attribute int amount;
	relationship Set forMis inverse Misdemeanor::fine;
	relationship Set forFel inverse Felony::fine;
}

interface Jail (key (min, max)) {
	attribute int min;
	attribute int max;
	relationship Set forFel inverse Felony::jail;
}

However, I was improved upon by a number of members of the class. First, since every crime can have a fine, we can move the two fine relationships into Crime and dispense with subclass Misdemeanor altogether. Even better, we can recognize that even though the problem statement suggested that fines and jail sentences were ``important'' classes, in fact they are just numbers or pairs of numbers, and thus can be incorporated into the crimes for which they are the punishment. Thus, I really liked the following solution:

interface Crime (key (name, degree)) {
	attribute string name;
	attribute int degree;
	attribute int fine;
}

interface Felony:Crime {
	attribute int minJail;
	attribute int maxJail;
}

Part B

From my original solution you get

Felony(name, degree, fineAmt, minJail, maxJail)
Misdemeanor(name, degree, fineAmt)

If you used the second solution, you would get the same thing, but misdemeanor would be called Crime.

The requirement that you eliminate relations whose schema was a subset of another eliminates the relation Crime(name, degree). That is definitely appropriate in this problem, because the statement makes it clear that there are no crime objects that are not felonies or misdemeanors.

However, in general there may be some confusion over my intent when I asked you to eliminate subsets. In one sense, we can call the atributes anything we want, so any relation could be said to have a schema that is a subset of any other relation with at least as many attributes. But that is not an appropriate interpretation. You need to focus on the intent of the attributes. Thus, for example, if you added to the solution above a relation for class Jail, such as Jail(min,max), it should be regarded as a subset of Felony, even though the attribute names are different. Conversely, Misdemeanor above is not a subset of Felony, because even though the attributes are a subset, the intent is different; one talks about only misdemeanors and the other only about felonies.

Part C

Here is the E/R diagram corresponding to my first solution. And for the second, simpler solution we get the following E/R diagram.

Part D

The first solution yields:

FelJail(name, degree, min, max)
FelFine(name, degree, amount)
MisFine(name, degree, amount)

Again, we should not combine the last two, because they distinguish between a misdemeanor and a felony for which there is only a fine.

For the second solution, we would get:

Crimes(name, degree, fine)
Felonies(name, degree, min, max)

Notice that here we cannot distinguish between a felony with only a fine and a misdemeanor, but that is probably a small price to pay for the simplicity.

Error Codes

Here are the crimes and the punishments.

A: Not declaring keys for Fine and Jail classes or E.S. (-2)

B: Treating Fines and jail sentences as if they were for unique crimes, e.g., making them weak E.S. or having a one-one relationship between crimes and punishments. (-2)

C: Including (in parts b or d) a relation schema that is a logical subset of another. (-1, each instance)

D: Creating a punishment class or E.S. This error could involve a number of mistakes, including creating a needless intermediate, a class or E.S. with no properties, or an E.S. without a key. (-3)

E: No Crimes class or E.S. (-3)

F: Not following the required strategy (ODL-to-rel or E/R-to-rel) in parts b or d. (-5, each)

G: Inventing unnecessary ID fields (usually in E/R, but sometimes in ODL). (-2)

H: Allowing only one punishment (either a fine or jail, but not both) or allowing any number of punishments (typically creating a many-many relationship between crimes and punishments). (-4)

I: Adding a type attribute to Crimes. (-1)

J: No Felony/Misdemeanor distinction or no Jail/Fine distinction. (-3)

K: Allowing jail for a misdemeanor. (-3)

L: Representing a relationship in both directions in part b. (-2)

Problem 2

(1) (5pt.): Minimal Key for R: (A, B, D)
(2) (5pt.): Minimal Basis for R1: AB->C
* Take off 1pt. if not minimal (e.g., more stuff added).
(3) (5pt.): Minimal Basis for R2: AD->E, ABE->F
* Take off 2pt. for missing one FD.
* Take off 1pt. if not minimal (e.g., more stuff added).
(4) (5pt.): Key(s) for R2: (A, B, D).
(5) (5pt.): BCNF violation in R2: AD->E
Decomposition: S(A, D, E) and T(A, B, D, F)
(6) (5pt.): Both S and T are in BCNF.
S has one FD: AD->E, and AD is the key. No BCNF violation.
T has one FD: ABD->F, and ABD is the key. No BCNF violation.

Problem 3

(a)

(b)

(c)

The more common errors were:
- not using PI to list just the platform or the os pair
- not indicating how the relations join
- expressions that were more complicated than necessary
- not eliminating pairs of the form (i,i) in part c
- not renaming AppOS in part c
- using AppOS in parts a and c
If a pair (i,j) was listed in part c, then (j,i) shouldn't have been listed -- < or > should have been used in comparing the two os's. However, <> was accepted.

Problem 4

a) SELECT os
   FROM AppOs
   WHERE os LIKE '%IX'

   A : Trying to use join with OsPlat : -2

b) (SELECT os FROM AppOs)
        EXCEPT
   (SELECT os FROM OsPlat)

c) SELECT platform
   FROM OsPlat
   GROUPBY platform
   HAVING COUNT(os) = 1

d) SELECT platform
   FROM OsPlat as O1
   WHERE NOT EXISTS (SELECT O2.platform
                     FROM OsPlat as O2
                     WHERE O2.platform = O1.platform AND
                           O2.os <> O1.os)

   A : Not a succinct query : -1