浙江大学数据库系统概念

©Silberschatz,

Korth

and

Sudarshan,

Bo15

.

1Database

System

ConceptsChapter

15:

Transactionsn

Transaction

Conceptn

Concurrent

Executionsn

Serializabilityn

Testing

for

Serializabilityn

Recoverabilityn

Transaction

Definition

in

SQLTransaction

Conceptn

E.g.

Transaction

to

transfer

$50

from

account

A

to

accountB:1.2.read(A)A

:=

A

–

50read(B)B

:=B

+

503.write(A)6.

write(Bn

A

transaction

is

a

unit

of

program

execution

that

accessesand

possibly

updates

various

data

items.ê

A

transaction

must

see

a

consistent

database.ê

During

transaction

execution

the

database

may

beinconsistent.ê

When

the

transaction

is

committed,

the

database

must

beconsistent.n

Two

main

issues

to

deal

with:ê

Failures

of

various

kinds,

such

as

hardware

failures

andsystem

crashesDatabase

System

Concepts

ê

Concurrent

execution

o1f5

.m1

ultiple

trans©aScitl

bieornssc

hatz,

Korth

and

Sudarshan,

BoACID

PropertiesDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoTo

preserve

integrity

of

data,

the

database

system

must

ensure:n

Atomicity.

Either

all

operations

of

the

transactionare

properly

reflected

in

the

database

or

none

are.ê

Commit

a

transactionê

Rollback

a

transactionn

Consistency.

Execution

of

a

transaction

in

isolationpreserves

the

consistency

of

the

database.n

Isolation.

Although

multiple

transactions

mayexecute

concurrently,

each

transaction

must

be

unawareof

other

concurrently

executing

transactions.Intermediate

transaction

results

must

be

hidden

fromother

concurrently

executed

transactions.n

Durability.

After

a

transaction

completessuccessfully,

the

changes

it

has

made

to

the

databasepersist,

even

if

there

are

system

failures.Example

of

Fund

TransferDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Transaction

to

transfer

$50

from

account

A

to

accountB:1.2.3.4.5.6.read(A)A

:=

A

–

50write(A)read(B)B

:=

B

+

50write(B)n

Consistency

requirement

–

the

sum

of

A

and

B

isunchanged

by

the

execution

of

the

transaction.n

Atomicity

requirement

—

if

the

transaction

fails

afterstep

3

and

before

step

6,

the

system

should

ensure

thatits

updates

are

not

reflected

in

the

database,

else

aninconsistency

will

result.ê

Failure

could

be

due

to

software

or

hardwareExample

of

Fund

Transfer

(Cont.)Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Durability

requirement

—

once

the

user

has

beennotified

that

the

transaction

has

completed

(i.e.,

thetransfer

of

the

$50

has

taken

place),

the

updates

tothe

database

by

the

transaction

must

persist

despitefailures.n

Isolation

requirement

—

if

between

steps

3

and

6,another

transaction

is

allowed

to

access

the

partiallyupdated

database,

it

will

see

an

inconsistent

database(the

sum

A

+

B

will

be

less

than

it

should

be).ê

Can

be

ensured

trivially

by

running

transactionsserially,

that

is

one

after

the

other.ê

However,

executing

multiple

transactions

concurrentlyhas

significant

benefits,

as

we

will

see.Concurrent

ExecutionsDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Multiple

transactions

are

allowed

to

run

concurrentlyin

the

system.

Advantages

are:ê

increased

processor

and

disk

utilization,

leading

tobetter

transaction

throughput:

one

transaction

can

be

usingthe

CPU

while

another

is

reading

from

or

writing

to

the

diskê

reduced

average

response

time

for

transactions:short

transactions

need

not

wait

behind

long

ones.n

Concurrency

control

schemes

–

mechanisms

toachieve

isolation,

i.e.,

to

control

the

interaction

amongthe

concurrent

transactions

in

order

to

prevent

themfrom

destroying

the

consistency

of

the

databaseT1T21Read(x)2Read(x)3X

=

x+1n

Dirt4y

Read:Write(x)X

=

x*25Write(x)1Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoTC1onsisteTn2cy

problems

of

concurrentWrite(T)

Execution

without

control2n

Lost

moRdeiafidc(aTt)ion:3

rollbacky

problems

(Cont.)Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoreadT1

ConsisTt2

enc1Read(x)2n

Non

repeWarittaeb(lx)e3Read(x)X

?SchedulesDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Schedules

–

sequences

that

indicate

the

chronologicalorder

in

which

instructions

of

concurrent

transactions

areexecutedê

a

schedule

for

a

set

of

transactions

must

consist

of

allinstructions

of

those

transactionsê

must

preserve

the

order

in

which

the

instructions

appear

ineach

individual

transaction.n

Some

notions:ê

Serial

Scheduleê

Equivalent

scheduleê

Serializable

ScheduleExample

Schedulesn

Let

T1

transfer

$50

from

A

to

B,

and

T2

transfer10%

of

the

balance

from

A

to

B.

The

following

isa

serial

schedule

(Schedule

1

in

the

text),

in

whichT1

is

followed

by

T2.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoExample

Schedule

(Cont.)n

Let

T1

and

T2

be

the

transactions

defined

previously.The

following

schedule

(Schedule

3

in

the

text)

is

not

aserial

schedule,

but

it

is

equivalent

to

Schedule

1.n

In

both

Schedule

1

and

3,

the

sum

A

+

B

is

preserved.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoExample

Schedules

(Cont.)n

The

following

concurrent

schedule

(Schedule

4in

the

text)

does

not

preserve

the

value

of

the

thesum

A

+

B.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoSerializabilityDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Basic

Assumptionê

Each

transaction

preserves

database

consistency.ê

We

ignore

operations

other

than

read

and

write

instructions,and

we

assume

that

transactions

may

perform

arbitrarycomputations

on

data

in

local

buffers

in

between

reads

and

writes.Our

simplified

schedules

consist

of

only

read

and

write

instructions.n

Thus

serial

execution

of

a

set

of

transactions

preservesdatabase

consistency.n

A

(possibly

concurrent)

schedule

is

serializable

if

it

isequivalent

to

a

serial

schedule.n

How

to

determine

a

schedule

is

equivalent

to

a

serialschedule?ê

Different

forms

of

schedule

equivalence

give

rise

to

the

notionsof:1.2.conflict

serializabilityview

serializabilityConflict

SerializabilityDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Instructions

li

and

lj

of

transactions

Ti

and

Tj

respectively,conflict

if

and

only

if

there

exists

some

item

Q

accessed

byboth

liand

lj,

and

atleast

one

of

these

instructions

wrote

Q.1.li

=

read(Q),lj

=

read(Q).

li

and

lj

don’t

conflict.2.

li=read(Q),

lj=write(Q).Theyconflict.3.

li=write(Q),

lj=read(Q).Theyconflict4.

li=write(Q),

lj=write(Q).Theyconflictn

Intuitively,

a

conflict

between

li

and

lj

forces

a

(logical)temporal

order

between

them.

If

li

and

lj

are

consecutive

ina

schedule

and

they

do

not

conflict,

their

results

wouldremain

the

same

even

if

they

had

been

interchanged

in

theschedule.Conflict

Serializability

(Cont.)n

If

a

schedule

S

can

be

transformed

into

a

scheduleS´

by

a

series

of

swaps

of

non-conflicting

instructions,we

say

that

S

and

S´

are

conflict

equivalent.n

We

say

that

a

schedule

S

is

conflict

serializable

ifit

is

conflict

equivalent

to

a

serial

schedulen

Example

of

a

schedule

that

is

not

conflictserializable:read(Q)T3

T4write(Q)write(Q)We

are

unable

to

swap

instructions

in

the

aboveschedule

to

obtain

either

the

serial

schedule

<

T3,

T4>,

or

the

serial

schedule

<

T4,

T3

>.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoConflict

Serializability

(Cont.)n

Schedule

3

below

can

be

transformed

into

Schedule1,

a

serial

schedule

where

T2

follows

T1,

by

series

ofswaps

of

non-conflicting

instructions.

Therefore

Schedule3

is

conflict

serializable.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoView

SerializabilityDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Let

S

and

S´

be

two

schedules

with

the

same

set

oftransactions.

S

and

S´

are

view

equivalent

if

the

followingthree

conditions

are

met:For

each

data

item

Q,

if

transaction

Ti

reads

theinitial

value

of

Q

in

schedule

S,

then

transaction

Ti

must,

inschedule

S´,

also

read

the

initial

value

of

Q.For

each

data

item

Q

if

transaction

Ti

executesread(Q)

in

schedule

S,

and

that

value

was

produced

bytransaction

Tj

(if

any),

then

transaction

Ti

must

in

schedule

S´also

read

the

value

of

Q

that

was

produced

by

transaction

Tj.For

each

data

item

Q,

the

transaction

(if

any)

thatperforms

the

final

write(Q)

operation

in

schedule

S

mustperform

the

final

write(Q)

operation

in

schedule

S´.As

can

be

seen,

view

equivalence

is

also

based

purelyon

readsand

writes

alone.View

Serializability

(Cont.)it

is

view

equivalentn

A

schedule

S

is

view

serializableto

a

serial

schedule.n

Every

conflict

serializable

schedule

is

also

viewserializable.n

Schedule

9

(from

text)

—

a

schedule

which

is

view-serializable

but

not

conflict

serializable.n

Every

view

serializable

schedule

that

is

not

conflictserializable

has

blind

writes

(write(Q)

without

havingperformed

a

read(Q)

operation).Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoOther

Notions

of

Serializabilityn

Schedule

8

(from

text)

given

below

producessame

outcome

as

the

serial

schedule

<

T1,

T5

>,yet

is

not

conflict

equivalent

or

view

equivalent

toit.n

Determining

such

equivalence

requires

analysisof

operations

other

than

read

and

write.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoTesting

for

Conflict

Serializabilityn

Consider

some

schedule

of

a

set

of

transactionsT1,

T2,

...,

Tnn

Precedence

graph

—

a

direct

graph

where

thevertices

are

the

transactions

(names).n

We

draw

an

arc

from

Ti

to

Tj

if

the

twotransaction

conflict,

and

Ti

accessed

the

data

itemon

which

the

conflict

arose

earlier.n

We

may

label

the

arc

by

the

item

that

wasaccessed.n

Example

1xyDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoExample

Schedule

(Schedule

A)T1

T2

T3T4

T5read(X)read(Y)read(Z)read(V)read(W)read(W)read(Y)write(Y)write(Z)read(U)read(Y)write(Y)read(Z)Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoPrecedence

Graph

for

Schedule

AT3T4T1T2T5Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoTest

for

Conflict

SerializabilityDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

A

schedule

is

conflict

serializable

if

and

only

if

itsprecedence

graph

is

acyclic.n

If

precedence

graph

is

acyclic,

the

serializability

order

canbe

obtained

by

a

topological

sorting

of

the

graph.

This

is

alinear

order

consistent

with

the

partial

order

of

the

graph.For

example,

a

serializability

order

for

Schedule

A

would

beT5

T1

T3

T2

T4

orTestsDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Testing

a

schedule

for

serializability

after

it

has

executedis

a

little

too

late!n

Goal

–

to

develop

concurrency

control

protocols

that

willassure

serializability.ê

They

will

generally

not

examine

the

precedence

graph

as

itis

being

created;ê

instead

a

protocol

will

impose

a

discipline

that

avoidsnonseralizable

schedules.ê

Will

study

such

protocols

in

Chapter

16.n

Different

concurrency

control

protocols

provide

differenttradeoffs

between

the

amount

of

concurrency

they

allow

andthe

amount

of

overhead

that

they

incur.n

Tests

for

serializability

help

understand

why

aconcurrency

control

protocol

is

correct.Recoverabilityn

If

T8

should

abort,

T9

would

have

read

(and

possiblyshown

to

the

user)

an

inconsistent

database

state.

Hencedatabase

must

ensure

that

schedules

are

recoverable.Need

to

address

the

effect

of

transaction

failures

on

concurrentlyrunning

transactions.n

Recoverable

schedule

—

if

a

transaction

Tj

reads

adata

items

previously

written

by

a

transaction

Ti

,

the

commitoperation

of

Ti

appears

before

the

commit

operation

of

Tj.n

The

following

schedule

(Schedule

11)

is

not

recoverable

ifT9

commits

immediately

after

the

readDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoRecoverability

(Cont.)n

Cascading

rollback

–

a

single

transaction

failure

leads

toa

series

of

transaction

rollbacks.

Consider

the

followingschedule

where

none

of

the

transactions

has

yet

committed(so

the

schedule

is

recoverable)If

T10

fails,

T11

and

T12

must

also

be

rolled

back.n

Can

lead

to

the

undoing

of

a

significant

amount

of

workn

Theoretically,

it

is

not

mandatory

to

avoid

cascadingrollback.Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

BoRecoverability

(Cont.)Database

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Cascadeless

schedules

—

cascading

rollbacks

cannotoccur;

for

each

pair

of

transactions

Ti

and

Tj

such

that

Tjreads

a

data

item

previously

written

by

Ti,

the

commitoperation

of

Ti

appears

before

the

read

operation

of

Tj.n

Every

cascadeless

schedule

is

recoverablen

It

is

desirable

to

restrict

the

schedules

to

those

that

arecascadelessTransaction

Definition

in

SQLDatabase

System

Concepts15

.

1©Silberschatz,

Korth

and

Sudarshan,

Bon

Data

manipulation

language

must

include

a

construct

forspecifying

the

set

of

actions

that

comprise

a

transaction.n

InSQL,a

transaction

begins

implicitly.êSomecommercial

DBMS

support

BEGIN

TRANSACTION;êAutoCommit

p