CSCI 6624/4524 -Advanced Databases -16 Spring

hw2.pdf

Home >Computer Science homework help >CSCI 6624/4524 -Advanced Databases -16 Spring

CSCI 6624/4524 — Advanced Databases— 16 Spring HW 2, Due: Tuesday, 3/8/16

• Because 3/12/16 - 3/20/16 is the Spring Break, this HW will be considered one week late if handed in by the start of class on 3/22/16 and two weeks late if handed in by the start of class on 3/29/16.

• Quiz 2 (open book, open notes) will be on Tuesday, 3/22/16 and will cover 21.6 – Transaction Support in SQL, 23.1–23.3: Database Recovery Techniques. 6.1–6.5: Relational Algebra.

1. (25 points) Consider what happens with the locks in order to get each of the following SQL isolation levels:

(a) READ UNCOMMITTED

(b) READ COMMITTED

(d) SERIALIZABLE

For each of the above, you have to

(i) briefly explain what ”locking policies” the DBMS enforces to get that isolation level.

(ii) briefly explain why this locking policy ensures that particular isolation level

(iii) briefly explain why this locking policy does not ensure the next isolation level. (you don’t have to do this for the SERIALIZABLE part).

2. (20 points)

(a) For this part of the problem, you can assume we are using the immediate update protocol. We saw that UNDOs have to be done right to left i.e. later writes are undone first and then earlier writes. Give an example to show why it should be done this way by doing the following:

i. Find a simple example where it does make a difference whether the UNDOs are done left to right or right to left.

ii. Show what the results will be if the UNDOs are done right to left.

iii. Show what the results will be if the UNDOs are done left to right.

(b) For this part of the problem, you can assume we are using the immediate update protocol We saw that REDOs have to be done left to right i.e. earlier writes are redone first and then later writes. Give an example to show why it should be done this way by doing the following:

i. Find a simple example where it does make a difference whether the REDOs are done left to right or right to left.

ii. Show what the results will be if the REDOs are done left to right.

iii. Show what the results will be if the REDOs are done right to left.

(c) Explain why is it that if we are using the immediate update protocol we need to keep the old value (BFIM) of an item along with the new value (AFIM), but if we are using deferred update protocol, we need to only keep the new value.

3. (10 points) Suppose that we use the immediate update protocol for the schedule given in the last slide of the week 5 power point notes.

(a) Show what will be the steps taken at the time of the recovery process i.e. specify, in the correct order, what are all the operations (undo and/or redo) which are carried out by showing what changes are made. No additional explanation is needed.

(b) What are the final values of A and B; no explanation needed.

4. (10 points) This problem is based on tables T 1 and T 2 from Elmasri Figure 6.15 ; this figure is also in the powerpoint notes. For each of the following relational algebra queries, show the output table (no explanations needed : just show the table):

(a) T 1 ./T 1.P ≤ T 2.A T 2

(b) T 1 ./T 1.R ≤ T 2.C T 2

5. (35 points) This problem is based on Elmasri’s company database. For each of the following, specify the query using relational algebra:

(a) Find the ssn of employees who work on Project number 30.

(b) Find the name of the employee supervising Franklin Wong.

(d) Find the names of employees who work on every project.

(e) Find the names of employees who work on on ProductY and who have a dependent.

(f) Find the names of the employees and the names of the departments they work for, for every employee who has a daughter.

Textbook Extra Credit Problems: 23.23, 23.25, 23.26

Extra Credit 5: Do some research and find out and explain the difference between how Oracle and SQLServer deal with the different SQL isolation levels.

Extra Credit 6: Do some research and find out and explain the difference between how Oracle and SQLServer deal with recovery.

Extra Credit 7: Consider a database with the following schema: Suppliers(sid: integer, sname: string, address: string) Parts(pid: integer, pname: string, color: string) Catalog(sid: integer, pid: integer, cost: real) The Catalog relation lists the prices charged for parts by Suppliers. Consider the transactions T1 and T2. T1 always has SQL isolation level SERIALIZABLE. We first run T1 1 concurrently with T2 and then we run T1 1 concurrently with T2 but we change the isolation level of T2 as specified below. Give a database instance and SQL statements for T11 and T2 such that result of running T2 with the first SQL isolation level is different from running T1 2 with the second SQL isolation level. Also specify the common schedule of T11 and T2 and explain why the results are different.

1. SERIALIZABLE versus REPEATABLE READ.

2. REPEATABLE READ versus READ COMMITTED.

3. READ COMMITTED versus READ UNCOMMITTED.

Extra Credit 8: In the language of your choice write a program which will take as input a SQL statement and produce as output an equivalent expression in relational algebra. Now obviously this is a very complex task, so your program need only handle a very simple type of SQL statement, namely SELECT atributename1 FROM tablename WHERE atributename2 = constant value. Turn in a hard copy of the documented source code, and sample runs and turn in the soft copy on blackboard.

Extra Credit 9: In the language of your choice write a program which will take as input a simple relational algebra statement (invloving only a selection and projection operation on a single table) and the table i.e. the relational instance. The output of your program should be the table that would have been output by the relational algebra statement. So what you have to do is to write a “compiler” type of program which will implement a relational algebra statement. Turn in a hard copy of the documented source code, and sample run (i.e. the relational algebra statment, the relational instance, the output table), and turn in the soft copy on blackboard.