TRANSACTION

T1
• Why we study transaction?
Read(A)
• According to general computation principle (operating system)
we may have partially executed program, as the level of A = A-100
atomicity is instruction i.e. either an instruction is executed Write(A)
completely or not
Read(B)
• But in DBMS view, user perform a logical work(operation)
which is always atomic in nature i.e. either operation is
B = B+100
execute or not executed, there is no concept like partial Write(B)
execution. For example, Transaction T1 which transfer 100
units from account A to B.

• In this transaction if a failure occurs after Read(B) then the

final statue of the system will be inconsistent as 100 units are
debited from account A but not credited in account B, this will
generate inconsistency. Here for ‘consistency’ before (A + B) ==
after (A + B)”. Knowledge Gate Website
 What is transaction
• To remove this partial execution problem, we increase the level of atomicity and
bundle all the instruction of a logical operation into a unit called transaction.

• So formally ‘A transaction is a Set of logically related instructions to perform a

logical unit of work’.
T1
Read(A)
A = A-100
Write(A)
Read(B)
B = B+100
Write(B)
Knowledge Gate Website
• As here we are only concerned with DBMS so we well only two basic operation
on database.

• READ (X) - Accessing the database item x from disk (where database stored data)
to memory variable also name as X.

• WRITE (X) - Writing the data item from memory variable X to disk.

Knowledge Gate Website

 Desirable properties of transaction
• Now as the smallest unit which have atomicity in DBMS view is transaction, so if
want that our data should be consistent then instead of concentrating on data
base, we must concentrate on the transaction for our data to be consistent.

T1
Read(A)
A = A-100
Write(A)
Read(B)
B = B+100
Write(B)

Knowledge Gate Website

• Transactions should possess several properties, often called the ACID
properties; to provide integrity and consistency of the data in the
database. The following are the ACID properties:

Knowledge Gate Website

• Atomicity - A transaction is an atomic unit of processing; it should
either be performed in its entirety or not performed at all.

T1
Read(A)
A = A-100
Write(A)
Read(B)
B = B+100
Write(B)

Knowledge Gate Website

• Consistency - A transaction should be consistency preserving, meaning that if it
is completely executed from beginning to end without interference from other
transactions, it should take the database from one consistent state to another.

Knowledge Gate Website

• Isolation - A transaction should appear as though it is being executed in isolation
from other transactions, even though many transactions are executing
concurrently.
• That is, the execution of a transaction should not be interfered with by any other
transactions executing concurrently.

Knowledge Gate Website

• Durability - The changes applied to the database by a
committed transaction must persist in the database.

Knowledge Gate Website

 Transaction states
• ACTIVE - It is the initial state. Transaction remains in this state while it is
executing operations.

Knowledge Gate Website

 Transaction states
• PARTIALLY COMMITTED - After the final statement of a transaction has been
executed, the state of transaction is partially committed as it is still possible that
it may have to be aborted (due to any failure) since the actual output may still be
temporarily residing in main memory and not to disk.

Knowledge Gate Website

 Transaction states
• FAILED - After the discovery that the transaction can no longer proceed (because
of hardware /logical errors). Such a transaction must be rolled back.

Knowledge Gate Website

 Transaction states
• ABORTED - A transaction is said to be in aborted state when the when the
transaction has been rolled back and the database has been restored to its state
prior to the start of execution.

Knowledge Gate Website

 Transaction states
• COMMITTED - A transaction enters committed state after successful completion
of a transaction and final updation in the database.

Knowledge Gate Website

 Why we need concurrent execution
• Concurrent execution is necessary because-
• It leads to good database performance , less weighting time.
• Overlapping I/O activity with CPU increases throughput and response time.

Knowledge Gate Website

 PROBLEMS DUE TO CONCURRENT EXECUTION OF TRANSACTION

• But interleaving of instructions between transactions may also lead to many problems
that can lead to inconsistent database.

• Sometimes it is possible that even though individual transaction are satisfying the acid
properties even though the final statues of the system will be inconsistent.

Knowledge Gate Website

 Solution is Schedule
• When two or more transaction executed together or one after another then
they can be bundled up into a higher unit of execution called schedule.

Knowledge Gate Website

• Serial schedule - A serial schedule consists of sequence of instruction belonging to
different transactions, where instructions belonging to one single transaction appear
together. Before complete execution of one transaction another transaction cannot be
started. Every serial schedule lead database into consistent state.

Knowledge Gate Website

• Non-serial schedule - A schedule in which sequence of instructions of a transaction
appear in the same order as they appear in individual transaction but the instructions
may be interleaved with the instructions of different transactions i.e. concurrent
execution of transactions takes place.

Knowledge Gate Website

• Conclusion of schedules
• We do not have any method to proof that a schedule is consistent, but from the
above discussion we understand that a serial schedule will always be consistent.

• So if somehow we proof that a non-serial schedule will also have same effects as of
a serial schedule than we can proof that, this particular non-serial schedule will
also be consistent.

Knowledge Gate Website

On the basis of
SERIALIZABILITY

Conflict
serializable

View
serializable

Knowledge Gate Website

 T1 T2 T1 T2 T1 T2 T1 T2
R(A) R(B) R(A) W(A)
R(B) R(A) W(A) R(A)

T1 T2 T1 T2 T1 T2 T1 T2
R(A) W(B) R(A) W(A)
W(B) R(A) W(A) R(A)

T1 T2 T1 T2 T1 T2 T1 T2
R(A) R(A) W(A) W(A)
R(A) R(A) W(A) W(A)

Knowledge Gate Website

Conflict equivalent – if one schedule can be converted to another schedule by swapping
of non- conflicting instruction then they are called conflict equivalent schedule.

T1 T2 T1 T2
R(A) R(B)
A=A-50 B=B+50
R(B) R(A)
B=B+50 A=A-50
R(B) R(B)
B=B+50 B=B+50
R(A) R(A)
A=A+10 A=A+10
Knowledge Gate Website
 SERIALIZABILITY
• Conflicting instructions - Let I and J be two consecutive instructions belonging to two different
transactions Ti and Tj in a schedule S, the possible I and J instruction can be as-
• I= READ(Q), J=READ(Q) ->Non-conflicting
• I= READ(Q), J=WRITE(Q) ->Conflicting
• I= WRITE(Q), J=READ(Q) ->Conflicting
• I= WRITE(Q), J=WRITE(Q) ->Conflicting

• So, the instructions I and J are said to be conflicting, if they are operations by different
transactions on the same data item, and at least one of these instructions is a write operation.

Knowledge Gate Website

 CONFLICT SERIALIZABLE
• The schedules which are conflict equivalent to a serial schedule are called conflict serializable
schedule.
• If a schedule S can be transformed into a schedule S’ by a series of swaps of non- conflicting
instructions, we say that S and S’ are conflict equivalent. A schedule S is conflict serializable, if
it is conflict equivalent to a serial schedule.

Knowledge Gate Website

Q Consider the following schedule for transactions T1, T2 and T3: what is the correct
serialization of the above?

Knowledge Gate Website

 Procedure for determining conflict serializability of a schedule

• It can be determined using PRECEDENCE GRAPH method:

• A precedence graph consists of a pair G (V, E)
• V= set of vertices consisting of all the transactions participating in the schedule.
• E= set of edges consists of all edges Ti → Tj, for which one of the following conditions holds:
• Ti executes write(Q) before Tj executes read(Q)
• Ti executes read(Q) before Tj executes write(Q)
• Ti executes write(Q) before Tj executes write(Q)

• If an edge Ti → Tj exists in the precedence graph, then in any serial schedule S’ equivalent to S,
Ti must appear before Tj.
• If the precedence graph for S has no cycle, then schedule S is conflict serializable, else it is
not.

Knowledge Gate Website

 VIEW SERIALIZABLE
• If a schedule is not conflict serializable, still it can be consistent, so let us study a weaker form
of serializability called View serializability, and even if a schedule is view serializable still it can
be consistent.

• If a schedule is conflict serializable then it will also be view serializable, so we must check view
serializability only if a schedule is not conflict serializable.

Knowledge Gate Website

• Two schedules S and S’ are view equivalent, if they satisfy following conditions –

• For each data item Q, if the transaction Ti reads the initial value of Q in schedule S , then then the
transaction Ti must, in schedule S’ ,also read the initial value of Q.

• If a transaction Ti in schedule S reads any data item Q, which is updated by transaction Tj, then a
transaction Ti must in schedule S’ also read data item Q updated by transaction Tj in schedule S’.

• For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule
S, then the same transaction must also perform final write(Q) in schedule S’.

Knowledge Gate Website

 View Serializable

A schedule S is view serializable, if it is view equivalent to a serial schedule.

Knowledge Gate Website

On the basis of On the basis of
SERIALIZABILITY RECOVERABILITY

Conflict
Recoverable
serializable

View
Cascadeless
serializable

Strict

Knowledge Gate Website

 NON- RECOVERABLE Vs RECOVERABLE SCHEDULE
• A schedule in which for each pair of transaction Ti and Tj , such that if Tj reads a data item
previously written by Ti, then the commit or abort operation of Ti appears before Tj. Such a
schedule is called Non- Recoverable schedule.
• A schedule in which for each pair of transaction Ti and Tj , such that if Tj reads a data item
previously written by Ti, then the commit or abort of Ti must appear before Tj. Such a schedule
is called Recoverable schedule.

S S
T1 T2 T1 T2
R(X) R(X)
W(X) W(X)
R(X) R(X)
C C
C C
Knowledge Gate Website
 CASCADING ROLLBACK Vs CASCADELESS SCHEDULE
• It is a phenomenon, in which even if the schedule is recoverable, the a single transaction failure leads
to a series of transaction rollbacks, is called cascading rollback. Cascading rollback is undesirable, since
it leads to undoing of a significant amount of work. Uncommitted reads are not allowed in cascade less
schedule.

• A schedule in which for each pair of transactions Ti and Tj, such that if Tj reads a data item previously
written by Ti then the commit or abort of Ti must appear before read operation of Tj. Such a schedule
is called cascade less schedule.
S S
T1 T2 T3 T1 T2 T3
R(X) R(X)
W(X) W(X)
R(X) C
W(X) R(X)
R(X) W(X)
C C
C R(X)
C C
Knowledge Gate Website
 Strict Schedule
• A schedule in which for each pair of transactions Ti and Tj, such that if Tj reads a data item
previously written by Ti then the commit or abort of Ti must appear before read and write
operation of Tj.

S1 S2 S3
T1 T2 T1 T2 T1 T2
R(a) R(a) R(a)
W(a) W(a) R(b)
W(a) C W(a)
C W(a) W(b)
R(a) R(a) C
C C R(a)
C

Knowledge Gate Website

Knowledge Gate Website
 Log based Recovery
• The system log, or transaction log, records all the changes or activities happening in the
database, ensuring that transactions are durable and can be recovered in the event of a
failure.

• Different types of log records represent various stages or actions in a transaction.

• <Ti start>: This log entry indicates that the transaction Ti has started its execution.
• < Ti, Xj, V1, V2>: This log entry documents a write operation. It states that transaction Ti has
changed the value of data item Xj from V1 to V2.
• < Ti commit>: This log entry marks the successful completion of transaction Ti.
• < Ti abort>: This log entry denotes that the transaction Ti has been aborted, either due to
an error or a rollback operation.

• Before any write operation modifies the database, a log record of that operation needs to be
created. This is to ensure that in case of a failure, the system can restore the database to a
consistent state using the log records.
Knowledge Gate Website
 Aspect Deferred Database Modification Immediate Database Modification

Write Operation Timing Only at the commit point. As soon as changes occur.

Reduced, as changes are batched

Increased, as each change triggers
and written at once during the
I/O Operations immediate write operations, leading
commit, saving on intermediate I/O
to more frequent I/O operations.
operations.

Simpler, as uncommitted changes More complex, as it may require

are not reflected in the database, undoing changes from uncommitted
Recovery Complexity
making rollback easier in case of transactions that have been written
failures. to the database.

Knowledge Gate Website

 Shadow Paging Recovery Technique

In the shadow paging recovery technique, the database maintains two page tables during a
transaction: the current page table (reflecting the state before the transaction began) and the
shadow page table (which tracks changes made during the transaction). Here's how it operates:

• Initialization: When a transaction begins, the database creates a shadow copy of the page
table. The database pages themselves are not duplicated; only the page table entries are
duplicated.

• Modifications: As the transaction progresses, any changes are reflected in the current page
table, while the shadow page table retains the original state. If a page is modified, a new copy
of the page is created, and the current page table is updated to point to this new version,
thereby ensuring that the shadow page table still points to the original unmodified page.

Knowledge Gate Website

• Commit: Upon transaction commit, the shadow page table is discarded, and the current page
table becomes the new committed state of the database. The database atomically switches to
using the current page table, ensuring that changes are installed all at once.

• Recovery: In case of a system failure before the transaction commits, the database can easily
recover by discarding the current page table and reverting back to the shadow page table,
thereby restoring the database to its state before the transaction began.

Knowledge Gate Website

 Data fragmentation
• Data fragmentation in the context of a Database Management System (DBMS) refers to the process of
breaking down a database into smaller, manageable pieces, and distributing these pieces across a
network of computers. This is a significant component in distributed database systems.
• Horizontal Fragmentation: In DBMS, horizontal fragmentation divides a table into sections based
on rows. Each fragment contains a subset of rows, usually segmented based on certain conditions
or attributes. This can enhance performance by facilitating parallel processing and quicker data
retrieval, especially useful in distributed database systems.
• Vertical Fragmentation: This fragmentation type divides a database table by columns, with
different sets of columns stored in separate fragments. This approach is employed when different
users require access to varied data attributes, promoting efficient data handling and minimizing
data transfer times, which is advantageous in scenarios where queries only necessitate a subset of
attributes.
• Hybrid Fragmentation: Hybrid or mixed fragmentation in DBMS combines both horizontal and
vertical strategies, optimizing data storage and retrieval for complex access patterns. This method
can potentially offer performance improvements by utilizing the merits of both horizontal and
vertical fragmentation, and is typically implemented in databases with complex, multifaceted data
access requirements.
Knowledge Gate Website
 Distributed database
• A distributed database is a database in which storage devices are not all attached to a
common processor. It may be stored in multiple computers, located in the same
physical location, or dispersed over a network of interconnected computers.

• Data Replication
• Advantages: Increased Availability, Improved Performance, Enhanced Reliability
• Disadvantages: Storage Costs, Maintenance Complexity, Write Complexity.

• Data Fragmentation
• Advantages: Efficient Data Access, Distributed Processing, Localized Management.
• Disadvantages: Complexity, Dependency on Network, Reconstruction Issues.

Knowledge Gate Website

 CONCURRENCY CONTROL
Here we will study those protocol which guarantee to generate schedule which
always satisfy desirable properties like conflict serializability. Along with we desire
the following properties from schedule generating protocols
• Concurrency should be as high as possible, as this is our ultimate goal
because of which we are making all the effort.
• The time taken by a transaction should also be less.
• Easy to understand and implement.

Knowledge Gate Website

• Time stamping based method: - Where before entering the system, a specific order is decided
among the transaction, so in case of a clash we can decide which one to allow and which to
stop.

• Lock based method: - where we ask a transaction to first lock a data item before using it. So
that no different transaction can use a data at the same time, removing any possibility of
conflict.
• 2 phase locking
1. Basic 2pl
2. Conservative 2pl
3. Rigorous 2pl
4. Strict 2pl
• Graph based protocol

• Validation based protocol – Majority of transactions are read only transactions, the rate of
conflicts among the transaction may be low, thus many of transaction, if executed without the
supervision of a concurrency control scheme, would nerveless leave the system in a consistent
state. Knowledge Gate Website
 TIME STAMP ORDERING PROTOCOL

• Basic idea of time stamping is to decide the order between the transaction
before they enter in the system using a stamp (time stamp), in case of any
conflict during the execution order can be decided using the time stamp.

• Let’s understand how this protocol works, here we have two idea of
timestamping, one for the transaction, and other for the data item.

Knowledge Gate Website

• Time stamp for transaction,

• With each transaction ti, in the system, we associate a unique fixed timestamp, denoted by
TS(ti).

• This timestamp is assigned by database system to a transaction at time transaction enters

into the system.

• If a transaction has been assigned a timestamp TS(ti) and a new transaction tj , enters into
the system with a timestamp TS(tj), then always TS(ti) <TS(tj).

Knowledge Gate Website

• Two things are to be noted

1. First time stamp of a transaction remain fixed throughout the execution

2. Second it is unique means no two transaction can have the same timestamp.

Knowledge Gate Website

• Time stamp with data item, in order to assure such scheme, the protocol maintains for each
data item Q two timestamp values:

1. W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q)

successfully.

2. R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q)

successfully.

• These timestamps are updated whenever a new read(Q) or write(Q) instruction is executed.

Knowledge Gate Website

• Suppose a transaction Ti request a read(Q)

1. 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 rolled back.

2. If TS(Ti )≥ W-timestamp(Q), then the read operation is executed, and R-timestamp(Q) is

set to the maximum of R-timestamp(Q) and TS(Ti).

Knowledge Gate Website

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

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

3. If TS(Ti ) ≥ R-timestamp(Q), then the write operation is executed, and W-timestamp(Q) is set to
max(W-timestamp(Q), TS(Ti )).

4. If TS(Ti ) ≥ W-timestamp(Q), then the write operation is executed, and W-timestamp(Q) is set to
max(W-timestamp(Q), TS(Ti )).

Knowledge Gate Website

 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule
Basic 2PL
Conservative 2PL
Rigorous 2PL
Strict 2PL

Knowledge Gate Website

 THOMAS WRITE RULE
• Thomas write is an improvement in time stamping protocol, which makes some modification
and may generate those protocols that are even view serializable, because it allows greater
potential concurrency.

• It is a Modified version of the timestamp-ordering protocol in which Blind write operations

may be ignored under certain circumstances.

• The protocol rules for read operations remain unchanged. while for write operation, there is
slightly change in Thomas write rule than timestamp ordering protocol.

Knowledge Gate Website

When Ti attempts to write data item Q,

• if TS(Ti ) < W-timestamp(Q), then Ti is attempting to write an obsolete value

of {Q}. Rather than rolling back Ti as the timestamp ordering protocol would
have done, this {write} operation can be ignored.

Knowledge Gate Website

• This modification is valid as the any transaction with TS(Ti ) < W-timestamp(Q), the value
written by this transaction will never be read by any other transaction performing Read(Q)
ignoring such obsolete write operation is considerable.

• Thomas' Write Rule allows greater potential concurrency. Allows some view-serializable
schedules that are not conflict serializable.

Knowledge Gate Website

 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule NO YES NO NO YES
Basic 2PL
Conservative 2PL
Rigorous 2PL
Strict 2PL

Knowledge Gate Website

 Lock Based Protocols
• To ensure isolation is to require that data items be accessed in a mutually
exclusive manner i.e. while one transaction is accessing a data item, no other
transaction can modify that data item. Locking is the most fundamental
approach to ensure this.

• Lock based protocols ensure this requirement. Idea is first obtain a lock on the
desired data item then if lock is granted then perform the operation and then
unlock it.

Knowledge Gate Website

• In general, we support two modes of lock because, to provide better concurrency.

• Shared mode
• If transaction Ti has obtained a shared-mode lock (denoted by S) on any data item
Q, then Ti can read, but cannot write Q, any other transaction can also acquire a
shared mode lock on the same data item(this is the reason we called this shared
mode).

• Exclusive mode
• If transaction Ti has obtained an exclusive-mode lock (denoted by X) on any data
item Q, then Ti can both read and write Q, any other transaction cannot acquire
either a shared or exclusive mode lock on the same data item. (this is the reason we
called this exclusive mode)

Knowledge Gate Website

 Lock –Compatibility Matrix
• Conclusion shared is compatible only with shared while exclusive is not compatible either with
shared or exclusive.
• To access a data item, transaction Ti must first lock that item, if the data item is already locked
by another transaction in an incompatible mode, or some other transaction is already waiting
in non-compatible mode, then concurrency control manager will not grant the lock until all
incompatible locks held by other transactions have been released. The lock is then granted.

Knowledge Gate Website

• Lock based protocol do not ensure serializability as granting and releasing of lock do not follow
any order and any transaction any time may go for lock and unlock. Here in the example
below we can see, that even this transaction in using locking but neither it is conflict
serializable nor independent from deadlock.
T1 T2
LOCK-X(A)
READ(A)
WRITE(A)
UNLOCK(A)
LOCK-S(B)
READ(B)
UNLOCK(B)
LOCK-X(B)
READ(B)
WRITE(B)
UNLOCK(B)
LOCK-S(A)
READ(A)
UNLOCK(A)
Knowledge Gate Website
• If we do not use locking, or if we unlock data items too soon after reading or writing them, we
may get inconsistent states, as there exists a possibility of dirty read. On the other hand, if we
do not unlock a data item before requesting a lock on another data item, concurrency will be
poor.

• We shall require that each transaction in the system follow a set of rules, called a locking
protocol, indicating when a transaction may lock and unlock each of the data items for e.g. 2pl
or graph based locking.

• Locking protocols restrict the number of possible schedules.

Knowledge Gate Website

 Two phase locking protocol(2PL)
• The protocol ensures that each transaction issue lock and unlock requests in two phases, note
that each transaction will be 2 phased not schedule.

• Growing phase- A transaction may obtain locks, but not release any locks.

• Shrinking phase- A transaction may release locks, but may not obtain any new locks.

Knowledge Gate Website

• Initially a transaction is in growing phase and acquires lock as needed and in between can
perform operation reach to lock point and once a transaction releases a lock, it can issue no
more lock requests i.e. it enters the shrinking phase.

T1 T2
LOCK-X(A)
READ(A)
WRITE(A)
LOCK-S(B)
READ(B)
LOCK-X(B)
READ(B)
WRITE(B)
LOCK-S(A)
READ(A)
UNLOCK(B)
UNLOCK(A)
UNLOCK(B)
Knowledge Gate Website
UNLOCK(A)
 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule NO YES NO NO YES
Basic 2PL YES YES NO NO NO
Conservative 2PL

Rigorous 2PL
Strict 2PL

Knowledge Gate Website

 Properties
• 2PL ensures conflict serializability, and the ordering of transaction over lock points is itself a
serializability order of a schedule in 2PL.

• If a schedule is allowed in 2PL protocol then definitely it is always conflict serializable. But it is
not necessary that if a schedule is conflict serializable then it will be generated by 2pl.
Equivalent serial schedule is based on the order of lock points.

• View serializability is also guaranteed.

• Does not ensure freedom from deadlock

• May cause non-recoverability.

• Cascading rollback may occur.

Knowledge Gate Website

 Conservative 2PL
• The idea is there is no growing phase transaction start directly from lock point,
i.e. transaction must first acquire all the required locks then only it can start
execution. If all the locks are not available then transaction must release the
acquired locks and must wait.

• Shrinking phase will work as usual, and transaction can unlock any data item
anytime.

• we must have a knowledge in future to understand what is data required so

that we can use it

Knowledge Gate Website

 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule NO YES NO NO YES
Basic 2PL YES YES NO NO NO
Conservative 2PL YES YES NO NO YES
Rigorous 2PL
Strict 2PL

Knowledge Gate Website

 RIGOROUS 2PL
• Requires that all locks be held until the transaction commits.

• This protocol requires that locking be two phase and also all the locks taken be
held by transaction until that transaction commit.

• Hence there is no shrinking phase in the system.

Knowledge Gate Website

 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule NO YES NO NO YES
Basic 2PL YES YES NO NO NO
Conservative 2PL YES YES NO NO YES
Rigorous 2PL YES YES YES YES NO
Strict 2PL

Knowledge Gate Website

 STRICT 2PL
• that all exclusive-mode locks taken by a transaction be held until that transaction commits.
This requirement ensures that any data written by an uncommitted transaction are locked in
exclusive mode until the transaction commits, preventing any other transaction from reading
the data.

• This protocol requires that locking be two phase and also that exclusive –mode locks taken by
transaction be held until that transaction commits.

• So it is simplified form of rigorous 2pl

Knowledge Gate Website

 Conflict View Recoverability Cascadelessness Deadlock
Serializability Serializability Freedom

Time Stamp Ordering YES YES NO NO YES

Thomas Write Rule NO YES NO NO YES
Basic 2PL YES YES NO NO NO
Conservative 2PL YES YES NO NO YES
Rigorous 2PL YES YES YES YES NO
Strict 2PL YES YES YES YES NO

Knowledge Gate Website

 Multiple Granularity

IS IX S X
IS
IX
S
X

Knowledge Gate Website

 Multiple Granularity

IS IX S X
IS true true true false
IX true true false false
S true false true false
X false false false false

Knowledge Gate Website

 Validation-Based Protocols
• In cases where a majority of transactions are read-only transactions, the rate of conflicts
among transactions may be low.

• Thus, many of these transactions, if executed without the supervision of a concurrency-control

scheme, would nevertheless leave the system in a consistent state.

• A concurrency-control scheme imposes overhead of code execution and possible delay of

transactions. It may be better to use an alternative scheme that imposes less overhead.

• A difficulty in reducing the overhead is that we do not know in advance which transactions
will be involved in a conflict. To gain that knowledge, we need a scheme for monitoring the
system.

• The validation protocol requires that each transaction Ti executes in two or three different
phases in its lifetime, depending on whether it is a read-only or an update transaction. The
phases are, in order:
Knowledge Gate Website
• Read phase. During this phase, the system executes transaction Ti. It reads the values of the
various data items and stores them in variables local to Ti. It performs all write operations on
temporary local variables, without updates of the actual database.

• Validation phase. The validation test (described below) is applied to trans- action Ti. This
determines whether Ti is allowed to proceed to the write phase without causing a violation of
serializability. If a transaction fails the validation test, the system aborts the transaction.

• Write phase. If the validation test succeeds for transaction Ti, the temporary local variables
that hold the results of any write operations performed by Ti are copied to the database.
Read-only transactions omit this phase.

Knowledge Gate Website