State True/False and justify. No credit for answers w/o suitable justification.

1. In case of Grid Files, a bucket split always results in a partitioning operation.
2. Random Access Media like Disk is never good for sequential scans.
3. Any number of insertions can always happen simultaneously in Grid File but not in a B+ tree.
4. B# tree cannot be used to organise records if decision making keys are not unique.

1. Give to-the-point answers for the following -

   1. Name the ACID properties of database transactions.
   2. Enumerate any two concurrency problems associated with database transactions.
   3. Why is "Two Phase Locking" called so?
   4. When is "Two Phase Commit" important?
   5. Complete the given statement -
      The expression "(A JOIN B) [projection]" is equivalent to the expression "(A [A-projection]) JOIN (B [B-projection])", if and only if ..... ?
   6. Consider a database organisation in which key is hashed to an address in a table that contains pointer to the actual record in program data file. Give (dis)advantages of this organisation wrt following issues -
      
      1. Variable length records.
      2. Random retrieval of records.
   7. Let transactions T1, T2 and T3 be defined to perform the following operations on some item A in the database -
      
      T1 : Add one to A
      T2 : Double A
      T3 : Display current value of A on screen and then set A to one

      If these transactions are allowed to execute concurrently -

      1. How many possible correct results are there?
      2. Enumerate all the correct results and corresponding transaction sequences, assuming the initial value of A as N.
2. Give the implications of following on recovery -
   1. Force writing buffers to database at commit.
   2. Never physically writing buffers to database prior to commit.
3. Consider the situation that updates are not made directly to the database itself, but instead are recorded in a physically distinct file, called as differential file, and are merged with the actual database at some suitable subsequent time. Briefly discuss the merits/demerits of this scheme wrt following issues -
   
   1. Database recovery.
   2. Sequential access to the data.
4. Consider a naive database system that executes user query as given, w/o performing any query optimisation. Which out of below two queries will you choose for better performance. Justify your choice.
   1. (A JOIN B) where (A.ja = B.ja and B.ja > 50)
   2. ((A where A.ja > 50) JOIN (B where B.ja > 50)) where (A.ja = B.ja)
5. Consider a secure database that permits queries that derive aggregated information but not queries that derive individual information. For example, the query - "What is the average salary of teachers?" will be permitted, while the query - "What is the salary of teacher Rustom?" will not be. Is there a possiblity to find the salary of Rustom via legal query/queries? If yes, give the query/queries in verbal English (the way example queries are given in this question).
6. Consider a DBMS with write-ahead logging. Which underlying file system will you choose for it, for better performance - ext2 or ext3? Justify your choice.

Hints for Mid Semester Examination

1. FALSE. Depends on (bucket) data distribution in search space (partitions, bucket is associated with).
2. FALSE. Sequential data could be laid on consecutive sectors on a track (and consecutive tracks, if needed) on the disk.
3. FALSE. As long as insertions are happening in different buckets that can accomodate them, no issue.
4. TRUE. B# tree is minor variation of B tree to achieve better space utilisation.

Hints for End Semester Examination

1. To-the-point answers.

   1. Atomicity, Consistency, Isolation and Durability
   2. Mention any two of following -
      - The lost update problem
      - Temporary update OR Dirty read OR The uncommitted dependency problem
      - Incorrect summary OR The inconsistent analysis problem
      - Unrepeatable read
      
   3. Because in Two Phase Locking, the transaction has two phases - a lock acquisition phase and a lock releasing phase. In practice the second phase is usually compressed into the single operation of COMMIT at end of transaction.
   4. Two Phase Commit is important whenever a given transaction can interact with multiple, independent "resource managers", each of them managing it's own set of recoverable resources, eg. a transaction than updates both an IMS database and a DB2 database.
   5. the attributes named in "projection" consist of the union of the attributes named in "A-projection" and "B-projection" and include all of the attributes that are common to the two relations.
   6. Hints -
      
      1. (Advantage) Variable length records can be accomodated easily.
      2. (Disadvantage) Additional block access for random retrieval of records.
   7. 1. Six possible correct results, corresponding to the six possible serializations of the three transactions.
      2. Following table enumerates all the correct results and corresponding transaction sequences -
         

             Transaction Sequence | Final Value of A | Value of A displayed on screen
             ---------------------+------------------+-------------------------------
                 T1 - T2 - T3     |         1        |           2*N + 2  
                 T1 - T3 - T2     |         2        |           N + 1  
                 T2 - T1 - T3     |         1        |           2*N + 1 
                 T2 - T3 - T1     |         2        |           2*N 
                 T3 - T1 - T2     |         4        |           N 
                 T3 - T2 - T1     |         3        |           N 
             ------------------------------------------------------------------------
            

2. 1. REDO is never necessary following system failure.
   2. Physical UNDO is never necessary, and hence UNDO logs are also unnecessary.

3. 1. Recovery after a program/hardware failure is fast. The risk of a serious data loss is reduced.
   2. Sequential access to the data - eg., via an index, is not efficient.

4. "Query B" will (always?) result in smaller size tables (subsets of A and B) being joined (cartesian product) and thus smaller table on which restriction is applied. Look out for overall I/O and comparison operations.

5. Yes. A possibility exists with queries like the one given below.

   Q1 : How many male PUCSD teachers aged between 38 and 42 are there, who are MCA graduates from PUCSD and expert in Functional Programming?
   Q2 : What is the average salary of male PUCSD teachers aged between 38 and 42, who are MCA graduates from PUCSD and expert in Functional Programming?

   If answer to query Q1 is one and Rustom matches the criteria of this query, we will get salary of Rustom via query Q2.

6. Ext3 is a logging based (journalling) flesystem.