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 launchesmany concurrent money transfer transactions under these variousthree isolationlevels. 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 ofaccount 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 followingform:

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 mayland. We represent the initial state of this problem in the followingtable:

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 tableconcurrently. 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 itsUPDATE operation. Use ps_sleep to automate this process. Always runthe transactions over the initial state of the database above**. Foreach of the problems below, run under all 9 possible permutations ofPostgreSQL isolation levels (READ COMMITTED, REPEATABLE READ,SERIALIZABLE) and group resulting behaviors into equivalenceclasses. For example case 1: T_1 under RC, T_2 under RC; case 2 T_1under RC, T_2 under RR; case 3. ... Think about what you can concludefrom 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 on a single page. 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 is being utilized.