Graph Based Protocol (Tree Locking Protocol) in Database Transactions

Graph Based Protocol (Tree Locking Protocol) in Database Transactions

Simplest graph based protocol is Tree Locking Protocol.

  • Tree Locking Protocol

Tree locking protocol is used to employ exclusive lock and when the database is in the form of a tree of data items.  Tree locking protocol is serializable.

Advantages of Tree Locking Protocol
Unlocking of data item is earlier.Shorter waiting time, increase in concurrency.

Disadvantages of Tree Locking Protocol
Transaction may have to unnecessary lock data items to access its child nodes.Huge number of locks and locking overhead.

What is Intension lock?
To indicate along the path from root to the desired node what type of lock it will require from one of the node’s descendants.

Three Types of Intension Locks

  • Intension Shared (IS)
  • Intension Exclusive(IX)
  • Shared Intension Lock (SIX)

Intension Shared (IS) to indicate that a shared lock will requested on some descendent node. Intension Exclusive(IX) to indicate that a exclusive lock will requested on some descendent node. Shared Intension Lock (SIX) to indicate that current node is locked in shared mode, but an exclusive lock will be requested.

Serial Schedule vs Non-Serial Schedule in Database Transactions

Serial Schedule vs Non-Serial Schedule  in Database Transactions


When multiple transactions are executing concurrently, then the order of execution of operations from the various transactions is known as schedule.

  • Serial Schedule
  • Non-Serial Schedule

Serial Schedule
Transactions are executed one by one with out any interleaved operations from other transactions.

Non-Serial Schedule
A schedule where the operations from a set of concurrent transactions are interleaved.

What is Serializability?
A given non serial schedule of n transactions are serializable if it is equivalent to some serial schedule.That is this non serial schedule produce the same result as of the serial schedule. Then the given non serial schedule is said to be serializable.A schedule that is not serializable is called a non-serializable.

Non-Serial Schedule Classification

  • Serializable
  • Not Serializable
  • Recoverable
  • Non Recoverable

Serializable Schedule Classification

  • Conflict Serializable
  • View Serializable 

Conflict Serializable Schedule
If a schedule S can be transformed into a schedule S’ by a series of swaps of non conflicting instruction then we say that S and S’ are conflict equivalent.A schedule S is called conflict serializable if it is conflict equivalent to a serial schedule.

View Serializable Schedule
All conflict serializable schedule are view serializable.But there are view serializable schedule that are not conflict serializable.A schedule S is a view serializable if it is view equivalent to a serial schedule.

Recoverable Schedule Classification

  • Cascade
  • Cascadeless

To recover form the failure of a transaction Ti, we may have to rollback several transactions. This phenomenon in which a single transaction failure leads to a series of transaction roll back is called cascading roll back.Avoid cascading roll back by not allowing to read uncommitted data. But this lead to a serial schedule.

Heap File Organization vs Sequential File Organization vs Hashing File Organization

File Organization

A file is organized as a sequence of records. The following are the various ways of organizing records in file

  • Heap File Organization
  • Sequential File Organization
  • Hashing File Organization.

Heap File Organization
Any record can be placed any where in the file where there is space for record.There is no ordering of record.Generally there is a single file for each relation (table)

Sequential File Organization
Records are stored in sequential order, according to the value of a “search key” of each record.

Hashing File Organization
A hash function is computed on some attribute of each record. It specifies the location of the record to be placed.

B Tree vs B+ Tree

B Tree  vs  B+ Tree

  • B Tree
  • B+ Tree

B Tree
A B Tree is a multi way search tree. A B tree of order n has maximum (n-1) keys and maximum n sons. In a B tree all leaves are at same level. Hence it is called balanced Tree.

Disadvantage of B Tree:  Difficulty of traversing the keys sequentially.

B+ Tree
In B+ Tree all the keys are maintained in the leaves and the keys are replicated in the non-leaf nodes to define paths for locating individual records.The leaves are linked together to provide a sequential path for traversing the keys in the tree.

Physical Data Independence vs Logical Data Independence in Database

 Data Independence

A major purpose of a database system is to provide the users with an abstract view of data. To hide the complexity from users database apply different levels of abstraction. The following are different levels of abstraction.

Physical Level
Logical Level
View Level 

Physical Level
Physical Level is the lowest level of abstraction and it defines the storage structure.The physical level describes complex low level data structures in detail.The database system hides many of the lowest level storage details from the database programmers. Database Administrators may be aware of certain details of physical organization of data.

Logical Level
This is the next higher level of abstraction which describe what data are stored in database, relation between data, types of data etc . Database programmers, DBA etc knows the logical structure of data

View Level
This the highest level of abstraction. It provides different view to different users. At the view level users see a set of application programs that hide details of data types. The details such as data type etc are not available at this level. Only view or Access is given to a part of data according to the users access right

Physical Data Independence
The changes in physical Level does not affect or visible at the logical level.The logical schema remain unchanged eventhough there is change in the internal schema at the physical level. This is called physical data independence.The physical level deals with the storage structure where as logical level deals with logical schema.

Logical Data Independence
The changes in the logical schema will not be visible or affect at the view level.The view level schema remain unchanged eventhough there is change in the schema  at the logical level. This is called logical data independence