Q10Data Base Management System

(a) Deadlock prevention

Deadlock prevention refers to techniques that guarantee deadlock can never occur in the first place, by imposing additional ordering constraints on how transactions request locks, rather than letting deadlocks happen and dealing with them afterward. One common family of prevention schemes assigns each transaction a unique timestamp when it starts (older transactions have smaller timestamps) and uses these timestamps to decide, whenever a transaction requests a lock held by another transaction, whether to wait or to abort.

• Wait-Die scheme (non-preemptive): if the requesting transaction Ti is older than the lock-holding transaction Tj (Ti has a smaller timestamp), Ti is allowed to wait for Tj to release the lock; if Ti is younger than Tj, Ti is forced to abort (die) and later restarts with the same original timestamp. Effectively, only older transactions may wait for younger ones.
• Wound-Wait scheme (preemptive): if the requesting transaction Ti is older than the lock-holding transaction Tj, Ti forces Tj to abort and release the lock (Ti wounds Tj); if Ti is younger than Tj, Ti is allowed to wait. Effectively, only younger transactions wait for older ones; older transactions preemptively abort younger ones holding a needed resource.
• Requesting all locks upfront: a simpler, more restrictive prevention approach requires each transaction to request and acquire all the locks it will ever need before it begins execution; if any requested lock is unavailable, none are granted and the transaction waits or restarts, so a transaction never holds some locks while waiting for others, which removes the circular-wait condition necessary for deadlock.

In both timestamp-based schemes, a restarted transaction keeps its original timestamp, which guarantees it eventually becomes the oldest transaction in the system and is no longer forced to abort, thereby preventing starvation.

(b) Two-phase locking (2PL)

Two-phase locking is a concurrency-control protocol that guarantees conflict-serializability by dividing each transaction's execution into exactly two phases with respect to lock management. In the growing phase, a transaction may acquire (request) new locks but may not release any lock it already holds. Once the transaction releases its first lock, it enters the shrinking phase, during which it may release locks but may no longer acquire any new ones. The point at which the transaction switches from growing to shrinking is called its lock point, and it can be shown that any schedule in which every transaction obeys this two-phase rule is guaranteed to be conflict-serializable.

A widely used variant is strict two-phase locking (strict 2PL), in which a transaction holds all of its exclusive (write) locks until it actually commits or aborts, rather than releasing them earlier during a separate shrinking phase. This ensures that no other transaction can read or overwrite data written by an as-yet-uncommitted transaction, which additionally avoids cascading rollbacks (where aborting one transaction would force the abort of others that had already read its uncommitted writes); strict 2PL is the protocol used by most commercial database systems in practice.

(c) ACID properties

ACID is the set of four properties that a database transaction must satisfy to be processed reliably.

• Atomicity: a transaction is treated as a single, indivisible unit of work - either all of its operations are successfully completed and reflected in the database, or none of them are, with any partial effects rolled back. Example: in a funds transfer that debits one account and credits another, atomicity ensures both updates happen together, or, if a failure occurs after the debit but before the credit, the debit is undone too.
• Consistency: a transaction, if executed alone on a database that starts in a consistent state satisfying all integrity constraints, must leave the database in another consistent state satisfying those same constraints. Example: if a constraint requires total bank balance across two accounts to remain constant, a correct transfer transaction preserves that invariant.
• Isolation: even when multiple transactions execute concurrently, each transaction must appear to execute as if it were the only transaction running, unaffected by the partial, uncommitted effects of other concurrent transactions. Example: while T1 is transferring money between accounts, a concurrently running T2 that reads those account balances should not see an intermediate, half-completed state of T1's transfer.
• Durability: once a transaction has committed, its effects must persist in the database permanently, surviving any subsequent system crash, power failure, or software error. Example: after a customer's order is confirmed and committed, that order record must still be present even if the server crashes one second later, typically guaranteed via the transaction log written to stable storage.

(d) Deadlock detection

Deadlock detection techniques take the opposite philosophy from prevention: transactions are allowed to request locks freely as needed, potentially leading to deadlock, and the system instead periodically checks whether a deadlock has actually occurred, resolving it only if and when it is detected. The standard tool for detection is the wait-for graph, a directed graph with one node per active transaction, where an edge is drawn from Ti to Tj whenever Ti is currently waiting to acquire a lock that is held by Tj. The DBMS periodically (or upon each blocking wait) checks this graph for cycles; the presence of a cycle Ti -> Tj -> ... -> Ti indicates that all the transactions on that cycle are mutually waiting for each other and none can proceed, i.e., a deadlock exists.

For example, if T1 is waiting for a lock held by T2, and T2 is in turn waiting for a lock held by T1, the wait-for graph has the cycle T1 -> T2 -> T1, confirming deadlock between exactly these two transactions. Once a cycle is detected, the system must resolve the deadlock by selecting one or more transactions on the cycle as victims and aborting them, releasing their locks so the remaining transactions can proceed; victim selection typically considers factors such as the transaction's age, the amount of work already done, and how many other transactions would need to be rolled back, aiming to minimize the total cost of the rollback while guaranteeing that the same transaction is not repeatedly chosen as a victim (to avoid starvation).

This concluding point completes the answer to the required depth.