1    (a) Describe four main characteristics of a database approach as compared to the traditional file

storage mechanism . [4 marks]

(b) In the ER diagram notation, explain the degree of a relationship type, the difference between a multi-valued attribute and a composite attribute ? [3 marks]

Maximum marks: 7

2   Construct (i.e., draw) the corresponding ER design diagram that maps into the exact same relational database schema as below (using the algorithm taught in the course).

[7 marks]

Maximum marks: 7

3   The following question uses the BANKING database schema shown below.

Suppose that the above database has been created and populated with valid data, define the following queries using SQL statements:

(i) Define a view to list all the loans under each bank and the branches (show attributes such as    the bank Code, the bank Name, the Branch_no, the Loan_no, the Amount and the Type). O rder the query result by Code, Branch_no, and Loan_no in an ascending order. [4 marks]

(ii) Retrieve the customers who have both their accounts and their loans all from the same bank    (show attributes such as the customer's Ssn, the customer's Name, the customer's Address and the bank's Name). [4 marks]

4   The following question uses the BANKING database schema shown below.

Suppose that the above database has been created and populated with valid data. Define the following queries using relational algebra expressions:

(i)  Retrieve the information of all banks and their branches (show attributes such as the bank Code, the bank Name, the Branch_no and the branch Address). [4 marks]

(ii) List the number of loans and the sum of loan amounts for each customer who has at least one loan (show the attributes such as the customer's Ssn, the customer's Name, the                           'Number_of_loans' and the 'Total_loan_amount'). [4 marks]

Maximum marks: 8

5   A popular airline builds a new online booking system . In this system , customers can order return

trips; these are trips consisting of a flight to a destination and a later return flight back . An example order would be a flight Auckland-Wellington and a flight Wellington-Auckland three days later.         Each flight has only a limited number of seats . The airline does not want to overbook flights .          The company considers using for this system a database that is not transactional.

Describe three problems that could happen with the example order above if the database is not transactional.

Explain why the problems could not happen with a database that is transactional. You should refer to three ACID properties in your explanation; choose the three problems accordingly. Discuss at   least one of the problems using schedules . [12 marks]

Maximum marks: 12

6   Consider the following schedule,

s: r1[z], r3[y], r3[x], r2[y], w 1[z], w3[y], w3[x], c3, r1[x], r1[z], r2[x], w2[y], w2[x], c 1, c2

(a) which phenomenon is appearing in this schedule, if any? [2 marks]

Select one alternative:

 dirty read

 write skew

 lost update

 none of the others

 fuzzy read

(b) which operation violates the rules of the common scheduler first, if any? [2 marks]

Select one alternative

 w2[x]

 None of the others

 r2[x]

 w3[y]

 w 1[z]

Maximum marks: 4

7   Consider the following schedule,

s: r1[x], r2[x], r3[z], r2[y], r1[y], r3[x], c2, w 1[y], w 1[x], c 1, r3[y], w3[y], r3[x], w3[z], c3

(a) which phenomenon is appearing in this schedule, if any? [2 marks]

Select one alternative:

 none of the others

 write skew

 lost update

 fuzzy read

 dirty read

(b) which operation violates the rules of the common scheduler first, if any?[2 marks]

Select one alternative

 w 1[x]

 None of the others

 r2[x]

 w 1[y]

 r3[y]

Maximum marks: 4

8   G ive your own example of a stable log and a stable database at the time of a system crash. The stable database should have two pages . O ne page should be a steal page, that means it should contain an uncommitted write.

The other page should be outdated, that means there should be a committed write not represented in this page.

Each page should have at least two data objects . There should be at least one write operation for each of these data objects in the stable log.

Say by referencing to log sequence numbers when the steal page was written to the stable database.

Perform crash recovery and give the resulting clean database.

[10 marks]

Maximum marks: 10

9    Indicate if the following statements are true or false. Explain your answers .

1. Databases must always be normalized to at least 3NF.

2. Normalization removes redundancy from the database instance.

3. Normalization adds spurious tuples to the database instance.

4. Normalisation speeds up queries on the database instance.

[4 marks]

Maximum marks: 4

10   Consider the universal relation R = {A, B, C,D , E, G} and the set of functional dependencies: F = {{A, C}→{B}, {A,D}→{E},{B}→{D}, {B,C}→{A}, {E}→{G}}. U

Consider the following decomposition, D1:

D1 = {R1, R2, R3, R4}; R1 = {A, B}, R2 = {B,C}, R3 = {A,B,D,E}, R4 = {E,G}

For decomposition D1,

1. give the primary key of each relation in the decomposition, [2 marks]

2. state which normal form ( 1NF, 2NF, 3NF) each relation in the decomposition is in, [1 mark]

3. state whether the decomposition has the dependency preservation property, with respect to F, [1 mark]

4. state whether the decomposition has the lossless join property, with respect to F. [2 marks]

Maximum marks: 6

11    In the following B+tree, each data block can contain up to 3 tuples; each internal node can hold up to 4 pointers and 3 keys . Tuples with 13 keys , 23, 94, 11, 25, 15, 13, 39, 19, 76, 12, 33, 92, 35,      are sequentially inserted to the following B+tree.

a) With the B+tree in the above figure, how many I/Os will it cost to find and report all tuples with key values greater than 50? [2 marks]

b) How many nodes (including both internal and leaf nodes) are there in the B+tree after inserting the first five new keys including 15? [2 marks]

c) During the sequential key insertion into the B+tree, when, for the first time, the I/O cost of finding an existing key becomes 4? [4 marks]

Select one alternative

 Before inserting 76.

 Before inserting 33

 None of the others .

 Before inserting 35.

 Before inserting 12.

d) Consider a B+tree as a secondary index T on a unique field of a relation. Assume that each internal node contains up to 200 pointers (and 199 keys). What is the least number of bytes the underlying file can have if the index T has 4 levels? --- Level-0 is the root and level-3 contains   pointers to the file blocks; each tuple takes 100 bytes to store. [4 marks]

Select one alternative

 4,000,000 Bytes

  100,000,000 Bytes

  1,000,000 Bytes

 2,000,000 Bytes

 None of the others .

Maximum marks: 12

12   a) Consider an extendible hashing directory whose size doubled after an insertion. The local depths of all the buckets , except one, are then strictly smaller than the global depth. [1 mark]

Select one alternative:

 False

 True

b) Extendible hashing can optimize the I/O cost when the selection query is a range search. [1 mark]

Select an alternative

 True

 False

c) When a block can hold at least 2 pointer and the directory has only 2 pointers , the global depth can be zero. [1 mark]

Select an alternative

 True

 False

Maximum marks: 3

13   Two relations r and s have a common attribute A and have, respectively, 20 fixed-length tuples  and 15 fixed-length tuples . Each block holds up to 2 tuples and the buffer pool has 4 frames . Fill in the answers in the following text boxes .

a) The number of I/Os engaged by block nested-loop join is  . [2 marks]

b) The I/O cost for sorting r is  ; the I/O cost for sorting s is  . [4 marks]

c) Including the sorting costs , the worst-case of merge sort takes merge sort takes  I/Os .

I/Os and the best-case

[4 marks]

Maximum marks: 10

14    Fill in the answers in the following text boxes .

a) SSTable and LSM-Tree are used for                                                                            workload. To speedup the search of a key which does not exist in the database, LSM-Tree adopts an internal   memory data structure called                                                   . [2 marks]

b) NoSQL is the abbreviation of

. A line of NoSQL systems store

relational data in

to optimize the query processing on a small