Question 1            (11 marks)

For each of the following questions, give you answer based on the content from this course.  The explanations should be concise descriptions of your understanding.  Marks will be lost for giving information that is irrelevant to a question or not from this course.

(a)  (6 marks)  Consider the following table

Suppose the table contains all the instances of the relation. Find all the functional dependencies that can be inferred from the relation.  Clearly state any reasonable assumptions that you choose to make. What is the highest form of this relation?

(b)  (5 marks)  Consider three buffer replacement polices:  Least Recently Used (LRU), Most Recently Used (MRU) and First In First Out (FIFO). Construct an example that, for the same query set, FIFO performs the worst in one buffer size and performs the best in another buffer size. Justify your answer, and explain why if it does not exist.

Question 2           (18 marks)

(a)  (10 marks)  Consider the following hospital database

. A doctor is uniquely identified by the docID. We also record the name, email, phone number, specialty and qualifications.  Each doctor can have more than one qualifications  (e.g., degrees, certificates,  ...).   A doctor can have zero or many patients.

. A patient is uniquely identified by the pID. We also record the name, email, phone number,  address  and  insurance.   A  patient  must  be  assigned  to  one doctor.

. A patient may need to take some medical images  (e.g.,  CT, MRI scan,  ...). Each medical imagefile is identified by a combination of pID and mID. We also record the modality and metadata.  A patient can take zero or many medical images.

.  Surgery is often considered as a necessary process to improve a patient’s con- dition.  A surgery is unique identified by the sID. We also record the surgery date, operating room, status and description.

. A surgery should involve exactly one patient and at least one doctor.  A patient can have zero or more surgeries. Each doctor can operate zero or more surgeries.

.  Sometimes, drugs may be prescribed to the patient based on the medical con- dition.  A drug is uniquely identified by the drugID. We also record its name, price, indication and quantity in stock.

.  Each patient can buy zero or more drugs.  Each drug maybe bought by zero or more patients.  Every time when a patient purchase a drug, the quantity also need to be stored.

. A pharmacist is uniquely identified by the phID. We also record the the name, email, phone number and shift schedule.  Each pharmacist manages one or more drugs. Each drug should be managed by one pharmacist.

Draw an ER diagram to represent this scenario and clearly state the assumptions you make if any. Note, please use the drawing conventions in the lecture notes.

(b)  (8 marks)  Translate the ER diagram in Figure 1 into a relational data model.  Note, please use the drawing conventions in the lecture notes.

Figure 1: ER Diagram

Question 3                                                                                  (17 marks)

Consider the following relational schema for real state agency records

. Agent(aID, aName, email, gender, DoB),

.  Owner(oID, oName, email, DoB, status),

. Buyer(bID, bName, email, DoB, credit score),

. Property(pID, address, suburb, size, description),

. Representation(oID, pID, aID, startDate, endDate),

.  Sale(bID, pID, price, saleDate)

Below are detailed descriptions for the fields in each schema

. Agent: For each agent, we record the aID,aName, email, gender and DoB (data of birth). aID is the primary key.

.  Owner: For each owner,we record the oID,oName, email, DoB (dateofbirth) and status. oID is the primary key. status tells whether the owner is “active” or not.

. Buyer: For each buyer,we record the bID,bName, email, DoB (dateofbirth) and credit score. bID is the primary key. credit score is an integer between 0 and 800 .

.  Property: For each property, we record its pID, address, suburb, size and descrip- tion. pID is the primary key.

.  Representation: For each representation, we record the Owner oID, Property pID, Agent aID, startDate and endDate.  The combination of oID, pID and aID is the primary key.

.  Sale:  For each sale, we record the Buyer bID, Property pID, price and saleDate. The combination of bID and pID is the primary key.

Note, all the attributes except for the primary keys may not be unique.  A property is considered sold by an agent if the sale occurs during the period when the agent is representing the property.

Use relational algebra to answer the following questions

1.  List bID of buyers whose credit score is not lower than 500 and the number of properties each buyer bought.  Only consider the property bought after 2005.   (4 marks)

2.  List pID of properties that have been represented by all the agents but only sold by some of them.  (4 marks)

3.  List oID of the owners who have only owned properties that are never represented by agents named ‘Joe Smith’.  (4 marks)

4.  List pID of the properties and aID of the agents that have sold the corresponding property by the highest price among all the sales of the same property.  (5 marks)

Question 4 (23 marks)

(a)  (12 marks)  Consider the relational schema R(A,B,C,D,E,G,H,I, J) and a set of functional dependencies F = {EHI → AB, DJ → GI, BC → EIJ, I → D,AE → CG}. Note that A,B,C,D,E,G,H,I,J are attributes.

1.  Compute total number of the superkeys of R with respect to F that are not candidate keys. Please justify your answer.  (4  marks)

2.  Decompose  R  into  3NF  and  indicate  a  key  in  each  of the  result  tables  by underling the attributes. Please show each step clearly.  (5 marks)

3. Regarding  F,  is  the  decomposition  R1  =  {ABEI}, R2  =  {DGIJ}, R3  = {CEHI} dependency preserving? Please justify your answer.  (3 marks)

(b)  (11 marks)  Consider the following query.  (The user is trying to read P1 from disk, then read P2, Write P3, ..., commit at the end.)

Q1 : Read P1, Read P2, Write P3, Write P4,Write P5, Read P5, Read P2, Read P4, Commit.

Every time when reading or writing a page that is not in the buffer pool, the page needs to be fetched from the disk first.  Assume that writing a page follows the same rule as reading a page. The only difference is, if a page that has been written in the buffer pool is going to be replaced, then it has to be written to disk before replacement.  Each fetch from disk or write to disk is considered as an equal-cost disk access.

Assume there are 3 buffers in the buffer pool.

1.  Sketch the process of how blocks are replaced in the Least Recently Used (LRU) policy. What is the number of page fault and disk access?  Justify your answer. (4 marks)

2.  Sketch the process of how blocks are replaced in the Most Recently Used (MRU) policy. What is the number of page fault and disk access?  Justify your answer. (4 marks)

3.  Between the LRU and MRU policies above, which one performs better in the given query? Justify you answer.  (3 marks)

Question 5         (16 marks)

(a)  (7 marks)  Consider the schedule below. Here, Ri (x) and Wi (x) indicate a read/write by transaction i on data item x.

R2(B);W2(B);R1(A);R5(B);R1(C);R2(C);W2(C);W4(A);W4(B);R3(C);W3(A);R2(C)

1.  Draw the precedence graph of the schedule with all the transactions.  (4 marks)

2.  State whether the schedule is serializable or not.  If it is serializable, write down the equivalent serial schedule. If not, briefly explain why.  (3 marks)

(b)  (9 marks)  Given the  four transactions T1 , T2 , T3  and T4  below, please construct schedule according to the requirements. In the constructed schedule, each transac- tion should keep its operations and the order of operations.

T1 : Write(A) Read(B) Read(D)

T2 : Read(C) Read(A) Read(C) Write(C)

T3 : Read(B) Read(A) Write(C)

T4 : Write(D) Read(A) Write(A)

1.  Construct a schedule of T1 , T2 , T3  and T4  which causes deadlock when using two-phase locking protocol.  You should clearly indicate all the locks in your schedule and draw the wait-for graph for the deadlock part only.  If no such schedule exists, explain why.  (5 marks)

2.  Construct  a schedule of T1 ,  T2 , T3   and T4   which does NOT cause deadlock when using two-phase locking protocol.   You  should clearly indicate all the locks in your schedule and draw the full wait-for graph which includes all the transactions. If no such schedule exists, explain why.  (4  marks)

Question 6  (15 marks)

Consider an employee table with 4 attributes: id, name, birth and salary. The tuples of the relation are stored in a sorted file based on an increasing ordering of the values of birth.  Furthermore, suppose id is the only key in the relation.  Below is the first 3 and last 3 tuples in the relation.

1. Is it meaningful or reasonable to build a clustered index over the attribute salary, if we frequently search people with a given salary? Justify your answer.  (4 marks)

2.  Is it meaningful or reasonable to build a hash or tree index over the name attribute, if we frequently search people with their family name, e.g., find all the tuples with family name as Lee? Justify your answer.  (3 marks)

3.  Suppose there is a dense tree index over the attribute birth and we want to find the tuples with birth equal 1977 or 1998.  Write the corresponding SQL that can better use the index and justify your answer.  (4 marks)

4.  Suppose we frequently search for people with a given name and salary pair, e.g., find all the tuples with name=Mark Lee and salary=2000.  How should we build the index to improve the search performance? Justify your answer.  (4 marks)