北郵-數(shù)據(jù)庫系統(tǒng)原理英文

PART

5TRANSACTION

MANAGEMENTC,Pascal

programs詞法/語法/語義分析中間代碼生成(中間)代碼優(yōu)化目標(biāo)代碼生成//OS進(jìn)程管理&并發(fā)進(jìn)控程制調(diào)度死鎖處理query掃描和語法/語義分析查詢優(yōu)化(優(yōu)化后)查詢執(zhí)行計(jì)劃查詢代碼生成Query

processing

/

DBMSprocess

/

thread事務(wù)處理/

DBMSChapter.13,14transaction關(guān)系代數(shù)表達(dá)式&查詢樹查詢計(jì)劃執(zhí)行的代碼事務(wù)管理目標(biāo)程序代碼(§14)&度并發(fā)事控務(wù)制調(diào)死鎖處理(§13)(§15)(§16)恢復(fù)技術(shù)(§17)Chapter.15,16,17Fig.

13.0.1DBS中，從DBMS的角度，用戶對DB的 體現(xiàn)為DBS中1個(gè)或多個(gè)事務(wù)的執(zhí)行事務(wù)是DBS中應(yīng)用程序/數(shù)據(jù)庫應(yīng)用系統(tǒng)的基本邏輯單位，也是DBMS管理DBS運(yùn)行的基本單位,§15.1體現(xiàn)為DBS中多多用戶DBS中，多個(gè)用戶對DB的并發(fā)個(gè)數(shù)據(jù)庫事務(wù)的并發(fā)執(zhí)行事務(wù)是動態(tài)的，具有一定生命周期事務(wù)具有多種狀態(tài)，事務(wù)的執(zhí)行體現(xiàn)為各狀態(tài)間的轉(zhuǎn)換過程,§15.2,Fig.15.1Introduction

to

Part

53Database

System

Concepts

-

Chapter

15

Transactions

-在DBS中，事務(wù)執(zhí)行時(shí)，特別是當(dāng)多個(gè)事務(wù)對共享數(shù)據(jù)進(jìn)行并發(fā) 時(shí)，為

DBS系統(tǒng)中數(shù)據(jù)的正確性(integrities)，事務(wù)必須滿足一定的約束條件，表現(xiàn)為事務(wù)的4個(gè)基本特征(ACID)

,§15.1原子性(atomicity)，一致性(consistency)，獨(dú)立性/性(isolation)，

性/

持續(xù)性/操作結(jié)果

保持性

(durability)DBMS中的recovery-managementcomponent負(fù)責(zé)保障事務(wù)的原子性?！?5.3,§17事務(wù)設(shè)計(jì)者/DBS應(yīng)用程序編程者負(fù)責(zé)保障事務(wù)的一致性(P611)Introduction

to

Part

5

(cont.)4Database

System

Concepts

-

Chapter

15

Transactions

-DBMS中的concurrency-control

component負(fù)責(zé)保障事務(wù)的獨(dú)立性?！?6DBMS中的recovery-management

component負(fù)責(zé)保障事務(wù)的永久性?！?5.3,§17當(dāng)DBS中存在多個(gè)并發(fā)事務(wù)時(shí)，DBMS通過事務(wù)調(diào)度對各事務(wù)進(jìn)行并發(fā)控制(§15.4)，以保證并發(fā)事務(wù)的運(yùn)行結(jié)果正確性DBMS中的concurrency-controlcomponent依據(jù)事務(wù)調(diào)度可串行性（Serializability)的基本原理，對事務(wù)進(jìn)行并發(fā)控制和調(diào)度,§15.5,15.6,15.75Database

System

Concepts

-

Chapter

15

Transactions

-Introduction

to

Part

5

(cont.)具體實(shí)現(xiàn)技術(shù)包括基于鎖的并發(fā)控制技術(shù)(§16.1)、基于時(shí)間戳的并發(fā)控制技術(shù)(§16.2)

、基于驗(yàn)證的并發(fā)控制技術(shù)

(§16.3)、多版本控制(§16.5)

、多粒度控制技術(shù)(§16.4)此外，DBMS的concurrency-control

component還需要對多個(gè)并發(fā)執(zhí)行的事務(wù)進(jìn)行死鎖處理(§16.6)6Database

System

Concepts

-

Chapter

15

Transactions

-Introduction

to

Part

5

(cont.)Chapter

15TRANSACTIONSDefinition

and

compositionRead

and

writeACID

properties8Database

System

Concepts

-

Chapter

15

Transactions

-§15.1

Transaction

ConceptcessesConceptaunit

of

DBS

application

programexecuting

thand

possiblyupdates

variousdata

items

inDBAnother

definitiona

transaction

isa

means

by

which

an

application

programmercan

package

together

a

sequence

of

DB

operations

so

that

theDBS

can

providea

numberof

guarantees,

knownasACIDproperties

ofatransaction15.1.1

Definition

and

Composition9Database

System

Concepts

-

Chapter

15

Transactions

-Components

ofthetransactionacollection

of operations

that

form

asingle

logic

unit

ofapplication

worksoperations:

read

orwrite

on

DB,

orotheroperationswritten

in

query

languages

(e.g.

SQL)

or

programminglanguages

(e.g.

C,C++,

Java)10Database

System

Concepts

-

Chapter

15

Transactions

-?begin-transactionop1;op2;.opn;end-transaction

(e.g.

commit

or

abort/rollback)Definition

and

Composition

(cont.)Conceptually,

atransaction

canbe

defined

by

read

and

writeoperations,

which

are

independent

of

DBS

query

languages

(e.g.SQL)

and

DBMS

(e.g.

SQL

Server)E.g.1.

Account-transfer

T1

:transfer

$50

from

account

Ato

account

BT1:

begin-transactionread

(

account_A

);account_A

:=

account_A

-50;write

(account_A

);read

(account_

B

);account_

B:=

account_

B+50;write

(account_

B

);end-transaction11Database

System

Concepts

-

Chapter

15

Transactions

-Definition

and

Composition

(cont.)begin-transactionread

(

amount_A

);amount_A:=

amount_A

-50;if amount_A

<0

thenthen

beginprint(‘insufficient

funds’)rollback

T2endelse

beginwrite

(account_A

);read

(amount_

B

);amount_

B:=

amount_

B+50;write

(amount_

B

);commit

T2endabort/

rollback

T2:

撤銷之前對loan_A

的修改,即恢復(fù)loan_A

的原值，并立即結(jié)束T2，不再執(zhí)行其后的各操作Fig.15.0.1

Account_transfer

T2

with

rollback13Database

System

Concepts

-

Chapter

15

Transactions

-In

view

of

implementation,

a

transaction

can

be

written

in

querylanguages

(e.g.T-SQL)andprogramming

languages

(C,C++,Java)E.g.2.

Implementation

of

Account_transfer

inT-SQLFig.15.0.2Definition

and

Composition

(cont.)DECLARE

@transfer_name

varchar(10) /*事務(wù)變量定義*/SET

@transfer_name

=

‘I-transfer-from-A-to-B’BEGINTRANSACTION

@transfer_name/*事務(wù)命名*//*事務(wù)開始*/USE

ACCOUNTGOUPDATE

account_A/*打開數(shù)據(jù)庫ACCOUNT*//*將上述批SQL語句提交SQLServer*//*

修改A帳戶*/SET balance

= balance–50WHERE branch_name=‘Brooklyn’/*

修改B帳戶*/UPDATESETaccount_Bbalance

=balance

+50/*事務(wù)提交*/WHERE branch_name=‘Brooklyn’GOCOMMITTRANSACTION

@transfer_nameGOFig.15.0.2

Account_transfer

T3

in

T-SQLAtransaction

correspondstoa

SQL

statement,

ora

sequence

of

statements,

oran

application

program

related

to

DB

accessAn

application

program

may

correspond

to

several

transactions15Database

System

Concepts

-

Chapter

15

Transactions

-Transactions

vs

DBS

ApplicationProgramsEach

data

access

in

transactions,

such

as

select,

Update

in

SQL,or

API

in

ODBC,

is posed

by

DBMS

into

oneormore

read

and

write

operationsRefer

to

Fig.15.0.3DBMS

executes

these

readand

write

operations

to

fulfill

dataaccess

intransactionsFor

each

transaction,

DBMS

allocates

a

local

buffer

in

mainmemory

as

the

working

area

for

thistransactionThe

database

permanently

resides

ondisk,but

some

portion

ofitis

temporarily

residing

in

the

disk

bufferin

main

memory15.1.2

Read

and

Write

Operations16Database

System

Concepts

-

Chapter

15

Transactions

-DB

fileondisklocal

buffer

for

Tiread(x)write(y)DBMSTransactiondata

accesses

ondata

item

xand

yissuedby

Ti,e.g.

select,

insert,delete,

update,…xi,yiBX

BYdiskbufferinput(X)output(Y)/

reflectBZ…BX

BY

…

BZ

BWBU

BV

…

BQ

BRFig.15.0.3

read

and

write

operations邏輯讀寫物理讀寫read(X)transfer

the

data

item

XfromDB

filesondisk

orthedisk/system

buffer

to

the

local

buffer

of

the

transaction

thatexecute

the

read

operationwrite(X)conceptually,

transfer

thedata

item

X

fromthe

local

buffer

ofthe

transaction

that

execute

the

write

operation

back

totheDB

filesondiskIn

real

DBS,

thewrite

operation

issued

bytransactions

doesnotnecessarily

result

in

the

immediate

update

of

thedata

onthedisks,

this

operation

may

be

temporarily

stored

in

the

systembuffers

andexecuted

onthedisklatere.g.

Fig.

15.0.318Read

and

Write

Operations

(cont.)Database

System

Concepts

-

Chapter

15

Transactions

-To

guarantee

integrities

of

DB,

ACID

Transaction

Propertiesshould

bemaintainedAtomicity,

Consistency,

Isolation,

DurabilityConsistencyexecution

of

a

transaction

in

isolation

(that

is,

with

noothertransaction

executing

concurrently)

preserves

theconsistency

of the

DB,i.e.

before

and

after

thetransactionexecution,

DB

isin

a

correct

DB

state/*1個(gè)事務(wù)的正確執(zhí)行使得DB從一個(gè)正確狀態(tài)轉(zhuǎn)移到另一個(gè)正確狀態(tài)DB

state: contents

oftables

in

DB, orDB19instanceDatabase

System

Concepts

-

Chapter

15

Transactions

-15.1.3TransactionPropertiesconsistency/correctness:

integrity

constraints

are

notviolatede.g.

for

account_transfer

T1andT2,the

consistency

requiresthat

the

sum

ofaccountA

and

account

Bbeunchanged

bytheexecution

ofT1andT2note:

during

the

execution

of

transactions,

consistency

maynot

be

maintained,

and

DB

maybe

ininconsistent/incorrectstates/*事務(wù)執(zhí)行過程中，完整性約束有可能被破壞20Database

System

Concepts

-

Chapter

15

Transactions

-Transaction

Properties

(cont.)Atomicityeither

all

operations

ofthetransaction

are

reflected

(

)properly

inthe

database,

or noneare/*事務(wù)中所有操作或者全部成功完成，并且這些操作結(jié)果被寫入到DB；或者事務(wù)中的所有操作一個(gè)都不作,該事務(wù)對數(shù)據(jù)庫和其他事務(wù)沒有任何影響/*將有操作作為1個(gè)不可分割的整體e.g.

account_transfer

T1Transaction

Properties

(cont.)21Database

System

Concepts

-

Chapter

15

Transactions

-Isolationeven

though

multipletransactions mayexecute

concurrently,the

system

guarantee

that

all

transactions

seem

to

executeserially,

so

the

consistent

states

of

DB

can

be

peach

transaction

isunaware

ofother

transactions

executingconcurrently

in

thesystem/*對多個(gè)并發(fā)執(zhí)行的事務(wù)，1個(gè)事務(wù)的執(zhí)行不能被其他事務(wù)干擾，即1個(gè)事物的 操作和數(shù)據(jù)對其它事務(wù)是的，并發(fā)執(zhí)行的事務(wù)間不能相互干擾，從執(zhí)行結(jié)果來看，相當(dāng)于事務(wù)串行執(zhí)行Transaction

Properties

(cont.)22Database

System

Concepts

-

Chapter

15

Transactions

-While

consistency

and

atomicity

ensurethe

correct

execution

ofan

individual

transaction,

isolation

guarantees

the

correctness

ofconcurrent

execution

ofmorethan

onetransactionsDurabilityafter

a

transaction

completes

successfully

(

i.e.

thetransaction

is

committed), thechanges

it

hasmade

tothe

DBpersist, even

if there

are

systemfailure/*事務(wù)一旦提交（成功完成），它對數(shù)據(jù)庫中數(shù)據(jù)的改變就應(yīng)該是性的，這些改變不隨其后的數(shù)據(jù)庫系統(tǒng)錯(cuò)誤而丟失Transaction

Properties

(cont.)23Database

System

Concepts

-

Chapter

15

Transactions

-e.g.1

the

modifications

on

Y

inFig.15.0.3beforetransaction

end, the

modified

resultsin

localbuffer

should

be

reflected

to

the

DB

file

ondiskTransaction

Properties

(cont.)24Database

System

Concepts

-

Chapter

15

Transactions

-Transaction

Properties

(cont.)e.g.2.

forT3inFig.15.0.2begin-trans.;

update(A)

;update(B)

;commitA=1000B=2000A=1000B=2000a=950a=950b=2050local

bufferfor

T3disk

buffera=950a=950b=2050a=950b=2050A=950B=2050a=1000a=1000A=1000B=200025Database

System

Concepts

-

Chapter

15

Transactions

-ACID

mechanisms

in

DBSA

: transaction

management

/

recovery

managementcomponentC: programmer/transaction

designer,

integrity

constraintstesting

mechanism

inDBMSI: concurrency

control

componentD: recovery

management

component26Database

System

Concepts

-

Chapter

15

Transactions

-Transaction

Properties

(cont.)§15.2Transaction

States27Database

System

Concepts

-

Chapter

15

Transactions

-Committed(提交)transactionsuccessfully

complete

all

itsoperationsAborted(撤銷/夭折)transactionnot

finishall

its

operations

successfullyrollbackDuring

its

execution,

a

transaction

can

stay

in

several

states,

asshown

inFig.15.1taking

Fig.15.0.5,

Fig.15.0.6

as

examplesbegin-transactioncommitrollbackFig.15.1.

State

diagram

of atransactionTransaction States

(cont.)Fig.15.0.4

Process

states

and

transitions29Database

System

Concepts

-

Chapter

15

Transactions

-Transaction States

(cont.)mitted

transactionTransactiondisk-buff.diskbegin-trans.allocateresources,e.g.

localbuffer;create

and

start

trans.op1;opn;

commit.activeFig.15.0.5

Life-cycle

ofapartiallycommitcommitreflect

datatodiskreleaseResources;end

trans.

states:opi;

…

opj;e.g.

insert,updatee.g.selectx,yDBMSlocal-buff.Transactiondisk-buff.Diskbegin-trans.op1;opn;

rollbackactive

failedFig.15.0.6

Life-cycle

of

a

rollback

transactionabortedreleaseresources;end

trans.

states:opi;

…

opj;e.g.

insert,updatee.g.selectDBMSlocal-buff.rollback(undo

or

redo)the

previousoperations

allocateresources,e.g.

localbuffer;create

and

start

trans.restoreActivethe

initial

state,

the

transaction

stays

in

this

state

while

it

isexecuting

from

begin-transactioninthis

state,

the

transaction

is

created

(afterbegin-transactionis

submitted),

resources,

e.g.

local

buffer

are

allocated

to

thetransactione.g.Notetransaction

operations

are

executed,

but

the

modifications

onDB

issued

by

operations

may

only

stored

temporally

inthedisk

buffer,not

reflected

toDB

file

ondisksimmedia

yTransaction States

(cont.)32Database

System

Concepts

-

Chapter

15

Transactions

-Partially

committed(部分提交):after the

final

statement

(i.e.

Commit

)

has

been

submitted,

thetransaction

enters

thisstatein

this

state,

the

influences

that

the

transaction’s

operationshave made

onDB

arereflected

from

the

diskbuffertoDB

byDBMS/*DBMS將disk緩沖區(qū)中的DB修改結(jié)果寫入磁盤DB文件中e.g.Transaction States

(cont.)33Database

System

Concepts

-

Chapter

15

Transactions

-Committed

after

the

transaction

has

successfully

completed

all

itsoperations,

andall

the

resultsofthese

operations

have

beenreflected

to

the

DB

in

partial

commit

state,

it

enters

thisstatein

this

state, the

transactionreleases

the

resources

occupiedand

then

terminated

(quits

DBS),thecycle-life

of

thetransaction

is

endede.g.Transaction States

(cont.)34Database

System

Concepts

-

Chapter

15

Transactions

-Failedifit

isdiscovered

that

normal

execution

can

nolongerproceed,thetransaction

enters

thisstatee.g.

Account_transfer

T2inFig.15.0.1in

this

state,

the

transaction

is

rolled

back

to

restore

DB

to

thestate

prior

to

the

start

of

the

transactions

(§17)/*在此狀態(tài)下進(jìn)行失敗處理工作e.g.Fig.15.0.6Transaction States

(cont.)35Database

System

Concepts

-

Chapter

15

Transactions

-Aborted (夭折/異常結(jié)束/中止?fàn)顟B(tài))after

the transaction

has

been

rolled

back

in

failed

state,

andthe

DB

has

been

restored

to

itsstate

prior

to

the

start

ofthetransactions,

it

enters

thisstate

toend

thetransaction/*表示DBMS已完成失敗處理工作,事務(wù)將要退出系統(tǒng)in

thisstate, the

transactionreleases

the

resources

occupiedreportstoitsuserthat the

transaction

is

abortedand

then

terminated

(quits

DBS),

the

cycle-life

ofthe

transaction

is

endede.g.Fig.15.0.6Transaction States

(cont.)36Database

System

Concepts

-

Chapter

15

Transactions

-An

Example

of

Roll

Backin

Transaction37Database

System

Concepts

-

Chapter

15

Transactions

-Roll

back(回滾、滾回)撤銷到目前為止事務(wù)已經(jīng)對數(shù)據(jù)庫做的所有修改，使數(shù)據(jù)庫狀態(tài)恢復(fù)到事務(wù)開始前的狀態(tài)E.g.

define

table

SC

ascreate table

SC(s#

integer,c#

integer,grade

integer,check

(grade

between

0

AND

100

))define

the

updatetransaction

update-tranas:update

SCset

grade

=

grade+5where….s#c#grade1011851022552012752105100401377………510260s#c#grade1011901022602012802105105401377………510260s#c#grade1011851022552012752105100401377………510260(a)

theinitialSC

instance(b)

SC

instance

whenfailure

occurs

duringexecution

oftransaction,egrity

isviolated(c)

SC

instance

afterroll

back,

i.e.

cancelingall

the

updateson

SChavingbeen

made,equal

to

the

initialinstanceupdate

on

some

tuplesrestore/rollback

thetuples

updatedWhen

tuple

1,

2,3

have

been

successfully

updated

and

tuple

4isupdated,

the

valuesof

t4[grade]=105>100,

the

integrityisviolatedDBMS

rollbacks

the

transaction

update-tranrestore

the

values

of

t1[grade],

t2[grade],

t3[grade]andt4[grade]

to

its

initial

values39Database

System

Concepts

-

Chapter

15

Transactions

-An

Example

of

Roll

Backin

Transaction

(cont.)§15.3

Implementation

of

Atomicityand

Durability(略)40Database

System

Concepts

-

Chapter

15

Transactions

-By

shadow

copy

scheme, the

recovery-management

componentof DBMS

can

support

atomicity

anddurability.Simple

but

extremely

inefficient, not

suitable

for

large-scaleDBSa

single

transaction

need

to

copy

the

entire

database

the

implementation

does

not

allow

concurrently

execution

ofmore

than

onetransactionsMany

text

editors

use

thisscheme§15.4

Concurrent

Executions41Database

System

Concepts

-

Chapter

15

Transactions

-Concurrent

executions

ofa

set

oftransactions

allowshigh

throughput

and

resourceutilization, reduced

waitingtimee.g.

the

multi-user

ticket-ordering

systemDemerits

for

allowing

transaction

concurrencyfor

a

set

of

transactions

which

contain

operations

onshareddata, the

different

schedules

(serial,

concurrent)

may

resultin

different

final

DB

states

after

all

these

transactionsterminateConcurrency-control

and

transaction

schedules

are

neededWith

respect

to

a

set

of

transactions,

a

schedule

on

this

set

isthe

execution

sequences

that

indicate

the

chronological

orderin

which

instructions/operations

of

concurrent

transactionsareexecutedarranged

by

DBMS’

concurrency-control

componentnote:a

schedule

for

a

set

of

transactions

must

consist

ofallinstructions

ofthosetransactionsmust

preserve

the

orderin

which

the

instructions

appearineach

individual

transaction.42Database

System

Concepts

-

Chapter

15

Transactions

-15.4

Concurrent Executions

(cont.)T1：

transfer $50funds from

account-A

to

account-BT2:

transfer 10%of

the balancefrom

A

to

B43Database

System

Concepts

-

Chapter

15

Transactions

-initial

value

of A

:$1000initial

value

of B:$2000initial

(A+B)

:$3000AnExampleFinal

results:A=$855,

B=$2145(A

+B)=$3000Fig.15.3-1

Serial

schedule

S1i.e.

T1;

T2A=950,

B=1050T2account-B

DB

file$2000account-A

DB

file$1000$1000$1000$950read(A2)temp:=

A2*0.1A2

:=

A2-temp$950write

(A2)read

(B2)$855B2:=

B2+tempwrite(B2)$2000$2000$2050$2050$2145temp=95,S1:

T1:read(A1)A1:=

A1-50write

(A1)read(B1)B1:=B1+50write(B1)Final

(

A

+

B

)

=$855+

$2145=$3000Fig.15.0.7 ysis

of

serial

schedule

S1time

t46Database

System

Concepts

-

Chapter

15

Transactions

-An

Example(cont.)Fig.15.3-2

Serial

schedule

S2i.e.

T2;

T1After

T1

and

T2

are

finished

under

theconstraints

of

the

scheduleS2,the

sum

of

A

andBis

p

as3000thefinal

value

of

account-A

is

850the

final

value

of

account-Bis

2150Serial

schedule

S1

and

S2

result

indifferent

final

values

of

shareddataitems

A

and

B,though

they

are

all

correctschedulesFinal

results:A=$855,

B=$2145(A

+B)=$3000Fig.15.5

Concurrent

schedule

S3并發(fā)調(diào)度將針對A的2次寫操作、針對B的2次寫操作安排在相近時(shí)間執(zhí)行，利于DBMS在checkpoint時(shí)刻 地將A、B的修改結(jié)果寫回?cái)?shù)據(jù)庫文件，減少DBfile的寫/output操作次數(shù)；類似地，將針對A的2次讀操作、針對B的2次讀操作安排在相近時(shí)間執(zhí)行，有利于減少對DB

file的讀/input操作次數(shù)T2account-B

DB

file$2000account-A

DB

file$1000$1000$1000$950$950$855$2000$2000$2050$2050$2145S3:

T1:read(A1)A1:=

A1-50write(A1)read(A2)=950temp:=

A2*0.1A2

:=

A2-

tempwrite(A2)read(B1)B1:=B1+50write(B1)read(B2)B2:=

B2+tempwrite(B2)temp=95

, final

(

A

+B)=

$855+$2145=$3000Fig.15.0.8 ysis

of

concurrent

schedule

S3time

tFig.15.6

Concurrent

schedule

S4Final

results:A=$950,

B=$2100(A

+B)=

$3050Note:assuming

inFig.15.0.9,read

fetches

data

directlyfrom

DB

file

on

diskwrite

(A1)read(B1)temp:=

A2*0.1=100A2

:=

A2-

temp=900write

(A2)read(B2)=2000B1:=

B1+50=2050write

(B1)B2:=

B2+tempwrite(B2)account-B

DB

file$2000account-A

DB

file$1000$1000$1000$1000$900$950$2000$2000$2000$2050$2100S4:T1:

T2read(A1)A1:=

A1-50

=950read(A2)=1000A1=950,

temp=100, final

(

A

+B

)=$950+

$2100=$3050Fig.15.0.9 ysis

1

of

concurrent

schedule

S4time

tWhy

S3

isrightinS3, T1

and

T2access

shared

data

Aand

Bseriallywith

respect

to

shared

data

A

and

B,

S3

has

thesameexecuting

results

as

serial

S1,

and

S3

is

equivalent

to

serialS1Why

S4

iswrongT1

and

T2

operate

on

shared

data

A

and

B

in

interweaving

(交錯(cuò),交織)waysS4

has

not

the

same

executing

results

as

serial

S1,

and

S4isnot

equivalent

to

serial

S1;S4

leaves

the

database

in

an

inconsistent

state,

and

isolationandconsistency

areviolated51Database

System

Concepts

-

Chapter

15

Transactions

-An

Example

(cont.)§15.5

Serializability/*數(shù)據(jù)庫系統(tǒng)中，多個(gè)事務(wù)的串行執(zhí)行可以保證事務(wù)的

ACID特性（如S1,S2），但執(zhí)行效率低/*多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，如果事務(wù)操作的調(diào)度順序不當(dāng)（如S4），將影響DBS正確性e.g.

S4

in操作并行/交織執(zhí)行/*事務(wù)并發(fā)控制基本原理事務(wù)調(diào)度可串行化:相互 的操作串行執(zhí)行，非e.g.

S3

in52Database

System

Concepts

-

Chapter

15

Transactions

-How

to

identify

whether

or

not

a

concurrent

schedule

S

on

a

setoftransactions

isright

?S

is

equivalent

to

a

serial

one

S’

?/*將對S正確性的判斷轉(zhuǎn)換為對S可串行性的判斷Schedule

equivalence?equivalence/*

view

equivalenceSerializability

(cont.)53Database

System

Concepts

-

Chapter

15

Transactions

-Given

two

transactions

Ti

=

{

Ii

},

Tj

=

{

Ij

},

and

a

schedule

Son

Ti

and

TjDef.

Ii

of

transactions

Ti

and

Ij

of

Tj

are ,

if

andonlyifthere

exists

some

item

Q

accessed

by

both

Ii

and

Ij,andatleast

one

of

these

two

instructions

is

write(Q)i.e.Ii

=

read(Q), Ij

=

write(Q)Ii

=

write(Q),Ij

=

read(Q)Ii

=

write(Q),Ij

=

write(Q)15.5.1

Serializability54Database

System

Concepts

-

Chapter

15

Transactions

-Def.

S

and

S’

are

equivalentif

the

schedule

S

can

be

transformed

into

S’

by

a

series

ofswaps

ofnon- ing

instructionse.g.Fig.15.8S5write(A)read(B)Serializability

(cont.)T1T2read

(A)write(A)read

(B)write(B)read

(A)write(A)read

(B)write(B)Fig.15.9S655Database

System

Concepts

-

Chapter

15

Transactions

-Note:onlyswap of

two

operations/instructions

Iiand

Ij

thatbelong

to

twodifferent

Ti

and

Tj

respectively

arepermittedswap should

not

change

the

orders

ofinstructionof

read(B)

and

write(B)

inT1

isexecuting

ineach

transactione.g.

in

Fig.15.8,swapnotallowedswap should

not

change

the

orders

ofinstructionof

write(A)

in

T1

and

read(A)

inexecuting inS

e.g.

in

Fig.15.8,swapT2

isnotallowedSerializability

(cont.)56Database

System

Concepts

-

Chapter

15

Transactions

-A

concurrent

schedule

S

is

serializable

if

it

isequivalent

to

a

serial

scheduleS’e.g.

concurrent

S3

in

Fig.15.5

is

equivalent

to

S1

inFig.15.3There

are

some

schedules

of

transactions,

which

are

notserializablee.g.T3

T4read(Q)write(Q)write(Q)Serializability

(cont.)57Database

System

Concepts

-

Chapter

15

Transactions

-Given

a

concurrent

schedule

S,

how

to

determine

whether

ornot

S

is serializable

(i.e.

is

right)

?Method

1starting

from

the

concurrent

S,

maintaining

executing

ordersof ing

operations

in

S,andswap

executingordersofnon- ing

operations

in

Sobserving

whether

or

not

a

serial

S’

can

be

obtainedMethod

2precedence-graph

in§15.8Identification

of

Serializability58Database

System

Concepts

-

Chapter

15

Transactions

-

Given

the

following

concurrent

schedule

S

on

transactions

T1,T2,

T3,

and

T4determine

whether

or

not

S

is

-serializable

?

if S

is

-serializable,

give

its

equivalent

serialschedule;

and

if

it

is

not, give

the

reasonIdentification

of

Serializability-An

Example59Database

System

Concepts

-

Chapter

15

Transactions

-Time

T1T2T3T41read(X)2write(X)3write(Y)4read(Y)5

read(Y)6read(X)7write(Z)8

write(X)Fig.15.0.10Answer: S

is

equivalent

to

<T3;

T2;

T4;

T1>Identification

of

Serializability-An

Example

(cont.)60Database

System

Concepts

-

Chapter

15

Transactions

-Testing

for

Serializability-

Precedence-graph

(§15.8)61Database

System

Concepts

-

Chapter

15

Transactions

-Def.

Given

a

schedule

S

of

a

set

of

transactions

T1,T2,...,Tn

,theprecedence

graph(前趨圖)G(S)for

Sisa

direct

graph

G(V,E)

where

the

vertices

are

thetransactionsan

arc

from

Ti

→

Tj

,

for

which

one

of

three

conditions

holdsTi

executes

write(Q)

before

Tj

executes

read(Q),Ti

executes

read(Q)

before

Tj

executes

write(Q)Ti

executes

write(Q)

before

Tj

executes

write(Q)Tiwrite(Q)....Tj.Tiread(Q)....Tj.Tiwrite(Q).....Tj.Fig.

15.0.11

Cases

for

arc

Ti

→

Tj

in

precedence

graphs..read(Q)..(a)..write(Q)..(b)..write(Q)..(c)Testing

for

Serializability-

Precedence-graph

(cont.)t62Database

System

Concepts

-

Chapter

15

Transactions

-63serializ