微信客服：xiaoxionga100
微信客服：ITCS521
Python代写-COMP9120
时间：2021-11-03
COMP9120
Week 8: Transaction Management
Semester 2, 2021
Dr Mohammad Polash
School of Computer Science
Contents developed by Dr Lijun Chang
Acknowledgement of Country
I would like to acknowledge the Traditional Owners of Australia and recognise their
continuing connection to land, water and culture. I am currently on the land of the
Burramattagal people and pay my respects to their Elders, past, present and
emerging.
I further acknowledge the Traditional Owners of the country on which you are on
and pay respects to their Elders, past, present and future.
Copyright warning
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to
you by or on behalf of the University of Sydney
pursuant to Part VB of the Copyright Act 1968 (the
Act).
The material in this communication may be subject
to copyright under the Act. Any further copying or
communication of this material by you may be the
subject of copyright protection under
the Act.
Do not remove this notice.
4
Outline
› What is a transaction?
› Four properties of transaction: Atomicity, Consistency, Isolation, Durability
- What is the meaning of this property? Why we need this property? How is this property
ensured to hold?
5
Transfer $100
from Account A
to Account B
Motivation
Account A
Withdraw $100
Account B
Deposit $100
System recovers but database state no
longer reflects amount of physical money
available (short $100)
Account balance successfully updated
for Account A
Transfer Operation
*System fails*
Should group withdraw & deposit operations
together – so that they either both succeed, or
none happen at all
6
BEGIN;
Withdraw $100 from Account A;
Deposit $100 into Account B;
COMMIT;
What is a transaction?
› When an event occurs in the real world that changes the state of the enterprise,
a program is executed to change the database state in a corresponding way
- e.g., Bank balance must be updated on 2 accounts when a transfer is made
› Such an execution of a program is often modelled as a transaction:
a collection of one or more operations on one or more databases, which
reflects a discrete unit of work
- Transactions should conform to certain requirements (ACID properties):
e.g: In the real world, a transaction either completes or does not happen at all
7
Required properties of a transaction
› Atomicity: A transaction is either
performed entirely or not performed at all.
› Consistency: A correct execution of a
transaction must take a database from one
consistent state to another.
› Isolation: Effect of multiple transactions is
the same as these transactions running one
after another.
› Durability: Once a transaction changes the
database and the changes are committed,
these changes must never be lost because
of subsequent failure.
8
Outline
› Consistency
- What, why, and how?
› Atomicity
› Durability
› Isolation
9
Transactions should be Consistent
› A transaction is consistent if, assuming the database is in a consistent state
initially (satisfying all constraints), when the transaction completes:
1. All database constraints are satisfied
2. The new database state satisfies specifications of the transaction
› Each transaction should preserve the consistency of the database.
› Note that this is mainly the responsibility of the application developer!
- Database cannot 'fix' the correctness of a badly coded transaction
- An example bad transaction for bank transfer
- Withdraw $100 from account A, but only deposit $90 into account B.
10
(but constraints might be violated in intermediate states)
Deferring Integrity Constraints
CREATE TABLE UnitOfStudy (
uos_code VARCHAR(8),
title VARCHAR(20),
lecturer_id INTEGER,
credit_points INTEGER,
CONSTRAINT UnitOfStudy_PK PRIMARY KEY (uos_code),
CONSTRAINT UnitOfStudy_FK FOREIGN KEY (lecturer_id)
REFERENCES Lecturer DEFERABBLE INITIALLY IMMEDIATE
);
BEGIN;
INSERT INTO UnitOfStudy VALUES(‘INFO1000’,’Graphics’, 3, 6);
INSERT INTO Lecturer VALUES(3,'Steve’, CSE);
COMMIT;
11
Uos_code title Lecturer_id Credit_points
COMP9120 DBMS 1 6
COMP9007 Algorithm 2 6
Lecturer_id name department
1 Adam CSE
2 Lily IT
SET CONSTRAINTS UnitOfStudy_FK DEFERRED;
Outline
› Consistency
› Atomicity
- What, why, and how?
› Durability
› Isolation
12
Transactions should be Atomic
› A DBMS user can think of a transaction as always executing all its operations in
one step, or not executing any operations at all.
- Every transaction should act as an atomic operation.
› A real-world event either happens or does not happen (e.g., for bank transfer,
either both withdrawal + deposit occur, or neither occurs).
- Partially completed transaction can lead to an inconsistent database state.
› DBMS logs all actions so that it can undo the actions of aborted transactions.
- In the case of a failure, all actions of not-committed transactions are undone.
13
Commit and Abort
› If the transaction successfully completes, it is said to commit
- The DBMS is responsible for ensuring that all changes to the database have been saved
› If the transaction does not successfully complete, it is said to abort
- The DBMS is responsible for undoing, or rolling back, all changes in the database that
the transaction has made
- Possible reasons for abort:
- System crash
- Transaction aborted by system, e.g.,
- Transaction or connection hits time-out,
- Violation of constraint, etc
- Transaction requests to roll back
14
Writing a transaction in SQL
› 3 new SQL commands to know:
- BEGIN
- COMMIT requests to commit current transaction
- ROLLBACK causes current transaction to abort - always satisfied.
› Can also SET AUTOCOMMIT OFF or SET AUTOCOMMIT ON
- With auto-commit on, each statement is its own transaction and 'auto-commits'
- With auto-commit off, statements form part of a larger transaction delimited by the
keywords discussed above.
- Different clients have different defaults for auto-commit.
15
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=1234 WHERE uosCode=‘COMP5138’;
COMMIT;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
16
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=1234 WHERE uosCode=‘COMP5138’;
ROLLBACK;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
17
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=4567 WHERE uosCode=‘COMP5138’;
COMMIT;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
18
Writing a transaction with JDBC
› APIs, like JDBC, often provide explicit functions for controlling the transaction
semantics
› By default, transactions are in AutoCommit mode
- Each SQL statement is considered its own transaction.
- No explicit commit, no transactions with more than one statement…
› 3 new methods to know (all for JDBC connection class):
- setAutoCommit(false)
- commit()
- rollback()
19
JDBC Transaction example
public boolean bookFlight ( String flight_num, Date flight_date, Integer seat_no) {
boolean booked = false;
PreparedStatement stmt;
Connection conn;
try {
conn = openConnection();
conn.setAutoCommit(false);
stmt = conn.prepareStatement(“UPDATE Flight SET occupied=1” +
“WHERE occupied = 0 AND flightNum=? AND flightDate=? AND seat=?”);
stmt.setString(1, flight_num); stmt.setDate(2, flight_date);
stmt.setInt(3, seat_no);
int updatedRows = stmt.executeUpdate();
if(updatedRows == 1){
conn.commit();
booked=true;
}
else
conn.rollback();
}
catch (SQLException sqle) {
/* error handling */ ...
} finally {conn.close(); }
return booked;
}
Note: should explicitly call conn.rollback()
before calling conn.close(), if you want to
rollback
20
Transactions with Python DB-API
› DB-API provides transaction control via connection object methods
› According to DB-API spec, db connections initially start with auto-commit mode
switched off
- Can use autocommit attribute of connection to set auto-commit mode
› Transaction control
- conn.commit() successfully finishes (commits) current transaction
- conn.rollback() aborts current transaction
21
DB-API: Transaction Example
import psycopg2
try:
# connect to the database
conn = psycopg2.connect(database='foo', user='dbuser', password='pwd‘)
conn.autocommit = True
# move some money from one person to the other
curs = conn.cursor()
curs.execute ("UPDATE money SET amt = amt - 100 WHERE name = ‘James Bond'")
curs.execute ("UPDATE money SET amt = amt + 100 WHERE name = ‘Bill Gates'")
except:
print("unable to connect to db or to execute query")
conn.rollback ()
finally:
#cleanup
curs.close()
conn.commit()
22
Outline
› Consistency
› Atomicity
› Durability
- What, why, and how?
› Isolation
23
Transactions should be Durable
› Once a transaction is committed, its effects should persist in a database, and
these effects should be permanent even if the system crashes.
- A database should always be able to be recovered to the last consistent state
› Implementing Durability:
- Database is stored redundantly on mass storage devices to protect against media failure
(e.g., RAID)
- Write-Ahead Log
24
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
25
Transactions should be Isolated
› Transactions should be isolated from the effects of other concurrent
transactions.
- Note that a DBMS usually handles many transactions concurrently.
› Let’s consider two transactions that are run concurrently
- Transaction T1 is transferring $100 from account A to account B.
- T2 credits both accounts with a 5% interest payment.
26
T1: BEGIN A=A-100, B=B+100 COMMIT
T2: BEGIN A=1.05*A, B=1.05*B COMMIT
We assume that all transactions commit,
there is no aborted transaction!
Example Executions of the Two Transactions
› Serial execution: we can look at the transactions in a timeline view
› The transactions could occur in the other order… DBMS allows!
› DBMS can also interleave the transactions.
T1 transfers $100 from
account A to account B
T2 credits both accounts with a
5% interest payment
Time
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1 transfers $100 from
account A to account B
T2 credits both accounts with a
5% interest payment
Time
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
27
Isolation through Serializability
› Serial Schedule – A schedule in which all transactions are executed from start to
finish, without interleaving, one after the other.
- In serial execution, each transaction is isolated from all others
› However, interleaving (concurrent execution) improves performance
- Some transactions may be slow and long-running – don’t want to block other
transactions!
- Disk access may be slow – let some transactions use CPUs while others accessing disk!
› Serializability:
A schedule is serializable if it is equivalent to some serial schedule
- Two schedules S1 and S2 are equivalent if, for any database state, the effect on the
database of executing S1 is identical to the effect of executing S2
28
Example Serializable Schedule
› Consider the following interleaved execution
› It is serializable, as the result of the above interleaved execution is the same as
that of the following serial execution of T1, T2
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
29
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = (1.05*Ai)-100, BF = (1.05*Bi)+100)
Example Non-Serializable Schedule
› Consider the following interleaved execution
› It is not serializable, as the result of the above interleaved execution is not the
same as that of either of the following two serial executions.
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = (Ai-100)*1.05, BF = Bi*1.05+100
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
AF = (1.05*Ai) -100, BF = (1.05*Bi)+100
30
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
31
DBMS’s View of a Schedule
› Serializability is hard to check
- It needs to check the effect of the schedule on all consistent databases
› Let’s see how to analyze schedules without executing them.
› To do this, we need to see DBMS’s view of a schedule
- R: reading the content of an object from the database
- R1: reading by trasaction T1 (also written as R1)
- R2: reading by trasaction T2 (also written as R2)
- W: writing the content of an object into the database
- W1, W2 are similarly defined
32
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: R1(A),W1(A), R1(B),W1(B)
T2: R2(A),W2(A),R2(B),W2(B)
Isolation through Conflict Serializability
› Two operations ai and aj of transactions Ti and Tj conflict if (1) they access
the same data X, (2) they come from different transactions, and (3) at least
one of them wrote X. (ai,aj) is called a conflict pair.
1. ai=R(X),aj=R(X). don’t conflict.
2. ai=R(X),aj=W(X). they conflict.
3. ai=W(X),aj=R(X). they conflict
4. ai=W(X),aj=W(X). they conflict
› Note: With SQL - SELECT corresponds to read,
INSERT, DELETE, UPDATE correspond to write
› A schedule is conflict serializable if it is conflict equivalent to some serial
schedule
- Two schedules are conflict equivalent if:
1. They involve the same set of operations of the same transactions
2. They order every pair of conflicting operations the same way
33
› Consider some schedule of a set of transactions T1,T2,...,Tn
› Precedence graph:
- direct graph where the vertices are the transactions.
- edge from Ti to Tj if the two transactions conflict, and Ti accessed the data item on
which the conflict arose earlier.
› Central Theorem:
- A schedule is conflict serializable if and only if its precedence graph is acyclic.
› Example:
- T1 and T2 have 3 conflict pairs
Testing for Conflict Serializability
34
T1: R1(c), W1(c)
T2: R2(c),W2(c)
T1 T2
Which of these schedules are conflict serializable?
› R1(x),R2(y),R1(z),R3(z),R2(x),R1(y)
- all reads – no conflicts – hence conflict serializable
› R1(x),W2(y),R1(z),R3(z),W2(x),R1(y)
- non-conflict serializable:
- putting T1 before T2 will make conflict (W2(y),R1(y)) violate conflict-serializability rule.
- putting T2 before T1 will make conflict (R1(x),W2(x)) violate conflict-serializability rule
› R1(x),W2(y),R1(z),R3(x),W2(x),R2(y)
- conflict serializable: conflicts on x by T1/T3 and T2 can conform to conflict serializability rule
35
Serializability vs Conflict Serializability
› If a schedule is conflict serializable, then it must also be serializable
› But not vice versa
- This schedule is serializable, but not conflict serializable
- It is equivalent to serial schedule T1, T2, T3 or T2, T1, T3
- It is not conflict equivalent to any serial schedule
36
T1: R1(A) W1(A)
T2: W2(A)
T3: W3(A)
Possible Anomalies for Non-conflict Serializable
Schedules
› Reading Uncommitted Data (“dirty reads”)
› Unrepeatable Reads: may not read same value twice
› Overwriting Uncommitted Data (“lost updates“):
T1: R1(A),W1(A), R1(B),W1(B)
T2: R2(A),W2(A),R2(B),W2(B)
T1: R(A), R(A)
T2: R(A),W(A)
T1: R(A), W(A)
T2: R(A),W(A)
38
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
39
Lock-based Concurrency Control
› Strict Two-phase Locking (S2PL) Protocol:
- Locks are associated with each data item
- A transaction must obtain a S (shared) lock on object before reading, and an X
(exclusive) lock on item before writing.
- exclusive (X) lock: Data item can be accessed by just one transaction
- shared (S) lock: Data item can only be read (but shared by transactions)
- All locks held by a transaction are released when the transaction completes.
- If a transaction holds an X lock on an item, no other transaction can get a lock (S
or X) on that item.
- Instead, such transactions must wait until the conflicting lock is released by
the previous transaction(s)
40
Locking Example 1
› Consider:
› Complete a schedule starting as:
› T2 must wait until T1 releases its lock on A (and B) – forces T2 to start only after
T1 commits or aborts (rolls back)
T1: R(A),W(A),R(B),W(B)
T2: R(A),W(A),R(B),W(B)
T1: S(A),R(A),X(A),W(A)
T2:
,S(B),R(B),X(B),W(B)
(A locked, must wait)
41
Lock Compatibility Matrix
Held by T1
T2 Requested
Shared Exclusive
Shared OK T2 wait on T1
Exclusive T2 wait on T1 T2 wait on T1
42
Locking Example 2
› Consider:
› Schedule with locking might start as:
› What happens next?
- T1 waiting on T2 to release lock on B
- T2 waiting on T1 to release lock on A
- DEADLOCK
T1: R(A),W(A),R(B),W(B)
T2: R(B),W(B),R(A),W(A)
T1: S(A),R(A),X(A),W(A)
T2: S(B),R(B),X(B),W(B)
43
Deadlocks
› Deadlock: Cycle of transactions waiting for locks to be released by each other.
Two ways of dealing with deadlocks:
› Deadlock prevention
- E.g. based on priorities
› Deadlock detection
- A transaction in the cycle must be aborted by DBMS (since transactions
will wait forever)
- DBMS uses deadlock detection algorithms or timeout to deal with it
44
Exercise
› 2 transactions, T1 & T2
› Assume no concurrency control, each row is an object
› Statements interleaved as below.
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=year+1 WHERE lecturerId = 4711 AND uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
45
Exercise
› 2 transactions, T1 & T2
› Assume no concurrency control, each row is an object
› Statements interleaved as below.
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=year+1 WHERE lecturerId = 4711 AND
uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
46
A
B
R1(A),R1(B)
R2(A)
R1(A),W1(A)
W2(A)
Time
Exercise
› 2 transactions, T1 & T2
› Assume strict 2PL with row-level locking is used.
› How would the following schedule be affected?
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=yr+1 WHERE lecturerId = 4711 AND
uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
47
A
B
S1(A),S1(B)
S2(A)
Request X1(A), wait
Request X2(A), wait
We have a deadlock!
› Let‘s return to our two transactions:
- Transaction T1 is transferring $100 from account A to account B.
- T2 credits both accounts with a 5% interest payment.
› Atomicity requirement
- all updates of a transaction are reflected in the db or none.
› Consistency requirement
- T1 does not change the total sum of A and B, and after T2, this total sum is 5% higher.
› Isolation requirement
- There is no guarantee that T1 will execute before T2, if both are submitted together. However,
the actions of T1 should not partially affect those of T2, or vice-versa.
› Durability requirement
- once a transaction has completed, the updates to the database by this transaction must persist
despite failures
T1: BEGIN A=A-100, B=B+100 COMMIT
T2: BEGIN A=1.05*A, B=1.05*B COMMIT
Summary
48
Key Skills
You should be able to:
› Explain how ACID properties define correct transaction behaviour
› Identify update anomalies when ACID properties aren’t enforced
› Explain whether an execution schedule is conflict serializable
› Use deferred integrity constraints in a transaction
› Implement appropriate transaction handling in client code (Java/JDBC)
› Explain how locking provides isolated transactions
49
References
› [RG] Ramakrishnan /Gehrke – Chapter 16, details in Ch. 17 & 18
› Kifer/Bernstein/Lewis – Chapter 18
› Ullman/Widom – Chapter 6.6
› Transactions & JDBC – [JDBC] JDBC documentation
- Docs for java.sql.connection (with commit, rollback and setAutoCommit)
http://docs.oracle.com/javase/6/docs/api/java/sql/Connection.html
- See also tutorial http://docs.oracle.com/javase/tutorial/jdbc/basics/transactions.html
› Transactions & DB-API:
- Python DB-API: https://www.python.org/dev/peps/pep-0249/
50
Next Week
› Schema Normalization
- Functional Dependencies
- Schema Normal Forms
- Schema Normalization
› Readings:
- Ramakrishnan/Gehrke (Cow book), Chapter 19
- Kifer/Bernstein/Lewis book, Chapter 6
- Ullman/Widom, Chapter 3 (up-to 3.5)
51
学霸联盟
Week 8: Transaction Management
Semester 2, 2021
Dr Mohammad Polash
School of Computer Science
Contents developed by Dr Lijun Chang
Acknowledgement of Country
I would like to acknowledge the Traditional Owners of Australia and recognise their
continuing connection to land, water and culture. I am currently on the land of the
Burramattagal people and pay my respects to their Elders, past, present and
emerging.
I further acknowledge the Traditional Owners of the country on which you are on
and pay respects to their Elders, past, present and future.
Copyright warning
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to
you by or on behalf of the University of Sydney
pursuant to Part VB of the Copyright Act 1968 (the
Act).
The material in this communication may be subject
to copyright under the Act. Any further copying or
communication of this material by you may be the
subject of copyright protection under
the Act.
Do not remove this notice.
4
Outline
› What is a transaction?
› Four properties of transaction: Atomicity, Consistency, Isolation, Durability
- What is the meaning of this property? Why we need this property? How is this property
ensured to hold?
5
Transfer $100
from Account A
to Account B
Motivation
Account A
Withdraw $100
Account B
Deposit $100
System recovers but database state no
longer reflects amount of physical money
available (short $100)
Account balance successfully updated
for Account A
Transfer Operation
*System fails*
Should group withdraw & deposit operations
together – so that they either both succeed, or
none happen at all
6
BEGIN;
Withdraw $100 from Account A;
Deposit $100 into Account B;
COMMIT;
What is a transaction?
› When an event occurs in the real world that changes the state of the enterprise,
a program is executed to change the database state in a corresponding way
- e.g., Bank balance must be updated on 2 accounts when a transfer is made
› Such an execution of a program is often modelled as a transaction:
a collection of one or more operations on one or more databases, which
reflects a discrete unit of work
- Transactions should conform to certain requirements (ACID properties):
e.g: In the real world, a transaction either completes or does not happen at all
7
Required properties of a transaction
› Atomicity: A transaction is either
performed entirely or not performed at all.
› Consistency: A correct execution of a
transaction must take a database from one
consistent state to another.
› Isolation: Effect of multiple transactions is
the same as these transactions running one
after another.
› Durability: Once a transaction changes the
database and the changes are committed,
these changes must never be lost because
of subsequent failure.
8
Outline
› Consistency
- What, why, and how?
› Atomicity
› Durability
› Isolation
9
Transactions should be Consistent
› A transaction is consistent if, assuming the database is in a consistent state
initially (satisfying all constraints), when the transaction completes:
1. All database constraints are satisfied
2. The new database state satisfies specifications of the transaction
› Each transaction should preserve the consistency of the database.
› Note that this is mainly the responsibility of the application developer!
- Database cannot 'fix' the correctness of a badly coded transaction
- An example bad transaction for bank transfer
- Withdraw $100 from account A, but only deposit $90 into account B.
10
(but constraints might be violated in intermediate states)
Deferring Integrity Constraints
CREATE TABLE UnitOfStudy (
uos_code VARCHAR(8),
title VARCHAR(20),
lecturer_id INTEGER,
credit_points INTEGER,
CONSTRAINT UnitOfStudy_PK PRIMARY KEY (uos_code),
CONSTRAINT UnitOfStudy_FK FOREIGN KEY (lecturer_id)
REFERENCES Lecturer DEFERABBLE INITIALLY IMMEDIATE
);
BEGIN;
INSERT INTO UnitOfStudy VALUES(‘INFO1000’,’Graphics’, 3, 6);
INSERT INTO Lecturer VALUES(3,'Steve’, CSE);
COMMIT;
11
Uos_code title Lecturer_id Credit_points
COMP9120 DBMS 1 6
COMP9007 Algorithm 2 6
Lecturer_id name department
1 Adam CSE
2 Lily IT
SET CONSTRAINTS UnitOfStudy_FK DEFERRED;
Outline
› Consistency
› Atomicity
- What, why, and how?
› Durability
› Isolation
12
Transactions should be Atomic
› A DBMS user can think of a transaction as always executing all its operations in
one step, or not executing any operations at all.
- Every transaction should act as an atomic operation.
› A real-world event either happens or does not happen (e.g., for bank transfer,
either both withdrawal + deposit occur, or neither occurs).
- Partially completed transaction can lead to an inconsistent database state.
› DBMS logs all actions so that it can undo the actions of aborted transactions.
- In the case of a failure, all actions of not-committed transactions are undone.
13
Commit and Abort
› If the transaction successfully completes, it is said to commit
- The DBMS is responsible for ensuring that all changes to the database have been saved
› If the transaction does not successfully complete, it is said to abort
- The DBMS is responsible for undoing, or rolling back, all changes in the database that
the transaction has made
- Possible reasons for abort:
- System crash
- Transaction aborted by system, e.g.,
- Transaction or connection hits time-out,
- Violation of constraint, etc
- Transaction requests to roll back
14
Writing a transaction in SQL
› 3 new SQL commands to know:
- BEGIN
- COMMIT requests to commit current transaction
- ROLLBACK causes current transaction to abort - always satisfied.
› Can also SET AUTOCOMMIT OFF or SET AUTOCOMMIT ON
- With auto-commit on, each statement is its own transaction and 'auto-commits'
- With auto-commit off, statements form part of a larger transaction delimited by the
keywords discussed above.
- Different clients have different defaults for auto-commit.
15
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=1234 WHERE uosCode=‘COMP5138’;
COMMIT;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
16
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=1234 WHERE uosCode=‘COMP5138’;
ROLLBACK;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
17
What value should be returned?
BEGIN;
UPDATE Course SET lecturerId=4567 WHERE uosCode=‘COMP5138’;
COMMIT;
SELECT lecturerId FROM Course WHERE uosCode=‘COMP5138’;
1. 1234
2. 3456
3. 4567
uosCode lecturerId
COMP5138 3456
COMP5338 4567
18
Writing a transaction with JDBC
› APIs, like JDBC, often provide explicit functions for controlling the transaction
semantics
› By default, transactions are in AutoCommit mode
- Each SQL statement is considered its own transaction.
- No explicit commit, no transactions with more than one statement…
› 3 new methods to know (all for JDBC connection class):
- setAutoCommit(false)
- commit()
- rollback()
19
JDBC Transaction example
public boolean bookFlight ( String flight_num, Date flight_date, Integer seat_no) {
boolean booked = false;
PreparedStatement stmt;
Connection conn;
try {
conn = openConnection();
conn.setAutoCommit(false);
stmt = conn.prepareStatement(“UPDATE Flight SET occupied=1” +
“WHERE occupied = 0 AND flightNum=? AND flightDate=? AND seat=?”);
stmt.setString(1, flight_num); stmt.setDate(2, flight_date);
stmt.setInt(3, seat_no);
int updatedRows = stmt.executeUpdate();
if(updatedRows == 1){
conn.commit();
booked=true;
}
else
conn.rollback();
}
catch (SQLException sqle) {
/* error handling */ ...
} finally {conn.close(); }
return booked;
}
Note: should explicitly call conn.rollback()
before calling conn.close(), if you want to
rollback
20
Transactions with Python DB-API
› DB-API provides transaction control via connection object methods
› According to DB-API spec, db connections initially start with auto-commit mode
switched off
- Can use autocommit attribute of connection to set auto-commit mode
› Transaction control
- conn.commit() successfully finishes (commits) current transaction
- conn.rollback() aborts current transaction
21
DB-API: Transaction Example
import psycopg2
try:
# connect to the database
conn = psycopg2.connect(database='foo', user='dbuser', password='pwd‘)
conn.autocommit = True
# move some money from one person to the other
curs = conn.cursor()
curs.execute ("UPDATE money SET amt = amt - 100 WHERE name = ‘James Bond'")
curs.execute ("UPDATE money SET amt = amt + 100 WHERE name = ‘Bill Gates'")
except:
print("unable to connect to db or to execute query")
conn.rollback ()
finally:
#cleanup
curs.close()
conn.commit()
22
Outline
› Consistency
› Atomicity
› Durability
- What, why, and how?
› Isolation
23
Transactions should be Durable
› Once a transaction is committed, its effects should persist in a database, and
these effects should be permanent even if the system crashes.
- A database should always be able to be recovered to the last consistent state
› Implementing Durability:
- Database is stored redundantly on mass storage devices to protect against media failure
(e.g., RAID)
- Write-Ahead Log
24
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
25
Transactions should be Isolated
› Transactions should be isolated from the effects of other concurrent
transactions.
- Note that a DBMS usually handles many transactions concurrently.
› Let’s consider two transactions that are run concurrently
- Transaction T1 is transferring $100 from account A to account B.
- T2 credits both accounts with a 5% interest payment.
26
T1: BEGIN A=A-100, B=B+100 COMMIT
T2: BEGIN A=1.05*A, B=1.05*B COMMIT
We assume that all transactions commit,
there is no aborted transaction!
Example Executions of the Two Transactions
› Serial execution: we can look at the transactions in a timeline view
› The transactions could occur in the other order… DBMS allows!
› DBMS can also interleave the transactions.
T1 transfers $100 from
account A to account B
T2 credits both accounts with a
5% interest payment
Time
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1 transfers $100 from
account A to account B
T2 credits both accounts with a
5% interest payment
Time
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
27
Isolation through Serializability
› Serial Schedule – A schedule in which all transactions are executed from start to
finish, without interleaving, one after the other.
- In serial execution, each transaction is isolated from all others
› However, interleaving (concurrent execution) improves performance
- Some transactions may be slow and long-running – don’t want to block other
transactions!
- Disk access may be slow – let some transactions use CPUs while others accessing disk!
› Serializability:
A schedule is serializable if it is equivalent to some serial schedule
- Two schedules S1 and S2 are equivalent if, for any database state, the effect on the
database of executing S1 is identical to the effect of executing S2
28
Example Serializable Schedule
› Consider the following interleaved execution
› It is serializable, as the result of the above interleaved execution is the same as
that of the following serial execution of T1, T2
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
29
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = (1.05*Ai)-100, BF = (1.05*Bi)+100)
Example Non-Serializable Schedule
› Consider the following interleaved execution
› It is not serializable, as the result of the above interleaved execution is not the
same as that of either of the following two serial executions.
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
AF = (Ai-100)*1.05, BF = Bi*1.05+100
AF = 1.05*(Ai-100), BF = 1.05*(Bi+100)
AF = (1.05*Ai) -100, BF = (1.05*Bi)+100
30
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
31
DBMS’s View of a Schedule
› Serializability is hard to check
- It needs to check the effect of the schedule on all consistent databases
› Let’s see how to analyze schedules without executing them.
› To do this, we need to see DBMS’s view of a schedule
- R: reading the content of an object from the database
- R1: reading by trasaction T1 (also written as R1)
- R2: reading by trasaction T2 (also written as R2)
- W: writing the content of an object into the database
- W1, W2 are similarly defined
32
T1: A=A-100, B=B+100
T2: A=1.05*A, B=1.05*B
T1: R1(A),W1(A), R1(B),W1(B)
T2: R2(A),W2(A),R2(B),W2(B)
Isolation through Conflict Serializability
› Two operations ai and aj of transactions Ti and Tj conflict if (1) they access
the same data X, (2) they come from different transactions, and (3) at least
one of them wrote X. (ai,aj) is called a conflict pair.
1. ai=R(X),aj=R(X). don’t conflict.
2. ai=R(X),aj=W(X). they conflict.
3. ai=W(X),aj=R(X). they conflict
4. ai=W(X),aj=W(X). they conflict
› Note: With SQL - SELECT corresponds to read,
INSERT, DELETE, UPDATE correspond to write
› A schedule is conflict serializable if it is conflict equivalent to some serial
schedule
- Two schedules are conflict equivalent if:
1. They involve the same set of operations of the same transactions
2. They order every pair of conflicting operations the same way
33
› Consider some schedule of a set of transactions T1,T2,...,Tn
› Precedence graph:
- direct graph where the vertices are the transactions.
- edge from Ti to Tj if the two transactions conflict, and Ti accessed the data item on
which the conflict arose earlier.
› Central Theorem:
- A schedule is conflict serializable if and only if its precedence graph is acyclic.
› Example:
- T1 and T2 have 3 conflict pairs
Testing for Conflict Serializability
34
T1: R1(c), W1(c)
T2: R2(c),W2(c)
T1 T2
Which of these schedules are conflict serializable?
› R1(x),R2(y),R1(z),R3(z),R2(x),R1(y)
- all reads – no conflicts – hence conflict serializable
› R1(x),W2(y),R1(z),R3(z),W2(x),R1(y)
- non-conflict serializable:
- putting T1 before T2 will make conflict (W2(y),R1(y)) violate conflict-serializability rule.
- putting T2 before T1 will make conflict (R1(x),W2(x)) violate conflict-serializability rule
› R1(x),W2(y),R1(z),R3(x),W2(x),R2(y)
- conflict serializable: conflicts on x by T1/T3 and T2 can conform to conflict serializability rule
35
Serializability vs Conflict Serializability
› If a schedule is conflict serializable, then it must also be serializable
› But not vice versa
- This schedule is serializable, but not conflict serializable
- It is equivalent to serial schedule T1, T2, T3 or T2, T1, T3
- It is not conflict equivalent to any serial schedule
36
T1: R1(A) W1(A)
T2: W2(A)
T3: W3(A)
Possible Anomalies for Non-conflict Serializable
Schedules
› Reading Uncommitted Data (“dirty reads”)
› Unrepeatable Reads: may not read same value twice
› Overwriting Uncommitted Data (“lost updates“):
T1: R1(A),W1(A), R1(B),W1(B)
T2: R2(A),W2(A),R2(B),W2(B)
T1: R(A), R(A)
T2: R(A),W(A)
T1: R(A), W(A)
T2: R(A),W(A)
38
Outline
› Consistency
› Atomicity
› Durability
› Isolation
- What, why, and how?
- Isolation through conflict serializability
- Lock-based concurrency control
39
Lock-based Concurrency Control
› Strict Two-phase Locking (S2PL) Protocol:
- Locks are associated with each data item
- A transaction must obtain a S (shared) lock on object before reading, and an X
(exclusive) lock on item before writing.
- exclusive (X) lock: Data item can be accessed by just one transaction
- shared (S) lock: Data item can only be read (but shared by transactions)
- All locks held by a transaction are released when the transaction completes.
- If a transaction holds an X lock on an item, no other transaction can get a lock (S
or X) on that item.
- Instead, such transactions must wait until the conflicting lock is released by
the previous transaction(s)
40
Locking Example 1
› Consider:
› Complete a schedule starting as:
› T2 must wait until T1 releases its lock on A (and B) – forces T2 to start only after
T1 commits or aborts (rolls back)
T1: R(A),W(A),R(B),W(B)
T2: R(A),W(A),R(B),W(B)
T1: S(A),R(A),X(A),W(A)
T2:
,S(B),R(B),X(B),W(B)
(A locked, must wait)
41
Lock Compatibility Matrix
Held by T1
T2 Requested
Shared Exclusive
Shared OK T2 wait on T1
Exclusive T2 wait on T1 T2 wait on T1
42
Locking Example 2
› Consider:
› Schedule with locking might start as:
› What happens next?
- T1 waiting on T2 to release lock on B
- T2 waiting on T1 to release lock on A
- DEADLOCK
T1: R(A),W(A),R(B),W(B)
T2: R(B),W(B),R(A),W(A)
T1: S(A),R(A),X(A),W(A)
T2: S(B),R(B),X(B),W(B)
43
Deadlocks
› Deadlock: Cycle of transactions waiting for locks to be released by each other.
Two ways of dealing with deadlocks:
› Deadlock prevention
- E.g. based on priorities
› Deadlock detection
- A transaction in the cycle must be aborted by DBMS (since transactions
will wait forever)
- DBMS uses deadlock detection algorithms or timeout to deal with it
44
Exercise
› 2 transactions, T1 & T2
› Assume no concurrency control, each row is an object
› Statements interleaved as below.
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=year+1 WHERE lecturerId = 4711 AND uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
45
Exercise
› 2 transactions, T1 & T2
› Assume no concurrency control, each row is an object
› Statements interleaved as below.
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=year+1 WHERE lecturerId = 4711 AND
uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
46
A
B
R1(A),R1(B)
R2(A)
R1(A),W1(A)
W2(A)
Time
Exercise
› 2 transactions, T1 & T2
› Assume strict 2PL with row-level locking is used.
› How would the following schedule be affected?
uosCode year semester lecturerId
COMP5138 2012 S1 4711
INFO2120 2011 S2 4711
T1 SELECT * FROM Offerings WHERE lecturerId = 4711
T2 SELECT year INTO :yr FROM Offerings WHERE uosCode = 'COMP5138'
T1 UPDATE Offerings SET year=yr+1 WHERE lecturerId = 4711 AND
uosCode = 'COMP5138'
T2 UPDATE Offerings SET year=:yr+2 WHERE uosCode = 'COMP5138'
T1 COMMIT
T2 COMMIT
47
A
B
S1(A),S1(B)
S2(A)
Request X1(A), wait
Request X2(A), wait
We have a deadlock!
› Let‘s return to our two transactions:
- Transaction T1 is transferring $100 from account A to account B.
- T2 credits both accounts with a 5% interest payment.
› Atomicity requirement
- all updates of a transaction are reflected in the db or none.
› Consistency requirement
- T1 does not change the total sum of A and B, and after T2, this total sum is 5% higher.
› Isolation requirement
- There is no guarantee that T1 will execute before T2, if both are submitted together. However,
the actions of T1 should not partially affect those of T2, or vice-versa.
› Durability requirement
- once a transaction has completed, the updates to the database by this transaction must persist
despite failures
T1: BEGIN A=A-100, B=B+100 COMMIT
T2: BEGIN A=1.05*A, B=1.05*B COMMIT
Summary
48
Key Skills
You should be able to:
› Explain how ACID properties define correct transaction behaviour
› Identify update anomalies when ACID properties aren’t enforced
› Explain whether an execution schedule is conflict serializable
› Use deferred integrity constraints in a transaction
› Implement appropriate transaction handling in client code (Java/JDBC)
› Explain how locking provides isolated transactions
49
References
› [RG] Ramakrishnan /Gehrke – Chapter 16, details in Ch. 17 & 18
› Kifer/Bernstein/Lewis – Chapter 18
› Ullman/Widom – Chapter 6.6
› Transactions & JDBC – [JDBC] JDBC documentation
- Docs for java.sql.connection (with commit, rollback and setAutoCommit)
http://docs.oracle.com/javase/6/docs/api/java/sql/Connection.html
- See also tutorial http://docs.oracle.com/javase/tutorial/jdbc/basics/transactions.html
› Transactions & DB-API:
- Python DB-API: https://www.python.org/dev/peps/pep-0249/
50
Next Week
› Schema Normalization
- Functional Dependencies
- Schema Normal Forms
- Schema Normalization
› Readings:
- Ramakrishnan/Gehrke (Cow book), Chapter 19
- Kifer/Bernstein/Lewis book, Chapter 6
- Ullman/Widom, Chapter 3 (up-to 3.5)
51
学霸联盟
