北邮-数据库系统原理英文

PART

5TRANSACTION

MANAGEMENTC,Pascal

programs词法/语法/语义分析中间代码生成(中间)代码优化目标代码生成//OS进程管理&并发进控程制调度死锁处理query扫描和语法/语义分析查询优化(优化后)查询执行计划查询代码生成Query

processing

/

DBMSprocess

/

thread事务处理/

DBMSChapter.13,14transaction关系代数表达式&查询树查询计划执行的代码事务管理目标程序代码(§14)&度并发事控务制调死锁处理(§13)(§15)(§16)恢复技术(§17)Chapter.15,16,17Fig.

13.0.1DBS中，从DBMS的角度，用户对DB的 体现为DBS中1个或多个事务的执行事务是DBS中应用程序/数据库应用系统的基本逻辑单位，也是DBMS管理DBS运行的基本单位,§15.1体现为DBS中多多用户DBS中，多个用户对DB的并发个数据库事务的并发执行事务是动态的，具有一定生命周期事务具有多种状态，事务的执行体现为各状态间的转换过程,§15.2,Fig.15.1Introduction

to

Part

53Database

System

Concepts

-

Chapter

15

Transactions

-在DBS中，事务执行时，特别是当多个事务对共享数据进行并发 时，为

DBS系统中数据的正确性(integrities)，事务必须满足一定的约束条件，表现为事务的4个基本特征(ACID)

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

性/

持续性/操作结果

保持性

(durability)DBMS中的recovery-managementcomponent负责保障事务的原子性。§15.3,§17事务设计者/DBS应用程序编程者负责保障事务的一致性(P611)Introduction

to

Part

5

(cont.)4Database

System

Concepts

-

Chapter

15

Transactions

-DBMS中的concurrency-control

component负责保障事务的独立性。§16DBMS中的recovery-management

component负责保障事务的永久性。§15.3,§17当DBS中存在多个并发事务时，DBMS通过事务调度对各事务进行并发控制(§15.4)，以保证并发事务的运行结果正确性DBMS中的concurrency-controlcomponent依据事务调度可串行性（Serializability)的基本原理，对事务进行并发控制和调度,§15.5,15.6,15.75Database

System

Concepts

-

Chapter

15

Transactions

-Introduction

to

Part

5

(cont.)具体实现技术包括基于锁的并发控制技术(§16.1)、基于时间戳的并发控制技术(§16.2)

、基于验证的并发控制技术

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

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

component还需要对多个并发执行的事务进行死锁处理(§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

的修改,即恢复loan_A

的原值，并立即结束T2，不再执行其后的各操作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) /*事务变量定义*/SET

@transfer_name

=

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

@transfer_name/*事务命名*//*事务开始*/USE

ACCOUNTGOUPDATE

account_A/*打开数据库ACCOUNT*//*将上述批SQL语句提交SQLServer*//*

修改A帐户*/SET balance

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

修改B帐户*/UPDATESETaccount_Bbalance

=balance

+50/*事务提交*/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个事务的正确执行使得DB从一个正确状态转移到另一个正确状态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/*事务执行过程中，完整性约束有可能被破坏20Database

System

Concepts

-

Chapter

15

Transactions

-Transaction

Properties

(cont.)Atomicityeither

all

operations

ofthetransaction

are

reflected

(

)properly

inthe

database,

or noneare/*事务中所有操作或者全部成功完成，并且这些操作结果被写入到DB；或者事务中的所有操作一个都不作,该事务对数据库和其他事务没有任何影响/*将有操作作为1个不可分割的整体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/*对多个并发执行的事务，1个事务的执行不能被其他事务干扰，即1个事物的 操作和数据对其它事务是的，并发执行的事务间不能相互干扰，从执行结果来看，相当于事务串行执行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/*事务一旦提交（成功完成），它对数据库中数据的改变就应该是性的，这些改变不随其后的数据库系统错误而丢失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缓冲区中的DB修改结果写入磁盘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)/*在此状态下进行失败处理工作e.g.Fig.15.0.6Transaction States

(cont.)35Database

System

Concepts

-

Chapter

15

Transactions

-Aborted (夭折/异常结束/中止状态)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已完成失败处理工作,事务将要退出系统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(回滚、滚回)撤销到目前为止事务已经对数据库做的所有修改，使数据库状态恢复到事务开始前的状态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并发调度将针对A的2次写操作、针对B的2次写操作安排在相近时间执行，利于DBMS在checkpoint时刻 地将A、B的修改结果写回数据库文件，减少DBfile的写/output操作次数；类似地，将针对A的2次读操作、针对B的2次读操作安排在相近时间执行，有利于减少对DB

file的读/input操作次数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

(交错,交织)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/*数据库系统中，多个事务的串行执行可以保证事务的

ACID特性（如S1,S2），但执行效率低/*多个事务并发执行时，如果事务操作的调度顺序不当（如S4），将影响DBS正确性e.g.

S4

in操作并行/交织执行/*事务并发控制基本原理事务调度可串行化:相互 的操作串行执行，非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正确性的判断转换为对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