Concurrency Control

On insert or group by. 2PL cannot managed it, predicate locking yes.

A sequence of read and write operations characterized by the same TID

sequence of read/write operations presents by concurrent transactions Concurrency control accepts or rejects schedules to avoid anomalies, the scheduler though has to accept or reject op. execution without knowing the outcome of the transactions (abort/commit)

Si is serializable when Si is equivalent to an arbitrary serial shedule of the same transactions.

Two schedules are view equivalent if they have the same reads-from set and the same final write set. A schedule is view serializable if it is view equivalent to an arbitrary serial schedule of the same transactions. Prevents: lost update: inconsistent read, ghost update (a). Detecting view equivalence to a given schedule is O(n). Detecting view equivalence to an arbitrary serial schedule is NP-complete (not feasible).

• Block of the concurrency control maanger • is in charge of deciding if and when read/write requests can be satisfiedd Without a scheduler we may have correctness problems

Value is read 2 times, and reads different values during the same T.

T1 only partially observes the effect of T2. All objects are already present. Ghost updates result from inconsistent reads.

Inconsistent read. A new set of objects are inserted by another transaction.

Is a simplifying hypothesis: the schedule contains only transactions performing commit

• View equivalence • Conflict equivalence • 2PL • Timestamp equivalence Each detecs a set of acceptable schedules, and is characterized by a different complexity in detecting equivalence.

Conflicting actions: Action Ai is in conflict with Aj (i != j) if both action operate on the same object and at least one of them is a write: • Read-Write conflicts (RW or WR) • Write-Write conflicts Two schedules are conflict equivalent if they have the same conflict set and each conflict pair is in the same order in both schedules. Conflict serializable: if it is equivalent to an arbitrary serial schedule of the same transactions. CSR: conflict serializable schedules. Detecting conflict serializability is possible through a conflict graph. CSR is a subset of VSR.

A node for each transaction. An edge Ti -> Tj if: • there exist at least a conflict between the two • Ai preceeds Aj Checking for cycles is O(V + E).

2 Phase Locking A lock may block others from accessing a resource. Locks: Write-Lock, Read-Lock. Read-Locks are shared. Write-Locks are exclusive. Lock escalation: R-Lock followed by W-lock on the same data. Used by most DBMS. Characterized by two phases: • Growing: needed locks acuired • Shrinking: all locks are released. 2PL is a subeset of CSR.

Scheduler becomes lock manager: • receives transaction requests and grants locks based on locks already granted. • when the lock is not granted the transaction is put in waiting state, the wait terminates when the locked resource is freed. • when a timeout runs out while a transaction is still waiting: extracts the transactions from waiting list, resumes it, returns an error code. • in the latter case the transaction may perform rollback (and possibly restart) or request again the same lock after some time (without releasing currently held resources) Lock manager exploits a lock table and the conflict table.

Transactions locks may be releasd only at the end of the transaction (after commit/abort). -> at the end of the transaction data is stable (this avoids dirty read completely). Allows the dropping of the commit projection hypothesis.

K * M / N K = active transactions M = average number of objects accessed by a transaction N = is the number of objects in the database

Table locks can be acquired at different granularities: • Table • Group of tuples (fragment): physical or logical • Single tuple • Single field in a tuple It is an extension of traditional locking, charaterized by a larger set of primitives: Shared lock (SL) eXclusive lock (XL) Intention of Shared Lock (ISL): intention of shared locking on node lower in the hierarchy. Intention of eXclusive Lock (IXL): same as ISL, but for exlusive lock Shared lock and Intention of eXclusive Lock(SIXL): shared lock of current object and intetion to get exlusive lock of lower level nodes. Locks are requested startinf from the root, relelased starting from the leafs. To request a SL or ISL need to own ISL or IXL on parent. To request a XL, IXL or SIXL, need own a IXL or SIXL, on its parent.

Depends on application type. If it performs localized reads or updates few objects -> detailed granularity if it performs massive reads or updates -> near root -> rough granularity Effects of granularity: too coorse -> reduces concurrency too fine -> forces overhead on lock manager.

The only solution capable of addressing Ghost (insert) Update (b). For 2PL a read operation is not in conflict with an insert op. -> new tuple cannot be locked in advance Predicate locking allows locking all data satisfying a given predicate. -> implemented in real systems using locking indices

There are two transaction types: • read-write • read only: no data or schema modifications, just SL. Isolation levels: • Serializable: predicate locking • Repeatable Read: strict 2PL (no predicate locking) -> repeated reads of existing objects can be correctly repeated, no protection gainst ghost update (b) • Read committed: no 2PL, read lock released ASA object is read. -> data is read only it is committed, dirty reads aboided • Read Uncommitted: only allowed for read only transactions. -> dirty read allowed. Syntax: SET TRANSACTION [ISOLATION LEVEL] [READ ONLY] [READ WRITE] Isolation level may be reduced only for read statements, since write operations are always executed with XLs.

Solving: Timeout • Most used solution in commercial systems • After time expires the transaction receives a negative answer and performs rollback. • Particular attention should be taken when choosing the timeout interval: too long (long waiting for resolving deadlock), short (many false positives, overloads the system) Preventing: Pessimistic/Conservative 2PL • All locks are acquired before the transaction starts (may not be possible) • Only younger transactions are allowed to wait Detection: Wait graph • nodes are transactions • a cycle represents a deadlock • used in distributed DBMS