Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 1 of 12

This exam paper must not be removed from the venue

School of Information
Technology and Electrical
Engineering
EXAMINATION
Semester One Final Examinations, 2017
INFS7901 Database Principles
This paper is for St Lucia Campus students.
Examination Duration: 90 minutes
Exam Conditions:
This is a School Examination
This is a Closed Book Examination - specified materials permitted
During reading time - write only on the rough paper provided
This examination paper will be released to the Library
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)
Calculators - Any calculator permitted - unrestricted
One A4 sheet of handwritten or typed notes double sided is permitted
Materials To Be Supplied To Students:
1 x 14 Page Answer Booklet
1 x Multiple Choice Answer Sheet
Instructions To Students:
provided upon request.

Venue ____________________
Seat Number ________
Student Number |__|__|__|__|__|__|__|__|
Family Name _____________________
First Name _____________________
For Examiner Use Only
Question Mark

Total ________
Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 2 of 12
Module 1

Question 1. (10 Marks) Functional Dependencies and Normal Forms

Consider the relation instance on the right-hand side. Observe
that B → A appears to hold with respect to the given
instance.

a. (4 marks) Check to see if all of the following
dependencies hold with respect to the instance and
explain why:

A B C
John 1 10
John 2 11
Jane 3 11
Jane 3 11
Jill 4 12
Jill 5 13

b. (2 marks) Determine the minimum number of tuples that can be added to the
above instance to invalidate B → A.

c. (4 marks) Assuming that B → A holds in the given schema. Decompose it, if
necessary, so that all the resultant relations are in BCNF.

A → B

B → C

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 3 of 12

Question 2. (10 Marks) Relational Algebra

Answer the following questions using queries in relational algebra.
The following schema introduces an example, concerning high-school students applying
for college. It involves the following relations:
• Student (sID, sName, age, GPA, sizeHS)
• College (cName, state, enrolment)
• Apply (sID, cName, major, decision)
The relation Student records the id, name, age, GPA, and size of the high school of the
student. The relation college records the name of the college, the state in which the
college is, and the current number of students that are attending the college. Finally, the
Apply relation keeps track of application and the decision that was made by the college.

a) (5 marks) Find the name of colleges that all of the students have applied to.

b) (5 marks) Find the id of students have been accepted in the CS major of both
Stanford and MIT.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 4 of 12

Question 3. (10 Marks) SQL

Answer the following questions using queries in SQL.

For this question, we will be using the schema that was introduced in Question 2:
• Student (sID, sName, age, GPA, sizeHS)
• College (cName, state, enrolment)
• Apply (sID, cName, major, decision)

a) (4 marks) Find IDs of students that are not from the smallest high school.

b) (6 marks) Find the id(s) and name(s) of the youngest student(s) that have been
accepted in the CS major in each of the states.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 5 of 12
Module 2
Question 4. (10 Marks) Asymptotic Analysis

Assume that you are asked to make a recommendation between two algorithms (A and
B) that accomplish exactly the same task. After measuring the run times for various
inputs sizes, you determine that the average running time (for input of size n) of algorithm
A is TA(n) = 3n2, and the average running time of algorithm B is TB(n) = 4n + 100.

a) (2 marks) For n =10, which algorithm would run faster? Explain your answer

b) (2 marks) For n = 1000, which algorithm would run faster? Explain your

c) (2 marks) Determine the big-o notation of each of the algorithms.

d) (4 marks) Which algorithm would you recommend? Refer to your answers
from part a, b, and c in your recommendation.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 6 of 12
Question 5. (6 Marks) Sorting

In class, a variety of sorting algorithms were examined. For parts (a) to (c), choose
the best algorithm from the ones we have examined. Justify your answer (in a
sentence or two) referencing the running time of the algorithms.

a) (2 marks) You are a data analyst and you are trying to put an input of a few
million numbers into order. You are aware that the input is almost sorted and
there may only be a few numbers that you need to move around. Which
sorting algorithm would you use?

b) (2 marks) You are sorting a few million numbers in a cloud environment in
which read operations take O(1), constant time, and write operations take
O(n), linear time. Which sorting algorithm would you use?

c) (2 marks) You are part of an analysis team that is operating under very strict
and sensitive timelines, so you want to be able to guarantee that the sorting
algorithm that you use runs in O(n log n) in the absolute worst case. What
sorting algorithm would you use?

Question 6. (4 Marks) Sorting

An array is supplied to the partition routine used by quicksort(). After the very first call
to partition() the array contains the following numbers.:

what number(s) in the array can be the pivot? Note the actual number(s) is wanted,
not the position of the number(s) in the array.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 7 of 12

Question 7. (10 Marks) Binary Search Trees

This question makes reference to the following Binary Search Tree:

a) (1 mark) What is the height of this
tree?

b) (1 mark) Which node is the root
node?

c) (1 mark) What is the depth of node
19?

d. (1 mark) Which nodes are leaves?

e. (2 marks) When building a tree using a sequence of insertions (i.e. the insertion
technique from class) which one of the following is the appropriate sequence of
insertions to build the tree?
I. 23, 60, 17, 80, 40, 19, 10, 90, 21, 11, 6, 81
II. 23, 81, 90, 80, 40, 60, 21, 19, 11, 6, 10, 17
III. 23, 17, 10, 6, 11, 19, 21, 40, 60, 80, 90, 81
IV. 6, 11, 10, 17, 21, 19, 23, 40, 60, 81, 90, 80
V. 6, 10, 11, 17, 19, 21, 23, 40, 60, 80, 81, 90
VI. 6, 11, 10, 21, 19, 17, 40, 81, 90, 80, 60, 23
VII. 81, 6, 11, 21, 90, 10, 19, 40, 80, 17, 60, 23
VIII. 81, 90, 21, 11, 6, 80, 40, 19, 10, 60, 17, 23

B → C

B → C

B → C

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 8 of 12

f. (2 marks) Draw the tree resulting from deletion of node with value 23, assuming
that we are using the node’s successor to replace it.

g. (2 marks) Suppose that we have numbers between 1 and 1000 in a binary search
tree, and we want to search for the number 363. Which of the following
sequence(s) could not be the sequence of nodes examined?

I. 23, 60, 17, 80, 40, 19, 10, 90, 21, 11, 6, 81
II. 23, 81, 90, 80, 40, 60, 21, 19, 11, 6, 10, 17
III. 23, 17, 10, 6, 11, 19, 21, 40, 60, 80, 90, 81
IV. 6, 11, 10, 17, 21, 19, 23, 40, 60, 81, 90, 80
V. 6, 10, 11, 17, 19, 21, 23, 40, 60, 80, 81, 90
VI. 6, 11, 10, 21, 19, 17, 40, 81, 90, 80, 60, 23
VII. 81, 6, 11, 21, 90, 10, 19, 40, 80, 17, 60, 23
VIII. 81, 90, 21, 11, 6, 80, 40, 19, 10, 60, 17, 23

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 9 of 12

Question 8. (6 Marks) Hashing

Consider a hash table of size 7 with hash function h(k) = k mod 7. Draw the contents
of the table after inserting, in the given order, the following values into the table: 9, 16,
27, 62, and 2.
a) (3 marks) When chaining is used to resolve collisions
0
1
2
3
4
5
6

b) (3 marks) When double hashing with secondary hash function h2(k) = 5−(k mod 5)
is used to resolve collisions.
0
1
2
3
4
5
6

Question 9. (4 Marks) Hashing

For good hashing performance, we need to have a good hash function. Can we create an ideal
hash function that would work well in all problems independent of the dataset? If so explain
how, and if not explain why?

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 10 of 12

Module 3
Question 10. (10Marks) Indexing

For this question, we will be using the schema that was introduced in Question two:
• Student (sID, sName, age, GPA, sizeHS)
• College (cName, state, enrolment)
• Apply (sID, cName, major, decision)
Suppose you know that the following queries are the most common queries in the
database and that all are roughly equivalent in frequency and importance:
1. Find name, age, GPA, and the high school size of student based on their SID
2. Find name of colleges in each state
3. Find students IDS with GPA higher than 3.6
4. Find SID of students that have applied to each college
These queries occur much more frequently than updates, so you should build whatever
indexes you need to speed up these queries. However, you should not build any un-
necessary indexes, as updates will occur (and would be slowed down by unnecessary
indexes). Given this information, decide which attributes should be indexed and whether
each index should be a clustered index or an unclustered index. Assume that both B+
trees and hashed indexes are supported by the DBMS and that both single- and multiple-
attribute index search keys are permitted.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 11 of 12
Question 11. (10 Marks) Query Optimization

For this question, we will be using the schema that was introduced in Question two:
• Student (sID, sName, age, GPA, sizeHS)
• College (cName, state, enrolment)
• Apply (sID, cName, major, decision)

Consider the following query

Select s.sID
from Student s, College c, Apply a
Where s.sID = a.sID and c.cName=a.cName and
GPA>3.5 and c.cName='stanford' and decision='Y'

a) (5 marks) Draw the initial query tree for this query and explain briefly why this
plan is considered inefficient.

Semester One Final Examinations, 2017 INFS7901 Database Principles
Page 12 of 12
b) (5 marks) Transform the initial query into an equivalent final query tree that is
efficient to execute.

END OF EXAMINATION

Email:51zuoyejun

@gmail.com