Lecture 6

concurrency control
the coordination of the simultaneous execution of transactions in a multi-user database system is concurrency control. the objective of concurrency control is to ensure the serializability of transaction multi-user database environment. concurrency control is important because the simultaneous execution of transactions over a shared database can create several data integrity and consistency problems. the three main problems are:
1. lost updatings
the lost updating problem occurs when two concurrent transactions, t1 and t2, are updating the same data element and one of the updatings is lost (overwritten by the other transaction).
the figure bellow explain the serial execution of two transactions
time transaction step stored value
1 t1 read prod_qoh 35
2 t1 prod_qoh = 35 + 100
3 t1 write prod_qoh 135
4 t2 read prod_qoh 135
5 t2 prod_qoh = 135 - 30
6 t2 write prod_qoh 105

the following figure show lost updatings
time transaction step stored value
1 t1 read prod_qoh 35
2 t2 read prod_qoh 35
3 t1 prod_qoh = 35 + 100
4 t2 prod_qoh = 35 - 30
5 t1 write prod_qoh (lost updating) 135
6 t2 write prod_qoh 5
2. uncommitted data
the phenomenon of uncommitted data occurs when two transactions, t1 and t2, are executed concurrently and the first transaction (t1) is rolled back after the second transaction (t2) has already accessed the uncommitted data—thus violating the isolation property of transactions.
the figure bellow explains the correct execution of two transactions.
time transaction step stored value
1 t1 read prod_qoh 35
2 t1 prod_qoh = 35 + 100
3 t1 write prod_qoh 135
4 t1 ****rollback**** 35
5 t2 read prod_qoh 35
6 t2 prod_qoh = 35 - 30
7 t2 write prod_qoh 5

the following figure show an uncommitted data problem
time transaction step stored value
1 t1 read prod_qoh 35
2 t1 prod_qoh = 35 + 100
3 t1 write prod_qoh 135
4 t2 read prod_qoh
(read uncommitted data) 135
5 t2 prod_qoh = 135 - 30
6 t1 ****rollback**** 35
7 t2 write prod_qoh 105

3. inconsistent retrievals
inconsistent retrievals occur when a transaction accesses data before and after another transaction(s) finish working with such data. for example, an inconsistent retrieval would occur if transaction t1 calculates some summary (aggregate) function over a set of data while another transaction (t2) is updating the same data, the problem is that the transaction might read some data before they are changed and other data after they are changed, thereby yielding inconsistent results.
retrieval during updating
transaction t1 transaction t2
select sum(prod_qoh)
from product updating product
set rrodq_qoh = prod_qoh +10
where prod_code = ‘1546-qq2’
updating product
s et prod_qoh = prod_qoh — 10
where prqd code == 1558-qw1‘
commutt
transaction results: data entry correction
before after
prod_code prod_qoh prod_qoh
11qer/31 8 8
13-q2/p2 32 32
1546-qq2 15 (15 + 10) ? 25
1558-qw1 23 (23 - 10) ? 13
2232-qty 8 8
2232-qwe 6 6
total 92 92

inconsistent retrieval
time transaction action value total
1 t1 read prod_qoh for prod_code = ‘11qer/31’ 8 8
2 t1 read prod_qoh for prod_code = ’13-q2/p2’ 32 40
3 t2 read prod_qoh for prod_code = ’1546-qq2’ 15
4 t2 prod_qoh = 15 + 10
5 t2 write prod_qoh for prod_code = ’1546-qq2’ 25
6 t1 read prod_qoh for prod_code = ’1546-qq2’ 25 (after) 65
7 t1 read prod_qoh for prod_code = ’1546-qw1’ 23 (before) 88
8 t2 read prod_qoh for prod_code = ’1546-qw1’ 23
9 t2 prod_qoh = 23 - 10
10 t2 write prod_qoh for prod_code = ’1546-qw1’ 13
11 t2 *****commit*****
12 t1 read prod_qoh for prod_code = ’2232-qty’ 8 96
13 t1 read prod_qoh for prod_code = ’2232-qwe’ 6 102

the scheduler
the scheduler is a special dbms process that establishes the order in which the operations within concurrent transactions are executed. the scheduler interleaves the execution of database operations to ensure serializability isolation of transactions. to determine the appropriate order, the scheduler bases its actions on concurrency control algorithms, such as locking or time stamping methods, however. important to understand that not all transactions are serializable. the dbms determines what transactions serializable and proceeds to interleave the execution of the transaction’s operations. generally, transactions that are not serializable are executed on a first-come, first-served basis by the dbms.
the scheduler’s main job is to create serializable schedule of a transaction’s operations. a serializable schedule is a schedule of a transaction’s operations in which the interleaved execution of the transactions (t1, t2, t3, etc.) yields the same results as if the transactions were executed in serial order (one after another).
the scheduler also makes sure that the computer’s central processing unit (cpu) and storage systems are efficiently used. if there were no way to schedule the execution of transactions, all transactions would be executed on a first-come, first-served basis. the problem with that approach is that processing time is wasted when the cpu waits for a read or write operation to finish, thereby losing several cpu cycles. in short , first-come. first-served. scheduling tends to yield unacceptable response times within the multi-user dbms environment. therefore, some other scheduling method is needed to improve the efficiency of the overall system.
additionally, the scheduler facilitates data isolation to ensure that two transactions do not updating the same data element at the same time. database operations might require read and/or write actions that produce conflicts. for example, the table bellow shows the possible conflict scenarios when two transactions, t1 and t2, are executed concurrently over the same data. note that in the table two operations are in conflict when they access the same data and at least one of them is a write operation.
read/write conflict scenario: conflicting database operations matrix
transaction
t1 t2 result
operations read read no conflict
read write conflict
write read conflict
write write conflict


several methods have been proposed to schedule the execution of conflicting operations in concurrent transactions. those methods have been classified as locking, time stamping, and optimistic.