Department of Computer and Information Science and Engineering

University of Florida

COP5725 Fall 2013

Exam I Solutions

Instructor: Dr. Daisy Zhe Wang

Mean 76.92 Median 78.50 Std. dev. 9.40

COP5725, Fall 2013 Exam I Page 1 of 7

I. [21 points] Database Design.

Suppose you and your friends are starting a social network service called “MyFriends”.
Now you are trying to design the database schema to store user information, which
should meet the following requirements:
• For every user, we record his/her name and a unique email address.
• People make friends with other people. A user may have zero or more friends.
• Each user owns a profile page and may post on his/her own or other people’s profile
pages. Each post contains some text and is identified by the author, the owner of the
page on which it appears, and the time-stamp. The posts are allowed to contain tags
that mention other people, e.g., using the @ syntax. Note we do not need to explicitly
record the profile pages since each page is uniquely associated with a user.
(1) [8 points] Draw an ER diagram for this database. Make sure to indicate primary
keys, cardinality constraints, weak entities, and participation constraints if any. List
the assumptions you make in the process.
Solution:

friends
writes

email times

Users owns posts

name text

tags

(2) [8 points] Translate the ER diagram into relational database tables. Make sure
that the translation captures any key and participation constraints in the ER dia-
gram.
Solution:

CREATE TABLE Users (

email VARCHAR(50) PRIMARY KEY,
name VARCHAR(50)
);

CREATE TABLE Friends (

user1 VARCHAR(50) REFERENCES Users(email),
user2 VARCHAR(50) REFERENCES Users(email),
PRIMARY KEY (user1, user2)
);

CREATE TABLE Posts (

author VARCHAR(50) REFERENCES Users(email),
COP5725, Fall 2013 Exam I Page 2 of 7

owner VARCHAR(50) REFERENCES Users(email),

text VARCHAR(200),
times TIMESTAMP,
PRIMARY KEY (author, owner, times)
);

CREATE TABLE Tags (

author VARCHAR(50) REFERENCES Posts(author),
owner VARCHAR(50) REFERENCES Posts(owner),
times TIMESTAMP REFERENCES Posts(times),
tagged VARCHAR(50) REFERENCES Users(email),
PRIMARY KEY (author, owner, times, tagged)
);

(3) [5 points] Based on your schema in (2), how would you disallow a user posting
on non-friends’ profile pages? Write down the SQL statement(s) you use to enforce
this constraint.
Solution: Assume Friends is symmetric, i.e., (x, y) are friends ⇒ (y, x) are friends.

CREATE ASSERTION post_friends CHECK (

NOT EXISTS (
SELECT author, owner FROM Posts
EXCEPT
SELECT user1, user2 FROM Friends
));

II. [28 points] Relational Algebra.

Consider the following database concerning World War II capital ships from Assignment
1:
Classes(class, type, country, numGuns, bore, displacement)
Ships(name, class, launched)
Battles(name, date)
Outcomes(ship, battle, result)

Ships are built in “classes” from the same design, and the class is usually named for the
first ship of that class. The relation Classes records the name of the class, the type
(‘bb’ for battleship of ‘bc’ for battlecruiser), the country that built the ship, the number
of main guns, the bore (diameter of the gun barrel, in inches) of the main guns, and the
displacement (weight, in tons). Relation Ships records the name of the ship, the name
of its class, and the year in which the ship was launched. Relation Battles gives the
name and date of battles involving these ships, and relation Outcomes gives the result
(sunk, damaged, or ok) for each ship in each battle.
Write relational algebra expressions to answer the following queries:
COP5725, Fall 2013 Exam I Page 3 of 7

(1) [5 points] Find the names and ages of ships that sunk in battles.
Solution:

πShips.name, date−launched (Ships

./Ships.name=Outcomes.ship Outcomes ./Outcomes.battle=Battles.name Battles)

(2) [5 points] Find the countries that had both battleships and battlecruisers.
Solution:

πcountry,type (Classes) ÷ πtype (Classes),

or πcountry (σtype=‘bb’ (Classes)) ∩ πcountry (σtype=‘bc’ (Classes)).

(3) [5 points] Find the year in which the last ship of class “Tennessee” was launched.

Solution:

R1 ← σclass=‘Tennesee’ (Ships)
R2 ← ρR2 (R1 )
Ans ← πlaunched (Ships) − πR1 .launched (R1 ./R1 .launched<R2 .launched R2 )

(4) [5 points] Express the following SQL query in relational algebra:

SELECT class, type, country
FROM Classes
WHERE NOT EXISTS (
SELECT * FROM Ships
WHERE Ships.class = Classes.class
AND name IN (
SELECT ship FROM Outcomes
WHERE result != ’ok’
)
);

Solution:

R1 ←πclass (Classes)−
πclass (σresult6=‘ok’ (Ships ./name=ship Outcomes)).
Ans ←πclass,type,country (R1 ./ Classes)

(5) [8 points] Consider three database relations (sets) R, S, T . Tell whether each of
the following is true or not. Give a counter-example if the law does not hold. (Hint:
./ stands for the full outer join.)
A. (R ./ S) ./ T = R ./ (S ./ T )
COP5725, Fall 2013 Exam I Page 4 of 7

B. πA (R ∩ S) = πA (R) ∩ πA (S), where A is a common attribute of R and S.

C. σC (R ./ S) = σC (R) ./ S, where C involves only attributes of R.
D. σC (R ./ S) = σC (R) ./ S, where C involves only attributes of R.
Solution: B. R(A, B) = {(1, 2)}; S(A, B) = {(1, 3)}.
C. R(A, B) = {(1, 2), (3, 3)}; S(B, C) = {(2, 2)}, σA=3 .

III. [28 points] SQL.

Consider the following database schema:
Product(maker, model, type)
PC(mode1, speed, ram, hd, rd , price)
Laptop(mode1, speed, ram, hd, screen, price)
Printer(mode1, color, type, price)

The P roduct relation gives the manufacturer, model number and type (PC, laptop,
or printer) of various products. We assume for convenience that model numbers are
unique over all manufacturers and product types. The P C relation gives for each model
number that is a PC the speed (of the processor, in gigahertz), the amount of RAM(in
megabytes), the size of the hard disk (in gigabytes), the speed and type of the removable
disk (CD or DVD), and the price. The Laptop relation is similar, except that the screen
size (in inches) is recorded in place of information about the removable disk. The P rinter
relation records for each printer model whether the printer produces color output (true
if so), the process type (laser, ink-jet, or bubble), and the price.
Write a SQL statement for the following questions:
(1) [5 points] Find the manufacturers that make at least three different models of PC.

Solution:

SELECT maker
FROM Product
WHERE type=’pc’
GROUP BY maker
HAVING COUNT(model) >= 3;

(2) [5 points] Find the average hard disk size of a PC for all those manufacturers that
make printers.
Solution:

SELECT AVG(P.hd) AS Avg_HD_Size

FROM Product R, PC P
WHERE R.model = P.model AND R.maker IN (
SELECT maker
FROM Product
WHERE type = ’printer’
);
COP5725, Fall 2013 Exam I Page 5 of 7

(3) [5 points] Find the model number of the item (PC, laptop, or printer) with the
highest price.
Solution:

SELECT model, price FROM

(SELECT model, price FROM PC UNION
SELECT model, price FROM Laptop UNION
SELECT model, price FROM Printer
) M1
WHERE M1.price >= ALL (
SELECT price FROM PC UNION
SELECT price FROM Laptop UNION
SELECT price FROM Printer
);

(4) [5 points] Delete all laptops made by a manufacturer that doesn’t make printers.

Solution: One deletion is enough.

DELETE FROM Laptop L

WHERE NOT EXISTS (
SELECT * FROM Product P1, Product P2
WHERE P1.model = L.model AND P1.maker = P2.maker
AND P2.type = ’printer’
);

DELETE FROM Product P

WHERE P.type = ’laptop’ AND NOT EXISTS (
SELECT * FROM Product P1, Product P2
WHERE P1.model = P.model AND P1.maker = P2.maker
AND P2.type = ’printer’
);

(5) [8 points] When inserting a new printer, check that the model number exists in
Product. Reject the printers with no corresponding models.
Solution:

CREATE TRIGGER NewPrinterTrigger

AFTER INSERT ON Printer
REFERENCING
NEW ROW AS NewRow,
NEW TABLE AS NewStuff
FOR EACH ROW
WHEN (NOT EXISTS (SELECT * FROM Product
WHERE Product.model = NewRow.model))
DELETE FROM Printer
COP5725, Fall 2013 Exam I Page 6 of 7

WHERE (model, color, type, price) IN NewStuff;

IV. [23 points] Disks, Files and Buffer Management.

(1) Answer the following knowledge questions.
i. [3 points] Describe two main technologies used in RAID.
Solution:
Data striping Data is partitioned; Partitions are distributed over several disks.
Redundancy More disks⇒more failures. Redundant information allows reconstruc-
tion of data if a disk fails.
ii. [3 points] Explain the page format for variable length records and its advan-
tages over other page formats.
Solution: Use a slot directory:
• Pointer and size of each record;
• Number of record entries;
• Start of free space in the block.
We can move records on page without changing rid; so attractive for fixed-length
records too.
(2) Assume there is a disk with the following characteristics:
1. There are eight surfaces with 10,000 tracks each.
2. Tracks hold an average of 2000 sectors of 1024 bytes each.
3. The disk rotates at 6,000 rpm.
4. The time it takes the head to move n tracks is 1 + 0.0003n milliseconds.
5. The time to transfer one sector of data is 0.2 ms.
Answer the following questions about this disk.
i. [3 points] What is the maximum seek time?
Solution: Maximum seek time = 1 + 0.0003×10000 = 4ms.
ii. [4 points] What is the maximum and average rotational latency?
Solution: Maximum rotational latency = 60/6000×1000 = 10ms,
Average rotational latency = 5ms.
iii. [4 points] If a block is 65,546 bytes (i.e., 64 sectors), how long does it take to
read a block in the worst case?
Solution: The total reading time = 10 + 4 + 64×0.2 = 26.8ms.
(3) Consider a buffer pool of 3 frames and a heap file of 100 sequential pages with page
IDs from 1 to 100. Assume we scan the heap file from beginning to end for the first
time and then from end to beginning for the second time.
i. [3 points] Starting with an empty buffer pool, using an LRU replacement
strategy, what is the hit rate (#hits/#requests)?
Solution: 3/200 or 1.5%. Only 98, 99, and 100 are hit, once each.
ii. [3 points] Suppose we are using MRU instead of LRU, what is the hit rate for
the scenario in Part i?
COP5725, Fall 2013 Exam I Page 7 of 7

Solution: 3/200 or 1.5%. Only 100, 99, and 98 are hit, one each.