Tuesday, 25 February 2014

Timestamp and its protocol |Concurrency Control


This protocol require that we must have prior knowledge about the order in which the transaction will be accessed.In order to ordering the transaction, we associate a unique fixed timestamp ,denoted by TS(Ti) to each transaction like Ti.This time stamp is assigned by the database system before the transaction Ti starts execution.If a transaction Ti has been assigned timestamp TS(Ti) ,and a new transaction Tj enters the system then



1. Each value stored in the database requires two additional timestamp fields one for the last time the field was read and one for the last update.

2. It increases the memory requirements and the processing overhead of database.


To implement this scheme ,we associate with each data item Q two timestamp values:-

1. W-timestamp(Q) denoted the largest timestamp of any transaction that executed write(Q) successfully.
2.  R-timestamp(Q) denoted the largest timestamp of any transaction that executed read(Q) successfully.


The timestamp-ordering protocol ensures that any conflicting read and write operations are executed in timestamp order.This protocol operates as follows-


(a) If TS(Ti)<W-timestamp(Q),then Ti needs to read a value of Q that was already overwritten.Hence the read operation is rejected and Ti is roll back.(Q)

(b) If TS(Ti)>=W-timestamp(Q),then read operation is executed and R-timesatmp(Q) is set to the maximum of R-timestamp(Q) i.e. TS(Ti).


(a) If TS(Ti)<R-timestamp(Q),then the value of Q that Ti is producing was needed previously and the system assumed that value would never be produced.Hence the write operation is rejected and Ti is roll back.(Q)

(b) If TS(Ti)<W-timestamp(Q),then Ti is attempting to write an obsolete value of Q. Hence the write operation is rejected and Ti is roll back.(Q).

(c) Otherwise the write operation is executed and W- timestamp(Q) is set o TS(Ti).

Cascading Rollback |Types of Cascading Rollback |Concurrency Control


As shown in partial schedule each transaction observes two phase locking protocol. EG-

                    T5                 T6                 T7



Let us consider if transaction T5 fails after the read(A,a) operation of transaction of T7. Then, T5 must be rolled back which also result into rolled back T6 & T7. Because transaction T6 & T7 reads the value modified by transaction T5. Thus,we can say that rollback of T5 results into rollback of T6 & T7 also. This problem is called a cascading of rollback.


1.) STRICT TWO PHASE LOCKING PROTOCOL:- It requires that in addition to locking being Two phase, all exclusive mode locks taken by a transaction must be held until that transaction commits.

2.) RIGOROUS TWO PHASE LOCKING PROTOCOL:- It requires all locks(Shared and Exclusive) to be held until the transaction commits.It can be easily verified that,this transaction can be serialized in the order in which they commit.                                                

Deadlock and their prevention |Concurrency Control

In order to understand deadlock, let us consider the following example:
 T1                T2                CONCURRENCY CONTROLLER

 lock-X(A)                         Lock granted
                     lock-X(B)     Lock granted
 lock-X(B)                        Request is queued i.e T1 wait for T2 to                              release the lock on data item B.

                  lock-X(A)        Request is again queued i.e T2 will                                                 wait for T1 to release the lock on data                                                                                               item A.

As shown in partial schedule transaction T1 is waiting for transactions T2 to release its lock on data item B and transaction T2 is waiting for transaction T1 to release its lock on data item A. Such a cycle of transactions waiting for locks to be released is called a Deadlock.

1. Circular wait
2. No preemption
3. Mutual exclusion
4. Hold & wait


IST APPROACH:- To allow every transaction lock all the data items, it needs before it starts execution and if any of the data items can't be obtained then none of the data items should be locked.

DRAWBACKS: It is very difficult to acquires locks on 3 data items simultaneously.

2ND APPROACH:- It involves assigning an arbitrary serial order on the data item and ensure that data items are locked by the transaction in the order.

DRAWBACKS: It reduces concurrency.

3RD APPROACH:- Based on the concept of Time Stamp Values.This approach is used to decide whether a transaction has to wait or abort & rollback.

A time stamp is a unique identifier assigned to each transaction. It usually based on the order in which the transactions are started.

Two methods under 3RD Approach:-
1.) Wait Die- If T1 is the requesting transaction and T2 is requested transaction then
CASE 1 - t(T1)<t(T2) then T1 is allow to wait.
CASE 2 - t(T1)>t(T2) then T1 is abort and rollback.
where t represents time stamp value.

2.) Wound Wait-If T1 is the requesting transaction and T2 is requested transaction then
CASE 1 - t(T1)<t(T2) then T1 is abort and rollback.
CASE 2 - t(T1)>t(T2) then T1 is allow to wait.
where t represents time stamp value.

For detecting a deadlock information requires are:
1.) The current set of transactions.
2.) Information about the current allocations of the data item to each of the transactions.
3.) Current set of data items for which each transaction is waiting.
Wait for graph method is used.In this we have to make graph for all transaction.Each node represent the active transaction and edges represents the waiting request.If the cycle is formed then it is in deadlock otherwise not.

There are three methods in which deadlock will recover which are:-

1.) SELECTION OF VICTIM: We should rollback those transactions that will incur the minimum cost. When a deadlock is detected the choice of which transaction to abort can be made using following criteria:
1.) The transaction which have the fewest locks
2.) The transaction that done the least work
3.) The transaction that is farthest from competition.

2.) ROLLBACK: Once we have decided that a particular transaction must be rolled back, we must determine how far this transaction should be rolled back.The simplest solution is to total rollback;Abort the transaction and then restart it. However it is necessary to rollback the transaction only as far as necessary to break the deadlock. But this method requires the system to maintain additional information about the state of all the running system.

3.) PROBLEM OF STARVATION: In a system where the selection of victim is based primary on cost factors, it may happen that the same transaction is always picked as a victim. As a result this transaction never completes its designated task. This situation is called Starvation. The most common solution is to include the number of rollbacks in the cost factor. 

Introduction to Database management system | Database management system

A database is a collection of related data.By data we mean known facts that can be recorded and that have implicit meaning. 
              EG. Consider the names,tel-phone numbers and address of the people you know. you may have recorded this data in an indexed address book or you may have stored it on a hard drive,using a personal computer and software such as Microsoft access or excel. This collection of related data with an implicit meaning is a database.

DATABASE MANAGEMENT SYSTEM- A DBMS is a collection of programs that enables users to create and maintain a database.The DBMS is a general purpose software system that facilitates the processes of defining,constructing, manipulating and sharing databases among various users and applications.Defining a database involves specifying the data types,structures and constraints of the data to be stored in the database.

1.) To solve growing business needs of any organization .
2.) Store,retrieve or update the data.
3.) Sharing data among various users.
4.) Providing security to the database.
5.) Recovery of data in case of any failure.

1.) It provides data definition language.
2.) It should provide facilities for storing,updating or deleting the data.
3.) It should support multiple views of a data.
4.) It provides facilities for specifying integrity constraints so that only valid information is stored in the database.
5.) It should provide security of data and prevent un-authorized access and update.
6.) It should provide con-currency control mechanisms.
7.) Facilities for database recovery and maintenance.


MASTER FILE-It stores static data.It changes occasionally and stores all the details of the object.

TRANSACTION FILE-The file that contains data about the costumer transaction is known transaction file.It is a dynamic file.

Collection of information stored in the database at any particular movement is known as instance of the database.The overall design of the database and its description is known as schema and it does not change frequently.

SUB-SCHEMA-It is a subset of schema and inherits the same properties that a schema has.

File system Versus DBMS |Introduction to Database management system


Also known as traditional file processing system.File processing systems was an early attempt to computerize the manual filing system that we are all familiar with. A file system is a method for storing and organizing computer files and the data they contain to make it easy to find and access them.
                            File systems may use a storage device such as a hard disk or CD-ROM and involve maintaining the physical location of the files. EG- In BANK there is a file name "accounts file".If anyone wants to search they have the ability to search the accounts of all users.

Characteristics of File Processing System:-
1.) It is a group of files storing data of an organization.
2.) Data stored in the simple files known as flat files.
3.) Data is stored in hard-disk or any CD-ROM.
4.) Each file is independent from one another.
(File Management System)

DBMS:-A DBMS is a collection of programs that enables users to create and maintain a database.The DBMS is a general purpose software system that facilitates the process of defining,constructing manipulating and sharing databases among various users and applications.Defining a database involves specifying the data types,structures and constraints of the data to be stored in the database.Only user can access his own data.

ADVANTAGE-The advantages of DBMS are:-
2. Non-redundancy
3. Consistency
4. Correctness Isolation

                                  (Data Base Management System)

Data Independence |Introduction to Database management system

Data independence means upper layers are unaffected by any change in the lower layers.

There are 2 types of data independence.

1. LOGICAL DATA INDEPENDENCE- If conceptual level changes no effect on external level.

2. PHYSICAL DATA INDEPENDENCE-If Internal level changes no effect on conceptual level.


Architecture of database System | Introduction to Database management system

Three layers of architecture of DBMS:-
1. External level/View level
2. Conceptual level/Logical level
3. Internal level/Physical level

1. External level/View level-It is the user view and it shows the data that is relevant to the user. It deals with the way in which individual user view the data.It hides the details of internal and conceptual level.

2. Conceptual level/Logical level-It describes what data is stored in the database and the relationship among them.It contains the logical structure of the database as seen by the DBA.

3. Internal level/Physical level- It is the physical representation of the database. It covers the data structures used to store the data on storage devices,It also deals with storage space allocation.

                                  (3-LEVEL ARCHITECTURE)

1. Each user access the same data but have a different view.
2. No dealing with physical storage details.
3. DBA changes database storage structure without effecting users view.
4. The main objective of this 3 level architecture is to provide DATA INDEPENDENCE.

Role of Database management system Database management system


Any access to the stored data is done by the data manager.

Data manager sends request for a specific physical record to the file manager. Then the file manager decides which physical block of secondary storage devices contains the required record and sends the request to the disk manager.


1. It makes the decision regarding the content of the database.
2. It plans for storage structures and access strategies.
3. It provides support to the users.
4. It defines security and integrity checks.
5. It interprets backup and recovery techniques.

Advantage of Database management system | Introduction to database management

1.) Data independence-
Application programs should be as independent as possible from details of data representation and storage. The DBMS can provide an abstract view of the data to insulate application code from such details.

2.) Efficient data access-
A DBMS utilizes a variety of sophisticated techniques to store and retrieve data efficiently. This feature is especially important if the data is stored on external storage devices.

3.) Data integrity and security-
If data is always accessed through the DBMS, the DBMS can enforce integrity constraints on the data. For example, before inserting salary information for an employee, the DBMS can check that the department budget is not exceeded. Also, the DBMS can enforce access controls that govern what data is visible to different classes of users.

4.) Data administration-
When several users share the data, centralizing the administration of data can offer significant improvements. Experienced professionals who understand the nature of the data being managed, and how different groups of users use it, can be responsible for organizing the data representation to minimize redundancy and for returning the storage of the data to make retrieval efficient.

5.) Concurrent access and crash recovery-
A DBMS schedules concurrent accesses to the data in such a manner that users can think of the data as being accessed by only one user at a time. Further, the DBMS protects users from the effects of system failures.

6.) Reduced application development time-
 The DBMS supports many important functions that are common to many applications accessing data stored in the DBMS. This, in conjunction with the high-level interface to the data, facilitates quick development of applications. Such applications are also likely to be more robust than applications developed from scratch because many important tasks are handled by the DBMS instead of being implemented by the application.

Monday, 17 February 2014

Two phase locking protocol in concurrency control | Transaction management


A transaction follows the two phase locking protocol, if all the locking operations precede the first unlock operation in the transaction. There are two phases in the Schedule. These are:

1.) GROWING PHASE- During which all the locks are requested.
2.) SHRINKING PHASE- During which all the locks are released.

Initially a transaction is in the growing phase. The transaction acquires locks as needed. Once the transaction releases a lock, it enters the shrinking phase and it can issue no more lock requests.

For Example:

             Lock X(A) 

             A:= A-200    GROWING PHASE
             Lock X(B)
             B:=B+200     SHRINKING PHASE


1.) Deadlock
2.) Cascading Roll-Back

Concurrency Control algorithm in transaction management |Database management system

There are two approaches used in algorithms to deals with the problems of concurrency control.These are:-

1.) Pessimistic Approach
2.) Optimistic Approach

1.) PESSIMISTIC APPROACH- This approach causes transaction to be delayed in case they conflict with each other at the some time in future.

PESSIMISTIC EXECUTION- The validate operation is performed first,if there is a validation according to compatibility  of lock then only read,compute and write operation are performed.

                           VALIDATE | READ | COMPUTE | WRITE

There are two commonly used algorithms,which are based on pessimistic approach:
a.) Two phase locking protocol
b.) Time stamp ordering protocol

2.) OPTIMISTIC APPROACH- The optimistic method of concurrency control is based on the  assumption that conflicts of database operations are rare and that it is better to let transaction run to completion and only check for conflicts before they commit.An optimistic concurrency control method is also known as validation or certification methods.The Optimistic method does not require locking or time stamping techniques.Instead,a transaction is executed without restrictions until it is committed.It allows transactions to proceed unsynchronized and check conflicts at the end.This approach is based on the premise that conflicts are rare.

OPTIMISTIC EXECUTION- It perform read and compute operation without validation and perform validation just before write operation.

                           READ | COMPOSITE | VALIDATE | WRITE 


1.) This technique is very efficient when conflicts are rare. The occasional conflicts result in the transaction rollback.
2.) The roolback involves only the local copy of data, the database is not involved and thus there will not be any cascading rollbacks.


1.) Conflicts are expensive to deal with, since the conflicting transaction must be rolled back.
2.) Longer transactions are more likely to have conflicts and may be repeatedly rolled back because of conflicts with short transactions.


1.) Only suitable for environment where there are few conflicts and no long transactions.
2.) Acceptable for mostly Read and Query database systems that requires very few update.

Thursday, 13 February 2014

Lock in transaction management | concurrency control

A lock is a variable associated with a data item that describes the status of the item with respect to possible operations that can be applied to it.Generally,there is one lock for each data item in the database.Locks are used as a means of synchronizing the access by concurrent transactions to the database items.

When the transactions are running concurrently the various locking methods are used to ensure serializability of the schedule i.e.to make the non-serial schedule produce the same result as that of a serial schedule.

LOCKING TECHNIQUES FOR CONCURRENCY CONTROL- The various techniques of concurrency control are:-

1.)Binary Locks-A Binary lock has two states or values:Locked and Unlocked.Represented as LOCK( ) and UNLOCK( )
                    EG-Suppose there is a data item A and there is two transaction T1 and T2.If transaction T1 locks data item A (LOCK(A))then it is set to 1 and the other transaction(T2) is forced to wait.When the transaction is through using the item,it issues an UNLOCK(A) operation ,which sets it to 0 so that (A) may be accessed by other transaction.Hence a binary lock enforces mutual exclusion on the data item.We use binary locks to avoid Lost Update Problem.

                                    T1                                   T2
               (Set to 1)      LOCK(A)                       (wait)
                                    Read A
               (set to 0)      UNLOCK(A)
                                                                            Read A

DISADVANTAGES OF BINARY LOCK:- It is too restrictive for database items.So, binary locking system cannot be used for practical purpose.

2.)SHARE/EXCLUSIVE(READ/WRITE LOCK)-Share lock can be used for read purpose only.However,if a transaction is to write an item A,it must have exclusive access to A.Share lock is represented as (LOCK S(A)) and exclusive lock is represented as (LOCK X (A)).Also known as read/wrie lock. EG-

                         LOCK X(SUM)   (exclusive lock on data item SUM)
                         LOCK S(A)     (Share lock on data item A)
                         Read A
                         LOCK S(B)     (Share lock on data item B)
                         Read B  

Tuesday, 11 February 2014

Concurrency Control in transaction management | Database management

Transaction processing systems usually allow multiple transactions to run concurrently.By allowing multiple transactions to run concurrently will improve the performance of the system in terms of increased throughput or improved response time but this allows causes several complications with consistency of the data.

EXAMPLE-To illustrate the concept of concurrency control, consider two travelers who go to electronic kiosks at the same time to purchase a train ticket to the same destination on the same train. There's only one seat left in the coach, but without concurrency control, it's possible that both travelers will end up purchasing a ticket for that one seat. However, with concurrency control, the database wouldn't allow this to happen. Both travelers would still be able to access the train seating database, but concurrency control would preserve data accuracy and allow only one traveler to purchase the seat.

1. Improved throughput
2. Reduced Waiting time

Process of managing simultaneous execution of transactions in a shared database, to ensure the serializability of transactions, is known as concurrency control.

Simultaneous execution of transactions over a shared database can create several data integrity and consistency problems:-
 1.Lost Updates(write-write conflict)
 2.Dirty Read Problem(write-read conflict)
 3.Unrepeatable reads(Read-Write conflict)


1.Lost Updates(write-write conflict)-A lost update problem occurs when two transactions that access the same database items have their operations in a way that makes the value of some database item incorrect. E.G.- if Transaction T1 and T2 both read a record and then update it,the effects of the first update will be overwritten by the second update.It occurs in case of write-write conflict.

2.Dirty Read Problem(write-read conflict)-A dirty read problem occurs when one transaction updates a database item and then the transaction fails for some reason. The updated database item is read or accessed by another transaction before it is changed back to the original value. E.G.- a transaction T1 updates a record ,which is read by the transaction T2 then T1 aborts and T2 now has values which have never formed part of stable database or we can say T1 reads a dirty data.It occurs in case of write-read conflict.

3.Unrepeatable reads(Read-Write conflict)-Read-Write conflict occurs if a transaction writes a data object previously read by another transaction.It means a transaction reads several values from a database while second transaction updates some of them.

Scheduling of transaction | Transaction Management

Scheduling of transaction represents the actual execution sequence. A schedule of a system is an abstract model to describe execution of transactions running in the system. A Schedule is a list of actions (reading, writing, aborting or committing) from a set of transaction must consist of all instructions of those transactions and must preserve the order in which the transaction appear in each individual transaction.

For Example- If in a transaction T1 the instruction write(A) appears before read(A) then in any valid schedule this sequence must also be preserved.

Let's discuss various types of scheduling-

 1. Complete Schedule- A  Schedule that contains either an abort or a commit for each transaction whose actions are listed in it is called a complete schedule. In simple words we can say after each transaction there is commit or abort command.A complete schedule must contain all the actions of every transaction that appears in it.

2. Serial Schedule- Serial Schedule is the schedule in which after completion of one transaction second take place.For Example- There are 2 transactions T1 and T2. 

                          T1                  T2

                                    (Schedule 1)
When T1 transaction completes its execution after that transaction T2 takes place.This is called Serial Schedule.

3. Non Serial Schedule- A Schedule in which the operations from a set of concurrent transaction are interleaved is called a non-serial Schedule.For Example- There are 2 transactions T1 and T2 and transaction takes place concurrently.This is called Non-serial transaction.

                          T1                      T2

                                    (Schedule 2)
4. Equivalent Schedule- The effect of executing the first schedule is identical to the effect of executing the second schedule. For Example- (Schedule 2) is equivalent to (Schedule 1).

5. Serializiable schedule- A non-serial schedule is said to be serializiable if it produces the same result as that of some serial execution of  transaction running concurrently without interfering with each other.For Example- Output of (Schedule 1=400) and (Schedule 2=400) then it is called serializiable. In serializability the ordering of read and writes operations are important.                          

Monday, 10 February 2014

States of Transaction | Transaction Management and Their states


A transaction must be in one of the following states.
1. Active-The initial state, the transaction stays in this state while it is executing.
2. Partially committed- After the final statement has been executed.
3. Failed-when the normal execution can no longer proceed.
4. Aborted-After the transaction has been rolled back and the database has been restored to its state prior to the start of the transaction.
5. Committed-After successful completion.

A transaction starts in the active state .When it finishes its final statement, it enters the partially committed state. At this point, the transaction has completed its execution but it is still possible that it may have to be aborted, since the actual output may still be temporarily residing in main memory and thus a hardware failure may preclude its successful completion.

Sunday, 9 February 2014

Transaction and their properties | Transaction management


A Transaction is a set of changes that must all be made together.It is a collection of Operations that form a single logical  unit of work.It must be either completed or entirely aborted to ensure the consistency and integrity of database.For Example - A transfer of money from one bank account to another requires two changes to the database both must succeed or fail together. Consider the example - You are working on a system for a bank.

A customer goes to the ATM and instructs it to transfer RS 1000 from saving to a checking account.This simple transaction requires 2 steps.
1. Subtracting the money from the savings account balance.
2. Adding the money to the checking account balance.
The code to create this transaction will require two updates to the database. There will be two SQL statements-one UPDATE  command to decrease the balance in savings and a second UPDATE command to increase the balance in the checking account.Both changes must be made successfully .Thus a transaction is defined as a set of changes that must be made together.


The transaction is executed as a series of reads and writes of database objects.
          To read a database object, it is first brought into main memory from disk and then its value is copied into a program variable.
          To write a database object,memory copy of the object is first modified and then written to disk.


ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties that guarantee that database transactions are processed reliably.
  1. A- Atomicity
  2. C- Consistency
  3. I- Isolation
  4. D- Durability
1.Atomicity-(all or nothing): A transaction is said to be atomic if a transaction always executes all its action in one step or not executes any action at all. EG-Assume that a transaction attempts to subtract 20 from A and add 20 to B. This is a valid transaction, since the data continue to satisfy the constraint after it has executed. However, assume that after removing 20 from A, the transaction is unable to modify B. If the database retained A's new value, atomicity requires that both parts of this transaction,is either completed or aborted.

2.Consistency(No violation of Integrity Constraints): A transaction must preserve the consistency of a database. EG- The sum of A and B must be same after and before the transaction.

3. Isolation-(concurrent changes invisibles): The transaction must behave as if they are executed in isolation.In other words if transaction are executed concurrently the result must be same.EG-Consider two transactions. T1 transfers 50 from A to B. T2 transfers 50 from B to A. Combined, there are four actions:
T1 subtracts 50 from A.
T1 adds 10 to B.
T2 subtracts 50 from B.
T2 adds 10 to A.
If these operations are performed in order, isolation is maintained otherwise there will be an error.

4.Durability-(committed update persist): The effect of complete or committed transaction should persist even after a crash or power failure.