CS145 Midterm Solutions

Note: Problem 1 was graded by Jeff. Brian did 2. Srinivas was responsible for 3a-c and Roy for 3d-f. Jim did 4. 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. Siroker can deliver these notes and exams if you like.


Problem 1



(c) Key attributes are in caps.

     Manfs(NAME, addr, phone)
     Products(MANF, MODEL#, type)
     Orders(ORDER#, date)
     Customers(SSNO, email, addr)
     PlacedBy(ORDER#, ssNo)
     LineItem(ORDER#, MANF, MODEL#, quantity)

Optionally, Orders and PlacedBy can be combined into one BCNF relation.

(d) The nontrivial FD's are ssNo->email addr and email->ssNo addr. Notice that it is only when we talk about FD's that the fact that email is an alternative key becomes expressible. The keys for the relation are {ssNo} and {email}.

Error Codes

1A (-2): Including superkeys in part (d).

1B (-1): In (b), treating Products as if it were a ``weak'' LRT, typically giving it a manufacturer attribute.

1C (-2): In (b), failing to handle the many-many relationship between orders and products correctly.

1D (-2): In (a), not making Products weak.

1E (-1): IN (b), declaring model# to be a key for Products.

1F (-1, each occurrence): Not including manf as part of the key for products.

1G (-1): Including ssNo in the key for PlacedBy (the relation between orders and customers).

1H (-2): In (d) failing to see that email is a key.

1I (-1): In (a), not making the relationship between orders and products many-many.

1J (-1, each occurrence up to 2): Using both ssNO and email as a joint key for Customers. Note that underlining them both means that they together form a key, but neither does by itself, which is false.

1K (-2): In (a), making a 3-way relationship among customers, orders, and products. Note that this relationship is more precisely expressed by two 2-way relationships.

1L (-1, each occurrence): One relation schema is a subset of another, and its instance is expected to be a projection of the latter's.

1M (-1): Using the E/R notation for attributes in the network diagram.

1N (-2): Omitting keys and attributes in (b).

1P: (-1, each occurrence up to 2): Allowing only one quantity per order, instead of one quantity for each order-product pair.

1Q (-2): In (a), making Orders a relationship instead of an entity set.

Problem 2

Problem 2a.
PROJECT_{type} ( SELECT_{name='Lee'} 
                 ( Accounts NATURALJOIN Owns NATURALJOIN Customers ) ) 

Problem 2b.

( PROJECT_{type, balance} ( Accounts ) ) -
  ( PROJECT_{A1.type, A1.balance}
      ( SELECT_{A1.type==A2.type AND A1.balance < A2.balance}
        ( ( RHO_{A1} Accounts ) CROSS ( RHO_{A2} Accounts ) ) ) )

Problem 2c.

/* Account numbers that do not appear in the owns relation */

R1 = ( PROJECT_{acctNo} Accounts ) - ( PROJECT_{acctNo} Owns )

/* Account numbers of accounts that appear in both the accounts and
   owns relations but do not have at least one related customer in the
   customer relation */

R2 = ( PROJECT_{acctNo} ( Owns NATURALJOIN Accounts) ) -
       ( PROJECT_{acctNo} ( Owns NATURALJOIN Customers ) )

Answer: R1 UNION R2
Here are the common problems and their abbreviations for number 2:

SM: Schema Mismatch. You cannot subtract, union, etc relations with mismatching schemas. -1

AA: Ambiguous Attribute. I cannot tell which relation an attribute belongs to, e.g., in SELECT_{acctNo) ( Accounts CROSSPRODUCT Accounts ) acctNo is ambiguous; use renaming to disambiguate. -1

EC: Exceedingly Complex. Usually occurs when a student joins, crosses or unions unnecessary relations into their result. If the extra stuff caused the wrong answer, of course, I took off more. If the query was still correct, I took off -1.

DAZC: Dangling Accounts have Zero Customers. On 2c, a common mistake was to find the accounts in owns for which at least one of the owners did not exist in the customers relation (which allows that other owners of the same account may exist in customers) instead of finding accounts in owns where zero of the owners occurred in the customers relation. The question specifically defines a dangling account as either not existing in Owns or existing in Owns but _every_ owner fails to appear in customers. -1

RA: In various places, I found it useful to use RA as an abbreviation for Relational Algebra, as in "Use RA here, not SQL".

Problem 3a-c

Problem 3d-f

Problem 4

Part a) The keys are: abd, abe, bcd, and bce.

Part b) There were four possible answers for this part. Any of them were fine: