山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)據(jù)庫系統(tǒng)英文課件 ch14

DatabaseSystem

Concepts,

6th

Ed.?Silberschatz,

Korth

and

SudarshanSee

www.db-

for

conditions

on

re-useChapter

14:

TransactionsChapter

14:14

.

2?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionTransactionsn

Transaction

Conceptn

Transaction

Staten

Concurrent

Executionsn

Serializabilityn

Recoverabilityn

Implementation

of

Isolationn

Transaction

Definition

in

SQLn

Testing

for

Serializability.Transaction

Concept14

.

3?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

A

transaction

is

a

unit

of

program

execution

that

accessesand

possibly

updates

various

data

items.n

E.g.transaction

to

transfer$50fromaccountAtoaccountB:1.read(A)2.A

:=

A

–

503.write(A)4.read(B)5.B

:=

B

+

506.write(B)n

Two

main

issues

to

deal

with:l

Failures

of

various

kinds,

such

as

hardware

failures

andsystem

crashesl

Concurrent

execution

of

multiple

transactionsExample

of

Fund

Transfer14

.

4?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Transaction

to

transfer

$50

from

account

A

to

account

B:read(A)A

:=

A

–

50write(A)read(B)B

:=

B

+

50write(B)n

Atomicity

requirementl

if

the

transaction

fails

after

step

3

and

before

step

6,

money

will

be“l(fā)ost”

leading

to

an

inconsistent

database

state4

Failure

could

be

due

to

software

or

hardwarel

the

system

should

ensure

that

updates

of

a

partially

executedtransaction

are

not

reflected

in

the

databasen

Durability

requirement

—

once

the

user

has

been

notified

that

thetransaction

has

completed

(i.e.,

the

transfer

of

the

$50

has

taken

place),the

updates

to

the

database

by

the

transaction

must

persist

even

if

thereare

software

or

hardware

failures.Example

of

Fund

Transfer

(Cont.)14

.

5?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Transaction

to

transfer

$50

from

account

A

to

account

B:read(A)A

:=

A

–

50write(A)read(B)B

:=

B

+

50write(B)n

Consistency

requirement

in

above

example:lthe

sum

of

A

and

B

is

unchanged

by

the

execution

of

the

transactionn

In

general,

consistency

requirements

include4

Explicitly

specified

integrity

constraints

such

as

primary

keys

andforeign

keys4

Implicit

integrity

constraints–

e.g.

sum

of

balances

of

all

accounts,

minus

sum

of

loanamounts

must

equal

value

of

cash-in-handl

A

transaction

must

see

a

consistent

database.l

During

transaction

execution

the

database

may

be

temporarilyinconsistent.l

When

the

transaction

completes

successfully

the

database

must

beconsistent4

Erroneous

transaction

logic

can

lead

to

inconsistencyExample

of

Fund

Transfer

(Cont.)14

.

6?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Isolation

requirement

—

if

between

steps

3

and

6,

anothertransaction

T2

is

allowed

to

access

the

partially

updateddatabase,

it

will

see

an

inconsistent

database

(the

sum

A

+

B

will

be

less

than

it

should

be).T2T1read(A)A

:=

A

–

50write(A)read(A),

read(B),

print(A+B)read(B)B

:=

B

+

50write(Bn

Isolation

can

be

ensured

trivially

by

running

transactions

serialll

that

is,

one

after

the

other.n

However,

executing

multiple

transactions

concurrently

hassignificant

benefits,

as

we

will

see

later.ACID

Properties14

.

7?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionA

transaction

is

a

unit

of

program

execution

that

accesses

andpossibly

updates

various

data

items.To

preserve

the

integrity

of

datadatabase

system

must

ensure:n

Atomicity.

Either

all

operations

of

the

transaction

are

properlyreflected

in

the

database

or

none

are.n

Consistency.

Execution

of

a

transaction

in

isolation

preserves

tconsistency

of

the

database.n

Isolation.

Although

multiple

transactions

may

execute

concurrenteach

transaction

must

be

unaware

of

other

concurrently

executingtransactions.

Intermediate

transaction

results

must

be

hidden

froother

concurrently

executed

transactions.l

That

is,

for

every

pair

of

transactions

Ti

and

Tj,

it

appears

tthat

either

Tj,

finished

execution

before

Ti

started,

or

Tj

starexecution

after

Ti

finished.n

Durability.

After

a

transaction

completes

successfully,

the

chanit

has

made

to

the

database

persist,

even

if

there

are

systemfailures.Transaction

State14

.

8?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Active

–

the

initial

state;

the

transaction

stays

in

this

statewhile

it

is

executingn

Partially

committed

–

after

the

final

statement

has

beenexecuted.n

Failed

--

after

the

discovery

that

normal

execution

can

nolonger

proceed.n

Aborted

–

after

the

transaction

has

been

rolled

back

and

thedatabase

restored

to

its

state

prior

to

the

start

of

thetransaction.

Two

options

after

it

has

been

aborted:l

restart

the

transaction4

can

be

done

only

if

no

internal

logical

errorl

kill

the

transactionn

Committed

–

after

successful

completion.Transaction

State

(Cont.)14

.

9?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionConcurrent

Executions14

.

10?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Multiple

transactions

are

allowed

to

run

concurrently

in

thesystem.

Advantages

are:l

increased

processor

and

disk

utilization,

leading

to

bettertransaction

throughput4

E.g.

one

transaction

can

be

using

the

CPU

whileanother

is

reading

from

or

writing

to

the

diskl

reduced

average

response

time

for

transactions:

shorttransactions

need

not

wait

behind

long

ones.n

Concurrency

control

schemes

–

mechanisms

to

achieveisolationl

that

is,

to

control

the

interaction

among

the

concurrenttransactions

in

order

to

prevent

them

from

destroying

theconsistency

of

the

database4

Will

study

in

Chapter

16,

after

studying

notion

ofcorrectness

of

concurrent

executions.Schedules14

.

11?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Schedule

–

a

sequences

of

instructions

that

specify

thechronological

order

in

which

instructions

of

concurrent

transactioare

executedl

a

schedule

for

a

set

of

transactions

must

consist

of

allinstructions

of

those

transactionsl

must

preserve

the

order

in

which

the

instructions

appear

ineach

individual

transaction.n

A

transaction

that

successfully

completes

its

execution

will

havecommit

instructions

as

the

last

statementl

by

default

transaction

assumed

to

execute

commit

instructionas

its

last

stepn

A

transaction

that

fails

to

successfully

complete

its

execution

wihave

an

abort

instruction

as

the

last

statementSchedule

1n

Let

T1

transfer

$50

from

A

to

B,

and

T2

transfer

10%of

the

balance

from

A

to

B.n

A

serial

schedule

in

which

T1

is

followed

by

T2

:14

.

12?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSchedule

2A

serial

schedule

where

T2

is

followed

by

T114

.

13?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSchedule

3n

Let

T1and

T2

be

the

transactions

defined

previously.The

followingscheduleisnotaserialschedule,butitisequivalent

toSchedule1.In

Schedules

1,

2

and

3,

the

sum

A

+

B

is

preserved.14

.

14?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSchedule

4n

The

following

concurrent

schedule

does

not

preserve

thevalue

of

(A

+

B).14

.

15?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionSerializability14

.

16?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Basic

Assumption

–

Each

transaction

preserves

databaseconsistency.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.

Different

forms

ofschedule

equivalence

give

rise

to

the

notions

of:conflict

serializabilityview

serializabilitySimplified

view

of

transactions14

.

17?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionl

We

ignore

operations

other

than

read

and

writeinstructionsl

We

assume

that

transactions

may

perform

arbitrarycomputations

on

data

in

local

buffers

in

betweenreads

and

writes.l

Our

simplified

schedules

consist

of

only

read

andwrite

instructions.Conflicting

Instructions14

.

18?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Instructions

li

and

lj

of

transactions

Ti

and

Tj

respectively,conflict

if

and

only

if

there

exists

some

item

Q

accessed

byboth

li

and

lj,

and

at

least

one

of

these

instructions

wrote

Q.1.

li

=

read(Q),

lj

=

read(Q).li

and

lj

don’t

conflict.They

conflict.They

conflictThey

conflictli

=

read(Q),

ljli

=

write(Q),

ljli

=

write(Q),

lj=

write(Q).=

read(Q).=

write(Q).n

Intuitively,

a

conflict

between

li

and

lj

forces

a

(logical)temporal

order

between

them.l

If

li

and

lj

are

consecutive

in

a

schedule

and

they

donot

conflict,

their

results

would

remain

the

same

even

ifthey

had

been

interchanged

in

the

schedule.Conflict

Serializability14

.

19?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

If

a

schedule

S

can

be

transformed

into

a

schedule

S′

by

aseries

of

swaps

of

non-conflicting

instructions,

we

say

that

S

andS′

are

conflict

equivalent.n

We

say

that

a

schedule

S

is

conflict

serializable

if

it

is

confliequivalent

to

a

serial

scheduleConflict

Serializability

(Cont.)n

Schedule

3

can

be

transformed

into

Schedule

6,

a

serialschedule

where

T2

follows

T1,

by

series

of

swaps

ofnon-conflicting

instructions.

Therefore

Schedule

3

isconflict

serializable.Schedule

3Schedule

614

.

20?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionConflict

Serializability

(Cont.)n

Example

of

a

schedule

that

is

not

conflict

serializable:n

We

are

unable

to

swap

instructions

in

the

above

scheduleto

obtain

either

the

serial

schedule

<

T3,

T4

>,

or

the

serialschedule

<

T4,

T3

>.14

.

21?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionView

Serializability14

.

22?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

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,1.

If

in

schedule

S,

transaction

Ti

reads

the

initial

value

of

Q,must

read

thethen

in

schedule

S’

also

transaction

Tiinitial

value

of

Q.2.

If

in

schedule

S

transaction

Ti

executes

read(Q),

and

thatvalue

was

produced

by

transaction

Tj

(if

any),

then

inschedule

S’

also

transaction

Ti

must

read

the

value

of

Q

that

was

produced

by

the

same

write(Q)

operation

oftransaction

Tj

.3.

The

transaction

(if

any)

that

performs

the

final

write(Q)operation

in

schedule

S

must

also

perform

the

final

write(Q)operation

in

schedule

S’.As

can

be

seen,

view

equivalence

is

also

based

purely

on

readsand

writes

alone.View

Serializability

(Cont.)n

A

schedule

S

is

view

serializable

if

it

is

view

equivalent

to

aserial

schedule.n

Every

conflict

serializable

schedule

is

also

view

serializable.n

Below

is

a

schedule

which

is

view-serializable

but

not

conflictserializable.n

What

serial

schedule

is

above

equivalent

to?n

Every

view

serializable

schedule

that

is

not

conflict

serializableblind

writes.14

.

23?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionOther

Notions

of

Serializabilityn

The

schedule

below

produces

same

outcome

as

the

serialschedule

<

T1,T5

>,

yet

is

not

conflict

equivalent

or

viewequivalent

to

it.n

Determining

such

equivalence

requires

analysis

ofoperations

other

than

read

and

write.14

.

24?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionTesting

for

Serializabilityn

Consider

some

schedule

of

a

set

of

transactions

T1,

T2,...,

Tnn

Precedence

graph

—

a

directed

graph

where

thevertices

are

the

transactions

(names).n

We

draw

an

arc

from

Ti

to

Tj

if

the

two

transactionconflict,

and

Ti

accessed

the

data

item

on

which

theconflict

arose

earlier.n

We

may

label

the

arc

by

the

item

that

was

accessed.n

Example

114

.

25?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionTest

for

Conflict

Serializabilityn

A

schedule

is

conflict

serializable

if

andonly

if

its

precedence

graph

is

acyclic.n

Cycle-detection

algorithms

exist

whichtake

order

n2

time,

where

n

is

thenumber

of

vertices

in

the

graph.l

(Better

algorithms

take

order

n

+

ewhere

e

is

the

number

of

edges.)n

If

precedence

graph

is

acyclic,

theserializability

order

can

be

obtained

by

atopological

sorting

of

the

graph.l

This

is

a

linear

order

consistent

withthe

partial

order

of

the

graph.l

For

example,

a

serializability

order

forSchedule

A

would

beT5

T1

T3

T2

T44

Are

there

others?14

.

26?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionTest

for

View

Serializability14

.

27?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

The

precedence

graph

test

for

conflict

serializability

cannot

beused

directly

to

test

for

view

serializability.l

Extension

to

test

for

view

serializability

has

cost

exponentiathe

size

of

the

precedence

graph.n

The

problem

of

checking

if

a

schedule

is

view

serializable

falls

ithe

class

of

NP-complete

problems.l

Thus

existence

of

an

efficient

algorithm

is

extremely

unlikeln

However

practical

algorithms

that

just

check

some

sufficientconditions

for

view

serializability

can

still

be

used.Recoverable

SchedulesNeed

to

address

the

effect

of

transaction

failures

on

concurrentlyrunning

transactions.n

Recoverable

schedule

—

if

a

transaction

Tj

reads

a

data

itempreviously

written

by

a

transaction

Ti

,

then

the

commit

operationTi

appears

before

the

commit

operation

of

Tj.n

The

following

schedule

(Schedule

11)

is

not

recoverable

if

T9commits

immediately

after

the

readn

If

T8

should

abort,

T9

would

have

read

(and

possibly

shown

to

theuser)

an

inconsistent

database

state.

Hence,

database

mustensure

that

schedules

are

recoverable.14

.

28?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionCascadeless

Schedules14

.

30?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Cascadeless

schedules

—

cascading

rollbacks

cannot

occur;

foreach

pair

of

transactions

Ti

and

Tj

such

that

Tj

reads

a

dataitem

previously

written

by

Ti,

the

commit

operation

of

Ti

appearsbefore

the

read

operation

of

Tj.n

Every

cascadeless

schedule

is

also

recoverablen

It

is

desirable

to

restrict

the

schedules

to

those

that

arecascadelessConcurrency

Control14

.

31?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

A

database

must

provide

a

mechanism

that

will

ensure

that

allpossible

schedules

arel

either

conflict

or

view

serializable,

andl

are

recoverable

and

preferably

cascadelessn

A

policy

in

which

only

one

transaction

can

execute

at

a

timegenerates

serial

schedules,

but

provides

a

poor

degree

ofconcurrencyl

Are

serial

schedules

recoverable/cascadeless?n

Testing

a

schedule

for

serializability

after

it

has

executed

is

atoo

late!n

Goal

–

to

develop

concurrency

control

protocols

that

will

assureserializability.Concurrency

Control

(Cont.)14

.

32?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Schedules

must

be

conflict

or

view

serializable,

andrecoverable,

for

the

sake

of

database

consistency,

andpreferably

cascadeless.n

A

policy

in

which

only

one

transaction

can

execute

at

a

timegenerates

serial

schedules,

but

provides

a

poor

degree

ofconcurrency.n

Concurrency-control

schemes

tradeoff

between

the

amount

ofconcurrency

they

allow

and

the

amount

of

overhead

that

theyincur.n

Some

schemes

allow

only

conflict-serializable

schedules

to

begenerated,

while

others

allow

view-serializable

schedules

thatare

not

conflict-serializable.Tests14

.

33?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Concurrency-control

protocols

allow

concurrent

schedules,

butensure

that

the

schedules

are

conflict/view

serializable,

and

arerecoverable

and

cascadeless

.n

Concurrency

control

protocols

generally

do

not

examine

theprecedence

graph

as

it

is

being

createdl

Instead

a

protocol

imposes

a

discipline

that

avoidsnonseralizable

schedules.l

We

study

such

protocols

in

Chapter

16.n

Different

concurrency

control

protocols

provide

different

tradeoffbetween

the

amount

of

concurrency

they

allow

and

the

amount

ofoverhead

that

they

incur.n

Tests

for

serializability

help

us

understand

why

a

concurrencycontrol

protocol

is

correct.Weak

Levels

of

Consistency14

.

34?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Some

applications

are

willing

to

live

with

weak

levels

ofconsistency,

allowing

schedules

that

are

not

serializablel

E.g.

a

read-only

transaction

that

wants

to

get

an

approximatetotal

balance

of

all

accountsl

E.g.

database

statistics

computed

for

query

optimization

canbe

approximate

(why?)l

Such

transactions

need

not

be

serializable

with

respect

toother

transactionsn

Tradeoff

accuracy

for

performanceLevels

of

Consistency

in

SQL-9214

.

35?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Serializable

—

defaultn

Repeatable

read

—

only

committed

records

to

be

read,

repeatedreads

of

same

record

must

return

same

value.

However,

atransaction

may

not

be

serializable

–

it

may

find

some

recordsinserted

by

a

transaction

but

not

find

others.n

Read

committed

—

only

committed

records

can

be

read,

butsuccessive

reads

of

record

may

return

different

(but

committed)values.n

Read

uncommitted

—

even

uncommitted

records

may

be

read.n

Lower

degrees

of

consistency

useful

for

gathering

approximateinformation

about

the

databasen

Warning:

some

database

systems

do

not

ensure

serializableschedules

by

defaultl

E.g.

Oracle

and

PostgreSQL

by

default

support

a

level

ofconsistency

called

snapshot

isolation

(not

part

of

the

SQLstandard)Transaction

Definition

in

SQL14

.

36?Silberschatz,

Korth

and

Suda

rDatabase

System

Concepts

-6

t

hEditionn

Data

manipulation

language

must

include

a

construct

forspecifying

the

set

of

actions

that

comprise

a

transaction.n