Graph Based Protocols | Database Management System

Graph Based Protocols | Database Management System

Graph Based Protocols: Graph-based protocols are an alternative to two-phase locking, but require additional info on how transactions access the Database.

Simplest model is that we know the order in which database items are accessed:

>> impose a partial ordering? on the set D = (d1,d2,…, dh of all data items.

>> If di —> dj, then any transaction accessing both di and dj must access di before accessing dj.

>> implies that the set D may now be viewed as a directed a cyclic graph, called a database graph.

>> is ordering of data items realistic for a database System?

The tree-protocol is a simple kind of graph protocol.

Tree Protocol

>> Only exclusive locks are allowed.

>> The first lock by Ti may be on any data item. Subsequently, a data O can be locked by Ti only if the parent of O is currently locked by Ti.

>> Data items may be unlocked at any time.

>> A data item cannot be re locked once it is unlocked.

Tree Protocol Discussion

The tree protocol ensures conflict serializability as well as freedom from deadlock. Unlocking may occur earlier in the tree-locking protocol than in the two-phase locking protocol.

>> Shorter waiting times and increase in concurrency.

>> Protocol is deadlock-free (no deadlock-related rollbacks).

However, Cascading rollbacks due to transaction aborts are possible. However, a transaction may have to lock data items that it does not access.

>> Increased locking overhead and additional waiting time.

>> Potential decrease in Concurrency. Schedules not possible under two-phase locking are possible under tree protocol, and vice versa.