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

Reading Time: 10 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:

Additional exam materials (eg. answer booklets, rough paper) will be

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

answer

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