Transcript Document

ITEC 3220A
Using and Designing Database Systems
Instructor: Gordon Turpin
Course Website:
www.cse.yorku.ca/~gordon/itec3220S07
Office: CSEB3020
Chapter 10
Transaction Management and
Concurrent Control
What is a Transaction?
• Any action that reads from and/or writes
to a database may consist of
– Simple SELECT statement to generate a list
of table contents
– A series of related UPDATE statements to
change the values of attributes in various
tables
– A series of INSERT statements to add rows to
one or more tables
– A combination of SELECT, UPDATE, and
INSERT statements
3
What is a Transaction? (continued)
• A logical unit of work that must be either entirely
completed or aborted
• Successful transaction changes the database
from one consistent state to another
– One in which all data integrity constraints are
satisfied
• Most real-world database transactions are
formed by two or more database requests
– The equivalent of a single SQL statement in an
application program or transaction
4
Example Transaction
• Examine current account balance
SELECT ACC_NUM, ACC_BALANCE
FROM CHECKACC
WHERE ACC_NUM = ‘0908110638’;
• Consistent state after transaction
• No changes made to Database
5
Example Transaction
• Register credit sale of 100 units of product X to
customer Y for $500
UPDATE PRODUCT
SET PROD_QOH = PROD_QOH - 100
WHERE PROD_CODE = ‘X’;
UPDATE ACCT_RECEIVABLE
SET ACCT_BALANCE = ACCT_BALANCE + 500
WHERE ACCT_NUM = ‘Y’;
• Consistent state only if both transactions are fully
completed
• DBMS doesn’t guarantee transaction represents
real-world event
6
Incomplete Transactions
• Reasons:
– An anomaly arises during execution
(automatically restart)
– System crashes
– An unexpected situation during transaction
execution
• May bring database to inconsistent state
7
Transaction Properties
• Atomicity
– All transaction operations must be completed
– Incomplete transactions aborted
• Durability
– Permanence of consistent database state
• Serializability
– Conducts transactions in serial order
– Important in multi-user and distributed databases
• Isolation
– Transaction data cannot be reused until its execution
complete
8
Transaction Management with
SQL
• Transaction support
– COMMIT
– ROLLBACK
• User initiated transaction sequence must
continue until:
–
–
–
–
COMMIT statement is reached
ROLLBACK statement is reached
End of a program reached
Program reaches abnormal termination
9
Transaction Log
• Tracks all transactions that update database
• May be used by ROLLBACK command
• May be used to recover from system failure
• Log stores
– Record for beginning of transaction
– Each SQL statement
• Operation
• Names of objects
• Before and after values for updated fields
• Pointers to previous and next entries
– Commit Statement
10
Transaction Log
Example
11
Example
• Suppose that you are a manufacturer of product ABC, which
is composed of parts A, B, C. Each time a new product ABC is
created, it must be added to the product inventory, using the
PROD_QOH in PRODUCT table. And each time the product is
created the parts inventory, using PART_QOH in PART table
must be reduced by one each of parts, A, B, and C.
PART
PRODUCT
PART_CODE
PART_QOH
PROD_CODE
PROD_QOH
A
567
ABC
1205
B
98
C
549
12
Example (Cont’d)
Given the information, answer:
• How many database requests can you identify for an
inventory update for both PRODUCT and PART?
• Using SQL, write each database request you have
identified above.
• Write the complete transactions.
• Write the transaction log, using the template in slide 11.
13
Concurrency Control
• Coordinates simultaneous transaction
execution in multiprocessing database
– Ensure serializability of transactions in
multiuser database environment
– Potential problems in multiuser
environments
•Lost updates
•Uncommitted data
•Inconsistent retrievals
14
Normal Execution of Two
Transactions
15
Lost Updates
16
More Example
17
Correct Execution of Two
Transactions
18
An Uncommitted Data Problem
19
Retrieval During Update
20
Transaction Results:
Data Entry Correction
21
Inconsistent Retrievals
22
Example
• A department store runs a multiuser DBMS on a local area
network file server which does not enforce concurrency control.
One customer has a balance due of $250 when the following
three transactions related to this customer were processed at
the same time:
–Payment of $250
–Purchase on credit of $100
–Merchandise return of $50.
Each transaction reads the customer record when the balance was
$250. the updated record was returned to the database in the
order shown above.
• What balance will be for the customer after the last transaction
was completed?
23
The Scheduler
• Establishes order of concurrent
transaction execution
• Interleaves execution of database
operations to ensure serializability
• Bases actions on concurrency control
algorithms
– Locking
– Time stamping
• Ensures efficient use of computer’s CPU
24
Read/Write Conflict Scenarios:
25
Concurrency Control
with Locking Methods
• Lock guarantees current transaction exclusive
use of data item
• Acquires lock prior to access
• Lock released when transaction is completed
• DBMS automatically initiates and enforces
locking procedures
• Managed by lock manager
• Lock granularity indicates level of lock use
26
Locking Mechanisms
• Locking level:
–
–
–
–
Database – used during database updates
Table – used for bulk updates
Block or page – very commonly used
Row – only requested row; fairly commonly
used
– Field – requires significant overhead;
impractical
27
Locking Granularity
• Granularity refers to the level of the database
item locked.
• A trade-off between overhead and waiting.
• Holding locks at a fine level decreases waiting
among users but increase the system
overhead.
• Holding locks at a coarser level reduces the
number of locks but increases the amount of
waiting.
28
A Database-Level Locking
Sequence
29
An Example of a Table-Level Lock
30
Example of a Page-Level Lock
31
An Example of a Row-Level Lock
32
Binary Locks
• Two states
– Locked (1)
– Unlocked (0)
• Locked objects unavailable to other
objects
– Unlocked objects open to any transaction
– Transaction unlocks object when complete
33
An Example of a Binary Lock
34
Shared/Exclusive Locks
• Shared
– Exists when concurrent transactions granted READ
access
– Produces no conflict for read-only transactions
– Issued when transaction wants to read and exclusive
lock not held on item
• Exclusive
– Exists when access reserved for locking transaction
– Used when potential for conflict exists
– Issued when transaction wants to update unlocked
data
35
Shared/Exclusive Locks (Cont’d)
T2
X
S
_
X
No
No
Yes
S
No
Yes
Yes
_
Yes
Yes
Yes
T1
36
Two-Phase Locking
to Ensure Serializability
• Defines how transactions acquire and
relinquish locks
• Guarantees serializability, but it does
not prevent deadlocks
– Growing phase, in which a transaction
acquires all the required locks without
unlocking any data
– Shrinking phase, in which a transaction
releases all locks and cannot obtain any
new lock
37
Two-Phase Locking
to Ensure Serializability (continued)
• Governed by the following rules:
– Two transactions cannot have conflicting
locks
– No unlock operation can precede a lock
operation in the same transaction
– No data are affected until all locks are
obtained—that is, until the transaction is in
its locked point
38
Two-Phase Locking Protocol
39
Deadlocks
• Condition that occurs when two transactions
wait for each other to unlock data
• Possible only if one of the transactions wants to
obtain an exclusive lock on a data item
– No deadlock condition can exist among shared locks
• Control through
– Prevention
– Detection
– Avoidance
40
How a Deadlock Condition Is
Created
41
Example on Concurrency Control
Given schedule S1 as follows, and the locks won’t be
released until commit. Is there any deadlock in S1
using Shared/Exclusive lock.
T1
T2
T3
R(A)
W(B)
W(A)
Commit A, B
W(B)
Commit B
W(B)
Commit B
42
More Example
T1
T2
T3
R(C)
R(B)
W(B)
R(B)
R(A)
W(A)
W(C)
W(B)
R(A)
R(B)
W(B)
W(A)
Commit A
Commit A, B & C
Commit B
43
More Example
• Let transactions T1, T2, and T3 be defined to
perform the following operations:
T1: Add one to A
T2: Double A
T3: Display A and then set A to one
• Suppose the structure for T1, T2, T3 is
indicated below. If the transactions execute
without any locking, please give an example of
wrong schedules.
44
More Examples (Cont’d)
T1
T11:
Read (A), A ←
A+1
T12:
Update (A)
T2
T21:
Read (A), A ←
A*2
T22:
Update (A)
T3
T31:
Read (A), A = 1
T32:
Update (A)
• Suppose the following schedule
T11- T31- T12- T32- T21- T22 obeyed the two-phase
locking algorithm. Explain what could be produced by
the schedule.
45
Concurrency Control
with Time Stamping Methods
• Assigns a global unique time stamp to each
transaction
• Produces an explicit order in which transactions
are submitted to the DBMS
• Uniqueness
– Ensures that no equal time stamp values can exist
• Monotonicity
– Ensures that time stamp values always increase
46
Wait/Die and Wound/Wait
Schemes
• Wait/die
– Older transaction waits and the younger is
rolled back and rescheduled
• Wound/wait
– Older transaction rolls back the younger
transaction and reschedules it
47
Wait/Die and Wound/Wait
Concurrency Control Schemes
48
Example
Concurrency control is implemented based on time
stamping method. Consider the following schedule:
T1
T2
R(A)
W(A)
W(B)
W(B)
W(C)
R(C)
49
Concurrency Control
with Optimistic Methods
• Optimistic approach
– Based on the assumption that the majority
of database operations do not conflict
– Does not require locking or time stamping
techniques
– Transaction is executed without
restrictions until it is committed
– Phases are read, validation, and write
50
Better Performance than Locking
51
Example
T1
T2
R(A)
W(A)
R(B)
R(B)
commit
52
Database Recovery Management
• Database recovery
– Restores database from a given state, usually
inconsistent, to a previously consistent state
– Based on the atomic transaction property
• All portions of the transaction must be treated as a
single logical unit of work, in which all operations must
be applied and completed to produce a consistent
database
– If transaction operation cannot be completed,
transaction must be aborted, and any changes to the
database must be rolled back (undone)
53
Transaction Recovery
• Deferred write
– Transaction operations do not immediately update
the physical database
– Only the transaction log is updated
– Database is physically updated only after the
transaction reaches its commit point using the
transaction log information
• Write-through
– Database is immediately updated by transaction
operations during the transaction’s execution, even
before the transaction reaches its commit point
54
Example
• Describe the restart work if transaction T1 is
committed after the checkpoint but prior to
the failure. Assume that the recovery manager
uses
– the deferred update approach
– The write though approach
Backup
Checkpoint
Failure
T1
55
Review
• Transaction property
• Transaction log
• Potential problems in multiuser
environments
• Different locking methods and how they
work
• Database recovery management
56