UNIT - 4

Transaction Processing Concepts

 Transaction Concept
• In DBMS (Database Management Systems), a transaction is a sequence of
operations performed on a database that must be executed as a single unit.
Transactions ensure ACID properties (Atomicity, Consistency, Isolation,
Durability).
• Scenario: Buying a Smartphone
• 1. Selecting the item
• 2. Payment
• 3. Issuing the receipt
• 4. Handing over the product
• E.g. transaction to transfer $50 from account A to account B:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
• Two main issues to deal with:
• Failures of various kinds, such as hardware failures and system crashes
• Concurrent execution of multiple transactions
• Lets take another example if we are using any ecommerce website
then:
• Order is created
• Stock is updated
• Cart is deleted
• If one of the instructions is not completed then the application will be
in inconsistent state
Transactions
• It is a set of operations used to perform a logical unit of work
• A transaction generally represent change in database
• In database there are two major operations that come in transaction :
READ and WRITE.

• READ: providing access to the database

• WRITE: making changes to the database
• When in a database we have to run multiple SQL queries that affects
the state of data in our database through INSERT, UPDATE or DELETE
queries. We must combine them into a single unit of work, so that all
of them pass together or fail together
• In case even a single query fails, then the whole bundle of the query
executed in a transaction, have to fail.
 Example of Fund Transfer
• Transaction to transfer $50 from account A to account B:
1.read(A)
2.A := A – 50
3.write(A)
4.read(B)
5.B := B + 50
6.write(B)
• Atomicity requirement
• if the transaction fails after step 3 and before step 6, money will be “lost” leading to an
inconsistent database state
• Failure could be due to software or hardware
• The atomicity requirement ensures that if a transaction can't be completed fully (like in
this case, if it fails after step 3), the system will undo any changes that were made. So if
the transfer failed after subtracting $50 from account A, the system would make sure that
the $50 is returned to account A, keeping everything consistent.
• Atomicity makes sure that either the whole transaction happens, or nothing happens if
there's an issue.
• Durability requirement — Durability means that once a transaction has
been successfully completed, the changes made to the database are
permanent and will not be lost, even if something goes wrong later (like a
crash, power failure, etc.).
• if the transfer of $50 from account A to account B is successfully completed
(you've subtracted $50 from A and added it to B), the system will make
sure these changes stick.
• Even if there's a software crash or power failure right after the transaction
is done, the database will remember that the $50 was transferred and will
not forget about it. So, durability ensures that once the transaction is
successful and you've been notified, the changes are safe.
 Example of Fund Transfer (Cont.)
• Transaction to transfer $50 from account A to account B:
1.read(A)
2.A := A – 50
3.write(A)
4.read(B)
5.B := B + 50
6.write(B)
• Consistency requirement in above example:
• the sum of A and B is unchanged by the execution of the transaction
• In general, consistency requirements include
• Explicitly specified integrity constraints such as primary keys and foreign keys
• Implicit integrity constraints
• e.g. sum of balances of all accounts, minus sum of loan amounts must equal
value of cash-in-hand
• A transaction must see a consistent database.
• During transaction execution the database may be temporarily inconsistent.
• When the transaction completes successfully the database must be consistent
• Erroneous transaction logic can lead to inconsistency
 Example of Fund Transfer (Cont.)
• Isolation requirement — if between steps 3 and 6, another transaction T2 is
allowed to access the partially updated database, it will see an inconsistent
database (the sum A + B will be less than it should be).
T1 T2
1. read(A)
2. A := A – 50
3. write(A)
read(A), read(B), print(A+B)
4. read(B)
5. B := B + 50
6. write(B
• Isolation can be ensured trivially by running transactions serially
• that is, one after the other.
• However, executing multiple transactions concurrently has significant benefits, as
we will see later.
Atomicity
• This is derived from "Atomic", that means 'One' or 'Single'.
• The tasks (SQL queries) executed inside a transactions, should act as a
Single Unit of Work.
• Partial success and Partial failure is not allowed.
• In case of Failure, any changes done must be rollbacked.
Consistency
• Just like any other SQL query, a transaction must also follow the
Database table constraints.
• If some constraint is failing due to the SQL queries running in the
transaction, then the transaction should be failed.
Isolation
• SQL Transactions are executed in isolation.
• Because SQL Transactions are executed in isolation, hence it makes
multiple Transaction processing slow.
• No Parallel execution for DB Transaction.
Durability
• Changes made by SQL queries in DB transaction should be
permanent.
 ACID Properties
• A transaction is a unit of program execution that accesses and possibly updates various
data items. To preserve the integrity of data the database system must ensure:

• Atomicity. Either all operations of the transaction are properly reflected in the database or
none are.
• Consistency. Execution of a transaction in isolation preserves the consistency of the
database.
• Isolation. Although multiple transactions may execute concurrently, each transaction must
be unaware of other concurrently executing transactions. Intermediate transaction results
must be hidden from other concurrently executed transactions.
• That is, for every pair of transactions Ti and Tj, it appears to Ti that either Tj, finished
execution before Ti started, or Tj started execution after Ti finished.
• Durability. After a transaction completes successfully, the changes it has made to the
database persist, even if there are system failures.
 Transaction State
• Active – the initial state; the transaction stays in this state while it is
executing
• Partially committed – after the final statement has been executed.
• Failed -- after the discovery that normal execution can no longer
proceed.
• Aborted – after the transaction has been rolled back and the database
restored to its state prior to the start of the transaction. Two options
after it has been aborted:
• restart the transaction
• can be done only if no internal logical error
• kill the transaction
• Committed – after successful completion.
Transaction State (Cont.)
 Concurrent Executions
• Multiple transactions are allowed to run concurrently in the system.
Advantages are:
• increased processor and disk utilization, leading to better
transaction throughput
• E.g. one transaction can be using the CPU while another is
reading from or writing to the disk
• reduced average response time for transactions: short
transactions need not wait behind long ones.
• Concurrency control schemes – mechanisms to achieve isolation
• that is, to control the interaction among the concurrent
transactions in order to prevent them from destroying the
consistency of the database
 Schedules
• Schedule – a sequences of instructions that specify the chronological
order in which instructions of concurrent transactions are executed
• a schedule for a set of transactions must consist of all instructions
of those transactions
• must preserve the order in which the instructions appear in each
individual transaction.
• A transaction that successfully completes its execution will have a
commit instructions as the last statement
• by default transaction assumed to execute commit instruction as
its last step
• A transaction that fails to successfully complete its execution will have
an abort instruction as the last statement
Serial Schedule
• A serial schedule is one in which transactions are executed
sequentially, one after another, without overlapping. This means:
• Each transaction is completed before the next one starts.
• There is no interleaving of operations from different transactions.
• Key Features:
1.Simple to implement and guarantees consistency.
2.No concurrency, so it can be slow if many transactions need to be
processed.
Parallel (Non-Serial) Schedule
• A parallel schedule (also called a concurrent schedule) is one in which
operations from multiple transactions are interleaved. Transactions
execute simultaneously, with their operations overlapping in time.
• Key Features:
1.Improves system performance by allowing concurrency.
2.Risk of conflicts (e.g., lost updates, dirty reads) if not carefully
controlled.
3.Requires mechanisms (e.g., locking, timestamps) to ensure
consistency.
 Schedule 1
• Let T1 transfer $50 from A to B, and T2 transfer 10% of the balance from A to B.
• A serial schedule in which T1 is followed by T2 :
 Schedule 2
• A serial schedule where T2 is followed by T1
 Schedule 3
• Let T1 and T2 be the transactions defined previously. The following schedule is not a
serial schedule it is a parallel schedule, but it is equivalent to Schedule 1.

In Schedules 1, 2 and 3, the sum A + B is preserved.

 Schedule 4
• The following concurrent schedule does not preserve the value of (A
+ B ).
 Serializability
• Conflict serializability is a concept in database transaction
management. It ensures that a schedule (sequence of
read/write operations from multiple transactions) is
equivalent to a serial schedule, where transactions are
executed one after the other without overlapping.
Key Points:
• Serial Schedule: Transactions are executed one at a time,
sequentially, without any interleaving.
• Conflict Serializable Schedule: A schedule is said to be
conflict serializable if it can be transformed into a serial
schedule by swapping non-conflicting operations without
changing the outcome.
Conflicts in Database Transactions
Conflicts arise when two or more transactions access the same data
item, and at least one of them performs a write operation. There are
three types of conflicts:
1.Write-Read (WR) (Dirty Read Problem): One transaction writes, and
another reads the same data item.
2.Read-Write (RW): One transaction reads, and another writes the same
data item.
3.Write-Write (WW) (Lost Update Problem): Two transactions write to
the same data item.
Checking Conflict Serializability
To check if a schedule is conflict serializable:
1.Construct a precedence graph (also known as a conflict graph):
• Nodes represent transactions.
• Directed edges represent conflicts (e.g., if one transaction
writes a data item that another reads).
2.Check for cycles in the graph:
• If there is no cycle, the schedule is conflict serializable.
• If there is a cycle, the schedule is not conflict serializable.
Dirty Read Problem
• If a transaction T2 read a temporary value ( which is not a value of the
database) that is the value of an uncommitted transaction.
• Or
• The dirty read problem occurs when one transaction updates an item
of the database, and somehow the transaction fails, and before the
data gets rollback, the updated database item is accessed by another
transaction. There comes the Read-Write Conflict between both
transactions.
T1 T2
R(A)
W(A)
R(A)
COMMIT
UNREPEATABLE READ Problem (Write-Read
Conflict)
T1 T2 If we read one data item value more than
one time and the value is different both the
R(X) time
R(X)
Or
W(X)
Unrepeatable Read: A transaction (T2) reads
R(X)
the same data twice, but between the two
reads, another transaction (T1) modifies or
updates the data. As a result, the value read
the second time by T2 is different from the
value it read initially.
 Lost Update Problem(write write conflict)
When a transaction write a data item without
reading the data item then it is called blind write
T1 T2
R(A)
W(A)
W(A)
COMMIT
COMMIT

This commit is overwriting the value updated by T2 in the database

however the value written by the T1 transaction is lost due to Write-
Write conflict
Recoverable schedule
T1 T2 A SCHEDULE CAN BE RECOVERABLE SCHEDULE ONLY
R(A) AND ONLY IF
A=A+10
W(A) 1. IF THERE IS NO DIRTY READ
OR
R(A)
2. IF THERE IS DIRTY READ , THEN IN THE ORDER
A=A-5
THE DIRTY READ IS HAPPENING THE COMMIT
W(5) SHOULD ALSO BE IN SAME ORDER
COMMIT
COMMIT
Phantom read
T1 T2
R(X)
R(X)
DELETE(X)
R(X)

Phantom read occurs when a transaction reads a data item but you cannot read
that data item because that structure or data item does not exist anymore
• Types of Recoverable Schedules-
• A recoverable schedule may be any one of these kinds-
1. Cascading Schedule
2. Cascadeless Schedule
3. Strict Schedule
Cascadeless Schedule
T1 T2 T3 Whenever a schedule has dirty read it will always have cascading
rollback, it will be a cascading schedule.
A schedule is cascading if:
R(A) • A transaction reads an uncommitted value written by another
transaction.
W(A) • Example:
• Transaction 𝑇1 writes a value but has not committed.
R(A) • Transaction 𝑇2 reads that uncommitted value. If 𝑇1 later
aborts, 𝑇2 may also need to roll back because its read was
based on invalid data, causing cascading rollbacks.
W(A) It simply leads to the wastage of CPU time.

R(A) To make it cascadeless schedule we have to remove dirty reads.

Here,

Transaction T2 depends on transaction T1.

Transaction T3 depends on transaction T2.
Transaction T4 depends on transaction T3.

In this schedule,

The failure of transaction T1 causes the transaction T2 to

rollback.
The rollback of transaction T2 causes the transaction T3 to
rollback.
The rollback of transaction T3 causes the transaction T4 to
rollback.
Such a rollback is called as a Cascading Rollback.
Cascadeless Schedule-

If in a schedule, a transaction is not allowed to read a data item until the last transaction that
has written it is committed or aborted, then such a schedule is called as a Cascadeless Schedule.

In other words,

Cascadeless schedule allows only committed read operations.

Therefore, it avoids cascading roll back and thus saves CPU time.
NOTE-

Cascadeless schedule allows only committed

read operations.
However, it allows uncommitted write
operations.
Strict Schedule-
If in a schedule, a transaction is neither allowed to read nor write a data item until the last transaction that has
written it is committed or aborted, then such a schedule is called as a Strict Schedule.

In other words,

Strict schedule allows only committed read and write operations.

Clearly, strict schedule implements more restrictions than cascadeless schedule.

Example-
 If a schedule is strict does that mean it will be serial schedule also - NO

This is a strict schedule but not a serial schedule so

T1 T2 it means that if a schedule is strict it does not mean
R(A) that it will be serial also.
R(B) A serial schedule executes one transaction
completely before starting the next transaction. In
W(A)
this example:
W(B)
 𝑇1 starts, performs 𝑅(𝐴), 𝑊(𝐴), and commits
COMMIT before 𝑇2 performs 𝑅(𝐴).
R(A)  However, 𝑇2 performs 𝑅(𝐵) and 𝑊(𝐵) before 𝑇1
COMMIT commits.
This indicates interleaving between the operations of
𝑇1 and 𝑇2 . Hence, it is not serial.
Remember-

•Strict schedules are more strict than

cascadeless schedules.
•All strict schedules are cascadeless
schedules.
•All cascadeless schedules are not strict
schedules.
 Conflict Serializability (Cont.)
Is Schedule 3 is conflict serializability ?

Schedule 3
 Conflict Serializability (Cont.)
• Schedule 3 can be transformed into Schedule 6, a serial schedule where T2
follows T1, by series of swaps of non-conflicting instructions. Therefore Schedule
3 is conflict serializable.

Schedule 3 Schedule 6
 Conflict Serializability (Cont.)
• Example of a schedule that is not conflict serializable:

• We are unable to swap instructions in the above schedule to obtain

either the serial schedule < T3, T4 >, or the serial schedule < T4, T3 >.
Check whether the given schedule S is conflict
serializable or not-
T1 T2 T3
R(A)
Solution in next slide
R(A)
R(B)
R(B)
R(B)
W(A)
W(B)
Conflict-Serializable Analysis: Precedence Graph:
 To check if the schedule is conflict-serializable, we construct a
precedence graph:
 Nodes: 𝑇1 , 𝑇2 , 𝑇3
 Each transaction 𝑇1 , 𝑇2 , 𝑇3 is a node.  Edges:
 Draw a directed edge 𝑇𝑖 → 𝑇𝑗 if 𝑇𝑖 's operation conflicts with 𝑇𝑗 's  𝑇1 → 𝑇2
operation and 𝑇𝑖 's operation occurs before 𝑇𝑗 s operation in the  𝑇2 → 𝑇3
schedule.
 𝑇3 → 𝑇1
1. Conflict Types:
3. Cycle Detection in Precedence Graph:
 Read-Write (RW) Conflict: 𝑇𝑖 reads, and 𝑇𝑗 writes the same item.
 The graph has a cycle: 𝑇1 → 𝑇2 → 𝑇3 → 𝑇1.
 Write-Read (WR) Conflict: 𝑇𝑖 writes, and 𝑇𝑗 reads the same item.
 A cycle in the precedence graph means
 Write-Write (WW) Conflict: 𝑇𝑖 writes, and 𝑇𝑗 writes the same item. the schedule is not conflict-serializable.
2. Step-by-Step Graph Construction:
 Analyze conflicts based on the given schedule:
 𝑇1 : 𝑅(𝐴), 𝑇2 : 𝑅(𝐴) → No conflict (both read).
 𝑇1 : 𝑊(𝐴), 𝑇2 : 𝑅(𝐴) → 𝑇2 reads 𝐴 after 𝑇1 writes 𝐴 (WR conflict
𝑇1 → 𝑇2 ).
 𝑇1 : 𝑊(𝐴), 𝑇2 : 𝑊(𝐵) → No conflict (different items).
 𝑇2 : 𝑅(𝐵), 𝑇3 : 𝑊(𝐵) − 𝑇3 writes 𝐵 after 𝑇2 reads 𝐵 (WR conflict
𝑇2 → 𝑇3 ).
 𝑇3 : 𝑊(𝐵), 𝑇1 : 𝑅(𝐵) − 𝑇1 reads 𝐵 after 𝑇3 writes 𝐵 (WR conflict
𝑇3 → 𝑇1 ).
Check whether the given schedule S is conflict serializable and recoverable
or not
Step-01:

List all the conflicting operations and determine the

dependency between the transactions-
•R2(X) , W 3(X) (T2 → T3)
•R2(X) , W 1(X) (T2 → T1)
•W 3(X) , W 1(X) (T3 → T1)
•W 3(X) , R4(X) (T3 → T4)
•W 1(X) , R4(X) (T1 → T4)
•W 2(Y) , R4(Y) (T2 → T4)

Step-02: •Clearly, there exists no cycle in the precedence graph.

•Therefore, the given schedule S is conflict serializable.

Draw the precedence graph-

Check whether the given schedule S is conflict serializable and
recoverable or not
Step-01:

List all the conflicting operations and

determine the dependency between
the transactions-
•R4(A) , W 2(A) (T4 → T2)
•R3(A) , W 2(A) (T3 → T2)
•W 1(B) , R3(B) (T1 → T3)
•W 1(B) , W 2(B) (T1 → T2)
•R3(B) , W 2(B) (T3 → T2)

•Clearly, there exists no cycle in the precedence graph.

Step-02:
•Therefore, the given schedule S is conflict serializable.

Draw the precedence graph-

Check whether the given schedule S is conflict serializable
and recoverable or not
Step-01:

List all the conflicting operations and determine the

dependency between the transactions-
•R1(A) , W 2(A) (T1 → T2)
•R2(A) , W 1(A) (T2 → T1)
•W 2(A) , W 1(A) (T2 → T1)
•R2(B) , W 1(B) (T2 → T1)
•R1(B) , W 2(B) (T1 → T2)
•W 1(B) , W 2(B) (T1 → T2) •Clearly, there exists a cycle in the precedence graph.
•Therefore, the given schedule S is not conflict
serializable.
Step-02:
•Thus, Number of possible serialized schedules = 0.

Draw the precedence graph-

 View Serializability
• Let S and S´ be two schedules with the same set of transactions. S and S´ are
view equivalent if the following three conditions are met, for each data item
Q,
1. If in schedule S, transaction Ti reads the initial value of Q, then in
schedule S’ also transaction Ti must read the initial value of Q.
2. If in schedule S transaction Ti executes read(Q), and that value was
produced by transaction Tj (if any), then in schedule S’ also transaction
Ti must read the value of Q that was produced by the same write(Q)
operation of transaction Tj .
3. The transaction (if any) that performs the final write(Q) operation in
schedule S must also perform the final write(Q) operation in schedule S’.
As can be seen, view equivalence is also based purely on reads and writes
alone.
 View Serializability (Cont.)
• A schedule S is view serializable if it is view equivalent to a serial schedule.
• Every conflict serializable schedule is also view serializable.
• Below is a schedule which is view-serializable but not conflict serializable.

• What serial schedule is above equivalent to?

• Every view serializable schedule that is not conflict serializable has blind
writes.
 Other Notions of Serializability
• The schedule below produces same outcome as the serial schedule < T1, T5 >,
yet is not conflict equivalent or view equivalent to it.

• Determining such equivalence requires analysis of operations other than

read and write.
 Testing for Serializability
• Consider some schedule of a set of transactions T1, T2, ..., Tn
• Precedence graph — a directed graph where the vertices are the
transactions (names).
• This graph consists of a pair G = (V, E), where V is a set of vertices and
E is a set of edges.
• The set of vertices consists of all the transactions participating in the
schedule.
• The set of edges consists of all edges Ti -> Tj for which one of three
condition holds:
1. Ti executes write(Q) before Tj executes read(Q).
2. Ti executes read(Q) before Tj executes write(Q).
3. Ti executes write(Q) before Tj executes write(Q).
 Testing for Serializability (Cont.)
• We draw an arc from Ti to Tj if the two transaction conflict, and Ti
accessed the data item on which the conflict arose earlier.
Example -

T3 T4
 Test for Conflict Serializability
• A schedule is conflict serializable if and only
if its precedence graph is acyclic.
• Cycle-detection algorithms exist which take
order n2 time, where n is the number of
vertices in the graph.
• (Better algorithms take order n + e where e is
the number of edges.)
• If precedence graph is acyclic, the
serializability order can be obtained by a
topological sorting of the graph.
• This is a linear order consistent with the
partial order of the graph.
 Test for View Serializability
View serializability ensures that a schedule (a sequence of database operations) produces the same
final state as a serial schedule, while also preserving the "view" of the transactions. To check for view
serializability, three conditions must be met:
1. Initial Reads Match Each transaction in the schedule must read the same initial value of a data
item as in a serial schedule. If a transaction reads a value from a data item that no other
transaction has modified in the schedule, it should be the same as in the serial order.
2. Intermediate Reads Match If a transaction 𝑇𝑖 reads a value written by another transaction 𝑇𝑗 in the
schedule, the same transaction 𝑇𝑗 must write that value in the equivalent serial schedule. This
ensures consistency of the intermediate states.
3. Final Writes Match The transaction that performs the final write on any data item in the schedule
must also perform the final write on that item in the equivalent serial schedule. This ensures the
database's final state is identical to the serial schedule.
PRACTICE PROBLEMS BASED ON VIEW SERIALIZABILITY-
Problem-01:
Check whether the given schedule S is view serializable or
not-
To determine whether the given schedule S is view Analyzing the given schedule:
serializable or not, we need to analyze the schedule For data item 'A': The read operations occur in
based on the concept of view serializability. the order: T1 -> T2 -> T3 -> T4, which matches a
The key steps to solve this problem are: serial schedule. The final write operation is by
1.Identify the read and write operations in the T4, which also matches a serial schedule.
schedule.
2.Determine if the schedule satisfies the view For data item 'B': The read operations occur in
serializability conditions. the order: T1 -> T2 -> T3 -> T4, which matches a
serial schedule. The final write operation is by
• The read and write operations are represented T4, which also matches a serial schedule.
by 'R' and 'W' respectively, with the transaction
identifier in parentheses. Therefore, the given schedule S is view
• To check for view serializability, we need to serializable.
ensure that:
1. For each data item, the order of read
operations is the same as in some serial
schedule.
2. For each data item, the final write
operation is the same as in some serial
schedule.
Problem-02:

Check whether the given schedule S is view serializable or

not-
Problem-03:
Check whether the given schedule S is view serializable
or not-
 Recoverable Schedules
Need to address the effect of transaction failures on concurrently running transactions.
• Recoverable schedule — if a transaction Tj reads a data item previously
written by a transaction Ti , then the commit operation of Ti appears before
the commit operation of Tj.
• The following schedule (Schedule 11) is not recoverable if T9 commits
immediately after the read

• If T8 abort, T9 would have read (and possibly shown to the user) an

inconsistent database state. Hence, database must ensure that schedules
are recoverable.
 Cascading Rollbacks
• Cascading rollback – a single transaction failure leads to a series of
transaction rollbacks. Consider the following schedule where none of
the transactions has yet committed (so the schedule is recoverable)

If T10 fails, T11 and T12 must also be rolled back.

• Can lead to the undoing of a significant amount of work
 Cascadeless Schedules
• Cascadeless schedules — cascading rollbacks cannot occur; for each
pair of transactions Ti and Tj such that Tj reads a data item previously
written by Ti, the commit operation of Ti appears before the read
operation of Tj.
• Every cascadeless schedule is also recoverable
• It is desirable to restrict the schedules to those that are cascadeless.
 Transaction Definition in SQL
• Data manipulation language must include a construct for specifying
the set of actions that comprise a transaction.
• In SQL, a transaction begins implicitly.
• A transaction in SQL ends by:
• Commit work commits current transaction and begins a new one.
• Rollback work causes current transaction to abort.
• In almost all database systems, by default, every SQL statement also
commits implicitly if it executes successfully
• Implicit commit can be turned off by a database directive
• E.g. in JDBC, connection.setAutoCommit(false);
Recovery System
 Recovery System
• Failure Classification
• Storage Structure
• Recovery and Atomicity
• Log-Based Recovery
 Failure Classification
1. Logical Errors
•Description: These occur due to mistakes in the transaction logic or input data, causing
the transaction to fail.
•Example: Suppose a banking application has a rule that an account balance cannot go
negative. A transaction to transfer $500 from an account with a $400 balance will result in
a logical error because the rule is violated.

2. System Errors
•Description: These occur when the database system detects an internal condition. These
happen due to issues inside the database system, like deadlocks (when two transactions
block each other) that prevents the transaction from proceeding.
•Example: Two transactions, A and B, access the same resources in reverse order:
• Transaction A locks Account 1 and requests a lock on Account 2.
• Transaction B locks Account 2 and requests a lock on Account 1. This creates a
deadlock. To resolve it, the database system will terminate one transaction (say,
Transaction B) and allow the other to proceed.
 3. System Crash
•Description: Occurs when the system halts due to hardware or software failure, resulting
in incomplete transactions.
•Example: While updating multiple rows in a database, the server loses power. If the
system crashes mid-way:
• Some updates may have been applied.
• Others may not.
• This leaves the database in an inconsistent state unless a recovery mechanism (like
write-ahead logging) is used.
4. Fail-Stop Assumption
•Description: This assumes that even if the system crashes, the stored data on the disk is
not corrupted.
•Example: After a crash, the database checks the logs stored on the disk to recover and
complete any interrupted transactions.
5. Disk Failure
•Description: Disk failure occurs when the physical storage device (like a hard drive or SSD)
experiences damage, making data stored on it partially or fully inaccessible. This can lead
to data loss, inconsistencies, or performance issues in database systems.
•Example:
• A head crash damages the magnetic surface, making certain disk sectors
unreadable.
• Suppose a table's data resides in a damaged sector. Attempts to query this data will
fail.
•Detection: Disk systems often use checksums to detect corruption. If the checksum of a
read block does not match the stored checksum, the database system identifies the failure
and raises an alert.
 Recovery Algorithms
Transaction Ti: Transferring $50 from Account A to Account B
1.Initial Operations:
• Subtract $50 from Account A: This updates A's balance in the database.
• Add $50 to Account B: This updates B's balance in the database.
2.Requirements:
• Both operations must commit together to ensure the transaction is atomic.
• A failure during this process could lead to an inconsistent state if only one of the
operations completes.
• Potential Failure Scenarios
1.Failure after Subtracting $50 from A but Before Adding to B:
1. Inconsistent State: A's balance reflects the deduction, but B has not received the
amount, violating the consistency of the database.
2. The total balance across both accounts is incorrect.
2.Failure after Adding $50 to B but Before Subtracting from A:
1. Inconsistent State: B's balance shows the addition, but A's balance remains
unchanged.
2. This also violates consistency, as it creates the illusion of "extra" money.
3.Failure After Both Updates but Before Commit:
1. Uncertainty: While both balances are updated, the transaction is not marked as
committed. On recovery, it is unclear whether the changes should be retained or
rolled back.
• Key Challenges
1.Modifying the Database Without Ensuring Commit:
1. If a failure occurs, the database may be left in an inconsistent state because
the updates are partially applied.
2. Example: Subtracting from A but not adding to B breaks atomicity.
2.Not Modifying the Database Immediately:
1. If the transaction fails just after committing but before updates are physically
written to disk, those updates may be lost.
2. Example: The commit succeeds, but the system crashes before A and B are
updated.
Role of Recovery Algorithms
Recovery algorithms ensure that the database can recover from failures while maintaining ACID
properties. These algorithms have two phases:
1. Actions During Normal Transaction Processing
•Write-Ahead Logging (WAL):
• Before modifying the database, changes are recorded in a log file.
• Ensures that if a failure occurs, the log contains enough information to either redo or undo
the changes.
•Deferred Updates:
• Actual updates are delayed until the transaction commits, avoiding partial updates.
•Checkpoints:
• Periodically save a snapshot of the database state to reduce recovery time.
2. Actions After a Failure
•Redo Operations:
• If a transaction was committed but its updates were not written to the database, the
system redoes the transaction using the log.
•Undo Operations:
• If a transaction did not commit, any changes it made are undone to maintain atomicity.
•Ensuring Consistency:
• The database state is verified to satisfy all constraints (e.g., total balance across accounts).
 Storage Structure
• Volatile storage:
• Volatile storage refers to storage mediums that lose their contents when power is lost or the
system crashes.
• examples: main memory, cache memory
• Cannot be relied upon for recovery after a failure.
• Important to transfer critical data to nonvolatile storage to prevent data loss.
• Nonvolatile storage:
• Nonvolatile storage retains data even after a power loss or system crash.
• examples: disk, tape, flash memory, non-volatile (battery backed up) RAM
• but may still fail, losing data
• Stable storage:
• Stable storage is a theoretical concept of a storage medium that can survive all failures,
ensuring that data is never lost under any circumstance.
• Storing copies of data in geographically distinct locations to prevent data loss due to localized
disasters.
 Data Access
• Physical blocks are those blocks residing on the disk.
• Buffer blocks are the blocks residing temporarily in main memory.
• Block movements between disk and main memory are initiated
through the following two operations:
• input(B) transfers the physical block B to main memory.
• output(B) transfers the buffer block B to the disk, and replaces the appropriate
physical block there.
• We assume, for simplicity, that each data item fits in, and is stored
inside, a single block.
 Example of Data Access
buffer
Buffer Block A input(A)
X A
Buffer Block B Y B
output(B)
read(X)
write(Y)

x2
x1
y1

work area work area

of T1 of T2

memory disk
 Data Access (Cont.)
• Each transaction Ti has its private work-area in which local copies of all
data items accessed and updated by it are kept.
• Ti's local copy of a data item X is called xi.
• Transferring data items between system buffer blocks and its private
work-area done by:
• read(X) assigns the value of data item X to the local variable xi.
• write(X) assigns the value of local variable xi to data item {X} in the buffer block.
• Note: output(BX) need not immediately follow write(X). System can perform the
output operation when it deems fit.
• Transactions
• Must perform read(X) before accessing X for the first time (subsequent reads
can be from local copy)
• write(X) can be executed at any time before the transaction commits
 Recovery and Atomicity
• To ensure atomicity despite failures, we first output information
describing the modifications to stable storage without modifying the
database itself.
• We study log-based recovery mechanisms in detail
• First, we discuss key concepts
• And then discuss the actual recovery algorithm
• Less used alternative: shadow-paging
 Log-Based Recovery
• A log is kept on stable storage.
• The log is a sequence of log records, and maintains a record of update activities on
the database.
• When transaction Ti starts, it registers itself by writing a
<Ti start>log record
• Before Ti executes write(X), a log record
<Ti, X, V1, V2>
is written, where V1 is the value of X before the write (the old value), and
V2 is the value to be written to X (the new value).
• When Ti finishes it last statement, the log record <Ti commit> is written.
• Two approaches using logs
• Deferred database modification
• Immediate database modification
 Deferred Database Modification
• The deferred database modification scheme records all modifications
to the log, but defers all the writes to after partial commit.
• Assume that transactions execute serially
• Transaction starts by writing <Ti start> record to log.
• A write(X) operation results in a log record <Ti, X, V> being written,
where V is the new value for X
• Note: old value is not needed for this scheme
• The write is not performed on X at this time, but is deferred.
• When Ti partially commits, <Ti commit> is written to the log
• Finally, the log records are read and used to actually execute the
previously deferred writes.
 Deferred Database Modification (Cont.)
• During recovery after a crash, a transaction needs to be redone if and only if both <Ti
start> and<Ti commit> are there in the log.
• Redoing a transaction Ti ( redoTi) sets the value of all data items updated by the
transaction to the new values.
• Crashes can occur while
• the transaction is executing the original updates, or
• while recovery action is being taken
• example transactions T0 and T1 (T0 executes before T1):
T0: read (A) T1 : read (C)
A: - A - 50 C:- C- 100
Write (A) write (C)
read (B)
B:- B + 50
write (B)
Deferred Database Modification (Cont.)
• Below we show the log as it appears at three instances of time.

• If log on stable storage at time of crash is as in case:

(a) No redo actions need to be taken
(b) redo(T0) must be performed since <T0 commit> is present
(c) redo(T0) must be performed followed by redo(T1) since
<T0 commit> and <Ti commit> are present
 Immediate Database Modification
• The immediate-modification scheme allows updates of an uncommitted
transaction to be made to the buffer, or the disk itself, before the transaction
commits
• Update log record must be written before database item is written
• We assume that the log record is output directly to stable storage

• Output of updated blocks to stable storage can take place at any time before or
after transaction commit
• Order in which blocks are output can be different from the order in which they
are written.
• The deferred-modification scheme performs updates to buffer/disk only at the
time of transaction commit
• Simplifies some aspects of recovery
• But has overhead of storing local copy
 Transaction Commit
• A transaction is said to have committed when its commit log record is
output to stable storage
• all previous log records of the transaction must have been output already
• Writes performed by a transaction may still be in the buffer when the
transaction commits, and may be output later
 Immediate DB Modification Recovery Example
Below we show the log as it appears at three instances of time.

Recovery actions in each case above are:

(a) undo (T0): B is restored to 2000 and A to 1000, and log records <T0, B, 2000>, <T0, A, 1000>,
<T0, abort> are written out
(b) redo (T0) and undo (T1): A and B are set to 950 and 2050 and C is restored to 700. Log
records <T1, C, 700>, <T1, abort> are written out.
(c) redo (T0) and redo (T1): A and B are set to 950 and 2050 respectively. Then C is set to 600
Shadow paging
1.It's an alternative to Log-based Recovery
•In shadow paging it maintains two page table during the transaction:
1. Current Page Table [volatile]
2. Shadow Page Table [Non Volatile]
•A page table is a structure that helps manage data stored on disk in the form
of pages, which are fixed-sized blocks of data.
How Shadow Paging Works:
1.Two Page Tables:
• Current Page Table: This table is like the working copy. It points to the
actual data that is being updated.
• Shadow Page Table: This is the backup copy that points to the original,
unmodified data on disk.
2. Making Changes:
1. When you need to make changes to the data (for example, updating a record), the system
doesn’t modify the original data directly.
2. Instead, it creates new pages with the updated data.
3. Updating the Current Page Table:
1. The current page table is updated to point to the new pages with the changes.
2. But the shadow page table stays the same, pointing to the original data until everything is
confirmed.
4. Switching to the New Data:
1. Once the new pages are successfully written and the updates are complete, the system
switches the pointer from the shadow page table to the new version in the current page
table.
5. Safety in Case of a Failure:
1. If something goes wrong during the update (e.g., a system crash), the shadow page table
remains unchanged and still points to the original, correct data.
2. This means the database can simply revert to the shadow copy and continue working
without data loss or corruption.
Why It’s Useful:
•No Data Corruption: The original data is never changed until the new data is
fully ready.
•Easy Rollback: If something goes wrong, it’s easy to roll back to the original
data.
•No Complex Logging: Unlike other techniques, shadow paging doesn’t
require writing logs of every change, making it simpler.
 Concurrency Control and Recovery
• With concurrent transactions, all transactions share a single disk buffer and
a single log
• A buffer block can have data items updated by one or more transactions
• We assume that if a transaction Ti has modified an item, no other
transaction can modify the same item until Ti has committed or aborted
• i.e. the updates of uncommitted transactions should not be visible to other
transactions
• Otherwise how to perform undo if T1 updates A, then T2 updates A and commits, and finally
T1 has to abort?
• Can be ensured by obtaining exclusive locks on updated items and holding the locks
till end of transaction (strict two-phase locking)
• Log records of different transactions may be interspersed in the log.
 Undo and Redo Operations
• Undo of a log record <Ti, X, V1, V2> writes the old value V1 to X
• Redo of a log record <Ti, X, V1, V2> writes the new value V2 to X
• Undo and Redo of Transactions
• undo(Ti) restores the value of all data items updated by Ti to their old values,
going backwards from the last log record for Ti
• each time a data item X is restored to its old value V a special log record <Ti , X, V> is
written out
• when undo of a transaction is complete, a log record <Ti abort> is written out.
• redo(Ti) sets the value of all data items updated by Ti to the new values, going
forward from the first log record for Ti
• No logging is done in this case
 Undo and Redo on Recovering from Failure
• When recovering after failure:
• Transaction Ti needs to be undone if the log
• contains the record <Ti start>,
• but does not contain either the record <Ti commit> or <Ti abort>.
• Transaction Ti needs to be redone if the log
• contains the records <Ti start>
• and contains the record <Ti commit> or <Ti abort>
• Note that If transaction Ti was undone earlier and the <Ti abort>
record written to the log, and then a failure occurs, on recovery from
failure Ti is redone
• such a redo redoes all the original actions including the steps that restored
old values
• Known as repeating history
• Seems wasteful, but simplifies recovery greatly
 Checkpoints
• Explain Checkpoints . How does it help in reducing the amount of time
required during recovery?
• CHECKPOINTS:- checkpoint is a mechanism to save the current state of
the database to ensure faster recovery after a crash or failure.
• At a checkpoint, all changes made in memory (buffer) to the database are
written to the disk, and the log file is updated. This minimizes the amount
of work needed during recovery by limiting the redo and undo operations
to the changes made after the checkpoint.
• Without checkpoints it can lead to:
• Extra time in processing entire log file
• Redoing of unnecessary transaction
 Key benefits of Checkpoints (Cont.)
• Key Benefits of Checkpoints
• Reduces recovery time after a crash.
• Ensures data consistency by writing recent changes to disk.
• Limits the number of logs that need to be processed during recovery.
 Example of Checkpoints
Tc Tf
T1
T2
T3
T4

checkpoint system failure

• T1 can be ignored (updates already output to disk due to checkpoint)

• T2 and T3 redone.
• T4 undone
 Deadlock
A deadlock occurs in a multi-threaded or multi-process environment when two or
more processes are blocked forever, each waiting for the other to release a resource.
There are four necessary conditions for a deadlock to occur, often referred to as the
Coffman conditions. These are:
1. Mutual Exclusion:
•At least one resource must be in a non-shareable mode, meaning only one process
can use it at a time. Other processes must wait until the resource becomes available.
•Example: A printer can only be used by one process at a time.
2. Hold and Wait:
•A process holding at least one resource is waiting for additional resources that are
currently being held by other processes.
•Example: Process A holds resource R1 and waits for resource R2, which is held by
process B.
3. No Preemption:
•Resources cannot be forcibly taken away from a process holding them. A process
must release the resource voluntarily after completing its task.
•Example: If a process is holding a resource and is waiting for another resource, the
system cannot preemptively take away the first resource to allocate it to another
process.
4. Circular Wait:
•A set of processes {P1, P2, ..., Pn} exists, such that each process is waiting for a
resource that the next process in the set holds. This forms a circular chain of waiting
processes.
•Example: Process A waits for resource R2, which is held by Process B, which in turn
waits for resource R3, held by Process C, and so on, until Process A waits for the
resource that Process A holds, creating a circle of dependencies.
 Deadlock Prevention
• To ensure no hold and wait, each transaction locks all the data item before it begins
execution.
• To ensure no cyclic wait, impose an ordering of all data item and requires that a
transaction lock data item only in the sequence consistent with ordering.
 However it is difficult to predict which data item are required
 Data item utilisation will be low
 Ordering of data item may be difficult or time taking to follow.
 Deadlock Handling
• Consider the following two transactions:
T1: write (X) T2: write(Y)
write(Y) write(X)
• Schedule with deadlock
 Deadlock Handling

• System is deadlocked if there is a set of transactions such that every

transaction in the set is waiting for another transaction in the set.
• Deadlock prevention protocols ensure that the system will never enter
into a deadlock state. Some prevention strategies :
• Require that each transaction locks all its data items before it begins execution
(predeclaration).
• Impose partial ordering of all data items and require that a transaction can lock
data items only in the order specified by the partial order (graph-based
protocol).
Deadlock Prevention Strategies
Wait-Die scheme
In this scheme, if a transaction requests for a resource which is already held with a conflicting lock
by another transaction then the DBMS simply checks the timestamp of both transactions. It allows
the older transaction to wait until the resource is available for execution.

Let's assume there are two transactions Ti and Tj and let TS(T) is a timestamp of any transaction T.
If T2 holds a lock by some other transaction and T1 is requesting for resources held by T2 then the
following actions are performed by DBMS:
1. Check if TS(Ti) < TS(Tj) - If Ti is the older transaction and Tj has held some resource, then Ti
is allowed to wait until the data-item is available for execution. That means if the older
transaction is waiting for a resource which is locked by the younger transaction, then the older
transaction is allowed to wait for resource until it is available.
2. Check if TS(Ti) < TS(Tj) - If Ti is older transaction and has held some resource and if Tj is
waiting for it, then Tj is killed and restarted later with the random delay but with the same
timestamp.
Wound wait scheme
1. In wound wait scheme, if the older transaction requests for a resource which is held by the
younger transaction, then older transaction forces younger one to kill the transaction and
release the resource. After the minute delay, the younger transaction is restarted but with the
same timestamp.
2. If the older transaction has held a resource which is requested by the Younger transaction,
then the younger transaction is asked to wait until older releases it.
 Deadlock prevention (Cont.)
• Both in wait-die and in wound-wait schemes, a rolled back
transactions is restarted with its original timestamp. Older
transactions thus have precedence over newer ones, and starvation is
hence avoided.
• Timeout-Based Schemes:
• a transaction waits for a lock only for a specified amount of time.
After that, the wait times out and the transaction is rolled back.
• thus deadlocks are not possible
• simple to implement; but starvation is possible. Also difficult to
determine good value of the timeout interval.
 Deadlock Detection
• A Wait-For Graph (WFG) is a directed graph used in Database Management
Systems (DBMS) to represent and analyze potential deadlocks in a multi-
transaction system. It visually depicts which transaction is waiting for which other
transaction to release resources.
• Components of a Wait-For Graph:
1.Nodes: Each node in the graph represents a transaction.
2.Edges: A directed edge (T1 → T2) indicates that transaction T1 is waiting for a
resource currently held by transaction T2.
• Purpose of a Wait-For Graph:
• It helps detect deadlocks in a system by identifying cycles in the graph. A cycle in
the graph implies a deadlock.
 Deadlock Detection (Cont.)

Wait-for graph without a cycle Wait-for graph with a cycle

 Deadlock Recovery
• Deadlock recovery in a Database Management System (DBMS) involves breaking the
circular wait condition to allow transactions to proceed. Once a deadlock is detected
(e.g., using a Wait-For Graph), the system must take measures to recover from it.
• Methods of Deadlock Recovery:
1.Transaction Termination:
1. Abort one or more transactions involved in the deadlock to free resources.
2. Victim Selection Criteria:
1.Priority: Abort low-priority transactions first.
2.Rollback Cost: Minimize cost by choosing transactions that have done the least
work.
3.Number of Resources Held: Abort transactions holding the fewest resources.
4.Waiting Time: Choose transactions waiting for the longest time.
3. The aborted transaction is typically rolled back to its initial state or a consistent
checkpoint and restarted later.
2. Resource Preemption:
• Temporarily take resources from some transactions and assign them to others to resolve
the deadlock.
• Considerations for resource preemption:
 Rollback: If a transaction loses a resource, it must be rolled back to a consistent state.
 Selection of Resource: Choose resources that will break the deadlock with minimal
disruption.
 Priority: High-priority transactions retain their resources.
3. Transaction Rollback:
•Rollback one or more transactions to a consistent checkpoint (partial rollback) or to the
beginning (total rollback).
•This action frees resources held by the rolled-back transaction, allowing others to proceed.
•Rolling back to checkpoints is preferred to minimize the cost of recovery.
4. Kill and Restart All Deadlocked Transactions:
•In extreme cases, all transactions in the deadlock are aborted and restarted.
•This is simple but costly in terms of time and resources.
5. Timeout-Based Recovery:
•Transactions that wait beyond a predefined time limit are considered potential deadlock victims
and are terminated.
•This is an indirect approach and avoids the explicit detection of deadlocks.
 Distributed Database
1. Distributed Database (DDB):
A Distributed Database is a system where data is stored across multiple different locations or
computers, but it all works together like one single database

2. Distributed Database Management System (DDBMS):

A Distributed Database Management System (DDBMS) is the software that manages these
distributed databases. It makes sure that even though the data is stored in different places, you can
access and interact with it as though it is all in one place. It hides the complexity of where and how
the data is stored and makes it seamless for you to use.
3. Features of Distributed Database:
• Data Stored at Multiple Sites: Data is spread across different locations (computers or
servers) rather than being stored in one single place.
• Sites Connected via Network: These different locations are connected through a
network, allowing them to communicate with each other.
• Logically One Database: Even though the data is stored in different places, it’s treated
as one single database. You won’t notice that it’s spread out.
• Full DBMS Functionality: The software provides all the usual features of a regular
database management system, such as allowing you to run queries, insert or delete
data, etc.
4. Advantages of Distributed Database:
• Sharing of Data: Multiple sites can share their data, making it accessible to everyone.
• Improved Availability and Reliability: If one site goes down (fails), other sites can still
provide the data. This makes the system more reliable.
• Autonomy: Each site has some level of control over its data. For example, each site can
decide how to manage its own data.
• Easier Expansion: You can easily add new sites or servers to the system if you need
more storage or power.
• Reduced Operating Costs: Since the system can use resources from multiple locations,
it can be more cost-effective.
• Faster Data Processing: With data stored in different locations, it’s possible to process
data faster because data can be accessed locally or processed in parallel by multiple
computers at once.
6. Disadvantages of Distributed Database:
• Complexity of Management and Control: Managing a distributed system is more
complex because you have to make sure that data at different locations is synchronized
and updated correctly.
• Deadlock Handling: Deadlocks happen when two processes prevent each other from
completing. In a distributed system, detecting and resolving deadlocks is more difficult.
• Security: With data spread across different sites, securing it becomes more challenging.
• Lack of Standards: Different sites might use different technologies or protocols, and this
lack of consistency can make management difficult.
7. Types of Distributed Databases:
•Homogeneous Distributed Database: All the sites in this type of system use the same
software and database structure. This makes it easy to manage and query because everything
is uniform across the system.
•Heterogeneous Distributed Database: In this system, different sites may use different types
of software or have different database structures. This makes it more challenging to manage
and process data across all sites.
8. Distributed Data Storage Approaches:
•Fragmentation: This is a way to break the database into pieces and store those pieces at
different sites.
• Horizontal Fragmentation: Data is split into rows, and each site stores different rows of
the database.
• Vertical Fragmentation: Data is split into columns, and each site stores different
columns of the database.
• Mixed Fragmentation: A combination of both horizontal and vertical fragmentation,
where data is split both by rows and columns.
•Replication: This means making copies of data or parts of the database and storing them at
multiple sites.
• Full Replication: Every site gets a copy of the entire database.
• Partial Replication: Only certain parts of the database are copied to different sites.
9. Why Replication is Desirable:
• Increased Availability of Data: If one site goes down, other sites with copies of the
data can still provide access to it, ensuring the data is always available.
• Better Performance: With multiple copies of data spread across sites, users can
access the data from the nearest site, improving speed.
• Disadvantage: When data is replicated, if you make any changes to the data, all the
copies need to be updated. This can cause extra work and slow down the system.
10. Transparency in Distributed Systems:
Transparency is about hiding the complexity of the distributed system from the user.
This means users don’t need to worry about where the data is stored, how it is split, or
whether it’s replicated. There are several types of transparency:
• Location Transparency: The user doesn’t need to know where the data is stored.
Whether it’s stored on the next computer or halfway across the world, the user
doesn’t need to worry about it.
• Fragmentation Transparency: Users don’t need to know how the data is split
(fragmented) or where each part is stored. They interact with it as if it’s a complete
database.
• Replication Transparency: Users don’t need to know if the data is replicated (copied)
across multiple sites. They interact with the data as if it’s only available from one site.
• Naming Transparency: Users don’t need to know the technical details about how the
data is named or how it’s identified across the distributed system.
DIRECTORY SYTEM
A Directory System in the context of databases or distributed systems refers to a system that
stores and manages information about the locations and attributes of data in a distributed
database or network. It acts like a "phonebook" or "address book" for the system, helping
users or applications locate data across multiple sites or servers.
Key Points about Directory Systems:
1.Centralized vs. Distributed Directory:
1. Centralized Directory: All information about the data is stored in a single, central
location. The directory is responsible for keeping track of the data’s location, so when a
request for data is made, the directory points to where the data can be found.
2. Distributed Directory: The directory is distributed across multiple locations, and each
location contains information about some portion of the data. It helps to keep the
system decentralized and scalable.
1.How it Works: In a directory system, when you need data from a distributed database, you first
consult the directory to find out where the required data is stored. The directory provides the
location (or location hint) and attributes (like who has access to it, how it's structured, etc.) for the
data, so the system can access it efficiently.
2.Functionality:
• Data Location: The directory system keeps track of which sites or servers store which
pieces of data. For example, it can tell you that data about "customer orders" is stored at
Site 1 and "product inventory" is stored at Site 2.
• Access Control: It may also manage access permissions, ensuring that only authorized
users can access certain pieces of data.
• Load Balancing: Some directory systems are designed to help with load balancing,
directing traffic to less busy parts of the system to improve performance.
Example of Use:
• In a distributed file system, the directory system could map file names to the locations of the
files on various servers in a network.
• In a distributed database, the directory could track which part of the database (which fragment
or replica) is stored at which server.
Directory System in a Distributed Database:
In a distributed database, the directory system helps in finding the data by:
• Storing information about the fragments (parts of a database) and their locations.
• Managing replicas of data, telling the system where copies of the same data are
stored.
• Helping the system handle data access by providing the required data's location and
managing efficient queries.
Let Ri(z) and Wi(z) denote read and write operations on a data element z by a transaction Ti, respectively.
Consider the following schedules S1 and S2
S1: R1(X), W1(X), R2(X), W2(X), R1(Y), W1(Y), R2(Y), W2(Y)
S2: R1(X), W1(X), R1(Y), W1(Y), R2(X), W2(X), R2(Y), W2(Y)
Check the correctness of the statement “S1 and S2 are view equivalent” step by step.
Let Ri(z) and Wi(z) denote read and write operations on a data element z by a
transaction Ti, respectively. Consider and analyze the schedule S with four
transactions.
S: R4(x), R2(x), R3(x), R1(y), W1(y), W2(x), W3(y), R4(y)
Find the correct serial schedule, which is conflict equivalent to S.
 T1 T2
Consider a schedule of transactions T1 and T2 :
R(A)
R(B)
Which one of the following schedules is
W(B)
conflict equivalent to the above schedule?
R(C)
R(D)
W(D)
W(C)
W(B)
T1 T2 T1 T2 T1 T2 T1 T2
COMMIT
R(B)
R(B) R(A) R(A)
COMMIT W(B)
W(B) R(C) R(C)
R(D)
R(D) W(D) W(D)
W(C)
R(A) W(B) R(B)
R(A)
R(C) R(B) W(B)
R(C)
W(D) W(B) R(D)
W(D)
W(B) R(D) W(B)
W(B)
W(C)
W(C) W(C) COMMIT
COMMIT
COMMIT COMMIT
COMMIT COMMIT
COMMIT COMMIT
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given
below.T1 : r1 (X) ; r1 (Z) ; w1 (X) ; w1 (Z)
S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?

A. Only S1 is conflict-serializable.
B. Only S2 is conflict-serializable.
C. Both S1 and S2 are conflict-serializable.
D. Neither S1 nor S2 is conflict-serializable.
Consider the following four schedules due to three transactions
(indicated by the subscript) using read and write on a data item x,
denoted by r(x) and w(x) respectively. Which one of them is conflict
serializable?

A. r1(x); r2(x); w1(x); r3(x); w2(x)

B. r2(x); r1(x); w2(x); r3(x); w1(x)
C. r3(x); r2(x); r1(x); w2(x); w1(x)
D. r2(x); w2(x); r3(x); r1(x); w1(x)
Check whether given schedule is conflict
serializable or not.
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)