LOCKING AND TIME STAMPS

Question 1

What is locking?

Answer 1

A procedure used to control concurrent access to data. When one transaction is accessing the database, a lock may deny access to other transactions to prevent incorrect results.
In this method, a scheduler uses the locks to ensure serializability

Question 2

How does a transaction obtain a lock?

Answer 2

Transactions must request and release locks in addition to reading and writing database elements.
A transaction obtains locks on the database elements it accesses , to prevent other transactions from accessing these elements, at roughly the same time, thereby incurring the risk of un-serializability .

Question 3

What are the two types of locks?

Answer 3

1. Shared lock If a transaction has a shared lock on a data item, it can read the item but not update it. Since read operations cannot conflict, it is permissible for more than one transaction to hold shared locks simultaneously on the same item
2. Exclusive lock If a transaction has an exclusive lock on a data item, it can both read and update the item. As long as a transaction holds the exclusive lock on the item, no other transactions can read or update that data item

Question 4

How are locks used?

Answer 4

Any transaction that needs to access a data item must first lock the item, requesting a shared lock for read only access or an exclusive lock for both read and write access.

If the item is not already locked by another transaction, the lock will be granted.

If the item is currently locked, the DBMS determines whether the request is compatible with the existing lock.
If a shared lock is requested on an item that already has a shared lock on it, the request will be granted; otherwise, the transaction must wait until the existing lock is released

Question 5

When is a lock released

Answer 5

A transaction continues to hold a lock until it explicitly releases it either during execution or when it terminates (aborts or commits). It is only when the exclusive lock has been released that the effects of the write operation will be made visible to other transactions

Question 6

Describe an incorrect locking Schedule

Answer 6

*See doc for pic

Question 7

What is two-phase locking (2PL)?

Answer 7

A protocol concerning the positioning of the lock and unlock operations in every transaction in order to guarantee conflict serializability.

Question 8

What is conflict serializability?

Answer 8

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

Question 9

What are conflicting operaions?

Answer 9

Conflicting operations: Two operations are said to be conflicting if all conditions satisfy:

They belong to different transactions
They operate on the same data item
At Least one of them is a write operation

Question 10

What are the two phases of a transaction according to 2PL?

Answer 10

• Growing phase, in which it acquires all the locks needed but cannot release any locks.
• Shrinking phase, in which it releases its locks but cannot acquire any new locks.

Question 11

What are the rules of 2PL?

Answer 11

• A transaction must acquire a lock on an item before operating on the item. The lock maybe read or write, depending on the type of access needed.
• Once the transaction releases a lock, it can never acquire any new locks.

Question 12

Describe how 2PL can prevent lost update problem, uncommitted dependency problem and inconsistent analysis problem using 2PL

Answer 12

*See phone for pics

Question 13

What is a deadlock?

Answer 13

several transactions are forced by the scheduler to wait for a lock held by another transaction
Results when two (or more) transactions are each waiting for locks to be released that are held by the other.

Question 14

How can one break deadlock?

Answer 14

Abort one or more of the transactions usually involving undoing all the changes made by aborted transaction(s)

Question 15

Describe deadlock prevention and how is it carried out?

Answer 15

DBMS looks ahead to see if transaction would cause deadlock and never allows deadlock to occur.

Could order transactions using transaction timestamps:

Wait-Die - only an older transaction can wait for younger one, otherwise transaction is aborted (dies) and restarted with same timestamp.
Wound-Wait - only a younger transaction can wait for an older one. If older transaction requests lock held by younger one, younger one is aborted (wounded).

Question 16

Describe deadlock detection and recovery?

Answer 16

DBMS allows deadlock to occur but recognizes it and breaks it.
Usually handled by construction of wait-for graph (WFG) showing transaction dependencies:
Create a node for each transaction.
Create edge Ti -> Tj, if Ti waiting to lock item locked by Tj.
Deadlock exists if and only if WFG contains cycle.
WFG is created at regular intervals

Question 17

Describe timeouts as a method of deadlock detection and recovery

Answer 17

Transaction that requests lock will only wait for a system-defined period of time.
If lock has not been granted within this period, lock request times out.
In this case, DBMS assumes transaction may be deadlocked, even though it may not be, and it aborts and automatically restarts the transaction

Question 18

Describe time stamping

Answer 18

Transactions ordered globally so that older transactions, transactions with smaller timestamps, get priority in the event of conflict.

Conflict is resolved by rolling back and restarting transaction.

No locks so no deadlock.

Question 19

What are the advantages and disadvantages of locks and timestamps

Answer 19

Locks:
Great when there are many conflicts
Poor when there are few conflicts
Great for read/write transactions.
Timestamps:
Poor when there are many conflicts (many rollbacks)
Great when there are few conflicts
Great for read only transactions

Question 20

How does 2PL guarantee conflict serializability

Answer 20

Each Xact must obtain a S (shared) lock on object before reading, and an X (exclusive) lock on object before writing.
 A transaction can release its locks once it has performed its desired operation (R or W). A transaction cannot request additional locks once it releases any locks.
 If an Xact holds an X lock on an object, no other Xact can get a lock (S or X) on that object. lock).

Question 21

unrepeatable read problem?

Answer 21

The unrepeatable problem occurs when two or more read operations of the same transaction read different values of the same variable.
EG. T1 Read(x), T2 Read(x), T1 Write(x), T2 Read(x)