Module 4
S R Hiray
Contents
• Concurrency Control: Need, Locking Methods, Deadlocks, Time-
stamping Methods, and Optimistic
• Techniques. Recovery Methods: Shadow-Paging and Log-Based
Recovery, Checkpoints.
• Introduction to Information Retrieval, Difference between Data
Retrieval and
• Information Retrieval, Types of IR Model, User Interaction with
Information Retrieval System.
Introduction
• Concurrent execution improves performance
• Multiple transactions run simultaneously
• Requires control to maintain consistency
Need for Concurrency Control
• Maintain Isolation (ACID)
• Avoid data inconsistency
• Ensure serializability
Concurrency Problems
• Lost Update
• Dirty Read
• Unrepeatable Read
• Phantom Read
Lost Update
1. Lost Update
Occurs when two transactions update the same data simultaneously.
One transaction’s update overwrites the other.
Final value reflects only one update → data loss.
2. Dirty Read
A transaction reads data that is not yet committed by another transaction.
If the first transaction rolls back, the read data becomes invalid.
Leads to incorrect decisions.
. Unrepeatable Read
A transaction reads the same data twice but gets different
values.
Happens when another transaction updates the data between
reads.
Violates consistency within a transaction.
4. Phantom Read
A transaction re-executes a query and finds new rows
added/deleted.
Caused by another transaction inserting or deleting records.
Affects range queries (e.g., SELECT WHERE condition).
Concurrency Techniques
• Lock-Based Protocols
• Timestamp-Based Protocols
• Optimistic Concurrency Control
Locking protocol
Each transaction in system should follow a set of rules,
called locking protocol, indicating when a transaction may
lock and unlock each of data items.
If {T1,T2,T3,..} are the transaction in S. Ti precedes Tj
noted by Ti Tj should be followed in any serial schedule
if
If there exists a data item Q such that Ti hold a lock on Q in
mode A and Tj holds a lock on Q in mode B
If Compatibility(A,B) = False
A schedule is legal under given locking protocol if it
follows all rules of it.
9
A locking protocol ensures conflict serializability
if and only
if all legal schedules are conflict serializable; in
other words, for all legal schedules the
associated→relation is acyclic.
10
Lock Types
• Shared Lock (Read)
• Exclusive Lock (Write)
• Lock compatibility rules
Lock-Based Protocols
A lock is a mechanism to control concurrent access to a
data item
Data items can be locked in two modes :
1. exclusive (X) mode. Data item can be both read as
well as written. X-lock is requested using lock-X
instruction.
2. shared (S) mode. Data item can only be read.
S-lock is requested using lock-S instruction.
12
Lock-Based Protocols (Cont.)
Lock-compatibility matrix
A transaction may be granted a lock on an item if the
requested lock is compatible with locks already held on the
item by other transactions
Multiple Shared locks….
Exclusive only 1 at atime….
13
**
14
Lock-Based Protocols (Cont.)
Example of a transaction
performing locking:
Locking as above is not sufficient
T2: lock-S(A); to guarantee serializability — if A
read (A); and B get updated in-between the
unlock(A); read of A and B, the displayed
lock-S(B);
sum would be wrong.
read (B);
unlock(B); A locking protocol
display(A+B)
15
T1 T2 CONCURRENCY-CONTROL MANAGER
Lock-X(B)
Grant-X(B, T1)
Read (B)
B:=B-50
Write (B)
Unlock (B)
Lock-S(A)
Grant-S (A, T2)
Read (A)
Unlock (A)
Lock-S (B)
Grant-S (B, T2)
Read (B)
Unlock (B)
Display (A+B)
Lock-X(A)
Grant-X(A, T1)
16
Problems in the schedule
T2 shows inconsistent result.
Solution delay the unlock till end of transaction.
The previous schedule is no longer possible.
17
18
**
19
Pitfalls of Lock-Based Protocols
Consider the partial schedule
Neither T3 nor T4 can make
progress — executing lock-
S(B) causes T4 to wait for T3
to release its lock on B,
while executing lock-X(A)
causes T3 to wait for T4 to
release its lock on A.
Such a situation is called a
deadlock.
To handle a deadlock one of
T3 or T4 must be rolled back
20
Pitfalls of Lock-Based Protocols (Cont.)
The potential for deadlock exists in most locking
protocols. Deadlocks are a necessary evil.
Starvation is also possible if concurrency control
manager is badly designed.
21
Granting of locks
To avoid starvation the locks can be granted in following
manner
When a transaction requests a lock on a data item Q in a
particular mode M, the concurrency-control manager
grants a lock provided that
There is no other transaction holding a lock on Q in a
mode that conflicts with M
There is no other transaction that is waiting for a lock on
Q and that made its lock request before Ti.
22
The Two-Phase Locking Protocol
This is a protocol which ensures conflict-serializable
schedules.
Phase 1: Growing Phase
Phase 2: Shrinking Phase
T3T4
23
Partial Schedule Under Two-Phase Locking
Failure of T5 after
read(A) step of T7,
leads cascading
rollbacks of T6 and T7
24
strict two-phase locking.
Here a transaction must hold all its exclusive locks till it commits/aborts.
25
The Two-Phase Locking Protocol (Cont.)
The protocol assures serializability. It can be proved that the
transactions can be serialized in the order of their lock points
(i.e. the point where a transaction acquired its final lock).
Two-phase locking does not ensure freedom from deadlocks
Cascading roll-back is possible under two-phase locking. To
avoid this, follow a modified protocol called strict two-phase
locking. Here a transaction must hold all its exclusive locks till
it commits/aborts.
Rigorous two-phase locking is even stricter: here all
26
The Two-Phase Locking Protocol (Cont.)
There can be conflict serializable schedules that cannot be
obtained if two-phase locking is used.
However, in the absence of extra information (e.g., ordering
of access to data), two-phase locking is needed for conflict
serializability in the following sense:
Given a transaction Ti that does not follow two-phase
locking, we can find a transaction Tj that uses two-phase
locking, and a schedule for Ti and Tj
27
28
T8: read(a1);
read(a2);
...
read(an);
write(a1).
T9: read(a1);
read(a2);
display(a1 + a2).
29
Graph-Based Protocols
Graph-based protocols are an alternative to two-phase locking
Impose a partial ordering on the set D = {d1, d2 ,..., dh} of all
data items.
If di dj then any transaction accessing both di and dj must
access di before accessing dj.
This partial ordering may be the physical, logical
arrangement of data or just added to achieve concurrency
control
Implies that the set D may now be viewed as a directed
acyclic graph, called a database graph.
The tree-protocol
30
Deadlock Concept
• Circular waiting condition
• Transactions block each other
• System halts progress
Tree Protocol
Only exclusive locks are
allowed.
The first lock by Ti may be on
any data item.
Subsequently, a data Q can be
locked by Ti only if the parent
of Q is currently locked by Ti.
Data items may be unlocked at
any time.
A data item that has been
locked and unlocked by Ti can
not subsequently be relocked
by Ti.
32
Timestamp-Based Protocols
Each transaction is issued a timestamp when it enters the
system. If an old transaction Ti has time-stamp TS(Ti), a
new transaction Tj is assigned time-stamp TS(Tj) such that
TS(Ti) <TS(Tj).
There are two ways for implementing this scheme
Use the value of system clock as the timestamp; that is a
transaction's time stamp is equal to the value of clock when
the transaction enters the system.
Use the logical counter that is incremented after a new
timestamp has been assigned; that is the transaction's time
stamp is equal to the value of the counter when the
transaction enters the system.
33
Timestamp-Based Protocols
The protocol manages concurrent execution such that the
time-stamps determine the serializability order.
In order to assure such behavior, the protocol maintains
for each data Q two timestamp values:
W-timestamp(Q) is the largest time-stamp of any
transaction that executed write(Q) successfully.
R-timestamp(Q) is the largest time-stamp of any
transaction that executed read(Q) successfully.
These timestamp are updated whenever a new read(Q) or
write(Q) is executed.
34
Timestamp-Based Protocols (Cont.)
The timestamp ordering protocol ensures that any
conflicting read and write operations are executed
in timestamp order.
Suppose a transaction Ti issues 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
35
Timestamp-Based Protocols (Cont.)
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. Otherwise, the write operation is executed, and W-
timestamp(Q) is set to TS(Ti
36
Example Use of the Protocol
T1 T2 T3 T4 T5
read(X)
read(Y)
read(Y)
write(Y)
write(Z)
read(Z)
read(X)
abort
read(X)
write(Z)
abort
write(Y)
write(Z)
A partial schedule for several data items for transactions
with timestamps 1, 2, 3, 4, 5
37
Schedule for Timestamp based protocol
38
Correctness of Timestamp-Ordering Protocol
The timestamp-ordering protocol guarantees
serializability since all the arcs in the precedence graph
are of the form:
transaction transaction
with smaller with larger
timestamp timestamp
Thus, there will be no cycles in the precedence graph
Timestamp protocol ensures freedom from deadlock as
no transaction ever waits.
39
Deadlock Example in DBMS
• T1 locks A, T2 locks B
• T1 requests B (held by T2)
• T2 requests A (held by T1)
• Circular wait occurs
Necessary Conditions (Coffman)
• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait
Deadlock Detection
• Use Wait-for Graph
• Nodes = Transactions
• Edges show waiting
• Cycle indicates deadlock
Deadlock Prevention
• Break one Coffman condition
• Request all resources at once
• Use resource ordering
• Allow preemption
Deadlock Avoidance
• Check system safety before allocation
• Grant only safe requests
• Example: Banker’s Algorithm
Deadlock Recovery
• Abort transaction
• Rollback and restart
• Preempt resources
Practical Example
• Doctor updates patient record
• Lab updates report
• Both wait for each other
• System freeze avoided with control
Key Points (Exam Focus)
• Deadlock = circular waiting
• Requires 4 conditions
• Handled by prevention, detection, avoidance, recovery
Thomas’ Write Rule
Modified version of the timestamp-ordering protocol in which
obsolete write operations may be ignored under certain
circumstances.
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.
Otherwise this protocol is the same as the timestamp ordering
protocol.
Thomas' Write Rule allows greater potential concurrency.
Allows some view-serializable schedules that are not conflict-
serializable.
Questions
[Link] Transaction Management. Explain ACID
propertiies with example(4)
2. Write a short note on Deadlock in Database (4)
[Link] 2 phase locking protocol with example (4)
[Link] note on 2 phase locking protocol (2)
[Link] lock-based protocol to control concurrency
in Database(4).
[Link] in brief 2 phase locking protocol (4)
[Link] Timestamp based concurrency control
protocol (3)
49
Recovery Schemes
Recovery schemes are techniques to ensure database
consistency and transaction atomicity and durability
despite failures such as transaction failures, system crashes,
disk failures.
Recovery algorithms have two parts
1. Actions taken during normal transaction processing to
ensure enough information exists to recover from failures
2. Actions taken after a failure to recover the database
contents to a state that ensures atomicity, consistency
and durability
Recovery and Atomicity
Modifying the database without ensuring that the
transaction commits may leave the database in an
inconsistent state.
Consider again the transaction Ti that transfers €50 from
account A to account B.
Several output operations are required for Ti (to output
A and B). A failure may occur after one of these
modifications have been made but before all of them
are made.
Recovery Schemes
Recovery schemes are techniques to ensure database
consistency and transaction atomicity and durability
despite failures such as transaction failures, system
crashes, disk failures.
Recovery algorithms have two parts
1. Actions taken during normal transaction processing to
ensure enough information exists to recover from
failures
2. Actions taken after a failure to recover the database
contents to a state that ensures atomicity, consistency
and durability
Recovery and Atomicity
Modifying the database without ensuring that the
transaction commits may leave the database in an
inconsistent state.
Consider again the transaction Ti that transfers €50 from
account A to account B.
Several output operations are required for Ti (to output
A and B). A failure may occur after one of these
modifications have been made but before all of them
are made.
Example of Data
buffer
Access
Buffer Block A input(A)
X A
Buffer Block B Y B
output(B)
read(X)
x1
y1
work area
of T1
memory disk
Recovery and Atomicity
To ensure atomicity despite failures, first output
information describing the modifications to stable
storage (i.e. storage guaranteed/assumed not to fail,
without modifying the database itself.
Two approaches are possible:
[Link]-based recovery, and
[Link]-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, and V2 is
the value to be written to X.
Log record notes that Ti has performed a write on data
item Xj Xj had value V1 before the write, and will have
value V2 after the write.
When Ti finishes it last statement, the log record <Ti commit>
is written.
For writing the actual records
Deferred database modification
Immediate database modification
Deferred Database Modification
The deferred database modification scheme records all
modifications to the log, and defers writes to after partial commit.
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 (old value is not needed).
The write is not performed on X at this time, but is deferred.
When Ti partially commits, <Ti commit> is written to the log
After that, the log records are read and used to actually execute
the previously deferred writes.
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.
Immediate Database Modification
The immediate database modification scheme allows database
updates of an uncommitted transaction to be made as the
writes are issued
since undoing may be needed, update logs must have both
old value and new value
Update log record must be written before database item is
written
We assume that the log record is output directly to stable
storage
Can be extended to postpone log record output, so long as
prior to execution of an output(B) operation for a data block B,
all log records corresponding to items B must be flushed to
stable storage
Output of updated blocks 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.
Immediate Database Modification Example
Log Write Output
<T0 start>
<T0, A, 1000, 950>
<To, B, 2000, 2050>
A = 950
B = 2050
<T0 commit> BC output before
<T1 start> T1 commits
<T1, C, 700, 600>
C = 600
BB , BC
<T1 commit> BA output after T0
BA commits
Note: BX denotes block containing X.
Immediate Database Modification
(Cont.)
Recovery procedure has two operations instead of one:
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
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
Both operations must be idempotent
That is, even if the operation is executed multiple times the
effect is the same as if it is executed once
Needed since operations may get re-executed during
recovery
When recovering after failure:
Transaction Ti needs to be undone if the log contains the
record
<Ti start>, but does not contain the record <Ti commit>.
Transaction Ti needs to be redone if the log contains both the
record <Ti start> and the record <Ti commit>.
Undo operations are performed first, then redo operations.
Introduction
• Recovery techniques ensure database consistency after failures.
• Two major methods:
• • Shadow Paging
• • Log-Based Recovery
Shadow Paging Concept
• Shadow paging maintains two page tables:
• • Current Page Table
• • Shadow Page Table
• Shadow table remains unchanged during transaction execution.
Working of Shadow Paging
• 1. Transaction starts
• 2. Changes made on copied pages
• 3. Current page table updated
• 4. Commit replaces shadow table
• 5. Failure restores shadow table
Advantages of Shadow Paging
• • No need for logs
• • Fast recovery
• • Simple rollback mechanism
• • Atomic transaction support
Disadvantages of Shadow Paging
• • Extra storage overhead
• • Page table copying cost
• • Garbage collection required
• • Difficult with concurrent transactions
Log-Based Recovery
• Log-based recovery records all database operations in a log file.
• Used for redo and undo operations after crash.
Checkpoints
Problems in recovery procedure as discussed earlier :
1. searching the entire log is time-consuming
2. one might unnecessarily redo transactions which
have already output their updates to the
database.
Streamline recovery procedure by periodically
performing checkpointing
1. Output all log records currently residing in main
memory onto stable storage.
2. Output all modified buffer blocks to the disk.
3. Write a log record < checkpoint> onto stable
storage.
Questions
1. Write a short note on Log Based recovery
1. Explain different concurrency control protocols in
database management systems
1. Explain the need for concurrency control in
transaction management.
Deadlocks in Concurrency Control
• Definition, Conditions, Detection & Handling
What is a Deadlock?
• Two or more transactions wait indefinitely
• Each waits for the other to release resources
• No transaction can proceed
Real-Life Analogy
• Person A holds Room 1, needs Room 2
• Person B holds Room 2, needs Room 1
• Both wait forever → Deadlock
Deadlock Handling
Consider the following two transactions:
T1: write (X) T2: write(Y)
write(Y) write(X)
T1 T2
lock-X on X
write (X)
lock-X on Y
write (X)
wait for lock-X on X
wait for lock-X on Y
74
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).
75
More Deadlock Prevention Strategies
Following schemes use transaction timestamps for the
sake of deadlock prevention alone.
wait-die scheme — non-preemptive
older transaction may wait for younger one to release
data item. Younger transactions never wait for older
ones; they are rolled back instead.
a transaction may die several times before acquiring
needed data item
wound-wait scheme — preemptive
older transaction wounds (forces rollback) of younger
transaction instead of waiting for it. Younger transactions
may wait for older ones.
may be fewer rollbacks than wait-die
76
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
77
Deadlock Detection
Deadlocks can be described as a wait-for graph, which
consists of a pair G = (V,E),
V is a set of vertices (all the transactions in the system)
E is a set of edges; each element is an ordered pair Ti Tj.
If Ti Tj is in E, then there is a directed edge from Ti to
Tj, implying that Ti is waiting for Tj to release a data item.
When Ti requests a data item currently being held by Tj,
then the edge Ti Tj is inserted in the wait-for graph. This
edge is removed only when Tj is no longer holding a data
item needed by Ti.
78
Introduction to Information Retrieval
• • Information Retrieval (IR) retrieves relevant information from large
collections of data.
• • Mainly used for unstructured data.
• • Examples: Search engines, digital libraries, multimedia search.
Need for Information Retrieval
• • Huge amount of digital information available.
• • Fast access to relevant documents.
• • Improves search efficiency.
• • Used in web search and online databases.
Data Retrieval vs Information Retrieval
• Data Retrieval:
• • Exact matching
• • Structured data
• • SQL based
• Information Retrieval:
• • Relevant matching
• • Unstructured data
• • Keyword based searching
Types of IR Models
• Main IR Models:
• 1. Boolean Model
• 2. Vector Space Model
• 3. Probabilistic Model
• 4. Semantic / Intelligent IR Model
Boolean Model
• • Uses Boolean operators AND, OR, NOT.
• • Retrieves exact matching documents.
• • Simple and easy to implement.
• • No ranking of documents.
Vector Space Model
• • Represents documents as vectors.
• • Uses cosine similarity.
• • Supports ranked retrieval.
• • Allows partial matching.
Probabilistic & Semantic IR Models
• Probabilistic Model:
• • Uses probability of relevance.
• Semantic IR Model:
• • Uses AI and NLP.
• • Understands context and meaning.
User Interaction with IR System
• Steps:
• 1. Query submission
• 2. Query processing
• 3. Searching documents
• 4. Ranking results
• 5. Displaying results
• 6. User feedback
Applications & Conclusion
• Applications:
• • Search engines
• • Digital libraries
• • E-commerce search
• • Medical systems
• Conclusion:
• IR systems help retrieve relevant information efficiently.
Introduction
• An Information Retrieval (IR) system retrieves relevant information
from a large collection of documents.
Main Components of IR System
• • User Interface
• • Query Processor
• • Indexing Module
• • Document Database
• • Search Engine
• • Ranking Module
User Interface
• Allows users to enter queries and view search results.
Query Processor
• Processes the user query by tokenization, stemming, and stop-word
removal.
Indexing Module
• Creates indexes for faster searching and retrieval.
Document Database
• Stores all documents, web pages, or multimedia files.
User Interface
• Allows users to enter queries and view search results.