assignment

MTCE 703A: Advanced DBMS

Week: 1

1. Consider the following relation

Professor (Pfcode, dept, head, time)

It is assumed that

(i) A professor can work in more than one dept.

(ii) The time he spends in each dept is given.

(iii) Each dept has only one head

Draw the dependency diagram for the above relation by identifying the dependencies.

 2.

3.

      

4. Consider the relation Student (stid, name, course, year)

Given that A student may take more than one course but has unique name and the year of joining.

(i) Identify the functional and multivalued dependencies for Student.

(ii) Identify a candidate key using the functional and multivalued dependencies arrived at in step (b).

(iii) Normalize the relation so that every decomposed relation is in 4NF.

5.  Design a generalization-specialization hierarchy for a motor-vehicle sales company. The company sells motorcycles which have an engine number and cost; cars which have a chassis number, an engine number, seating capacity and cost; trucks which have chassis number, an engine number and cost.

6. Consider the following tables :

customer (c_id, c_name, c_address)

branch (br_name, br_city, assets)

account (c_id, act_no, br_name, balance)

(i) Customers who have accounts in all branches of Bhopal.

(ii) Customers who have accounts in branches with assets more than 50 crores.

7. Given two relations R (A,B) and S (B,C) with number of tuples in R and S equal to 500 and 1000 respectively and B is the foreign key in R, what is the number of tuples in R  S.

          

MTCE 703A: Advanced DBMS

Week: 2

1.      Given the following relations :

vehicle (reg_no, make, colour)

Person (eno, name, address)

Owner (eno, reg_no)

Write expressions in relational algebra to answer the following queries :

(i) List the names of persons who do not own any car.

(ii) List the names of persons who own only Maruti Cars.

2. The entity set EMPLOYEE is a generalization of the entity sets  

 FULL_TIME_EMPLOYEE and PART_TIME_EMPLOYEE. The former is a

generalization of the entity sets FACULTY with attributes degree and subject of interest and STAFF with attribute classification; the latter, is a generalization of the entity sets TEACHING with attribute stipend and CASUAL_FACULTY with attribute hour rate. STAFF inherits the attribute Salary of the entity set FULL_TIME_EMPLOYEE and the latter, in turn, inherits the attributes of EMPLOYEE. FULL_TIME_EMPLOYEE is a specialization of the entity set EMPLOYEE and is differentiated by the additional attribute Salary. Similarly, PART_TIME_EMPLOYEE is specialization differentiated by the presence of the attribute Type. Each employee must have attributes empno, name and hire_date.

(i) Draw an E-R diagram for the system.

(ii) Convert this E-R diagram to relational tables.

3.

Consider a relation named EMP DEPT with attributes: ENAME, SSN, BDATE, ADDRESS, DNUMBER, DNAME, and DMGRSSN. Consider also the set G of functional dependencies for EMP DEPT:

a) Calculate the closures SSN+ and DNAME+ with respect to G.

b) Is the set of functional dependences G minimal? If not, find a minimal set of functional dependencies that is equivalent to G.

c) List an update anomaly that can occur for relation EMP DEPT.

d) List an insertion anomaly that can occur for relation EMP DEPT.

e) List a deletion anomaly that can occur for relation EMP DEPT.

4. Given relation R(W, X, Y, Z) and set of functional dependencies

where G is a minimal cover:

a) Decompose R into a set of relations in Third Normal Form.

b)Is your decomposition in part a) also in Boyce Codd Normal Form? Explain your answer.

5  Suppose you are given a relation R(A;B;C;D). For each of the following (complete) sets of FDs, (i) identify the candidate key(s) for R, and (ii) state whether or not the proposed decomposition of R into smaller relations is a \good" decomposition and briey explain why or why not.

           

           

MTCE 703A: Advanced DBMS

Week: 3

1. Consider the following relations

Physician (rgno, phyname, addr, phno)

Patient (ptname, ptaddr)

Visits(rgno, ptname, dateofvisit, fees-charged)

Answer the following in SQL :

(i) Define the tables. Identify the keys and foreign keys.

(ii) Create an assertion that the total fees charged for a patient can not be more than

Rs.1000/- assuming that patients can visit the same doctor more than once.

(iii) Create a view Patient_visits(name, times) where name is the name of the patient

and times is the number of visits of a patient.

(iv) Display the ptname, ptaddr of the patient(s) who have visited more than one

physician in the month of May 2000 in ascending order of ptname.

2.  In some situations, Cross product (cross join) and Join do the same task (retrieve the same number of records. State one situation.

3. Given the following relations :

vehicle (reg_no, make, colour)

Person (eno, name, address)

Owner (eno, reg_no)

       For the query

Select eno, name, reg_no

From Person, Owner

Where Person.eno = Owner.eno and Person.name = ‘Hari’

1. Draw the initial query tree.

2.      Optimise the query and draw the optimised query tree.

4.  Assume the following database schema consisting of two relations as follows:

STUDENT(ID, Sname, Major, Grade)

DEPARTMENT(Dnumber, Dname, Location, Budget)

Consider the following SQL query:

Select Sname

From STUDENT, DEPARTMENT

where Major=Dnumber

AND Dname = 'IS'

AND Grade<75

·        Write the initial query tree of this SQL query

·        Write the optimal equivalent query tree

·        Assume that there is a rule stating that: the grade of IS students is at least 75; What an intelligent query optimizer can do to optimize the above query.

MTCE 703A: Advanced DBMS

Week: 4

1. Given the following relations for the entities Professor and Course and the

    relationship Teaching:

Professor (P_ID, Name, Dept_ID)

Course(Code, Dept_ID, CName, syllabus)

Teaching(P_ID, Code, Semester)

Given the following SQL query Q, draw the query plan with an early selection and an index nested loops join strategy knowing that the relation Professor is indexed on P_ID. How relevant is it that the index on Professor is clustered or not?

2. How do you estimate the query cost for natural join  When

3. Estimate the cost of r . s using

(a) Sort-merge join

(b) Block nested loops

     where r has 1,000 tuples, 20 tuples per page; s has 2,000 tuples, 4 tuples per page; and the main memory buffer for this operation is 22 pages long.

  4. Compute the cost of using the following methods:

(a) Nested loops

(b) Block-nested loops

(c) Index-nested loops with a hash index on B in s. (Do the computation for both clustered and unclustered index.)

 where r occupies 2,000 pages, 20 tuples per page, s occupies 5,000 pages, 5 tuples per page, and the amount of main memory available for block-nested loops join is 402 pages. Assume that at most 5 tuples in s match each tuple in r.

MTCE 703A: Advanced DBMS

Week: 5

1. Consider the following table. Give an example of update anomaly, an example of deletion anomaly and an example of insertion anomaly knowing that different salesmen can sell the same car but each salesman has a different commission. The commission for one salesman is always the same. The discount depends upon the date.

2. Consider the schedule of three transactions T1,T2 and T3.

S : r (A); r22 (B);w (A); r (B); r (A);w (B);w (A);w (B) 2

Where r stands for READ, w for WRITE and determine if the schedule is seializable. If so, give the schedule.

        3.

.

4. Assume the following actions listed in the order they are scheduled and prefixed with the transaction name. Assume that the timestamp of a transaction Ti is i. T1:R(Y), T2:R(X), T3:R(Y), T1:R(X), T1:W(Y), T2:W(X), T3:R(X)

       Add lock and unlock requests and describe how the following concurrency control mechanism A, B and C handle the sequence by giving the schedule with waiting time between actions. The DBMS should process the actions in the order shown. If a transaction is blocked it waits and its actions are queued until it resumes. When a transaction waits, the DBMS continues with the next action of an unblocked transaction in the sequence.

A- Strict 2PL with deadlock detection

B- Strict 2PL with timestamps used for deadlock prevention with Wait-Die policy

C- Strict 2PL with timestamps used for deadlock prevention with Wound-Wait policy.

5.  What are the costs to be considered when a transaction has to be rolled back when    recovering from deadlock?

MTCE 703A: Advanced DBMS

Week: 6 and 7

1. Consider the following two transactions

T1 : read (A);

read (B);

B = A + B;

write (B)

T2 : write (A)

read (B)

Add lock and unlock instructions so that the transaction T1 and T2 observe two-phase locking protocol. Is it deadlock free?

2. When are two schedules said to be view equivalent? 4

3. Define granularity, hierarchy of granularity of locks and multiple granularity locking.   Describe the modified two phase locking with multiple granularity locking.

4. Consider the data base with two areas A1 and A2 with files F1, F2 and A2 with files F3.F1 has records r11 to r19, and F2 has records r21 to r29, F3 has records r31 to r39.

(i) What is a granularity hierarchy? Draw the granularity hierarchy for the above database .

(ii) Suppose transaction T1 wants to read record r35 and T2 wants to read file F3 what are the locks to be placed? Can T1 and T2 execute concurrently? Justify.

(iii) Is it possible for T1 to unlock file F3. Justify.

(iv) If a transaction T3 now wants to write r11 will it be allowed to proceed?