University of Ottawa
CSI 2132 and 2532 – Final Examination
Professor(s): Herna L. Viktor and Iluju Kiringa
21 April 2012
09:h30-12h30
Duration: 3 hrs
Closed book; no aid allowed, except one double-sided letter-size “cheat sheet”. Answer all
questions in ink. Good luck! / Bonne Chance!
Family name:
First name:
Student number:
Circle your section (For CSI3317 students):
Section A Section B
There are 6 questions and a total of 100 points.
This exam must contain 16 pages, including this cover page.
1 – EER Diagram / 15
2 – Relational Algebra and Relational Calculus / 15
3 – The Relational Model and SQL / 15
4 – Normal Forms / 20
5 – Physical database design / 15
6 – Storage and Indexing / 20
Total / 100
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 2 of 16
1 EER Diagram — 15 points
SmartGames is a company that develops educational games for kids. Consider the following
description of the SmartGames database, which is used to maintain information about all their
employees.
The employee information is stored in a database with the following relevant specification:
• For every employee SmartGames record their social insurance number (SIN); their names
and the year in which they were hired.
• SmartGames hires both regular and seasonal employees. For regular employees, we record
the year in which they became regular employees. Seasonal employees have an indication
of the year in which they can apply for the regular status.
• Amongst regular employees, there are part-time and full-time employees. Full-time employ-
ees have an indication of the year in which they were promoted to full-time employees.
• Seasonal employees must be expert in a given area, but an area may have zero or more
seasonal employees who are expert in it.
• All the areas of expertise have an identification, and a description. Areas of expertise include,
but are not limited to, programming, graphics design, artist, multimedia coordinator, and so
on.
• A full-time employee can advise a seasonal employee on his expertise in a given area. On the
other hand, each expertise of a seasonal employee in an area must have a full-time employee
advising on it.
• Each employee must work exactly on one project (which corresponds to a game), and each
project may have more than one employees working on it.
• A full-time employee must supervise the work of an employee on a project. On the other
hand, each work of an employee on a project must have exactly one full-time employee
supervising it.
Draw an EER diagram for the SmartGame employee database setting. Make sure to indicate all
the appropriate constraints and state all your assumptions.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 3 of 16
Draw your EER diagram here.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 4 of 16
2 Relational Algebra and Relational Calculus — 15 points
Consider the following relational schema about the Nursing staff working in Hospitals across rural
Ontario.
Nurse(nid : int, nname : string, age : real, salary : real, sid : int)
Supervisor(sid : int, rating : real)
WorksIn(nid : int, hid : int, hours : real)
Hospital(hid : int, hname : string, tid : int)
Town(tid : int, tname : string,mayor : string)
Part A — 4 points Provide the relational algebra expression to display the names and salaries of
all nurses who do not work at any hospital.
Part B — 5 points Provide the relational algebra expression to display the names of all nurses,
younger than 30 years old, who worked at all the hospitals that are based in a town called Camp-
bellford.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 5 of 16
Part C — 3 points Explain, by means of your own example, the main difference between tuple
and domain relational calculus.
Part D — 3 points Explain, by means of your own example, what a safe relational calculus
expression ensures.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 6 of 16
3 The Relational Model and SQL — 15 points
Consider, again, the following relational schema about the Nursing staff working in Hospitals
across rural Ontario.
Nurse(nid : int, nname : string, age : real, salary : real, sid : int)
Supervisor(sid : int, rating : real)
WorksIn(nid : int, hid : int, hours : real)
Hospital(hid : int, hname : string, tid : int)
Town(tid : int, tname : string,mayor : string)
Part A — 3 points Explaining a Query
Consider the following query and explain what data it retrieves.
SELECT nname
FROM Nurse N
WHERE NOT EXISTS
( (SELECT H.hid
FROM Hospital H
WHERE H.town = ’Toronto’)
EXCEPT
(SELECT W.hid
FROM WorksIn W
WHERE N.nid = W.nid)
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 7 of 16
Part B — 4 points
Explain how views may be used to ensure logical data independence.
Part C — 8 points (SQL Queries)
1. Write the following query in SQL:
“For each Hospital in which more than 100 nurses work, find the hospital name, and the number
of nurses who work in the hospital.” (4 points)
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 8 of 16
2. Write the SQL integrity constraint (primary/foreign key, check, assertion or any other) to ensure
each one of the following requirements:
“Every supervisor must also be a nurse.” (2 points)
“Every nurse must have a supervisor.” (2 points)
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 9 of 16
4 Normal Forms — 20 points
Consider the following data recorded about contestants in the new BigTeeth TV reality show. This
show focuses on conflicts between humans and animals with big teeth, such as crocodiles, tigers
and lions. You are asked to run a background check on the contestants to determine whether a
person has a police record (PR), to double-check his or her employment history (EMP), and so on.
You create a table, which records the following information.
Name YofB PRecord PRDate PRCat PROutcome EmpName EmpComments
John Smith 1980 Ottawa 12 Sept 11 Serious Jail JollyBouncer Fired
John Smith 1980 Ottawa 1 Sept 08 Minor Fine JollyBouncer Fired
John Smith 1979 none none none none Walmart Good Employee
John Smith 1979 Toronto 1 Dec 06 Minor Fine none none
Ann Doe 1975 none none none none Sears Resigned
Ann Doe 1975 Montreal 3 Dec 08 Serious Jail none none
Sam Watson 1981 none none none none none none
A. (8 points) This table may be susceptible to a number of data inconsistencies, due to informa-
tion redundancy. Explain, by means of your own examples with reference to the BigTeeth
data, what potential problems (or anomalies) may occur.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 10 of 16
B. (4 points) Identify all the functional dependencies, as based on the data in the BigTeeth table.
C. (4 points) Normalize the relation to Boyce Codd Normal Form and show your resultant re-
lations, indicating all primary and foreign keys.
D. (2 points) Determine whether your decomposition is dependency preserving and motivate
your answer.
E. (2 points) Determine whether your decomposition is a lossless-join decomposition and mo-
tivate your answer.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 11 of 16
5 Physical database design — 15 points
Consider, for the last time, the following relational schema about the Nursing staff working in
Hospitals across rural Ontario.
Nurse(nid : int, nname : string, age : real, salary : real, sid : int)
Supervisor(sid : int, rating : real)
WorksIn(nid : int, hid : int, hours : real)
Hospital(hid : int, hname : string, tid : int)
Town(tid : int, tname : string,mayor : string)
Assume that there are currently no indexes defined on any of the tables. The Nurse relation spans
100 disk pages and the current buffer size is 10. Further, the WorksIn relation spans 20 disk pages.
Consider the following query 1.
SELECT N.nname, W.hours
FROM Nurse N, WorksIn W
WHERE N.salary > 20000
AND N.nid = W.nid
AND hours = 100;
A. (5 points) Discuss a scenario where adding indexes may improve the efficiency of the query.
Motivate your answer by listing two different indexing options to consider.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 12 of 16
B. (4 points) Explain how the buffer manager processes a read request for a page.
C. (6 points) Having variable-length fields in a record may raise some subtle issues, especially
when a record is modified. Discuss three (3) issues that may arise.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 13 of 16
6 Storage and Indexing — 20 points
Part A — 10 points (B+ Trees)
Consider the following instance of the Sailors relation, as seen in class.
sid sname srating age
7 ’Sam’ 10.0 67
1 ’Joe’ 2.0 71
3 ’Sumo’ 3.0 23
5 ’Mikey’ 10.0 67
4 ’Jil’ 2.0 71
2 ’Noam’ 3.0 23
6 ’Ann’ 10.0 67
8 ’Louis’ 2.0 71
10 ’Nathan’ 3.0 23
9 ’Liu’ 10.0 67
12 ’Wang’ 2.0 71
11 ’Jones’ 3.0 23
In this question, you must use the bulk loading algorithm to build a B+ tree index on the relation
instance above. Use the index organization (alternative 1) where a data entry k∗ is an actual data
record with search key value k. Assume an order of 1.
Answer the following questions:
1. (4 Points) Show only the first three steps of the bulk loading algorithm.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 14 of 16
2. (2 Points) Show the final tree, after the bulk loading algorithm has been executed.
3. (4 points) Consider the tree you obtained in (2) and show the resulting B+ tree after the
deletion (in the order given) of the tuples :
〈3,′ Sumo′, 3.0, 23〉, 〈5,′ Mikey′, 10.0, 67〉, 〈2,′ Noam′, 3.0, 23〉, and 〈4,′ Jil′, 2.0, 71〉.
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 15 of 16
Part B — 10 points ((Hash Indexing))
In this question, use the following assumptions and notations:
• k∗ denotes the data entry corresponding to the search key k.
• h is the hash function, and for any key k, h(k) returns the last two bits of the binary repre-
sentation of the ASCII code of k.
• Each bucket contains a maximum of 4 data entries.
• The set of available keys, along with their associated ASCII codes is given in the table below.
binary ASCII code key binary ASCII code key
1000001 A 1001110 N
1000010 B 1001111 O
1000011 C 1010000 P
1000100 D 1010001 Q
1000101 E 1010010 R
1000110 F 1010011 S
1000111 G 1010100 T
1001000 H 1010101 U
1001001 I 1010110 V
1001010 J 1010111 W
1001011 K 1011000 X
1001100 L 1011001 Y
1001101 M 1011010 Z
... Cont’d
CSI 2132 and 2532 Final Examination, 21 April 2012 Page 16 of 16
Consider the following initial hash table.
Local depth
1
1
1
Global depth
0
1
Show the steps of the extendible hashing algorithm by inserting the following keys from the table
above into this table, in this order: D, H, K, M, A, O, P, R, Y, W and V. (Hint: follow the method
used in the example of the textbook, where a new figure was introduced only if you must double
the directory).
... End of Final Examination