HW4 Solutions Page

Return to homework page.

14.4

We are given R has 10,000 tuples at 10 tuples/page ; S has 2000 tuples at 10 tuples/page. b is a primary key of S. Both R and S are stored as heap files neither has any indexes and the buffer can hold up to 52 pages. We are then asked to answer the following questions:

What is the cost of joining R and S using a page-oriented simple nested loops join? What is the minimum number of buffer pages required for this cost to remain unchanged?

So roughly R is 10000/10 = 1000 pages long and S is 2000/10=200 pages long. Putting S as the outer loop gives 200+1000*200 =200200 I/Os. We need at least a 3 page buffer to do this one to hold a page from each of R and S and one to output the result.

What is the cost of joining R and S using block nested loops join? What is the minimum number of buffer pages required for this cost to remain unchanged?

We have 52 buffer pages. If we use 50 of them to hold pages from S and the other two to hold a page of R and to output, then the cost will be 200 + 1000*(200/50) = 4200 I/Os. We will need to use all 52 buffer pages for this cost to remain the same.

What is the cost of joining R and S using sort-merge join? What is the minimum number of buffer pages required for this cost to remain unchanged?

I will use the simpler/less accurate ``one-step'' estimate of the number of I/Os for sorting. The total cost is 2Mlog_{51}M + 2Mlog_{51}N + M + N. That is, 2*200*2+ 2*1000*2 + 1000 + 200 = 6000 I/Os. The minimum number of buffers is the least integer value X such log_{X-1}1000 <= 2. Exponentialing both seides gives 1000 <= (X-1)^2. 31.6 <= X-1. So X = 33 pages.

What is the cost of joining R and S using hash join? What is the minimum number of buffer pages required for this cost to remain unchanged?

The cost of hash merge join is 3(M+N)= 3(1000+200) = 3600 I/Os. The minimum number of buffers can be calculated using the condition B > (f*M)^{1/2}. (Note : in class used (f*(M+N))^{1/2}. This is an overestimate because we only need to be able to hold a whole hash partition of S in memory plus one page of R from the matching partition plus one page for output. Don't need to be able to hold a partition from both R and S; however, if you did it this way you should receive full marks. The answer in this case is 41 pages). Given this condition we have B > (1.4*200)^{1/2}. So B=17 pages would work.

What would be the lowest possible cost of joining R and S using any join algorithm? How much buffer space would be needed to achieve this cost? Explain briefly.

If we could read one of the two tables into memory then we could use the optimized block nested loop join. This would have a cost of M+N = 1200 I/Os. This would require 202 pages of buffer. The plus 2 is to read one page of R and still have a page left over for output.

How many tuples does the join of R and S produce, at most, and how many pages are required to store the result of the join back on disk?

Since S.b is a key for S each tuple of R can join with at most 1 tuple of S. So the join can at most have 10000 tuple. Assuming in the joined result we can store 5 tuples per page (since they are twice as long now), this will require roughly 2000 pages to store.

Would your answers to any of the previous questions in this exercise change if you were told that R.a is a foreign key that refers to S.b?

Since R.a is a foreign key of S.b, this gives us that the at most is part (6) will be exactly. That is 10000 tuples will be produced. Otherwise, the answers are unchanged.

16.3

We are given two transactions: T1=(R(X),R(Y),W(X)) and T2=(R(X),R(Y),W(X), W(Y)). Then we are asked to do the following problems:

1. Give an example schedule with actions of transaction T1 and T2 that results in a write-read conflict.

Consider:
S=(R_2(X),R_2(Y),[W_2(X),R_1(X)],R_1(Y),W_1(X), W_2(Y), c_1,c_2)
The square bracketted items give a write-read conflict.

2. Give an example schedule with actions of transaction T1 and T2 that results in a read-write conflict.

Consider:
S=(R_2(X),R_2(Y),[R_1(X), W_2(X)], R_1(Y),W_1(X), W_2(Y), c_1,c_2)
The square bracketted items give a read-write conflict.

3. Give an example schedule with actions of transaction T1 and T2 that results in a write-write conflict.

Consider:
S=(R_2(X),R_2(Y), R_1(X), R_1(Y), [W_2(X), W_1(X)], W_2(Y), c_1,c_2)
The square bracketted items give a write-write conflict.

4. For each of the three schedules, show that Strict 2PL disallows the schedule.

Schedule (1) would be disallowed because T2 would have to release its exclusive lock on X before T1 could acquire a share lock. But T2 in strict 2PL would not by able to release its lock until after it does it last operation, the W(Y).

Schedule (2) would be disallowed because T1 would have to release its share lock on X before T2 could get the exclusive lock. However, T1 cannot release any lock until after its last operation, W(X), if strict 2PL is followed.

Schedule (3) would be disallowed because T2 would have to release its exclusive lock on X before T1 could get the exclusive lock. However, T2 cannot release any lock until after its last operation, W(Y), if strict 2PL is followed.

16.5

Two new kinds of lock are introduced: an increment lock I and a decrement lock D. Associated with these locks are two operation increment an object and decrement an object. These locks on a given X are mutually compatible, but they are not compatible with share or exclusive locks on X. We are asked to solve the following problems related to these locks:

Illustrate how the I and D locks can increase concurrency.

Consider the schedule S=(I_1(X), incr_1(X), D_2(X), decr_2(X), X_1(Y), R_1(Y), X_1(Z) W_2(Z), W_1(Y), C1, UI_1(X), UX_1(Y), C2, UD_2(X), UX_2(Z)). This schedule uses strict 2PL locking with the I and D locks (Notice the unlocking is indicated by a U then the lock type). If I and D locks were not available one would need to get exclusive locks to simulate the increment and decrement. However, then T1 would need to finish before T2 began so that T2 could get the lock on X.

Informally explain how Strict 2PL guarantees serializability even in the presence of of I and D locks.

Since I and D locks are incompatible with X and S locks, if we follow strict 2 PL we can't get in to serializable problems by mixing locks between these two type. If we only use X and S types we already know we are serializable. This leaves mixing I and D locks on an object X. This will be okay because the operations of adding one to a number and subtracting one from a number commute.

16.6

We are asked to answer the following questions with regards to the four isolation levels and two access modes:

1. Consider the four isolation levels. Describe which of the phenomena can occur at each of these isolation levels: dirty read, unrepeatable read, phantom problem.

This question is a little hard to interpret. It could mean could the transaction cause this phenomena? Or could it experience this phenomena? I am assuming they mean experience the phenomena. That is, we are given the transaction is in some isolation level and we have no control over the isolation levels of the other transactions, what phenomena might the transaction expererience?

Access Mode should have no effect on the answer.
Isolation level    Possible Phenomena
Read Uncommitted: Dirty Read, Unrepeatable Read, Phantom
Read Committed: Unrepeatable Read, Phantom
Repeatable Read: Phantom
Serializable: None

In terms of Oracle the only level on which effects might be observed is the READ COMMITTED level. SO we illustrate those effect below. First, here is our set-up script:

/*
 Set up file for Hw4 16.1
*/

CREATE TABLE S (a INT, b INT);

INSERT INTO S VALUES (1, 1);
INSERT INTO S VALUES (2, 2);
INSERT INTO S VALUES (3, 2);

Here are the transcripts from the demonstration sessions:

2. For each of the four isolation levels, give examples of transactions that could be run safely at that level.

Read Uncommitted: insert into R values (5,6);
This transaction can run safely at the read uncommitted level since it never reads anything so cannot read uncommitted data.

Read Committed: select * from R where key_attrib=4;
Since we only read the value once and it is a key value it won't have any problem with unrepeatable reads or phantoms. This transaction could not run at the read uncommitted level as the read could still be dirty.

Repeatable Read:
select * from R where key_attrib=4;
select * from R where key_attrib=4;
Because of the repeated read this could not be run at any lower level.

Serializable: select avg(attr), max(attr) from R;
Someone could insert a row while this aggregate was being computed throwing off the count.

JDBC code for transactions:

//Hw4Transactions.java

import java.io.*;
import java.sql.*;

/**
   The purpose of this class is to implement test transactions which could
   run without problems at each of the various isolation levels:
   read uncomitted, read committed, repeatable read, and serilaizable.
   Each level has a corresponding public method with the transaction
   that can run at that level. There are also public create and desroy methods.
   For the isolation levels that Oracle has the transaction isolation level
   is set. main has a driver program. This class can be demonstrated
   by compiling it and running it as:

   java Hw4transactions.

   @author Chris Pollett
   @version 2003/11/27


*/
public class Hw4Transactions
{
   /**
      Test transaction for Read Uncommitted isolation level.
      Does an insert; does not read so can't have dirty read problems
    */
   public void readUncommitted()
   {
      System.out.println("\n***Read uncommitted transaction...");

      open();

      execute("INSERT INTO R VALUES (5,6)","Insert (5,6) succeeded",
         "Insert (5,6) failed.");

      close();
   }
   /**
      Test transaction for Read Committed isolation level.
      Does a read of a single row out of table then exits.
      Could be a dirty  read but since only one read don't
      have to worry about being unrepeatable.
    */
   public void readCommitted()
   {
      System.out.println("\n***Read Committed transaction...");
      open();
      execute("SET TRANSACTION ISOLATION LEVEL READ COMMITTED",
         "set isolation level read committed",
         "set isolation failure");
      executeRead(commonQuery, "Read succeeded.", "Read failed.");

      close();
   }
   /**
       Test transaction for Repeatable Read isolation level.
       Does the read committed read twice.
    */
   public void repeatableRead()
   {
      System.out.println("\n***Reapeatable Read transaction...");
      open();

      executeRead(commonQuery, "Read1 succeeded.", "Read1 failed.");
      executeRead(commonQuery, "Read2 succeeded.", "Read2 failed.");

      close();
   }
   /**
        Test transaction for Repeatable Read isolation level.
        Computes two aggregates: an average and a max. These
        could be thrown off by phantom problems if run at an
        isolation level below serializable
    */
   public void serializable()
   {
      System.out.println("\n***Read serializable transaction...");
      open();

      execute("SET TRANSACTION ISOLATION LEVEL SERIALIZABLE",
         "set isolation level serializable",
         "set isolation failure");
      executeRead("SELECT AVG(attr), MAX(attr) FROM R",
         "Read count succeeded",
         "Read count failed");

      close();

   }

   /**
       Used to set up our database. Database consists of one
       table R and initially has two rows.
    */
   public void create()
   {
      System.out.println("***Creating Database...");

      open();

      execute("CREATE TABLE R(key_attrib INT, attr INT, PRIMARY KEY(key_attrib))",
         "Table R created.",
         "Table R not created.");

      execute("INSERT INTO R VALUES (4,2)",
         "Row (1,2) inserted.",
         "Row (1,2) not inserted");

      execute("INSERT INTO R VALUES (2,2)",
         "Row (2,2) inserted.",
         "Row (2,2) not inserted");

      close();
   }


   /**
      Used to tear down (get rid of) the database after the tests are down.
    */
   public void destroy()
   {
      System.out.println("***Destroying Database...");

      open();
      execute("DROP TABLE R", "Dropped Table R", "Failed to Drop R.");
      close();
   }

   /*
      Uses global object conn to open a connection to a database.
    */
   void open()
   {
      try
      {
         conn =
            DriverManager.getConnection(connectString, login, password);

         stmt = conn.createStatement();
      }
      catch(SQLException e)
      {

         System.err.println("Error opening connection.");

         e.printStackTrace();

      }
   }
   /*
       Closes database connection held by global object conn.

    */
   void close()
   {
      try
      {
         stmt.close();

         conn.close();
      }
      catch(SQLException e)
      {

         System.err.println("Error closing connection.");

         e.printStackTrace();

      }
   }

   /*
      Used to execute one SQL statement against the database
      we are currently connected to.

      @param sql - SQL command to execute
      @param msgSuccess - String to print if successful
      @param msgFail - String to print if command fails
   */
   void execute(String sql, String msgSuccess, String msgFail)
   {
      try
      {
         stmt.execute(sql);
         System.out.println(msgSuccess);

      }
      catch(SQLException e)
      {

         System.err.println(msgFail);

         e.printStackTrace();

      }
   }

   /*
      Used to execute one SQL query and print first two columns of
      first row. Query is done against the database
      we are currently connected to.

      @param sql - SQL command to execute
      @param msgSuccess - String to print if successful
      @param msgFail - String to print if command fails
   */
   void executeRead(String sql, String msgSuccess, String msgFail)
   {
      execute(sql,msgSuccess,msgFail);

      try
      {
         ResultSet rset = stmt.getResultSet();
         rset.next();
         System.out.println("First row of result: Col1="
            + rset.getInt(1) + " Col2=" + rset.getInt(2));

      }
      catch(SQLException e)
      {

         System.err.println(msgFail);

         e.printStackTrace();

      }
   }

   /*
      Creates the toy database, executes the transaction for each
      isolation level, then tears down the database.
   */
   public static void main(String[] args)
   {
      try
      {
         DriverManager.registerDriver(
            new oracle.jdbc.OracleDriver());
      }
      catch(SQLException e)
      {

         System.err.println("Problem getting driver.");

         e.printStackTrace();

      }

      Hw4Transactions hw4 = new Hw4Transactions();
      hw4.create();

      hw4.readUncommitted();
      hw4.readCommitted();
      hw4.repeatableRead();
      hw4.serializable();

      hw4.destroy();


   }

   String connectString="jdbc:oracle:thin:@sigma.mathcs.sjsu.edu:1521:cs157b";
      // Connection string to connect to school database
   String login="my_login"; //Oracle Login
   String password="my_password"; //Oracle password

   String commonQuery="SELECT * FROM R WHERE key_attrib=4";
      //query used by both read committed and repeatable read transactions

   Connection conn; // Connection object reference used in connecting to a DB
   Statement stmt; // Statement object used to execute queries and updates
}

3. Why does the access mode of a transaction matter?

If the access mode is READ ONLY then since only shared locks are required more concurrency can be achieved. Similar, such a transaction is less likely to get aborted if multiversion concurrency control is used.

17.2

For each schedule below we are supposed to determine if it is serializable, conflict-serializable, view-serializable, recoverable, avoid-cascading-aborts, or strict. It might belong be more than one of these. We adopt the convention that we list the most stringent classes it belongs to. Use Figure 17.9 from the book to see what other classes are implied by our answer.

1. R_1(X), R_2(X), W_1(X), W_2(X), C1, C2
Avoid cascading aborts. Could be made strict by moving the C1 before the W_2(X).

2. W_1(X), R_2(Y), R_1(Y), R_2(X), C1, C2
Conflict serializable as T1, T2. It is also recoverable. If the C1 were before the R_2(X) it would strict.

3. R_1(X), R_2(Y), W_3(X), R_2(X), R_1(Y), C1, C2, C3
Conflict serializable as T1, T3, T2. Not recoverable becuase T2 reads X from uncommitted T3.

4. R_1(X), R_1(Y), W_1(X), R_2(Y), W_3(Y), W_1(X), R_2(Y), C1, C2, C3
Not serializable becuase of the interaction of T1 and T2 on Y. For the same reason not recoverable.

5. R_1(X), W_2(X), W_1(X), A2, C1
Schedule is serializable as the schedule T1 and avoids cascading rollbacks.

6. R_1(X), W_2(X), W_1(X), C2, C1
Schedule is not serializable but avoids cascading rollbacks.

7. W_1(X), R_2(X), W_1(X), A2, C1
Schedule is serializable as the schedule T1 and is recoverable but does not avoid cascading rollbacks. T2 read from uncommitted T1.

8. W_1(X), R_2(X), W_1(X), C2, C1
Not serializable but is recoverable since T2 read from T1 which commites eventually.

9. W_1(X), R_2(X), W_1(X), C2, A1
Not serializable becuase T2's read is of bogus data as T1 aborts. Also not recoverable for the same reason.

10. R_2(X), W_3(X), C3, W_1(Y), C1, R_2(Y), W_2(Z), C2
Conflict serializable as T1, T2, T3. It also avoids cascading aborts.

11. R_1(X), W_2(X), C2, W_1(X), C1, R_3(X), C3
Not Serializable. It also avoid cascading aborts.

12. R_1(X), W_2(X), W_1(X), R_3(X), C1, C2, C3
Not serializable. Recoverable but T3's read of T1 implies does not avoid cascading aborts.

Return to homework page.