(Chapter 12) Transaction

( 출처 : 연세대학교 데이터베이스 시스템 수업 (CSI6541) 강의자료 )

Chapter 12. Transaction

Contents

• Transaction Concept
  • Transcation
  • ACID properties
  • Example
  • Operations in transaction
• Transaction State
• Implementation of Atomicity & Durability
• Concurrent Executions
  • Introduction
  • Schedules
• Serializability
  • Conflict serializable
  • View serializable
• Testing for Serializability

(1) Transaction Concept

a) Transaction

• def ) UNIT of program execution that accesses & updates various data
• must see a “CONSISTENT” DB
• during transaction execution…
• the DB may be INCONSISTENT
• when the transaction is committed…
  • the DB must be CONSISTENT

2 main issues :

• (1) FAILURES of various kinds
  • ex) hardware failures and system crashes
• (2) “CONCURRENT” execution of multiple transactions

b) ACID properties

to preserve integrity of data …

• [A] Atomicity
  • either ALL or NONE operations of the transaction are properly reflected in the DB
• [C] Consistency
  • execution of a transaction in isolation preserves the CONSISTENCY of the DB
• [I] Isolation

  • although multiple transactions may execute CONCURRENTLY,

    each transaction must be UNAWARE OF other concurrently executing transactions

• [D] Durability
  • after a transaction completes successfully, the changes it has made to the DB persist, even if there are system failures

c) Example

Transaction to transfer $$50 from account A to account B:

1. read(A)

2. A := A – 50

3. write(A)

4. read(B)

5. B := B + 50

6. write(B)

Requirements

(a) Consistency

• sum(A,B) is unchanged by the execution of the transaction

(b) Atomicity

• if the transaction fails after (step 3) and before (step 6) ,

  the system should ensure that its updates are NOT REFLECTED in the DB

  ( if not … an inconsistency will result )

(c) Durability

• once the user has been notified that the transaction has completed,

  the updates to the DB by the transaction must PERSIST despite failures

(d) Isolation

• if another transaction is allowed to access the partially updated DB between (step 3) and (step 6)

  \(\rightarrow\) will see an INCONSISTENT DB (the sum(A,B) will be less than it should be)

• Isolation can be ensured trivially by running transactions SERIALLY

  \(\rightarrow\) However, executing multiple transactions CONCURRENTLY has significant benefits

d) Operations in transaction

(a) Commit

• transaction이 성공적으로 완료되었음을 선언하는 연산
• commit 실행 시, transaction의 결과가 DB에 반영 & 일관된 상태를 지속적으로 유지

(b) Rollback

• transaction이 실패 했음을 선언하는 연산

• Rollback 실행 시, transaction이 지금까지 실행한 연산의 결과가 취소

  & DB가 transaction 수행 전의 일관된 상태로 되돌아감

(2) Transaction State

(1) Active

• the initial state
• transaction stays in this state while it is executing

(2) Partially committed

• after the final statement has been executed

(3) Failed

• after the discovery that normal execution can no longer proceed

(4) Aborted

• after the transaction has been rolled back

  & DB restored to its state prior to the start of the transaction

(5) Committed

• after successful completion

(3) Implementation of Atomicity & Durability

[1] Recovery-management component of DB

• implements the support for “atomicity” and “durability”

[2] Shadow-DB scheme

• assume that only “one transaction is active at a time”

• a “pointer called db_pointer” always points to the CURRENT consistent copy of the DB

• all updates are made on a SHADOW copy of the DB

• if FAIL …..

  \(\rightarrow\) old consistent copy ( pointed to by db_pointer ) can be used,

  & the shadow copy can be deleted

• Useful for text editors …

  • but extremely inefficient for large DB

  • executing a single transaction requires copying the entire DB

(4) Concurrent Executions

a) Introduction

Multiple transactions are allowed to run CONCURRENTLY (동시에) in the system

Advantages :

• Increased processor and disk utilization

• Reduced average response time

Concurrency control schemes

• Mechanisms to achieve ISOLATION

• Control the interaction among the concurrent transactions,

  in order to prevent them from destroying the CONSISTENCY of the DB

b) Schedules

• SEQUENCES that indicate the chronological ORDER ,

  in which instructions of “concurrent transactions are executed”

• must consist of all instructions of those transactions

• must preserve the order in which the instructions appear in each individual transaction

Examples )

(5) Serializability ( = 직렬성 )

Each transaction is assumed to preserve database consistency

\(\rightarrow\) \(\therefore\) serial execution of a set of transactions preserves DB consistency

A schedule is serializable, if it is equivalent to a serial schedule

• a) CONFLICT serializable

• b) VIEW serializable

We ignore operations other than read and write instructions

a) Conflict serializable

A conflict between \(l_i\) and \(l_j\) forces a temporal order between them

If \(l_i\) and \(l_j\) are consecutive in a schedule & they do not conflict…

\(\rightarrow\) their results would remain the SAME even if they had been INTERCHANGED in the schedule

Conflict Equivalent

Schedule \(S\) & \(S^{'}\) are conflict equivalent…

• If \(S\) can be transformed into \(S^{’}\) by a series of swaps of non-conflicting instructions

Conflict serializable

Schedule \(S\) is conflict serializable..

• If \(S\) is conflict equivalent to a serial schedule

Example )

b) View serializable

Let \(S\) and \(S^{’}\) be 2 schedules with the same set of transactions.

View equivalent

\(S\) & \(S^{'}\) are view equivalent ….

if the following 3 conditions are met for each data item Q

• If transaction \(T_i\) reads the initial value of Q in schedule S

  \(\rightarrow\) transaction \(T_i\) must also read the initial value of Q in schedule \(S^{'}\)

• If transaction \(T_i\) executes read(Q) in schedule \(S\)

  & that value was produced by transaction \(T_j\)

  \(\rightarrow\) then transaction \(T_i\) must also read the value of Q in schedule \(S^{'}\) that was produced by transaction \(T_j\)

• If transaction \(T_i\) performs the final write(Q) operation in schedule \(S\)

  \(\rightarrow\) then transaction \(T_i\) must also perform the final write(Q) operation in schedule \(S^{'}\)

Summary

• A schedule S is “view serializable” if it is view equivalent to a serial schedule

• Every conflict serializable schedule is also view serializable

Example ) view serializable (O) , conflict serializable (X)

(6) Testing for Serializability

Notation

• \(T_1 \cdots T_n\) : set of transcations

Precedence graph :

• direct graph where the vertices represent the transactions

• draw an arc from \(T_i\) to \(T_j\)…

  • if the two transactions conflict and \(T_i\) accessed the data item earlier on which the conflict arose

Details :

• A schedule is conflict serializable \(\leftrightarrow\) its precedence graph is acyclic

• precedence graph is acyclic \(\rightarrow\) the serializability order can be obtained by a topological sorting of the graph

• The problem of checking if a schedule is view serializable falls in the class of NP-complete problems

• However practical algorithms that just check some sufficient conditions for view serializability can still be used