Transcript slides

Theory, Practice & Methodology
of Relational Database
Design and Programming
Copyright © Ellis Cohen 2002-2008
Transactions
These slides are licensed under a Creative Commons
Attribution-NonCommercial-ShareAlike 2.5 License.
For more information on how you may use them,
please see http://www.openlineconsult.com/db
1
Overview of Lecture
The ACID Properties
Transactions and Commit
Abort and Rollback
Statement Failure & Nested Rollback
SavePoints and Nested Transactions
Autonomous Transactions
Concurrency Problems
Locking
Phantom Reads
Deadlock
Read-Consistent Concurrency
Read-Committed Concurrency
© Ellis Cohen 2001-2008
2
ACID Properties of Transactions
Atomicity
All DB modifications made in a transaction are
done or none are done
Consistency
Each transaction leaves the database in a
consistent state (i.e. based on enforcement of
state constraints)
Isolation
Each transaction, when executed concurrently
with other transactions, should have the same
effect as if executed by itself
Durability
Once a transaction has completed successfully,
its changes to the database should be
permanent
© Ellis Cohen 2001-2008
3
Transactions and
Commit
© Ellis Cohen 2001-2008
4
Transaction
Logical unit of work that must be
either entirely carried out or
aborted
Example:
a sequence of SQL commands,
grouped together,
e.g. in an SQL*Plus script
If only part of the transaction were
carried out, the database could be
left in an inconsistent state
© Ellis Cohen 2001-2008
5
Example SQL*Plus Script
This script moves money
from one account to another.
Parameters:
:srcacct - The account to move money from
:dstacct - The account to move money to
:amt - The amount of money to be moved
UPDATE checking
SET balance = balance - :amt
WHERE acctid = :srcacct;
UPDATE checking
SET balance = balance + :amt
WHERE acctid = :dstacct;
Suppose a crash
occurs right here!
© Ellis Cohen 2001-2008
6
Transactions & COMMIT
All SQL commands are
performed within a transaction
Transaction starts
Modify
Transaction
ensures
these are
done
atomically
Modify
Modify
Modify
Transaction commits
Modifications persisted to DB
• Each modification is
visible to the SQL
commands executed after
it in the same transaction
• But the modification is not
actually persisted to the
database until the
transaction commits
• So, if a crash occurs in the
middle of a transaction,
after some modifications
have been done,
the DB acts as if the
modifications never
happened!
© Ellis Cohen 2001-2008
7
Uncommitted & Committed
Transactions
start
transaction
modify
modify
Modifications not
yet persisted
start
transaction
modify
modify
modify
COMMIT
Modifications
persisted to DB
© Ellis Cohen 2001-2008
8
SQL*Plus Commit Example
SQL> set autocommit off
Transaction started automatically at first
update if not already in progress
SQL> UPDATE checking
SET balance = balance - :amt
WHERE acctid = :srcacct;
SQL> UPDATE checking
SET balance = balance + :amt
WHERE acctid = :dstacct;
SQL> COMMIT;
© Ellis Cohen 2001-2008
9
Starting Transactions
The COMMIT command ends a transaction
How do transactions start?
– Most databases start a new transaction
automatically
• on the first access to the DB within a
session, and
• on the first access following a COMMIT
– Some databases have a START
TRANSACTION command (to support
nested transactions)
© Ellis Cohen 2001-2008
10
Transactions & DB Requests
CrossRequest
Transactions
WithinRequest
Transactions
UPDATE …
UPDATE …
COMMIT
UPDATE …
COMMIT
Execute
Stored
Procedure
Middle Tier
© Ellis Cohen 2001-2008
PROCEDURE
StoredProc IS
BEGIN
UPDATE …
UPDATE …
COMMIT
UPDATE …
COMMIT
END;
Data Tier
11
Automatic Commit
DB Modifications may persist even when
COMMIT is not explicitly called
• Most databases support — either on the server or
just through the client-side API — an autocommit
mode which automatically does a commit after
execution of each request made to the database.
This is often the default.
• Most databases automatically COMMIT when a
client cleanly closes their connection to the
database.
• Most databases (including Oracle) do not allow
DDL statements (e.g. CREATE TABLE) to be part of
a larger transaction, and automatically do a
commit before and after executing a DDL
statement.
© Ellis Cohen 2001-2008
12
Java Commit Example
Connection conn = …;
conn.setAutoCommit( false );
movemoney( conn, 30479, 61925, 2000 );
…
//--------------------------------------static void movemoney( Connection conn,
int srcacct, int dstacct, float amt )
{
Statement stmt = conn.createStatement();
String sqlstr = "update checking" +
" set balance = balance - " + amt +
" where acctid = " + srcacct;
stmt.executeUpdate( sqlstr );
sqlstr = "update checking" +
" set balance = balance + " + amt +
" where acctid = " + dstacct;
stmt.executeUpdate( sqlstr );
}
conn.commit();
© Ellis Cohen 2001-2008
13
Abort & Rollback
© Ellis Cohen 2001-2008
14
Abort
Aborting a transaction undoes the
effects of the transaction -- it is as
if the transaction never started
Transactions are aborted in 3 ways:
1. The system crashes: All active
transactions are aborted
2. An uncaught error occurs while
executing the transaction
3. The transaction explicitly aborts (this
is called a ROLLBACK)
A transaction completes when it
either commits or aborts
© Ellis Cohen 2001-2008
15
Rollback
Rollback aborts a transaction
• SQL
ROLLBACK
• Java
conn.rollback()
© Ellis Cohen 2001-2008
16
Commit vs Rollback
start
transaction
modify
modify
modify
COMMIT
modify
modify
ROLLBACK
start
transaction
modify
© Ellis Cohen 2001-2008
17
Explicit Rollback
With AUTOCOMMIT OFF
SQL> COMMIT;
SQL> UPDATE Emps SET job = 'COOK';
SQL> UPDATE Emps SET sal = sal + 200;
SQL> ROLLBACK;
After the ROLLBACK, the state is exactly as it
was following the COMMIT.
It is as if the two UPDATEs never happened!
© Ellis Cohen 2001-2008
18
Explicit Rollback in Java
{
Connection conn = …;
conn.setAutoCommit( false );
Statement stmt = conn.createStatement();
String sqlstr = "UPDATE Emps SET job = 'COOK'";
stmt.executeUpdate( sqlstr );
sqlstr = "UPDATE Emps SET sal = sal + 200";
stmt.executeUpdate( sqlstr );
}
…
if (…)
conn.commit();
else
conn.rollback();
© Ellis Cohen 2001-2008
19
Statement Failure
& Nested Rollback
© Ellis Cohen 2001-2008
20
Failure During Modification
UPDATE Emps SET sal = sal + 200
Emps
empno
ename
dept
sal
comm
7499
ALLEN
30
1600
300
 1800
7654
MARTIN
30
1250
1400
 1450
7698
BLAKE
30
2850
7839
KING
10
5000
7844
TURNER
30
1500
7986
STERN
50
1500
 3050
OOPS!
0
check( sal < 5100 )
What happens to the changes
that were already made?
© Ellis Cohen 2001-2008
21
Statement Failure
A statement can fail
– E.g. due to violation of an integrity
constraint, e.g. check( sal < 5100 )
Result of statement failure:
– The statement is rolled back.
if an update statement would update
100 records, but updating the 11th
records causes failure of an integrity
constraint, the 10 previously
updated records are rolled back to
their old state
© Ellis Cohen 2001-2008
22
Effect of Statement Failure
With AUTOCOMMIT OFF
SQL> COMMIT;
SQL> UPDATE Emps SET job = 'COOK';
SQL> UPDATE Emps SET sal = sal + 200;
Suppose the second update fails.
Will everyone's job still be COOK?
© Ellis Cohen 2001-2008
23
Statement Failure Does Not
Automatically Rollback Outer Transaction
With AUTOCOMMIT OFF
SQL> COMMIT;
SQL> UPDATE Emps SET job = 'COOK';
SQL> UPDATE Emps SET sal = sal + 200;
If this update fails, the statement
will have no effect.
It does not cause a rollback.
Everyone's job is still cook!
© Ellis Cohen 2001-2008
24
Statement-Level Nesting
Every SQL statement executes
within a nested transaction
Result of statement success
– Statement-level transaction is
released
Result of statement failure:
– The statement is rolled back.
– The outer transaction is not
automatically rolled back, but
(depending on the programming
environment) an error is raised
© Ellis Cohen 2001-2008
25
SQL*Plus Exception Handling
With AUTOCOMMIT OFF
If an error is reported to SQL*Plus
as a result of a request it sends to
the database
• It will catch and announce the
error
• But it will NOT rollback the outer
transaction
© Ellis Cohen 2001-2008
26
Rollback vs Statement Failure
start
transaction
modify
modify
ROLLBACK
Statement
Failure
start
transaction
modify
modify
modify
modify
Raise
Error
© Ellis Cohen 2001-2008
27
Statement Failure
within a Block Request
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
END;
/
Suppose the
second update
fails.
Will everyone's
job still be COOK?
© Ellis Cohen 2001-2008
28
Block Requests as
Nested Transactions
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
END;
/
Suppose this
update fails.
Will everyone's
job still be
COOK?
When a PL/SQL block is
passed to the server, it
is executed as a nested
transaction, which is
rolled back by an
unhandled exception.
© Ellis Cohen 2001-2008
29
Rollback of Block Requests
Statement
Failure
start
transaction
SQL*Plus
modify
PL/SQL Block sent
to server
modify
Exception automatically
caught and PL/SQL block
(ONLY) rolled back;
error reported to SQL*Plus
modify
Raises
Error
© Ellis Cohen 2001-2008
30
Exceptions vs. Rollbacks
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
EXCEPTION
WHEN OTHERS THEN
pl( 'Caught it!' );
END;
/
Suppose the
second update
fails.
Will everyone's
job still be
COOK?
© Ellis Cohen 2001-2008
31
Answer: Exceptions vs. Rollbacks
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
EXCEPTION
WHEN OTHERS THEN
pl( 'Caught it!' );
END;
/
YES! The exception raised when
the update fails is caught by the
exception handler. The
outermost block exits normally.
Nothing causes an automatic
rollback of the first update.
© Ellis Cohen 2001-2008
Suppose the
second update
fails.
Will everyone's
job still be
COOK?
32
Rollback with Output
With AUTOCOMMIT OFF
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET comm = 1000;
UPDATE Emps SET sal = sal + 200;
END;
/
Suppose I want to execute this code.
If any UPDATE fails
• I want to write out an error message
• Ensure that any changes made by all
3 updates are rolled back
What’s the required code?
© Ellis Cohen 2001-2008
33
Use Explicit Rollback
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET comm = 1000;
UPDATE Emps SET sal = sal + 200;
EXCEPTION WHEN OTHERS THEN
pl( 'Oops, did not work' );
ROLLBACK;
Alternately, call
END;
a procedure
which prints
/
out the
exception
details & rolls
WARNING: If autocommit
back
is turned off, this will
ROLLBACK the entire outer
transaction, not just these
3 statements!
© Ellis Cohen 2001-2008
34
Alternative: Re-Raise
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET comm = 1000;
UPDATE Emps SET sal = sal + 200;
EXCEPTION WHEN OTHERS THEN
pl( 'Oops, did not work' );
RAISE;
END;
/
The re-raised exception will be
caught by the exception handler
which rolls back the outermost
block, but not the entire transaction
Note that output does not get rolled back
An exception is reported by SQL*Plus
© Ellis Cohen 2001-2008
35
SavePoints &
Nested Transactions
© Ellis Cohen 2001-2008
36
Nested Transactions
Transaction can nest
start
transaction
set
savepoint
modify
modify
modify
Only the outermost transaction can
commit and persist data
Nested transactions can control the
degree of rollback
Nested transactions in SQL are
implemented using SAVEPOINTs
© Ellis Cohen 2001-2008
37
Savepoints
SAVEPOINT <savepointName>
Explicitly starts new named nested transaction.
Reusing the name of an existing savepoint
automatically releases it first.
ROLLBACK TO <savepointName>
Rolls back to state at start of named nested
transaction
and releases any savepoints within it
ROLLBACK
Rolls back to state at start of outermost
transaction
and releases any savepoints
COMMIT
Releases all savepoints within outermost
transaction & commits
© Ellis Cohen 2001-2008
38
Savepoint & Rollback
start
transaction
set
save
point
A
set
save
point
B
set
save
point
C
set
save
point
D
rollback
to B
© Ellis Cohen 2001-2008
39
Savepoints for Alternative
Execution Paths
Set savepoint to try something that is quick
but doesn’t always work
e.g. access to some remote database
that is not always available
On failure, back up to the savepoint
(undoing any changes to the DB you have
made) and try slower but more reliable
technique
Failure &
Rollback
Save
point
© Ellis Cohen 2001-2008
40
Alternative Path in PL/SQL
BEGIN
DoInitialSetup( … );
BEGIN
SAVEPOINT RetryPoint;
DoQuickButUnreliableUpdates(…);
EXCEPTION WHEN OTHERS THEN
ROLLBACK TO RetryPoint;
DoSlowButReliableUpdates(…);
END;
END;
© Ellis Cohen 2001-2008
41
Alternative Path in Java
Connection conn = …;
Statement stmt = conn.createStatement();
DoInitialSetup(…);
try {
Savepoint spRetry =
conn.setSavepoint( "RetryPoint" );
DoQuickButUnreliableUpdates(…);
}
catch( Exception e ) {
conn.rollback( spRetry );
DoSlowButReliableUpdates(…);
}
© Ellis Cohen 2001-2008
42
Outer Block Savepoints
SQL> BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
END;
/
is automatically transformed to
SQL> BEGIN
SAVEPOINT _outer_block;
BEGIN
UPDATE Emps SET job = 'COOK';
UPDATE Emps SET sal = sal + 200;
END;
EXCEPTION WHEN OTHERS THEN
ROLLBACK TO _outer_block;
RAISE;
END;
/
© Ellis Cohen 2001-2008
43
Releasing Savepoints
RELEASE SAVEPOINT <savepointName>
Releases savepoint and associated transaction and
all savepoints within it
Savepoints are similar to maintaining previous
versions of a file
Releasing a savepoint is similar to deleting an old
version you won't want to ever restore
Not supported in Oracle
© Ellis Cohen 2001-2008
44
Savepoint, Release & Rollback
start
transaction
set
save
point
A
release
save
point
A
set
set save
save point
point D
C
release set
save
save
point point
D
E
set
save
point
B
release
save
point
E
rollback
to B
© Ellis Cohen 2001-2008
45
Autonomous
Transactions
© Ellis Cohen 2001-2008
46
Logging Successful Logins
Login( :userid, :pwd )
BEGIN
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :userid AND pwd = :pwd;
INSERT INTO LoginLog
VALUES ( :userid, :pwd, getDate );
END;
Note: The pwd really should be encrypted!
The code above adds a record to a login log
everytime someone successfully logs in.
If the id/password combination is not legal,
an exception will be raised, and the entry in
the log will not be added
But suppose we want to log attempted as
well as successful login attempts
© Ellis Cohen 2001-2008
47
Logging Attempted Logins
Login( :userid, :pwd )
With AUTOCOMMIT ON
BEGIN
INSERT INTO LoginLog
VALUES ( :userid, :pwd, getDate );
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :userid AND pwd = :pwd;
END;
Will this work?
If so, why?
With AUTOCOMMIT ON
If not, why not, and what
would work instead?
© Ellis Cohen 2001-2008
48
Use Auto-Commit
Login( :userid, :pwd )
With AUTOCOMMIT ON
INSERT INTO LoginLog
VALUES ( :userid, :pwd, getDate );
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :userid AND pwd = :pwd;
© Ellis Cohen 2001-2008
49
Explicit Commit
Login( :userid, :pwd )
With AUTOCOMMIT ON
BEGIN
INSERT INTO LoginLog
VALUES ( :userid, :pwd, getDate );
COMMIT;
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :userid AND pwd = :pwd;
END;
© Ellis Cohen 2001-2008
50
Catch & Discard Exceptions
Login( :empno, :pwd )
With AUTOCOMMIT ON
BEGIN
INSERT INTO LoginLog
VALUES ( :empno, :pwd, getDate );
BEGIN
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :empno AND pwd = :pwd;
EXCEPTION WHEN OTHERS THEN NULL;
END;
END;
Oops; No Error Message is
printed though!
© Ellis Cohen 2001-2008
51
Also Catch & Discard Exceptions
Login( :empno, :pwd )
With AUTOCOMMIT ON
BEGIN
INSERT INTO LoginLog
VALUES ( :empno, :pwd, getDate );
SELECT empno INTO :curuser FROM AuthUsers
WHERE empno = :empno AND pwd = :pwd;
EXCEPTION WHEN OTHERS THEN NULL;
END;
Oops; No Error Message is
printed though!
© Ellis Cohen 2001-2008
52
Procedure Logging
Suppose you have written a procedure that makes
important changes to the database, and you want to
log all uses of it.
PROCEDURE ImportantProcedure( p1 int, p2 int )
BEGIN
INSERT INTO ImportantLog
VALUES ( p1, p2, getDate );
UPDATE something important;
UPDATE something else important;
…
END;
This procedure is called in a number of places from
complex operations, and you want to make sure that
the ImportantLog entries persist even if the
operation is aborted after the ImportantProcedure is
called. Can this be done?
© Ellis Cohen 2001-2008
53
Autonomous Nested Transactions
When a transaction fails, all modifications made
during that transaction are undone.
That may not be what you want!
– Suppose you want to add an audit record every time
someone tries to make some specific kind of change.
– You want to add that audit record even if the
operation is ultimately rolled back.
Solution: Add the audit record inside an autonomous
nested transaction.
– Autonomous transactions can durably commit inside
of a parent transaction
– If the parent transaction is aborted after the nested
autonomous transaction commits, modifications
made inside the autonomous transaction will NOT be
undone.
© Ellis Cohen 2001-2008
54
Using Autonomous Transactions
PROCEDURE ImportantProcedure( p1 int, p2 int )
BEGIN
LogImportant( p1, p2 );
UPDATE something important;
This will be
UPDATE something else important;
rolled back if the
…
outer transaction
is aborted
END;
PROCEDURE LogImportant( p1 int, p2 int IS
PRAGMA AUTONOMOUS TRANSACTION;
BEGIN
INSERT INTO ImportantLog VALUES(
p1, p2, getDate );
COMMIT;
END;
Just commits the autonomous transaction!
It will never be rolled back,
even if the calling transaction is aborted
© Ellis Cohen 2001-2008
55
Completing Autonomous Transactions
Before returning from a
procedure which is associated
with an autonomous transaction,
you need to complete the
transaction via COMMIT (or
ROLLBACK),
otherwise the transaction will
never finish (and the log record
will never be written)!
© Ellis Cohen 2001-2008
56
Autonomous & Parent Transactions
An autonomous transaction
• is a transaction which runs in a procedure called
within an existing transaction
• the autonomous transaction is completely
UNRELATED to its parent transaction
• if the autonomous transaction commits or rolls
back, that has NO effect on its parent transaction
(the autonomous transaction cannot rollback to a
savepoint of the parent transaction)
• if the autonomous transaction code returns to the
parent WITHOUT completing, and the parent
commits or rolls back, that has no effect on the
autonomous transaction!
© Ellis Cohen 2001-2008
57
Isolation & Autonomous Transactions
Changes made by one transaction
– do not persist
– are not visible to any other transaction
until the transaction commits
An autonomous transaction and the
transaction invoking it are independent
 an autonomous transaction does not see
any changes made by the invoking
transaction
 an autonomous transaction can see the
state of data BEFORE it was changed by
its invoking transaction!
© Ellis Cohen 2001-2008
58
Functions Which Query
You can define a function that
performs a query on a table
If this function is called from an
operation which modifies the
same table, the function must
use an autonomous transaction
if you want it to perform
correctly.
© Ellis Cohen 2001-2008
59
Concurrency Problems
© Ellis Cohen 2001-2008
60
Attaining Isolation
Isolation requires that changes made
by a transaction
– do not persist
– are not visible to any other transaction
until the transaction commits
Isolation is achieved in two ways
– Cache-Based Mechanisms
– Non Cache-Based Mechanisms
© Ellis Cohen 2001-2008
61
Cache vs Non-Cache Mechanisms
Cache-Based Mechanisms
A separate cache is maintained by/for each client
All data modifications are made to the cache,
which is how isolation is achieved
When the transaction commits, all data updated
by the transaction is written back from the
client's cache to the server database state.
Non-Cache-Based Mechanisms
All data modifications are made directly to the
server database state
Isolation is achieved by preventing operations
from proceeding which cause problems (e.g. by
using Locking)
If do not prevent operations from interleaving in
arbitrary order, a number of classic problems
can arise!
© Ellis Cohen 2001-2008
62
Classic Concurrency Problems
• Lost Update Problem
One transaction’s update
overwrites another one’s
• Dirty Read Problem
A transaction reads uncommitted
data of another transaction
• Non-Repeatable Read Problem
A transaction reads data once,
and then reads a different value
after another transaction commits
a change to it
© Ellis Cohen 2001-2008
63
Serializability
Given
A group of transactions
proceed concurrently
The transactions interleave execution
Serializability requires
The result must be equivalent to some serial
execution schedule
(i.e. some execution schedule in which
entire transactions proceed one-at-a-time)
Without some mechanism to ensure
serializability / isolation,
there will be problems!
© Ellis Cohen 2001-2008
64
Lost Update Problem
Suppose transactions A & B simultaneously
deposit $1000 into a checking account
1) select balance into curbal from checking
where acctid = 30792;
2) curbal = curbal + 1000;
3) update checking
set balance = curbal
where acctid = 30792;
Each transaction
has its own local
copy of curbal
Serial Schedule A1, A2, A3, B1, B2, B3 ok
Schedule A1, B1, A2, B2, A3, B3 is not
What are balance & curbal values at each step if
the balance is initially $2300
© Ellis Cohen 2001-2008
65
Lost Update Values
A's curbal
balance
2300
B's curbal
A1
2300
2300
B1
2300
2300
2300
2300
2300
A2
3300
B2
3300
2300
3300
3300
3300
A3
3300
B3
3300
3300
3300
Arghh, this should be 4300, not 3300
© Ellis Cohen 2001-2008
66
Lost Update Pattern (WW)
Transaction
Transaction
A
B
1 Read data
1 Read data
2 Write data
B writes over
the same data
written by A,
without taking
into account
the changes
made by A
2 Write data
© Ellis Cohen 2001-2008
67
Dirty Read Problem
Transaction A
1) update checking
set balance = balance + 1000000
where acctid = 30792;
2) ROLLBACK;
Transaction B
FOR aRec in (select * in checking
where balance > 500000) LOOP
insert into IRS_Report( ssno, acctid, balance)
values ( aRec.ssno, aRec.acctid, aRec.balance );
ENDLOOP;
Serial Schedule A1, A2, B is ok
Schedule A1, B, A2 is not
© Ellis Cohen 2001-2008
68
Dirty Read Pattern (WR)
Transaction
Transaction
A
B
1 Write data
1 Read data
2
2
A Dirty Read
(also called an
Uncommitted
Read)
happens when
B reads
uncommitted
data
modified by A
© Ellis Cohen 2001-2008
69
Non Repeatable Read Problem
Suppose transactions A & B simultaneously
withdraw $1000 from a checking account
1) select balance into curbal from checking
where acctid = 30792;
2) if curbal < 1000 then raise error;
3) update checking
set balance = balance - 1000
where acctid = 30792;
4) emit $1000 from ATM;
Serial Schedule A1 A2 A3 A4 B1 B2 B3 B4 ok
Schedule A1 A2 B1 B2 B3 B4 A3 A4 is not
What are balance & curbal values at each step if
the balance is initially $1200
© Ellis Cohen 2001-2008
70
Non-Repeatable Read Values
A's curbal
balance
1200
B's curbal
A1/A2
1200
(no error)
1200
B1/B2
1200
1200
(no error)
A3/A4
200
B3/B4
-800
Arghh, when B initially read balance at B1,
it was 1200. But when B read balance
again at B3 (without changing it), it was
200. That's weird!
© Ellis Cohen 2001-2008
71
Non-Repeatable Read Pattern (RW)
Transaction
Transaction
A
B
1 Read data
1 Write data
2
2
Re-Read data
COMMIT
A NonRepeatable
read occurs
when B can
modify and
commit data
read by A
(which has not
yet completed),
and when A
then re-reads
the same data
© Ellis Cohen 2001-2008
72
Locking
© Ellis Cohen 2001-2008
73
Locking & Waiting
Databases can implement
serializability using locks
– When A first accesses table T,
T is locked for use by A
• More accurately, the DB locks T for A
– If B then tries to access T while A is
still executing the transaction
• B will try to lock T, but won't succeed
because A already has it locked
• B waits until T is unlocked
– When A completes, it unlocks T
• B now proceeds to lock T and continue with
its transaction
© Ellis Cohen 2001-2008
74
Database Locking
If a transaction needs to access a data item in the
database
– It must request a suitable lock for it first (unless it
already has been granted the lock)
If NO other transaction has a conflicting lock
– The DB scheduler may grant the lock to the
transaction.
– The lock is then acquired or held by the transaction
If some other transaction holds a conflicting lock
– The database scheduler will NOT grant the lock to
the requesting transaction. Generally either
• the requesting transaction waits, or
• the requesting/conflicting transaction is aborted
When a lock is released by a transaction
– the DB scheduler checks to see whether it can now
grant a lock to a waiting transaction which may
then be able to continue.
© Ellis Cohen 2001-2008
75
Lock Acquisition & Release
In commercial databases where concurrency
control is lock-based,
locks are acquired automatically.
When a transaction needs to access a resource,
the DB scheduler automatically tries to acquire
a lock on that resource for the transaction
(unless the transaction is already holding the
required lock on the resource).
Most databases also have a way to allow a
transaction to explicitly request locks before
they are needed (e.g. LOCK TABLE)
As a transaction continues, locks can continue to
be acquired, but are not released. Locks are
released all at once when the transaction
completes.
This is called 2PL (two phase locking).
© Ellis Cohen 2001-2008
76
Can’t Release Before Commit
X=30
1
Transaction
Transaction
A
B
update XT
set x = x + 100
RELEASE LOCK
2
X=130
1
update XT
set x = x * 2
2
COMMIT
X=260
3
Suppose A releases
locks (A2) immediately
after doing its updates
(A1)
B acquires that lock and
does its update (B1),
and commits (B2)
Then A is aborted (A3)
Is A1 A2 B1 B2 A3
serializable?
Is there anything the
database scheduler can
do to prevent or correct
this problem?
ABORT
© Ellis Cohen 2001-2008
77
Avoiding Unrecoverability &
Cascading Aborts
If locks can be released early
• To avoid unrecoverable and
unserializable schedules:
A transaction must wait to commit if it
– has read data written by a still active
transaction
– that released its lock on that data
• To avoid cascading aborts
A transaction must wait to
– read data written by a still active
transaction
– that released its lock on that data
© Ellis Cohen 2001-2008
78
Shared vs Exclusive Locks
When 2 transactions read the same
table, there is no problems
Problems only arise when one or
both write the table
• Both write => Lost update problem
• One reads, One writes =>
Dirty/Non-Repeatable Read Problem
Provide Different Locking Modes
• S (shared) locks (for reading)
• X (exclusive) locks (for writing)
© Ellis Cohen 2001-2008
79
Grant Matrix
If one
transaction
already
has this
lock on a
resource
Will the system grant the lock
to another transaction?
S
X
S
X
YES
NO
NO
NO
Using S & X table locks,
with locks released on commit
ensures that all schedules allowed
are serializable
© Ellis Cohen 2001-2008
80
Lock Granularity
Granularity - size of data items to lock
e.g., table, page, row, cell
Coarse (e.g. table) granularity implies
very few locks, so little locking overhead
must lock large chunks of data =>
increased chance of conflict =>
less concurrency
Medium (e.g. page) granularity implies
medium # of locks, so moderate locking overhead
minimized because locking integrated with
cacheing
locking conflict occurs only when two transactions
try to access the exact same page concurrently
Fine (e.g. row) granularity implies
many locks, so high locking overhead
locking conflict occurs only when two transactions
try to access the exact same tuples concurrently
© Ellis Cohen 2001-2008
81
Explicit Locking
Most databases implicitly acquire locks as
needed
– depending upon isolation level
– depending upon other concurrency controls
Many databases also allow you to request
(groups of) locks explicitly
– Specify table(s)
– Specify locking mode
– Specify whether to wait if necessary
Oracle: LOCK TABLE Emps, Depts
IN EXCLUSIVE MODE NOWAIT
Explicit locking
– Can ensure serializability (if necessary)
– Can prevent deadlock
© Ellis Cohen 2001-2008
82
Phantom Reads
© Ellis Cohen 2001-2008
83
Phantom Reads
Phantom reads
are a special case of the non-repeatable
read problem
Phantoms result
when an INSERT or an UPDATE
adds a row to a group which is already
locked!
Row-level locking alone
does not prevent phantom reads
and can result in non-serializable
schedules
© Ellis Cohen 2001-2008
84
Phantom Read Example
A:
(1) SELECT avg(sal) FROM Emps
B:
WHERE deptno = 10
(1) UPDATE Emps SET deptno = 10
WHERE empno = 3142
(this employee was previously in dept #30)
(2) COMMIT
(2) SELECT avg(sal) FROM Emps
WHERE deptno = 10
Suppose the DB locks rows
B1 can still proceed, because it doesn’t
affect any rows locked by A1!
But A2 and A1 produce different results,
although A didn’t change any data
© Ellis Cohen 2001-2008
85
Phantom Reads & Index Locks
When Databases lock at the row level
an index must be used to identify the group of
rows which need to be locked
Phantom Reads
are a special case of the non-repeatable read
problem
they occur when an INSERT or an UPDATE
adds a row to a group of rows which is already
locked
Databases prevent phantoms by associating
locks with indices
Obtain S locks on all indices used by a SQL
command
For an UPDATE: Acquire X locks on all indices on
attributes set by the UPDATE
For an INSERT: Acquire X locks on all indices
© Ellis Cohen 2001-2008
86
Deadlock
© Ellis Cohen 2001-2008
87
Waiting can cause Deadlock
Transaction A
Transaction B
1) update checking
set amt = amt - 1000
where id = 30792;
2) update savings
set amt = amt + 1000
where id = 30792;
1) update savings
set amt = amt - 1000
where id = 30792;
2) update checking
set amt = amt + 1000
where id = 30792;
Consider schedule A1, B1, A2, B2
© Ellis Cohen 2001-2008
88
Resource Allocation Graph
Means that A is waiting
to use savings
A
savings
checking
B
Means that B has
acquired a lock on
savings
Deadlock occurs when there
is a deadly embrace:
a cycle in the Resource
Allocation Graph
© Ellis Cohen 2001-2008
89
Deadlock Detection Approaches
• On each lock request, check if it
causes a deadly embrace
• Regularly, check if there is a
deadly embrace
• If a transaction has waited too
long, just assume it has
deadlocked (especially useful
for distributed transactions).
Can lead to cyclic restart
(also called livelock)
© Ellis Cohen 2001-2008
90
Deadlock Recovery
Once a deadlock is detected, (at least)
one of the deadlocked transactions
must be aborted.
Auto Restart
– When database aborts a transaction, it
automatically restarts it, possibly after a
short/randomized time.
Abort Causes Exception
– When a database aborts a transaction, it raises an
exception, which the process can handle, and
• explicity restart the transaction, or
• do something else
© Ellis Cohen 2001-2008
91
Read-Consistent
Concurrency
© Ellis Cohen 2001-2008
92
Concurrency Approaches
Optimistic Concurrency Approaches
Allows transaction to proceed to
completion.
When it attempts to commit, abort it if it
does not serialize with transactions
which already completed.
Pessimistic Concurrency Approaches
Each operation in a transaction is only
allowed to proceed if it serializes with
overlapping transactions.
Otherwise it must wait (or possibly
cause its own or another transaction to
abort)
Lock-based concurrency is pessimistic
© Ellis Cohen 2001-2007
93
Concurrency Control Mechanisms
• Locking [Pessimistic]
– Transactions lock data before they use it
• Optimistic [Optimistic]
– Uses cache & pretends entire transaction
occurs when it commits
• Timestamp [Pessimistic]
– Pretends entire transaction occurs when
it starts
• Read-Consistent [Combination]
– Oracle's Concurrency Model
– Uses cache which holds virtual snapshot
of the DB state when the transaction
starts. Not fully serializable.
© Ellis Cohen 2001-2007
94
Read Consistent Concurrency
Locking data on reads is expensive, so some
commercial databases do not automatically
lock data before reading it.
Instead they ensure Read Consistency
(Oracle calls this Serializable, but it's not!)
data read during a transaction
has the value it had at the
start of the transaction
(unless updated by the transaction itself).
Often this is OK
In other cases, it can cause surprising (and
incorrect behavior) unless the database
developer does explicit locking.
© Ellis Cohen 2001-2008
95
Consistency & Concurrency Problems
• Transactions see a "consistent"
view of the database (i.e. as it
was when the transaction started)
• Avoid Dirty Reads,
Non-Repeatable Reads
& Phantom Reads
• Still need to prevent lost updates
Use X Locks, but can't just wait.
If other transaction aborts, can
continue, but if other transaction
commits, must ABORT!
© Ellis Cohen 2001-2008
96
X Locks Can't Just Wait!
Transaction
A
update XT
set x = x + 100
COMMIT
Ax
130
130
x
30
Bx
Transaction
B
update XT
set x = x + 100
30
Blocks until A
commits.
Still sees 30
instead of 130!
130
130
130
130
COMMIT
Adding X Locks
does not prevent Lost Updates if locks just block
Lost Updates are only prevented
If lock conflicts only allow one of the conflicting
transactions to commit
© Ellis Cohen 2001-2008
97
Constraint Violation Problem
Suppose that
– C is a constraint (or assertion) about the
database
– Every transaction T, when run in isolation, has
the property that
C is true before T  C is true after T
If a DB uses a serializable concurrency
control
If C is true initially,
Then (looking just at the state of the committed
data), C will always remain true
This may be violated with Read-Consistency
That is, it violates the ACID Consistency Property
© Ellis Cohen 2001-2008
98
The General Problem
An operation
Pool of Information
1. queries a pool of
information
2. adds/updates
information
(in a way that
would change the
results of the query)
If locking were used
two such operations couldn’t interleave
(it would cause a deadlock)
With read consistency
they can interleave if the changes are independent,
and the second one may make a change that
doesn't take into account the first change
© Ellis Cohen 2001-2008
99
Constraint Violation Example
dilipOwns( id )
chuOwns( id )
Constraint: an id may appear in
dilipOwns or chuOwns, but not both
Suppose T1 tries assigning an id to dilipOwns &
concurrently T2 tries assigning same id to chuOwns
BEGIN
With 2PL,
SELECT count(*) INTO dilipknt FROM dilipOwns
both would
WHERE (id = &id);
acquire
read locks on
SELECT count(*) INTO chuknt FROM chuOwns
both tables
WHERE (id = &id);
IF (dilipknt + chuknt = 0) THEN
IF (&who = 'dilip') THEN
INSERT INTO dilipOwns VALUES( &id );
If both T1 and T2
ELSIF (&who = 'chu') THEN
INSERT INTO chuOwns VALUES( &id ); get to this point at
the same time,
END IF;
then with 2PL, they
With Read Consistent
END IF;
will deadlock
Concurrency Control,
END;
both continue & the
constraint is violated
© Ellis Cohen 2001-2008
100
Use Explicit Locking
dilipOwns( id )
chuOwns( id )
Constraint: an id may appear in
dilipOwns or chuOwns, but not both
Suppose T1 tries assigning an id to dilipOwns &
concurrently T2 tries assigning same id to chuOwns
BEGIN
LOCK TABLE dilipOwns, chuOwns IN SHARE MODE;
SELECT count(*) INTO dilipknt FROM dilipOwns
WHERE (id = &id);
SELECT count(*) INTO chuknt FROM chuOwns
WHERE (id = &id);
IF (dilipknt + chuknt = 0) THEN
IF (&who = 'dilip') THEN
INSERT INTO dilipOwns VALUES( &id );
ELSIF (&who = 'chu') THEN
INSERT INTO chuOwns VALUES( &id );
END IF;
END IF;
END;
© Ellis Cohen 2001-2008
101
A Real Constraint Violation Problem
Constraint: There are no two reservations for
the same room with overlapping times
Consider
The code below
reserves &roomnum
rooms( roomnum, location, … )
from &stime to &ftime,
reservations( roomnum,
assuming there is no
stime, ftime, reserver, purpose ) conflicting reservation
Code
SELECT count(*) INTO overlaps FROM reservations
WHERE (roomnum = &roomnum)
AND (stime BETWEEN &stime AND &ftime
OR ftime BETWEEN &stime AND &ftime);
IF (overlaps = 0) THEN
INSERT INTO reservations VALUES (
&roomnum, &stime, &ftime, &reserver, &why );
END IF;
Suppose two reservations are made concurrently
COMMIT;
for the same room, but for overlapping times. No
problem with 2PL. With Read Consistency, both
reservations could be inserted.
© Ellis Cohen 2001-2008
102
Use FOR UPDATE
Consider
rooms( roomnum, location, … )
reservations(
roomnum, stime, ftime, reserver, purpose )
Code
SELECT * FROM rooms
WHERE (roomnum = &roomnum) FOR UPDATE;
SELECT count(*) INTO overlaps FROM reservations
WHERE (roomnum = &roomnum)
AND (stime BETWEEN &stime AND &ftime
OR ftime BETWEEN &stime AND &ftime);
IF (overlaps = 0) THEN
INSERT INTO reservations VALUES (
&roomnum, &stime, &ftime, &reserver, &why );
END IF;
COMMIT;
Using FOR UPDATE forces
acquisition of X locks for the
selected rows
© Ellis Cohen 2001-2008
103
Read-Committed
Concurrency
© Ellis Cohen 2001-2008
104
Isolation Levels
Theoretical aim is for DB systems to
maintain serializability automatically
• Maintaining serializability is expensive
and not always necessary
• DB systems allow users to specify weaker
levels of isolation to be maintained
automatically
Weaker levels of isolation will allow
problems (e.g. Non Repeatable Read) to
show up.
• OK as long as they're "not a problem"
• Transactions can selectively serialize
explicitly (via locking) when necessary
© Ellis Cohen 2001-2008
105
Setting Isolation Level
 In Oracle 
SET TRANSACTION
ISOLATION LEVEL SERIALIZABLE
Prevents dirty reads, non-repeatable reads and
lost updates
However, not truly serializable.
Permits constraint violation problems
Developers must sometimes do explicit locking!
SET TRANSACTION
ISOLATION LEVEL READ COMMITTED
Allows a transaction to see other transaction's
committed writes.
Permits non-repeatable reads;
Prevents dirty reads & lost updates
Often not a problem; problems can be
eliminated by explicit locking
THIS IS ORACLE's DEFAULT, because it has very
low overhead.
© Ellis Cohen 2001-2008
106
Read-Committed Isolation
Weakened form of Read-Consistency
A transaction takes a new virtual snapshot at
the beginning of every query
– contains any data written by own transaction
– plus all data committed by other transactions
If this transaction waits for a write lock
– then if the transaction holding the lock aborts,
continue the transaction
– else if the transaction holding the lock commits,
re-execute the query
[don't abort the transaction!]
Allows Non-Repeatable Reads (& Phantoms)
© Ellis Cohen 2001-2008
107
Read Committed Problem
Suppose transactions A & B simultaneously
withdraw $1000 from a checking account
1) select balance into curbal from checking
where acctid = 30792;
2) if curbal < 1000 then raise error
3) update checking
set balance = balance - 1000
where acctid = 30792;
4) emit $1000 from ATM;
Schedule A1 A2 B1 B2 B3 B4 A3 A4 doesn’t
work using Read Committed Isolation.
How could the code be changed to work even
with Read Committed Isolation?
© Ellis Cohen 2001-2008
108
Read Committed and FOR UPDATE
Suppose transactions A & B simultaneously
withdraw $1000 from a checking account
1) select balance into curbal from checking
where acctid = 30792 FOR UPDATE;
2) if curbal < 1000 then raise error
3) update checking
set balance = balance - 1000
where acctid = 30792;
4) emit $1000 from ATM;
© Ellis Cohen 2001-2008
109