Recitation #3

NOTE THIS IS PURELY OPTIONAL

PAPER PROBLEMS

1. r_1(x), r_2(x), w_1(x),w_2(x)

Write the DSG for the above schedule.
Is this schedule conflict serializable?
Is this schedule view serializable?

2. w_2(z),r_1(x),r_1(y),r_2(y),w_1(x),r_2(x),w_2(y),w_1(z),w_2(z)

Is this schedule conflict serializable?
Is this schedule view serializable?

3. Assume that the following schedule with locks is executed over a SVCC mechansm.

rlk_1(x), r_1(x), rlk_2(x), wlk_1(x),w_1(x),ulk_1(x),cmt_1, wlk_2(x),w_2(x),ulk_2(x), cmt_2

Describe what happens.
Does this schedule respect 2PL, SS2PL (AKA Rigorous), Conservative 2PL?

SYSTEM PROBLEMS

Run these system exercises on PostgreSQL version 9.1 or greater.

4. Consider that we have concurrent transactions of the following form:

BEGIN;
SET TRANSACTION ISOLATION LEVEL X;
  select amount from account where id=1;
  select amount from account where id=2;
  -- here the host program checks if there are positive funds in account 1.
  update account set amount = amount - 10 where id = 1;
  update account set amount = amount + 10 where id = 2;
COMMIT;

The initial state of the database is

Account (id, amount)
          1      10
          2      10

Test system when X is READ COMMITTED, REPEATABLE READ and SERIALIZABLE.

Under which conditions is the amount in account 1 able to dip below 0?

(Extra) If you are really interested, write a script that launches
many concurrent money transfer transactions under these three isolation
levels. Document the performance (i.e. throughput).

5. Consider two transaction T1 and T2

T1 updates the amount of account for id 1, then updates the amount of
account for id 2. T2 does the same, but updates account for id 2 then id 1.
Create a deadlock under serializable and describe what happens.

6. Consider that we have two concurrent transactions of the following
form:

BEGIN;
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
  select amount from account where id=1;
  -- here the host program compounds amount by 10% and stores in local
  -- variable X
  update account set amount = X where id = 1;
COMMIT;

Why is this big time trouble? How would you fix it?

Problems 7-12*

Consider we have 2 runways and three time slots that planes may
land. We represent the initial state of this problem in the following
table:

runway time_slot flight condition
     1         1   NULL      fair
     1         2   NULL      fair
     1         3   NULL      fair
     ...
     2         1   NULL      fair
     2         2   NULL      fair
     2         3   NULL      fair   
     ...

Note that runway and time_slot are a primary key of the table and should be declared so!

Two transactions (T_1 and T_2) want access to this table
concurrently. In the problems that follow, always run T_1 before T_2,
but start T_2 before T_1 commits, but after T_1 has executed its
UPDATE operation. Use ps_sleep to automate this process. Always run
the transactions over the initial state of the database above**. For
each of the problems below, run under all 9 possible permutations of
PostgreSQL isolation levels (READ COMMITTED, REPEATABLE READ,
SERIALIZABLE) and group resulting behaviors into equivalence
classes. For example case 1: T_1 under RC, T_2 under RC; case 2 T_1
under RC, T_2 under RR; case 3. ... Think about what you can conclude
from these observations and be ready to discuss.

7. T_1: Book flight SK123 for runway 1 at time 1
T_2: Book flight DY321 for runway 1 at time 1

8. T_1: Book flight SK123 for runway 1 at time 1
T_2: Book flight DY321 for runway 1 at time 2

9. T_1: Book flight SK123 for runway 1 at time 1
T_2: Set condition = 'rain' for runway 1 at time 1

10. T_1: Select the available runways for time 1, wait 20 seconds, and book the lowest number runway for SK123.
T_2: Select the available runways for time 1, wait 20 seconds, and book the lowest number runway for DY321.

Note you should start T_2 as T1 is 'waiting 20' seconds.

11. Define a PostgreSQL rule that guards against updates that allow for two flights being booked on the same runway in consecutive time steps.

12. Rerun problem 7 under with the rule of 11 defined.

* Problems 7-12 are modeled loosely on the exercises given in Steve
Hegner's Database Systems course.

** Sorry, but there is likely strange behaviour in PostgrSQL when all
the tuples fit in a single page/block. So it is advisable to generate an
initial database with say 1000 time slots and 50 runways. That will
insure that more than one page/block is being utilized.

Recitation #3

***NOTE THIS IS PURELY OPTIONAL***

PAPER PROBLEMS

NOTE THIS IS PURELY OPTIONAL