Concurrency problems are common in a database. Locking and stamping are two techniques to avoid them. Here are corrected exercises on this subject.
Preamble
Expression of constraints
—————————
0. PL/SQL Preamble
SQL:
– Declarative therefore no control structures (loops, conditions, etc.)
– Data+set operations
=> Few applications achievable by a simple sequence of SQL queries; need to enrich SQL with procedural capabilities.
3 possibilities
– Embedded SQL (PRO*C…)
– Communication API (SQL-CLI…)
– Dedicated language (PL/SQL…)
Advantage of dedicated languages: Procedures executed on the server side -> Only results are returned to the client -> Minimal network exchanges
Q0. PL/SQL procedures
Q0.1
CREATE OR REPLACE PROCEDURE D
(noc IN ACCOUNTS.Numero%TYPE,
credit IN NUMBER )
IS
BEGIN
UPDATE ACCOUNTS SET BALANCE = BALANCE – debit
WHERE Number = noc;
END;
/
Q0.2
CREATE OR REPLACE PROCEDURE C
(noc IN ACCOUNTS.Numero%TYPE,
credit IN ACCOUNTS.Balance%TYPE)
IS
BEGIN
UPDATE ACCOUNTS SET BALANCE = BALANCE + credit
WHERE Number = noc;
END;
/
Q0.3
CREATE OR REPLACE PROCEDURE S
(noc IN ACCOUNTS.Number%TYPE)
IS
theBalance ACCOUNTS.Balance%TYPE;
BEGIN
SELECT Balance INTO theBalance
FROM ACCOUNTS
WHERE Number = noc;
DBMS_OUTPUT.PUT_LINE(theBalance);
END;
/
Q0.4
CREATE OR REPLACE PROCEDURE V
(nofrom IN ACCOUNTS.Numero%TYPE,
noto IN ACCOUNTS.Numero%TYPE,
trans IN ACCOUNTS.Balance%TYPE)
IS
BEGIN
D (nofrom, trans);
C (noto, trans);
END;
/
Q0.5
CREATE OR REPLACE FUNCTION check
(noc IN ACCOUNTS.Numero%TYPE,
amount IN ACCOUNTS.Balance%TYPE)
RETURN BOOLEAN
IS
isSolvent BOOLEAN;
theBalance ACCOUNTS.Balance%TYPE;
BEGIN
SELECT Balance INTO theBalance
FROM ACCOUNTS
WHERE Number = noc;
IF Balance >= amount THEN
isSolvent := TRUE;
ELSE
isSolvent := FALSE;
END IF;
RETURN is Solvent;
END check;
Exercise 1
Question 1
To avoid possible concurrency issues, the administrator chooses to execute transactions serially. We consider the case of two simultaneous transactions on account X, the balance of which is initially 1000 Euros. Both are debits, the first is 400 Euros, the second is 800 Euros.
At the precise moment when T1 starts its flow, T2 starts.
What is going on ?
How can we speed up the execution of these transactions?
Question 2
Six bank account managers each carry out, in a transaction, and simultaneously, operations on 4 accounts A, B, C, and D. Let Ei(A) be a writing operation on account A by manager i, and Li( A) a reading operation of account A by manager i. Consider the following operation sequence: E2(A), L2(B), L6(D), E5(C), E3(A), L5(A), L1(C), L2(D), L3( C), E4(C), E3(D), L4(B), L1(B).
- Build it graph precedence of these transactions.
- What execution issues might arise?
- Is this execution serializable?
Exercise 2
Question 3
We place ourselves in the case of locking, with tuple level granule.
Show that the locking algorithm “spots” the problem of this execution. What would be the most suitable conflict resolution algorithm for this execution?
Exercise 3
Question 4
Suggest a algorithm reading and a writing algorithm with stamping. Are we sure to make this execution serializable with the stamping system? Prove that this is true for any non-serializable execution.
Question 5
Compare the two families of techniques seen previously (locking and stamping). Is the simple stamping algorithm better suited for this execution than locking?
Q4. Precedence graph
The competition control mechanism must provide each transaction with the illusion that it is the only one executing on the DB, ie, the effective execution (therefore interleaved) of the transactions must be equivalent to a serial execution of these (execution: ordered sequence of read/write operations).
Executions equivalent to a serial execution are called serializable. The concurrency mechanism must ensure that it only generates serializable executions.
Execution: ordered sequence of read/write operations by different transactions.
Serial execution: Operations from different transactions do not interleave.
Is it possible to reorder the execution to make it serial?
No, because it is impossible to swap entries with any other operation -> Induces a precedence relationship between transactions.
More formally:
Ti precedes Tj (“Ti < Tj”) if Ai occurs before
Aj in the execution Ai and Aj imply the same object of the BD
Ai or Aj is a writing action
This precedence relationship generates the precedence graph, in which a vertex is a transaction, and a directed edge is a precedence relationship.
Eg: Ti -> Tj means Ti precedes Tj
View by object of operations (simpler than global view, but loses the order of operations within a transaction):
A: E2(A) E3(A) L5(A)
B: L2(B) L4(B) L1(B)
C: E5(C) L1(C) L3(C) E4(C)
D: L6(D) L2(D) E3(D)
Precedence graph:
T2 -> T3 <-> T5 -> T1 -> T4
T6 ->|
Precedence graph property:
Serializable execution iff absence of cycle (eg, above, T3 must be carried out before T5, which must be carried out before T3)
Problem: detecting cycles is NP Complete (Non-deterministic, Polynomial, difficult)
Noticed:
Isolation Property = Transactions must execute AS if they were alone on the database. Serializability ensures that the result of an interleaved execution is the same as that of a serial execution. But, serializability is not a sufficient condition to ensure that transactions execute in isolation.
Example of non-isolated serializable execution (cascaded ABORT):
T1 < T2 < … < Tn
Q5. Most used mechanism for isolation: lock and unlock
Most used locking protocol: 2 Phase lock
Phase 1: All locks are acquired, no unlock is performed
Phase 2: All unlocks are completed, no locks are acquired
Property: Ensures the serializability of the execution of a legal schedule (ie, lock1(X) cannot be followed by lock2(X) but by unlock1(X))
Four types of locks: Shared VS Exclusive / Short VS long (see compatibility matrix stated)
Two types of operation: Read and Write.
Different degrees of insulation:
* Degree 0 (Read uncommitted):
Installation of exclusive short write locks
-> Reads even objects modified by transactions that have not committed
* Degree 1 (Read committed):
Installation of exclusive long write locks
Setting short shared read locks
-> Only read objects modified by committed transactions
* Degree 2 (Repeatable Read):
Degree 1 + Installation of long shared read locks
-> Repeatable reading
* Degree 3 (Serializable):
Level 2 + Eliminate ghosts
Locking “spots” the serializability problem: deadlocks
Several ways to manage deadlocks
* TimeOut: Kills transactions that take more than x seconds to execute
* Detection: Waiting graph
T5 <-> T3
<- T1
<- T4
Graph Built as execution progresses
Rollback any transaction that may cause a cycle to appear in the waiting graph
Example: 1. T5 -> T3 2. T1 -> T5 -> T3 3. T1 -> T5 <-> T3 ==> Rollback of T3
Problem: Cycle detection always NP complete; can be long if the graph is wide
* Prevention: Timestamps
Prioritizes old transactions to prevent deadlocks from occurring.
Timestamp associated with each transaction.
T1 wants to acquire a lock on an object locked by T2.
Solution 1: Wait-Die
if T1 older than T2, T1 waits
otherwise T1 Rollback (and is restarted with the same timestamp)
Solution 2: Wound-Wait (waits for old transactions)
if T1 older than T2, T2 must leave the lock and Rollback
otherwise T1 waits
-> Never deadlock: T1 will end up being the oldest and therefore executed with priority.
Wait-die VS Wound-wait:
Locks acquired at the start of a transaction -> Old transactions are more likely to have their locks before young ones
-> Wound-wait: causes little Rollback because see assumption
Wait-die causes a lot of Rollback because see assumption; but each time at the beginning of young transactions
Stamps:
T2:1 T6:2T5:3T3:4T1:5T4:6
Wait-die:
Stamps:
T2:1 T6:2T5:3T3:4T1:5T4:6
Wound-wait:
Q5.b.
Altruistic locking: A transaction releases its locks when it no longer needs them.
+: Effective
– : (i) Dirty read problem; (ii) Execution a priori not 2PL therefore a priori not serializable.
Q6.
Stamping system: Assigns a stamp to each transaction (generally the timestamp of its creation), prevents access to objects contrary to the order of the stamps -> Priority to young transactions. Transactions arriving late are Rollbacked and restarted with a new time stamp. Part of the family of optimistic protocols, ie, effective method when few conflicts because little overhead but potentially a lot of rollback.
Two rules:
Read too late: A transaction can only read data if it is younger than the last writer
Write too late: A transaction can only write data if it is younger than the last reader and writer
Basic algorithm:
– Place stamp on each transaction
– Each object retains the stamp of the last reader as well as that of the last writer
– When Ti wants to read object O:
If stamp < O.LastWriter: Read too late -> Ti ROLLBACK then restarts with new stamp
Otherwise OK
– When Ti wants to write the object O:
If Ti.stamp < O.LastReader || Ti.stamp < O.LastWriter: Write too late -> Ti ROLLBACK then restarts with new stamp
Otherwise OK
Example:
Stamps:
T2: 1-8 T6: 2T5: 3-7T3: 4T1: 5T4: 6
Objects:
A (L: ; E: 1) A (L: ; E: 4)
B (L: 1; E: )
C (L: 5; E: 3-6) C (L: 5; E: 6)
D (L: 2; E: 4)
The precedence graphs of stamping executions never have a cycle.
Proof by absurdity:
Consider the cyclic precedence graph of an execution obtained by stamping:
T1 -> … -> Ti <-> Tj -> … -> Tn => Ti < Tj < Ti
<=> i < j < i
Contradiction
Q8.
Stamping good when few conflicts (no waiting); bad when a lot of conflicts (lots of rollback).
Good locking when lots of conflicts (less Rollback than stamping); bad when few conflicts (useless waits, lock management overhead).
Commercial systems attempt to combine the advantages of both: multiversion stamping (a variation of single stamping discussed above) for Read Only transactions, and 2PL locking for Read/Write transactions. (see p. 978 of “DB Systems: the complete book” by Widom and Ullmann)
EN 
FR 
ES