CS145 Midterm Examination

Please read all instructions (including these) carefully.

The exam is open book and open notes; any written materials may be used.

There are four parts on the exam, with a varying number of points for a total of 75 points.
There are also two extra-credit questions with a total of 10 points. You should look through
the entire exam before getting started, in order to plan your strategy. You have 75 minutes to
complete the exam.

There is no penalty for guessing multiple-choice questions. For short-answer questions,

simplicity and clarity of solutions will count. You may get as few as 0 point for a problem if
your solution is far more complicated than necessary.

Unless otherwise specified, assume that all relations are duplicate-free in questions not re-
lated to SQL. All questions about SQL refer to the SQL2 or SQL3 standard, not necessarily
to the Oracle implementation of SQL used in programming assignments.

NAME:

In accordance with both the letter and spirit of the Honor Code, I have neither given nor received
assistance on this examination.

SIGNATURE:

Part Max points Points

I 20
II 24 (+4)
III 16
IV 15 (+6)
TOTAL 75 (+10)

Jun Yang 1 CS145 Spring 1999

Part I. E/R, ODL, and Basic Relational Design (20 points)

Question 1: (4 points) Below is an ODL specification:

interface A { interface B { interface C {
relationship Set<B> R relationship Set<A> R relationship Set<B> S
inverse B::R; inverse A::R; inverse B::S;
relationship C T relationship C S relationship A T
inverse C::T; inverse C::S; inverse A::T;
}; }; };
For simplicity, all attributes are omitted. Which one of the E/R diagrams below best captures the
intent of the ODL specification above?

A R B A R B

(A) T S (B) T S

C C

A R B A R B

(C) T S (D) T S

C C

Answer:

Question 2: (4 points) Consider the following E/R diagram.

A B

C D
Suppose the key of entity set A is attribute , the key of B is , the key of C is , and the key of
D is . If we translate relationship set R into a relation , what are all the keys of ?
(A)
(B) , , and
(C)
(D) , , and
Answer:

Jun Yang 2 CS145 Spring 1999

Questions 3–5 below refer to the following E/R design for a database that keeps track of buildings,
rooms, and in particular, conference rooms.

capacity number area name year

ConferenceRooms ISA Rooms In Buildings

Question 3: (4 points) Suppose that we convert the above E/R diagram into relations using the
E/R-style translation for subclasses. What will we get for the ConferenceRooms entity set?
(A) ConferenceRoom(capacity)
(B) ConferenceRoom(room number, capacity)
(C) ConferenceRoom(building name, room number, capacity)
(D) ConferenceRoom(building name, room number, area, capacity)
Answer:

Question 4: (4 points) Suppose that we have specified an ODL schema that captures the design
of the above E/R diagram. We then convert the ODL schema into three relations BuildingODL ,
RoomODL , and ConferenceRoomODL , using the ODL-style translation for subclasses. Suppose
there are rooms in the database, and among these, are conference rooms. How many tuples
are in relations RoomODL and ConferenceRoomODL , respectively?
(A) and (B) and (C) and (D) 0 and
Answer:

Question 5: (4 points) Which of the following statements are true according to the constraints
encoded by the E/R diagram above? Do not make any assumptions other than those encoded by
the E/R diagram.
I. The number of entities in the Rooms entity set must be greater than or equal to the number
of entities in the ConferenceRooms entity set
II. The number of entities in the Rooms entity set must be greater than or equal to the number
of entities in the Buildings entity set
(A) I only (B) II only (C) Both I and II (D) Neither I nor II
Answer:

Jun Yang 3 CS145 Spring 1999

Part II. FD’s and BCNF (24 (+4) points)

Question 6: (4 points) In the instance of the relation shown below, which of the
following functional dependencies (FD’s) hold?

1 2 3 4 5
1 4 3 4 5
1 2 4 4 1

I. II. III.
(A) I only (B) II only (C) I and III only (D) II and III only
Answer:

Questions 7–9 below refer to a relation with the FD’s:

Question 7: (4 points) What are all the keys of ?

(A)
(B) and
(C)
(D) and
Answer:
Question 8: (4 points) is a BCNF violation for . Suppose we decide to decompose
into and . Which of the following statements are true?
I. is a minimal basis for the FD’s that hold in
II. is a BCNF violation for
III. should be decomposed further into and
(A) I only (B) II only (C) I and II only (D) II and III only (E) I, II, and III
Answer:
Question 9: (4 points) Which of the following statements are true?
I. Instead of decomposing using , we could decompose using first
II. It does not matter whether we start with first or first: at the end of the
BNCF decomposition algorithm we will get the same set of relations
(A) I only (B) II only (C) Both I and II (D) Neither I nor II
Answer:

Jun Yang 4 CS145 Spring 1999

Questions 10–12 below refer to a relation with the following FD’s:

Unfortunately we don’t know what is—it could be any nonempty subset of ’s attributes. (In
particular, might even contain itself, which would make a trivial dependency.)

Question 10: (4 points) Which of the following must be true regardless of what is inside ?
(A) Every key of contains
(B) No key of contains
(C) Some key of contains while some other key does not
(D) None of the above
Answer:

Question 11: (4 points) Which of the following must be true regardless of what is inside ?
(A) Every key of contains
(B) No key of contains
(C) Some key of contains while some other key does not
(D) None of the above
Answer:

Question 12: (4 points)[extra credit] Which of the following must be true regardless of what is
inside ?
I. If some key of contains , then some other key must contain
II. If some key of contains , then some other key must contain
(A) I only (B) II only (C) Both I and II (D) Neither I nor II
Answer:

Jun Yang 5 CS145 Spring 1999

Part III. Relational Algebra and SQL: Multiple-Choice Questions (16 points)

Question 13: (4 points) Suppose that two relations and have exactly the same
schema. Which of the following equalities hold in relational algebra?
I.
II.
III.
(A) I only (B) I and II only (C) I, II, and III (D) None of the above
Answer:

Question 14: (4 points) Suppose we have two relations and with the same
schema. The only key of is ; the only key of is as well. Let relation be the
set union of and , i.e., . What are the keys of ?
(A) (B) (C) and (D)
Answer:

Jun Yang 6 CS145 Spring 1999

Questions 15 and 16 below refer to the following database schema:
Person(SSN, employerSymbol, salary)
Holding(SSN, symbol, numShares)
A person is uniquely identified by a social security number (SSN). A company is uniquely identi-
fied by its stock ticker symbol. Each person is employed by exactly one company, but may hold
any number of different stocks.

Question 15: (4 points) Suppose we wish to find the SSN’s of the persons who do not own stocks
of their employers. Which of the following queries will return the correct set of SSN’s?
I. SSN employerSymbol symbol Person Holding
II. SSN SSN sym P SSN sym sal Person SSN sym H SSN sym num Holding
III. SELECT SSN
FROM Person
WHERE employerSymbol <> ALL
(SELECT symbol FROM Holding WHERE Person.SSN = Holding.SSN);

(A) II only (B) I and II only (C) I and III only (D) II and III only
Answer:

Question 16: (4 points) Suppose we wish to find the average salary of the persons who own more
than 100 shares of Microsoft (MSFT) or more than 100 shares of Yahoo! (YHOO). Which of the
following queries will correctly compute the desired average?
I. SELECT AVG(salary)
FROM Person
WHERE SSN IN (SELECT SSN FROM Holding
WHERE (symbol = ’MSFT’ OR symbol = ’YHOO’)
AND numShares > 100);

II. SELECT AVG(salary)

FROM Person, Holding
WHERE Person.SSN = Holding.SSN
AND ((symbol = ’MSFT’ AND numShares > 100) OR
(symbol = ’YHOO’ AND numShares > 100));

(A) I only (B) II only (C) Both I and II (D) Neither I nor II
Answer:

Jun Yang 7 CS145 Spring 1999

Part IV. Relational Algebra and SQL: Short-Answer Questions (15 (+6) points)

Questions 17–20 below refer to the following database schema:

Person(SSN, employerSymbol, salary)
Holding(SSN, symbol, numShares)
StockPrice(symbol, date, price)
Person and Holding relations are identical to the ones used by Questions 15 and 16. We have
added a third relation StockPrice, which tracks the closing price (per share) of each stock on
each trading day.
Question 17: (5 points) Write a relational algebra query to find the SSN’s of all Informix (IFMX)
employees who own more than 50 shares of Oracle (ORCL) stock.

Question 18: (5 points) Write a SQL query to find the total number of shares of Oracle (ORCL)
stock owned by Informix (IFMX) employees.

Jun Yang 8 CS145 Spring 1999

Question 19: (5 points) Write a relational algebra query to find the ticker symbols of all “super-
stocks”. A superstock is a stock whose closing price always rises on every trading day. You may
compare date values using , , etc. (Hint: you do not need arithmetics on date values.)

Question 20: (6 points)[extra credit] Let us define a “widely-held” stock to be one that is owned
by more than 40% of the investors in our database. Write a SQL query to find the latest closing
price for each widely-held stock. Note that some quotes may be delayed: for example, the latest
closing price of Microsoft stored in our database might be one day old, while the latest closing
price of Macrohard might be two days old.

Jun Yang 9 CS145 Spring 1999