Concurrency Control

Question 1

Ghost update type b: when does it happen.

Can it be managed with 2PL?

Answer 1

On insert or group by.

2PL cannot managed it, predicate locking yes.

Question 2

Definition of transaction

Answer 2

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

Question 3

Schedule definition

Answer 3

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)

Question 4

Serializable schedule

Answer 4

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

Question 5

View equivalence and view serializable schedule

Answer 5

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).

Question 6

Scheduler

Answer 6

• 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

Question 7

Lost Update

Answer 7

Question 8

Dirty Read

Answer 8

Question 9

Inconsistent read

Answer 9

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

Question 10

Ghost update (a)

Answer 10

T1 only partially observes the effect of T2.

All objects are already present.

Ghost updates result from inconsistent reads.

Question 11

Ghost update (b)

Answer 11

Inconsistent read.

A new set of objects are inserted by another transaction.

Question 12

Commit projection

Answer 12

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

Question 13

Equivalence classes

Answer 13

• View equivalence
• Conflict equivalence
• 2PL
• Timestamp equivalence

Each detecs a set of acceptable schedules, and is characterized by a different complexity in detecting equivalence.

Question 14

Conflict equivalence, conflict serializable

Answer 14

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.

Question 15

Conflict graph

Answer 15

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).

Question 16

2PL

Answer 16

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.

Question 17

2PL: Lock manager

Answer 17

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.

Question 18

Strinct 2PL

Answer 18

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.

Question 19

2PL: Probability of conflict

Answer 19

K * M / N

K = active transactions

M = average number of objects accessed by a transaction

N = is the number of objects in the database

Question 20

Hierarchical locking

Answer 20

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.

Question 21

Selction of lock granularity

Answer 21

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.

Question 22

Predicate locking

Answer 22

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

Question 23

SQL2 Standard: Locking

Answer 23

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.

Question 24

Deadlock: solutions, how to prevent it, how to detect it

Answer 24

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