DECEMBER 2006

Code: C-14 / T-11                                       Subject: DATABASE MANAGEMENT SYSTEMS

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Choose the correct or best alternative in the following:                                         (2x10)

a. Which one is the correct Option?

Logical data independence provides following without changing application programs:

(i) Changes in access methods.

(ii) Adding new entities in database.

(iii) Splitting an existing record into two or more records.

(iv) Changing storage medium.                                                                 

(A)  (i) and (ii)                                     (B)  (iv) only

(C)   (i) and (iv)                                   (D)  (ii) and (iii)

b. In an E-R diagram , Y is the dominant entity and X is a subordinate entity.  Then which of the following is incorrect :

(A) Operationally, if Y is deleted, so is X                                                                        

(B) X existence is dependent on Y

(C) Operationally, if X is deleted, so is Y                                                                         

(D)  Operationally, if X is deleted, Y remains the same

             c.   Relational Algebra is 

(A) Data Definition Language              (B)  Meta Language

(C)  Procedural query Language          (D)  None of the above

             d.   Which of the following aggregate functions does not ignore nulls in its results?

(A)  COUNT                                     (B)  COUNT (*)

(C)  MAX                                          (D)  MIN  

             e.   R(A,B,C,D) is a relation.  Which of the following does not have a lossless join dependency preserving BCNF decomposition

(A) (B) 

(C)  (D)

f.    Consider the join of a relation R with a relation S.  If R has m tuples and S has n tuples, then the maximum and minimum size of the join respectively are

(A) m+n and 0                                   (B)  m+n and

(C)  mn and 0                                      (D)  mn and m+n

             g.   Maximum height of a B+ tree of order m with n key values is

(A) (B)

(C) (D)  none of the above

             h.   Which one is the true statement:

(A) With finer degree of granularity of locking a high degree of concurrency is possible.    

(B) Locking prevents non-serializable schedules.

(C) Locking cannot take place at field level.          

(D) An exclusive lock on data item X is granted even if a shared lock is 

       already held on X.

             i.    Which of the following statement on the view concept in SQL is invalid?

(A) All views are not updateable        

(B)  The views may be referenced in an SQL statement whenever tables are 

       referenced.

(C) The views are instantiated at the time they are referenced and not when 

       they are defined.                          

(D) The definition of a view should not have GROUP BY clause in it.

             j.    Which of the following concurrency control schemes is not based on the serializability property?

 (A)  Two – phase locking                   (B)  Graph-based locking 

(C)  Time-stamp based locking            (D)  None of these.

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Supreme Products manufactures products like pressure cookers, cookwares, water purifiers, food processors etc.  The company markets its products to wholesalers all over the country and dealers sell them to customer.  The company has five regional offices and many sales persons are attached to regional offices.  Salespersons contact dealers and explain about products, incentives offered, training programs for wholesalers and demonstrations for customers etc.  Dealers place orders with the salespersons attached with the regional office of their location.  After receiving goods they make payments, which may be in instalments.  Company would like to develop a system to monitor sales of different products, performance of salespersons and orders from wholesalers.

Do the following:

                   (i)  Identify entities, attributes and relationships giving functionalities and draw an E-R diagram for the system.

                   (ii)  Convert this to relational tables explaining the logic involved.                     (5+5)

             b.   Give examples of:

(i) A many-to-many relationship in which one of the participants is another relationship.

(ii) A subtype that has an associated weak entity that does not apply to the super type.                                   (3 x 2)

Q.3     a.   Consider the following Relational Database

Employee (employee_name, street, city)

                   Works (employee_name, company_name, salary)

                   Company (company_name, city)

                   Manages (employee_name, Manager_name)

                   Write tuple calculus expressions for the following queries.

(i) Find the names of all employees in this database who live in the same city as the company for which they work.

(ii) Find the names of all employees who live in the same city and on the same street as do their Manager.

(iii) Find the names of all employees in this database who do not work for the company ‘FBC’.                                                           (4+3+3)

             b.   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)

                   * Give a relational-algebra expression for each of the following queries:

(i) Find the customers who have accounts in all branches of Bhopal.

(ii) Find the customers who have accounts in branches with assets more than 50 crores.                                                          (32)

Q.4     a.   Consider the following tables.

                   EMP (emp_no, name, salary, supervisor_no, sex_code, dept_code)

                   DEPT (dept_cd, dept_name)

                   Write down queries in SQL for getting the following information:

(i) Employees getting more salary than their supervisor.

(ii) Department name and total number of employees in each department who earn more than average salary for their department.

(iii) Department(s) having maximum employees earning more than 25000.

(iv) Name of employee(s) who earn maximum salary in their organisation.                     (4 x 3)

b.   Let R = (A,B,C,D) and F be the set of functional dependencies for R given by

Prove .                                                                                                 (4)

  Q.5     a. Consider a relation TENANT (NAME, CITY, STREET#, APT#, APT-TYPE, RENT, LANDLORD, ADDRESS) where following functional dependencies hold

APT#STREET#CITY  ADDRESS

                   ADDRESSAPT-TYPE

                   NAME ADDRESSRENT

                   LAND-LORD APT-TYPERENT

                   (i)  Are the following relation schemes in 3 NF?

                        APARTMENT (APT-TYPE, ADDRESS, RENT)

                        DWELLER (NAME, ADDRESS, RENT)

                   (ii) What updating and insertion anomalies do you foresee in TENANT, 

                        APARTMENT & DWELLER relations.

(iii) Do the APARTMENT & DWELLER relations have lossless join?

(iv) Find a key of this relation.  How many keys does TENANT have?        (2 x 4)

             b.   Find the decomposition of TENANT into 3NF having lossless join and preserving dependencies.                                                               (8)

Q.6   a.    Construct a B+ tree for the following set of key values under the assumption that the number of key values that fit in a node is 3.                          

               Key values (3,10,12,14,29,38,45,55,60,68)

               Show the steps involved in the following insertions (use your algorithm)

               Insert 11, insert 30.                                                                                         (10)

     b.   Explain the concept of two phase locking and show that it guarantees serialisability.             (6)

Q.7     a.   Explain the recovery process after system failure using checkpoint.                      (6)

b.   How does a query tree represent a relational algebra expression?  Give the rules, which allow selection operation to move as far down the tree as possible.                                                            (10)

Q.8     a.   What are the advantages of the tree locking protocol over the two-phase locking protocol?  Explain the phantom phenomenon.  Why this phenomenon may lead to an incorrect concurrency execution despite the use of a protocol that ensures serializability?                                                      (12)

             b.   Prove that a relation which is in 4NF must be in BCNF.                                      (4)

Q.9     a.   Explain the ill effects of concurrency in terms of the 3 problems which occur.                      (10)

             b.   Compare the two log-based recovery schemes in terms of ease of implementation and overhead cost.                                                                    (6)