=DU]G]DQLHZVSyáELH*QRFLWUDQVDNFML

Tomasz Koszlajda

,QVW\WXW,QIRUPDW\NL3ROLWHFKQLNL3R]QDVNLHM

e-mail: [e-mail]

1.

:VWS

-HGQ\P]SRWHQFMDOQ\FK(UyGHáEáGyZGDQ\FKSU]HFKRZ\ZDQ\FKZED]DFKGDQ\FKVQLHSR*-

GDQH LQWHUIHUHQFMH PLG]\ DV\QFKURQLF]Q\PL RSHUDFMDPL ZVSyáELH*QLH Z\NRQ\ZDQ\FK WUDQVDNFML

7HRULD V\VWHPyZ ED] GDQ\FK MX* Z ODWDFK VLHGHPG]LHVLW\FK L RVLHPG]LHVLW\FK ]LGHQW\ILNRZDáD

SUREOHP]DU]G]DQLDZVSyáELH*QRFLWUDQVDNFMLL]DSURSRQRZDáDNLONDDOWHUQDW\ZQ\FKDOJRU\WPyZ

V\QFKURQL]XMF\FK 1DMEDUG]LHM ]QDQH ] W\FK DOJRU\WPyZ WR EORNRZDQLH GZXID]RZH PHWRGD
znaczników czasowych i

ZLHORZHUV\MQRüGDQ\FK$OJRU\WP\WHUR]ZL]XMSUREOHPSRSUDZQRFL

ZVSyáELH*QLHZykonywanych transakcji.

:ZLNV]RFLNRPHUF\MQ\FKV\VWHPyZ]DU]G]DQLDED]DPLGDQ\FK]DLPSOHPHQWRZDQRPHFKa-

QL]P\V\QFKURQL]DFMLZ]RURZDQHQDMHGQHM]W\FKPHWRG3HáQDDXWRPDW\]DFMDSURFHVXV\QFKURQi-

]DFMLWUDQVDNFMLPDQDFHOXRGFL*HQLHSURJUDPLVWyZEXGXMF\FKDSOLNDFMHED]GDQ\FKRGNRQLHFz-

QRFLVDPRG]LHOQHJRUR]ZL]\ZDQLDWUXGQ\FKSUREOHPyZ]DU]G]DQLDZVSyáELH*QRFLGRVWSXGR
danych.

-HGQDN ] SRZRGX RJUDQLF]DQLD SU]H] DOJRU\WP\ V\QFKURQL]XMFH HIHNW\ZQRFL SU]HWZDU]DQLD Ga-

Q\FK SURGXFHQFL V\VWHPyZ NRPHUF\MQ\FK SUyEXM ]QDOH(ü NRPSURPLV PLG]\ SRSUDZQRFL D

HIHNW\ZQRFL SURFHVX SU]HWZDU]DQLD WUDQVDNF\MQHJR =D]Z\F]DM GRP\OQ\P WU\EHP SUDF\ W\FK

V\VWHPyZ MHVW WU\E QLH JZDUDQWXMF\ SHáQHM SRSUDZQRFL SU]HWZDU]DQLD ZVSyáELH*QHJR DOH ]D WR

FKDUDNWHU\]XMF\ VL ZLNV] Z\GDMQRFL 'OD ]DJZDUDQWRZDQLD SHáQHM SRSUDZQRFL SURFHVX

SU]HWZDU]DQLDQLH]EGQHMHVW]DVWRVRZDQLHGRGDWNRZ\FKPHFKDQL]PyZV\VWHPRZ\FK:\PDJDWR

RGNRQVWUXNWRUyZDSOLNDFMLED]GDQ\FKSU]HDQDOL]RZDQLDVSHF\ILNLGDQHJR]DVWRVRZDQLDLRNUHOe-

QLDZáDFLZHJRWU\EXV\QFKURQL]DFMLWUDQVDNFML=LJQRURZDQLHWHJRSUREOHPXSU]H]SURJUDPLVWyZ

PR*HGRSURZDG]LüGREáGyZZED]LHGDQ\FKLWUXGQ\FKGRRV]DFRZDQLDVWUDWLFKX*\WNRZników.

2.

3RSUDZQRüUHDOL]DFMLZVSyáELH*Q\FKWUDQVDNFML

2.1. Definicja transakcji

-HGQ\P]SRGVWDZRZ\FKZ\PRJyZVWDZLDQ\FKED]RPGDQ\FKMHVWLFKVSyMQRüSROHJDMFDQD

SRSUDZQRFLVNáDGRZDQ\FKZQLFKGDQ\FK-HGQDNQDZHWGREU]HQDSLVDQHLSRSUDZQLHX*\WNRZDQH

DSOLNDFMHED]\GDQ\FKG]LDáDMFHZ]DZRGQ\PZVSyáELH*Q\PLUR]SURV]RQ\PURGRZLVNXVSU]-

WRZRSURJUDPRZ\PQLHJZDUDQWXMVSyMQRFLED]\GDQ\FK*áyZQ\PL]DJUR*HQLDPLGODSRSUDw-

QRFLSU]HFKRZ\ZDQ\FKLSU]HWZDU]DQ\FKGDQ\FKVDQRUPDOQHSU]HUZDQLHSURFHVXSU]HWZDU]DQLD

XV]NRG]HQLHQRQLNDGDQ\FKRUD]LQWHUIHUHQFMHPLG]\UyZQROHJá\PLVHVMDPLNLONXX*\WNRZQLNyZ
Reme

GLXPQDSRZ\*V]H]DJUR*HQLDVWUDQVDNFMH

7UDQVDNFMD MHVW VHNZHQFM ORJLF]QLH SRZL]DQ\FK RSHUDFML Z\NRQ\ZDQ\FK QD ED]LH GDQ\FK Z

UDPDFKVHVMLX*\WNRZQLND3U]\NáDGHPWDNLFKORJLF]QLHSRZL]DQ\FKRSHUDFMLVRSHUDFMHXPQLHj-

V]HQLDVWDQXNRQWDLZ\SáDW\SU]H]EDQNRPDWRGSRZLHGQLHMVXP\SLHQLG]\7HGZLHRSHUDFMHVRG

VLHELHZ]DMHPQLH]DOH*QHPXV]E\üZ\NRQDQHUD]HP2VREQR*DGQD]QLFKZ\SáDWDSLHQLG]\

EH]XPQLHMV]DQLDVWDQXNRQWDOXEXPQLHMV]HQLHWDQXNRQWDEH]Z\SáDW\SLHQLG]\QLHLPSOHPHn-
tuje poprawnej operacji bankowej.

58

Tomasz Koszlajda

:XSURV]F]HQLXPR*QDSU]\Mü*HWUDQVDNFMHZ\NRQXMQDED]LHGDQ\FKF]WHU\SRGVWDZRZHUo-

G]DMH RSHUDFML RGF]\WX ]DSLVX ZVWDZLHQLD L XVXQLFLD GDQ\FK 3RG]LDá VHVML X*\WNRZQLNyZ QD

WUDQVDNFMH MHVW UHDOL]RZDQ\ ]D SRPRF SDU\ GZyFK GRGDWNRZ\FK RSHUDFML ]DWZLHUG]HQLD DQJ
commit) i wycofania (ang. rollback

WUDQVDNFML2SHUDFMD]DWZLHUG]HQLDMHVWSRP\OQ\P]DNRF]e-

QLHPWUDQVDNFMLUyZQRZD*Q\P]DWZLHUG]HQLXZV]\VWNLFKZ\NRQDQ\FKSU]H]QLPRG\ILNDFMLVWDQX

ED]\ GDQ\FK 2SHUDFMD Z\FRIDQLD R]QDF]D QLHSRP\OQH ]DNRF]HQLH WUDQVDNFML L XQLHZD*QLHQLH

ZV]\VWNLFK PRG\ILNDFML ZSURZDG]RQ\FK SU]H] WUDQVDNFM :\FRIDQLH WUDQVDNFML MHVW UyZQRZD*QH

V\WXDFMLQLHZ\VWSLHQLDWHMWUDQVDNFMDZKLVWRULLED]\GDQ\FK7UDQVDNFMHPRJE\üZ\FRI\ZDQH

QD*\F]HQLHX*\WNRZQLNDOXEDXWRPDW\F]QLHSU]H]V\VWHP]DU]G]DQLDED]GDQ\FKZSU]\SDGNX
anormalnego przerwania procesu przetwarzania transakcji.

$E\XRGSRUQLüED]GDQ\FKQDZ\PLHQLRQH]DJUR*HQLDVSyMQRFLED]\GDQ\FKWUDQVDNFMHPXV]

SRVLDGDüFLOHRNUHORQHFHFK\6QLPLDWRPRZRüVSyMQRüL]RODFMDLWUZDáRü]QDQH UD]HP
pod akronimem ACID (od ang. Atomicity, Consistency, Isolation, Durability

$WRPRZRüWUDQVDk-

FML R]QDF]D *H Z Z\SDGNX DQRUPDOQHJR SU]HU\ZDQLD SURFHVX SU]HWZDU]DQLD GDQ\FK RSHUDFMH

ZFKRG]FH Z VNáDG WUDQVDNFML PXV] Z\NRQDü VL ZV]\VWNLH UD]HP OXE *DGQD ] QLFK 6SyMQRü

WUDQVDNFMLR]QDF]D*HWUDQVDNFMDJZDUDQWXMHVSyMQRüED]\GDQ\FKMDNRFDáRü:F]DVLHZ\NRQy-

ZDQLD WUDQVDNFML D SU]HG MHM ]DNRF]HQLHP VWDQ ED]\ GDQ\FK PR*H SR]RVWDZDü SU]HMFLRZR QLe-

VSyMQ\,]RODFMDWUDQVDNFMLR]QDF]DEUDNLQWHUDNFMLPLG]\UyZQROHJá\PLWUDQVDNFMDPL0LPRIDk-

W\F]QHMZVSyáELH*QRFLWUDQVDNFMHÄPXV]PLHü]áXG]HQLH´*HVZ\NRQ\ZDQHZVSRVyEVHNZHn-

F\MQ\7UZDáRüWUDQVDNFMLR]QDF]D]NROHL*HPRG\ILNDFMHVWDQXED]\GDQ\FKZSURZDG]RQHSU]H]

SRSUDZQLH ]DNRF]RQH WUDQVDNFMH PXV] PLHü FKDUDNWHU WUZDá\ PLPR HZHQWXDOQ\FK XV]NRG]H

QRQLNyZGDQ\FK:áDVQRFL$&,'SRZLQQ\E\üLPSOHPHQWRZDQHSU]H]V\VWHP]DU]G]DQLDED]
danych, w sposób transparentny dla programi

VWyZLX*\WNRZQLNyZDSOLNDFMLED]\GDQ\FK

2.2.

3U]\NáDG\EáGyZZ\QLNDMF\FK]HZVSyáELH*QRFLWUDQVDNFML

,QWHUIHUHQFMH PLG]\ ZVSyáELH*Q\PL WUDQVDNFMDPL SROHJDM QD UyZQRF]HVQ\P NRQIOLNWRZ\P

GRVWSLHUy*Q\FKWUDQVDNFMLGRW\FKVDP\FKGDQ\FK:\QLNLHPWDNLFKLQWHUIHUHQFMLVEáG\SR]o-

VWDZLRQHSU]H]WUDQVDNFMHZED]LHGDQ\FKOXEEáGQ\REUD]ED]\GDQ\FKZLG]LDQ\SU]H]WUDQVDNFMH

F]\OLEáGQHUDSRUW\Z\NUHV\OXEZDUWRFLRGF]\W\ZDQHSU]H]X*\WNRZQLNyZED]\GDQ\FK6NODVy-
fikowano kilka podstawowych typów takich interferencji nazywanych anomaliami.

Brudny zapis (ang. dirty write

MHVW DQRPDOL SROHJDMF QD W\P *H SR ]DSLVDQLX GDQHM

x

przez

WUDQVDNFM 7

1

(operacja

w

1

(x)

L SU]HG MHM ]DNRF]HQLHP SRP\OQ\P RSHUDFMD

c

1

EG( QLHSo-

P\OQ\PRSHUDFMD

a

1

QDVWSXMH]DSLVWHMVDPHMGDQHMSU]H]LQQWUDQVDNFM7

2

(operacja

w

2

(x)

).

$QRPDOLMHVWZLFVHNZHQFMDRSHUDFML

w

1

(x), w

2

(x), ..., {c

1

|

a

1

`=Dáy*P\*HSRF]WNRZDZDr-

WRüGDQHM

x

Z\QRVLáDWUDQVDNFMDSLHUZV]DQDGDáDMHMZDUWRüDWUDQVDNFMDGUXJDZDUWRü

LGRGDWNRZRWUDQVDNFMDSLHUZV]D]DNRF]\áDVLRSHUDFMZ\FRIDQLD'ODWDNLHMVHNZHQFMLQLH

PR*QDMHGQR]QDF]QLHVWZLHUG]LüMDNDSRZLQQDE\üSRSUDZQDZDUWRüGDQHM

x

po wycofaniu trans-

DNFMLSLHUZV]HM&]\QDOH*\SU]\ZUyFLüZDUWRüSR]RVWDZLüF]\PR*HRGMüUy*QLFPL-
dzy 200 i 100?

Brudny odczyt (ang. dirty read

MHVW DQRPDOL SROHJDMF QD W\P *H SR ]DSLVDQLX GDQHM

x

przez

WUDQVDNFM7

1

LSU]HGMHM]DNRF]HQLHPQDVWSXMHRGF]\WWHMGDQHMSU]H]LQQWUDQVDNFM7

2

. W przy-

padku zatwierdzenia transakcji T

2

i jednoczesnym wycofaniu transakcji T

1

, obraz bazy danych (stan

danej

x

ZLG]LDQ\SU]H]WUDQVDNFM7

2

MHVWQLHSRSUDZQ\:]ZL]NX]Z\FRIDQLHPWUDQVDNFML7

1

,

transakcja T

2

RGF]\WDáDVWDQGDQHM

x

NWyU\IRUPDOQLHQLJG\QLH]DLVWQLDá$QRPDOLMHVWVHNZHQFMD

operacji:

w

1

(x), r

2

(x), ...,(

ZGRZROQHMNROHMQRFL

a

1

lub

c

2

).

Rozmyty odczyt (ang. fuzzy read lub unrepeatable read

MHVW DQRPDOL SROHJDMF QD W\P *H SR

odczytaniu danej

x

SU]H]WUDQVDNFM7

1

QDVWSXMH]DSLVOXEXVXQLFLHWHMGDQHMSU]H]WUDQVDNFM7

2

,

NWyUDQDVWSQLH]RVWDMH]DWZLHUG]RQD-H*HOLWUDQVDNFMD7

1

EG]LHSUyERZDáDMHV]F]HUD]RGF]\WDü

x

,

RWU]\PDRQDLQQZDUWRüWHMGDQHMOXERGNU\MH*HGDQDWD]RVWDáDXVXQLWD$QRPDOLMHVWVHNZHn-
cja operacji:

r

1

(x), ..., w

2

(x), ..., c

2

, ... ,

r

1

(x)

.

=DU]G]DQLHZVSyáELH*QRFLWUDQVDNFML

59

Utracona modyfikacja (ang. lost update

MHVWDQRPDOLSROHJDMFQDW\P*HSRRGF]\WDQLXGDQHM

x

przez transakcje T

1

i T

2

QDVWSXMH]DSLV]PRG\ILNRZDQHMZDUWRFLGDQHM

x

SU]H]WUDQVDNFM7

1

, która

QDVWSQLH PR*H ]RVWDü ]DWZLHUG]RQD -H*HOL WHUD] WUDQVDNFMD 7

2

UyZQLH* ]DSLV]H ]PRG\ILNRZDQ

ZDUWRüGDQHM

x

PRG\ILNDFMDZSURZDG]RQDSU]H]WUDQVDNFM7

1

]RVWDQLHXWUDFRQD$QRPDOLMHVW

ZLFVHNZHQFMDRSHUDFML

r

1

(x), ..., r

2

(x), ..., w

1

(x), ..., c

1

, ... ,

w

2

(x)

.

Fantom (ang. phantom

MHVW DQRPDOL SROHJDMF QD W\P *H SR RGF]\WDQLX SU]H] WUDQVDNFM 7

1

,

zbioru danych

X

VSHáQLDMF\FKZDUXQHNORJLF]Q\

p

QDVWSXMHZVWDZLHQLHSU]H]WUDQVDNFM7

2

danej

x

NWyUDUyZQLH*VSHáQLDZDUXQHN

p,

OXEPRG\ILNDFMDLVWQLHMFHMGDQHM

x

, która do tej pory nie spe

á-

QLDáDZDUXQNX

p

DOHZZ\QLNXWHMPRG\ILNDFMLEG]LHJRVSHáQLDáD-H*HOLWUDQVDNFMD7

1

EG]LHSUó-

ERZDáDMHV]F]HUD]RGF]\WDüGDQHNWyUHVSHáQLDMZDUXQHN

p,

otrzyma ona w wyniku zbiór danych

X’

równy zbiorowi

X

SRZLNV]RQHPXRGDQ

x

. O danej

x

PyZLVLZW\PZ\SDGNX*HMHVWIDQWo-

PHP NWyU\ SRMDZLá VL Z Z\QLNX SRZWyU]RQHJR ]DS\WDQLD $QRPDOL MHVW VHNZHQFMD RSHUDFML

r

1

(X), ..., w

2

(x), ...,

,

r

1

(X’)

.

2.3.

'HILQLFMDL]RODFMLXV]HUHJRZDOQRFL±DQJ

serializability) transakcji

2SHUDFMHQDOH*FHGRUy*Q\FKWUDQVDNFMLXSRU]GNRZDQHZNROHMQRFLLFKZ\NRQ\ZDQLDVQa-

zywane historiami lub realizacjami tego zbioru transakcji. W zbiorze wszystkich potencjalnych

KLVWRULLGDQHJR]ELRUXWUDQVDNFML]QDMGXMVLhistorie sekwencyjne, czyli takie, w których operacje

*DGQHM]WUDQVDNFMLQLHSU]HSODWDMVL]RSHUDFMDPLLQQ\FKWUDQVDNFMLRUD]KLVWRULHZVSyáELH*QH, w

NWyU\FKRSHUDFMHUy*Q\FKWUDQVDNFMLSU]HSODWDMVL+LVWRULHVHNZHQF\MQH]GHILQLFMHVZROQHRG

EáGyZ Z\QLNDMF\FK ]H ZVSyáELH*QRFL +LVWRULH ZVSyáELH*QH PRJ E\ü ]DUyZQR SRSUDZQH WR

MHVWZROQHRGZV]\VWNLFKQLHW\ONRW\FKZ\PLHQLRQ\FKSRZ\*HMDQRPDOLLMDNLQLHSRSUDZQH'e-

ILQLFMDSRSUDZQ\FKKLVWRULLZVSyáELH*Q\FKMHVWRSDUWDQDSRMFLXXV]HUHJRZDOQRFLWUDQVDNFML (ang.
serializability).

:]RUFHPSRSUDZQRFLZVSyáELH*Q\FKKLVWRULLWUDQVDNFMLVKLVWRULHVHNZHQF\MQH+LVWRULDZVSyá-

ELH*QDNWyUDSR]RVWDZLDWDNLVDPVWDQED]\GDQ\FKLZNWyUHMSRV]F]HJyOQHWUDQVDNFMHRGF]\WXMF

GDQHZLG]WDNLHVDPHZDUWRFLMDNWHVDPHWUDQVDNFMHZVHNZHQF\MQHMKLVWRULLWHJR]ELRUXWUDQVDk-

FMLMHVWKLVWRULUyZQRZD*QWHMKLVWRULLVHNZHQF\MQHM+LVWRULHZVSyáELH*QHUyZQRZD*QHZSRZ\*-

V]\VSRVyEFKRüMHGQHMVHNZHQF\MQHMKLVWRULLW\FKVDP\FKWUDQVDNFMLVQD]\ZDQHKLVWRULDPLusze-
regowalnymi

%UDN XV]HUHJRZDOQRFL KLVWRULL ZVSyáELH*Q\FK MHVW SU]\F]\Q QLHVSyMQRFL ED] Ga-

Q\FKOXESU]\F]\QEáGyZZRGF]\FLHVWDQXED]\GDQ\FK

Niech

T

1

=(r

1

(x), w

1

(x-100), r

1

(y), w

1

(y+100), c

1

)

i

T

2

=(r

2

(x), r

2

(y), c

2

)

EG GZRPD GDQ\PL

transakcjami. Transakcja

T

1

RGF]\WXMHDQDVWSQLHPRG\ILNXMHGDQH

x

i

y

. Transakcja

T

2

odczytuje

stan danych

x

i

y

Z\ZLHWOD LFK VXP X*\WNRZQLNRZL 3RQL*HM SU]HGVWDZLRQR WU]\ SU]\NáDGRZH

historie transakcji

T

1

i

T

2

. Historia

H

1

:

H

1

=(r

1

(x), w

1

(x), r

1

(y), w

1

(y), c

1

, r

2

(x), r

2

(y), c

2

)

MHVWSU]\NáDGHPKLVWRULLVHNZHQF\MQHM7UDQVDNFMD

T

2

odczytuje stan danych

x

i

y

SR]DNRF]HQLX

transakcji

T

1

. Historia

H

2

:

H

2

=(r

1

(x), r

2

(x), w

1

(x), r

1

(y), r

2

(y), w

1

(y), c

1

, c

2

)

MHVWZVSyáELH*QKLVWRULXV]HUHJRZDOQ+LVWRULDWDMHVWUyZQRZD*QDKLVWRULLVHNZHQF\MQHMZNWó-
rej transakcja

T

2

SRSU]HG]DWUDQVDNFM

T

1

. Transakcja

T

2

odczytuje stan danych

x

i

y

sprzed zako

-

czenia transakcji

T

1

. Historia

H

3

:

H

3

=(r

1

(x), r

2

(x), w

1

(x), r

1

(y), w

1

(y), r

2

(y), c

1

, c

2

)

MHVW]NROHLKLVWRULZVSyáELH*QQLHXV]HUHJRZDOQ1LHMHVWRQDUyZQRZD*QD*DGQHM]GZyFKPR*-
liwych sekwencji transakcji

T

1

i

T

2

. Transakcja

T

2

odczytuje stan danej

x

sprzed transakcji

T

1

, a

stan danej

y

SR]DNRF]HQLX

T

1

.

1LHNWyUHKLVWRULHXV]HUHJRZDOQHSRVLDGDMZGDOV]\PFLJXSHZQHQLHSR*GDQHFHFK\1DSU]\NáDG
historia

H

4

:

60

Tomasz Koszlajda

H

4

=(r

1

(x), w

1

(x), r

2

(x), r

1

(y), w

1

(y), r

2

(y) , c

2

, r

1

(z), w

1

(z), c

1

)

MHVWXV]HUHJRZDOQDERMHVWUyZQRZD*QDKLVWRULLVHNZHQF\MQHMZNWyUHM

T

1

poprzedza

T

2

. Rozwa

*-

P\MHGQDNSU]\SDGHNDZDULLV\VWHPXNWyUDZ\VWSLSRRSHUDFML]DWZLHUG]HQLDWUDQsakcji

T

2

:

H

4

=(r

1

(x), w

1

(x), r

2

(x), r

1

(y), w

1

(y), r

2

(y) , c

2

, <awaria>)

i wymusi tym samym wycofanie przez system transakcji

T

1

DE\]DJZDUDQWRZDüMHMDWRPRZRü

NWyUD QLH ]RVWDáD MHV]F]H SRP\OQLH ]DNRF]RQD =DNRF]RQD WUDQVDNFMD

T

2

PXVL ]RVWDü UyZQLH*

Z\FRIDQDSRQLHZD*RGF]\WDáDRQDVWDQED]\GDQ\FKZSURZDG]RQ\SU]H]

T

1

, która formalnie nie

Z\VWSLáDZKLVWRULLED]\GDQ\FK-HVWWRVSU]HF]QH]]DVDGWUZDáRFLWUDQVDNFML+LVWRULHWUDQVDNFML

NWyUHQDZ\SDGHNDZDULLQLHZ\PDJDMNDVNDGRZHJRZ\FRI\ZDQLDMX*]DWZLHUG]RQ\FKWUDQVDNFML

VQD]\ZDQHKLVWRULDPLodtwarzalnymi (ang. recoverable).

&HOHP ]DU]G]DQLD ZVSyáELH*QRFL WUDQVDNFML MHVW WDNLH VWHURZDQLH NROHMQRFL RSHUDFML Z

VSRQWDQLF]Q\FKZVSyáELH*Q\FKKLVWRULDFKWUDQVDNFMLDE\ZED]LHGDQ\FKUHDOL]RZDQHE\á\MHG\QLH
uszeregowalne i odtwarzalne historie transakcji.

2.4. Poziomy izolacji

:LNV]Rü NRPHUF\MQ\FK V\VWHPyZ ED] GDQ\FK XPR*OLZLD X*\WNRZQLNRP ED] GDQ\FK NRU]y-

VWDQLH]WU\EXSUDF\V\VWHPXZNWyU\PGODSRGQLHVLHQLDZ\GDMQRFLSU]HWZDU]DQLDRJUDQLF]DVL

SRSUDZQRü JHQHURZDQ\FK KLVWRULL 5R]ZL]DQLH WR XPR*OLZLD HODVW\F]QH GRSDVRZDQLH SR]LRPX

L]RODFMLZVSyáELH*Q\FKWUDQVDNFMLGRZ\PDJDQHJRZGDQ\P]DVWRVRZDQLXPRGHOXSU]HWZDU]DQLD

3R]LRP\L]RODFMLGHILQLXMVLZRSDUFLXRDQRPDOLH'DQ\SR]LRPL]RODFMLRNUHODMDNLHDQRPDOLHV
w nim dopuszczalne, a jakie zabronione.

6WDQGDUG\LNRPHUF\MQHV\VWHP\ED]GDQ\FKGHILQLXMUy*QHF]VWRSRNU\ZDMFHVLSR]LRP\

L]RODFML:\QLNDWR]Uy*QLFZ]DVWRVRZDQ\FKPHWRGDFKV\QFKURQL]DFML.D*G\]DOJRU\WPyZV\n-

FKURQL]DFMLPDQDWXUDOQHWUXGQRFL]XVXQLFLHPRNUHORQ\FKW\SyZDQRPDOLL1DSU]\NáDGZPe-
todzie blokowania dwu-fazowego trudna jest eliminacja anomalii typu fantom, a w algorytmach
wielower

V\MQ\FK]áR*RQDMHVWHOLPLQDFMDDQRPDOLLutraconego zapisu.

-HGQ]GHILQLFMLSR]LRPyZL]RODFMLMHVWVWDQGDUG64/'HILQLXMHRQWU]\SR]LRP\L]RODFMLEa-

]XMFHQDDQRPDOLDFKbrudnego odczytu, rozmytego odczytu i fantomu'HILQLFMWSU]HGVWDZLRQR

ZWDEHOLSRQL*HM

Dopuszczalne

Poziom anomalie
izolacji

Brudny

zapis

Brudny

odczyt

Rozmyty

odczyt

Fantom

Read uncommitted

nie

tak

tak

tak

Read committed

nie

nie

tak

tak

Repeatable read

nie

nie

nie

tak

Serializable

nie

nie

nie

nie

Nazwa poziomu izolacji: Serializable

MHVW P\OFD SRQLHZD* ] MHM GHILQLFML QLH Z\QLND MHGQo-

]QDF]QLH*HXV]HUHJRZDOQRüQLHGRSXV]F]DMDNLFKNROZLHNDQRPDOLLZVSyáELH*QHJRZ\NRQDQLDD

QLHW\ONRF]WHUHFKZ\PLHQLRQ\FK'HILQLFMDWD]DNáDGDPLOF]FR*HVWRVRZDQPHWRGV\QFKURQL]a-
cji jest blokowanie dwufazowe. Dla tej metody, eliminacja rozmytego odczytu i fantomów przy

RND]MLHOLPLQXMHUyZQLH*LQQHQLHZ\PLHQLRQHDQRPDOLH'ODLQQ\FKPHWRGV\QFKURQL]DFMLWUDQVDk-

FML]Dáo*HQLHWRQLHMHVWSUDZG]LZH

=DU]G]DQLHZVSyáELH*QRFLWUDQVDNFML

61

3.

$OJRU\WP\V\QFKURQL]DFMLZVSyáELH*Q\FKWUDQVDNFML

=DU]G]DQLH ZVSyáELH*QRFL WUDQVDNFML PD QD FHOX WUDQVIRUPDFM ZHMFLRZ\FK SRZVWDá\FK Z

spontaniczny sposób, niepoprawnych historii transakcji, w historie uszeregowalne i odtwarzalne.

:V]\VWNLH SRSUDZQH ZHMFLRZH KLVWRULH SRZLQQ\ SR]RVWDü QLH]PLHQLRQH L Z\NRQ\ZDü VL EH]

RSy(QLHQLD &HO G]LDáDQLD PRGXáX ]DU]G]DQLD ZVSyáELH*QRFL WUDQVDNFML SU]HGVWDZLRQR V\PEo-

OLF]QLHQDU\VXQNXSRQL*HM

Modu

á]DU]G]DQLD

wspó

áELH*QRFL

•

propagacja

operacji

•

opó

(QLDQLHRSHUDFML

•

wycofywanie

transakcji

•

wybór wersji danej

spontaniczne,

potencjalnie

niepoprawne historie

wej

FLRZH

poprawne historie

wyj

FLRZH

0HWRG\V\QFKURQL]DFMLZVSyáELH*Q\FKWUDQVDNFMLUy*QLVLPLG]\VREVSRVREDPL]PLDQ\No-

OHMQRFLRSHUDFMLZVSRQWDQLF]Q\FKKLVWRULDFKZHMFLRZ\FK0HWRG\Z\NRU]\VWXMFHEORNDG\]PLe-

QLDM NROHMQRü ZHMFLRZ\FK VHNZHQFML RSHUDFML SRSU]H] RSy(QLDQLH Z\NRQ\ZDQLD RSHUDFML NRn-

IOLNWRZ\FK0HWRG\]QDF]QLNyZF]DVRZ\FKZ\NU\ZDMQLHSRSUDZQHKLVWRULHL]PLHQLDMMHSU]H]

Z\FRI\ZDQLHWUDQVDNFMLQDUXV]DMF\FKXV]HUHJRZDOQRüWUDQVDNFML0HWRG\Z\NRU]\VWXMFHZLHOo-

ZHUV\MQRüGDQ\FKXQLNDMNRQIOLNWyZPLG]\RSHUDFMDPLSU]H]Z\NRQ\ZDQLHNRQIOLNWRZ\FKRSe-

UDFMLQDUy*Q\FKZHUVMDFKGDQ\FK3RQDGWRSRV]F]HJyOQHPHWRG\Uy*QLVLVWRSQLHPRJUDQLF]DQLD

ZVSyáELH*QHJRZ\NRQ\ZDQLDWUDQVDkcji.

3.1.

6\QFKURQL]DFMD]DSRPRFEORNRZDQLDGRVWSXGRGDQ\FK

Najpowszechniej stosowanym mechanizmem synchronizacji jest metoda blokowania dwufazo-

ZHJR:PHWRG]LHWHMND*GDRSHUDFMDQDGDQ\FKPXVLE\üSRSU]HG]RQDXVWDZLHQLHPRGSRZLHGQLHM

EORNDG\QDWHMGDQHM:SU]\SDGNXX]\VNDQLDZ\PDJDQHMEORNDG\GDQDRSHUDFMDMHVWEH]]ZáRF]QLH

Z\NRQ\ZDQD1LHPR*QRüXVWDZLHQLDEORNDG\]HZ]JOGXQDNRQIOLNW]LQQMX*]DáR*RQEORNDG

]DZLHV]DZ\NRQDQLH]ZL]DQHM]QLRSHUDFMLD*GRPRPHQWX]GMFLDNRQIOLNWRZHMEORNDG\6WRVo-

ZDQHVGZDURG]DMHEORNDGEORNDGDZ\áF]QDGR]DSLVX

X

LEORNDGDZVSyáG]LHORQDGRRGF]\WX

S

.

.RQIOLNWRZRüEORNDGSU]HGVWDZLRQD]RVWDáDZWDEHOLSRQL*HM=QDNÄ'” w tabeli oznacza kompa-

W\ELOQRüEORNDGWDNLHEORNDG\PRJE\üUyZQROHJOHXVWDZLRQHQDWHMVDPHMGDQHM1DWRPLDVW]QDN

Ä´R]QDF]DNRQIOLNWRZRüEORNDGXVWDZLHQLH*GDQHMEORNDG\LZ\NRQDQLHSRZL]DQHM]QLRSe-

UDFMLEG]LHRGURF]RQHD*GRPRPHQWX]GMFLDEORNDG\NRnfliktowej.

Blokada

]DáR*ona
%ORNDGD*GDQD

Brak

blokad

Blokada

S

Blokada

X

Blokada S

'

'

-

Blokada X

'

-

-

0HWRGD EORNRZDQLD GZXID]RZHJR ]DNáDGD L ]GHMPXMH EORNDG\ GOD ND*GHM WUDQVDNFML Z GZyFK

UR]áF]Q\FK ID]DFK %ORNDG\ ]ZL]DQH ] SRV]F]HJyOQ\PL RSHUDFMDPL V ]DNáDGDQH Z SLHUZV]HM

ID]LH WUDQVDNFML D ]GHMPRZDQH Z ID]LH GUXJLHM )D]\ WUDQVDNFML V UR]G]LHORQH SU]H] WDN ]ZDQ\
punkt akceptacji

WUDQVDNFML-HVWWRPRPHQWWX*SRZ\NRQDQLXSU]H]WUDQVDNFMZV]\VWNLFKRSHUDFML

62

Tomasz Koszlajda

DOHMHV]F]HSU]HGMHM]DNRF]HQLHP7DNG]LDáDMF\DOJRU\WPQLHGRSXV]F]DGRSRZVWDQLDZLNV]o-

FLDQRPDOLL

6SUDZG(P\WRQDSU]\NáDG]LHQLHXV]HUHJRZDOQHMKLVWRULL

H

3

. Historia ta po synchronizacji przez

algorytm blokowania dwufazowego zostanie zmodyfikowana do poprawnej historii

H

3

’

:

H

3

’=(r

1

(x), r

2

(x), (1), r

2

(y), c

2

, (2), w

1

(x), r

1

(y), w

1

(y), c

1

).

:SXQNFLHQDVWSLáR]DZLHV]HQLHZ\NRQ\ZDQLDRSHUDFML

w

1

(x)

LFDáHMWUDQVDNFML

T

1

]HZ]JOGX

QDNRQIOLNW]DáR*RQHMEORNDG\GRRGF]\WXWUDQVDNFML

T

2

L*GDQHMEORNDG\GR]DSLVXWUDQVDNFML

T

1

. W

SXQNFLH ]DNRF]HQLH WUDQVDNFML

T

2

SRZRGXMH ]GMFLH ZV]\VWNLFK MHM EORNDG L Z NRQVHNZHQFML

odwieszenie wykonywania transakcji

T

1

.

:FHOXSRGQLHVLHQLDHIHNW\ZQRFLG]LDáDQLDGODGX*HMOLF]E\]DNáDGDQ\FKEORNDGDOJRU\WPEORNo-

ZDQLDGZXID]RZHJRPR*HE\üUR]V]HU]RQ\RPR*OLZRüEORNRZDQLDGDQ\FKRUy*QHM]LDUQLVWRFL

=DPLDVW]DNáDGDQLDLQG\ZLGXDOQ\FKEORNDGQDZLHOXGDQ\FKPR*QD]ZLNV]\ü]LDUQREORNRZDQLD

GRFDáHJR]ELRUXGDQ\FK:LNV]\PL]LDUQDPLEORNRZDQLDPRJE\üEORNLGDQ\FKSOLNLUHODFMH
sche

PDW\OXEFDáHED]\GDQ\FK-HGQRVWNLWHWZRU]KLHUDUFKLOXEJUDI]LDUQLVWRFLEORNRZDQLD

2 LOH SRMHG\QF]H GDQH V EORNRZDQH DXWRPDW\F]QLH SU]H] V\VWHP ]DU]G]DQLD ED] GDQ\FK WR

ZLNV]HMHGQRVWNLPRJE\üEORNRZDQHMDZQLHSU]H]X*\WNRZQLNyZOXESURJUDPLVWyZ6\QFKURQi-

]DFMDEORNDGQDUy*Q\FKSR]LRPDFK]LDUQLVWRFLZ\PDJDZSURZDG]HQLDQRZHJRW\SXEORNDG]Za-

Q\FK LQWHQF\MQ\PL 8]\VNDQLH EORNDG\ QD QL*V]\P SR]LRPLH ]LDUQLVWRFL PXVL E\ü SRSU]HG]RQH

]DáR*HQLHPEORNDGLQWHQF\MQ\FKQDZV]\VWNLFKMHGQRVWNDFKZ\*V]HJRSR]LRPX

$OJRU\WPEORNRZDQLD GZXID]RZHJR MHVW SRZV]HFKQLH VWRVRZDQ\ ]H Z]JOGX QD SURVWRW MHJR

LPSOHPHQWDFML3RVLDGDRQMHGQDNV]HUHJZDG1DOH*GRQLFKQLVNLVWRSLHZVSyáELH*QRFLWUDQs-
akcji, wy

VWSRZDQLH]DNOHV]F]HRUD]EUDN]DSHZQLHQLDXV]HUHJRZDOQRFLWUDQVDNFML

1LVNLVWRSLHZVSyáELH*QRFLWUDQVDNFMLZ\QLND]WHJR*HDOJRU\WPWHQMHVWPDáRVHOHNW\ZQ\

3RZRGXMH RQ RSy(QLHQLD Z UHDOL]DFML QLH W\ONR QLHSRSUDZQ\FK DOH UyZQLH* SRSUDZQ\FK KLVWRULL
trans

DNFML1DSU]\NáDGXV]HUHJRZDOQDLRGWZDU]DOQDKLVWRULD

H

5

:

H

5

=(r

1

(x), w

2

(x), r

1

(y), c

1

, c

2

),

zostanie przez algorytm blokowania zmodyfikowana do historii

H

5

’

, w której wykonywanie

transakcji

T

2

zostanie zawie

V]RQHGRF]DVX]DNRF]HQLDWUDQVDNFML

T

1

:

H

5

’=(r

1

(x), r

1

(y), c

1

, w

2

(x), c

2

).

:NODV\F]QHMZHUVMLDOJRU\WPEORNRZDQLDGZXID]RZHJRQLHJZDUDQWXMHUyZQLH*SHáQHMXV]HUe-

JRZDOQRFLWUDQVDNFML-HVWRQQLHRGSRUQ\QDDQRPDOLIDQWRPyZ3U]\NáDGHPQLHFKEG]LHKLVWRULD

H

6

:

H

6

=(r

1

(X), i

2

(y

∈

X), c

2

, r

1

(X’=X

∪

y), c

1

).

'X*H

X

w

r

1

(X)

R]QDF]DRGF]\WFDáHJR]ELRUXGDQ\FKVSHáQLDMF\FKZDUXQHNORJLF]Q\]DS\WDQLD

Operacja

i

2

(y

∈

X)

MHVWRSHUDFMZVWDZLHQLDGDQHM

y

NWyUDUyZQLH*VSHáQLDWHQZDUXQHN3R]DNR-

F]HQLXWUDQVDNFMLGUXJLHMNROHMQH]DS\WDQLH]ZUDFDLQQ\Z\QLNREHMPXMF\UyZQLH*IDQWRPGDQ

y

.

Historia

H

6

jest nieuszeregowalna. Transakcja

T

1

widzi w pierwszym zapytaniu stan bazy danych

sprzed wykonania transakcji

T

2

, a w drugim stan po wykonaniu

T

2

. Jednak algorytm blokowania

GZXID]RZHJRQLH]PRG\ILNXMHWHMKLVWRULL1LHXPLHRQ]V\QFKURQL]RZDüRSHUDFMLRGF]\WX]ELRUX

GDQ\FKLRSHUDFMLZVWDZLDQLDGDQ\FKGRWHJR]ELRUX.RPHUF\MQHV\VWHP\ED]GDQ\FKQDSU]\NáDG

SURGXNW,%0±'%UR]ZL]XMSUREOHPIDQWRPyZSU]H]EDUG]LHMUHVWU\NF\MQHEORNRZDQLH3Rd-

F]DVRSHUDFMLRGF]\WXOXE]DSLVXEORNRZDQHVQLHSRMHG\QF]HGDQHDOHFDáH]ELRU\GDQ\FK-HGQDN

]HZ]JOGXQDUDG\NDOQHREQL*HQLHVWRSQLDZVSyáELH*QRFLWDNLHUR]ZL]DQLHMHVWWUDNWRZDQHMDNR
opcjonalne.

=DU]G]DQLHZVSyáELH*QRFLWUDQVDNFML

63

3.2.

6\QFKURQL]DFMD]DSRPRF]QDF]QLNyZF]DVRZ\FK

=GHF\GRZDQLHPQLHMSRSXODUQDPHWRGV\QFKURQL]DFMLWUDQVDNFMLVDOJRU\WP\NWyU\FKG]LDáa-

QLH RSLHUD VL QD HW\NLHWRZDQLX GDQ\FK ]QDF]QLNDPL F]DVRZ\PL WUDQVDNFML : PHWRG]LH WHM MDNR

SRSUDZQSU]\MPXMHVLNROHMQRüZ\NRQ\ZDQLDWUDQVDNFML]JRGQ]F]DVDPLSRMDZLDQLDVLWUDQs-

DNFMLZV\VWHPLH.D*GD]WUDQVDNFMLZPRPHQFLHUR]SRF]FLDRWU]\PXMHXQLNDOQ\]QDF]QLNF]DVo-

Z\PR*HE\üWRQDSU]\NáDGNROHMQ\QXPHUVHNZHQVHUDDND*GGDQDSU]HFKRZXMHGZDGRGDWNo-

ZHDWU\EXW\ SDPLWDMFH ]QDF]QLN F]DVRZ\ QDMPáRGV]HM WUDQVDNFML NWyUD M RGF]\WDáD 576 read
time stamp

L ]QDF]QLN F]DVRZ\ RVWDWQLHM WUDQVDNFML NWyUD M ]PRG\ILNRZDáD :76 write time

stamp

7UDQVDNFMH SU]HWZDU]DMF GDQH SR]RVWDZLDM Z W\FK DWU\EXWDFK ODG\ VZRMHJR G]LDáDQLD

Mechanizm synchronizacji polega na wycofywaniu transakcji, których znacznik czasowy jest wcze-

QLHMV]\RG]QDF]QLNyZ]ZL]aQ\FK]RGF]\W\ZDQOXE]DSLV\ZDQGDQ

=Dáy*P\*HZED]LHGDQ\FK]DZLHUDMFHMGDQH[576 :76 L\576 :76 Zy-

konywa

QDMHVWQDVWSXMFDQLHXV]HUHJRZDOQDKLVWRULDWUDQVDNFML

T

1

i

T

2

:

H

3

=(r

1

(x), r

2

(x), w

1

(x), r

1

(y), w

1

(y), r

2

(y), c

1

, c

2

).

Transakcji

T

1

nadano znacznik TS=6, a transakcji

T

2

znacznik TS=7. Historia ta zostanie zmody-

fi

NRZDQDGRQDVWSXMFHMKLVWRULLXV]HUHJRZDOQHM

H

3

’

:

H

3

’=(r

1

(x), r

2

(x), (1) a

1

, r

2

(y), (2), c

2

, r

1

(x), w

1

(x), r

1

(y), w

1

(y), c

1

).

Odczyty danej

x

przez transakcje

T

1

i

T

2

PRG\ILNXM]QDF]QLNF]DVRZ\WUDQVDNFMLRGF]\WXMFHM

NROHMQRGRZDUWRFL576 L576 :SXQNFLHZ]ZL]NX]W\P*H]QDF]QLNF]DVRZ\WUDQs-
akcji

T

1

(TS=6) jest mniejszy od znacznika czasowego RTS=7 co oznacza brak synchronizacji

WUDQVDNFMD ZF]HQLHMV]D Z\NRQXMH RSHUDFM NRQIOLNWRZ SR WUDQVDNFML Sy(QLHMV]HM WUDQVDNFMD

T

1

MHVW Z\FRIDQD : SXQNFLH QDVWSXMH UHVWDUW WUDQVDNFML

T

1

z nowym znacznikiem czasowym

TS=8.

Rzadkie zastosowanie metody znaczników czasowych w komercyjnych systemach baz danych

wynika z kosztownego sposobu synchronizacji jakim jest wycofywanie transakcji.

3.3. Algorytmy wielowersyjne

: ZLHORZHUV\MQ\FK DOJRU\WPDFK V\QFKURQL]DFML ZVSyáELH*Q\FK WUDQVDNFML RSHUDFMH ]DSLVX QLH

SRZRGXMQDGSLVDQLDVWDUHMZDUWRFLGDQ\FKOHF]WZRU]QRZZHUVMGDQHMSU]\]DFKRZDQLXVWDUHM

ZHUVML : SU]\SDGNX Z\VWSLHQLD RSHUDFML NRQIOLNWRZ\FK V\VWHP PR*H XQLNQü NRQIOLNWX SU]H]

Z\NRQDQLHW\FKRSHUDFMLQDUy*Q\FKZHUVMDFKWHMVDPHMGDQHM1DSU]\NáDGZV\WXDFMLJG\WUDQVDk-

FMDFKFHRF]\WDüGDQ]PRG\ILNRZDQSU]H]LQQQLH]DNRF]RQWUDQVDNFMRGF]\WWHQPR*HGRWy-

F]\üVWDUV]HMZHUVMLWHMGDQHM:WHQVSRVyEZLHORZHUV\MQHDOJRU\WP\V\QFKURQL]DFML]QDF]QLHSRd-

QRV]ZVSyáELH*QRüV\QFKURQL]RZDQ\FKWUDQsakcji.

=Dáy*P\ *H Z ZLHORZHUV\MQHM ED]LH GDQ\FK ]DZLHUDMFHM GDQH ZLHORZHUV\MQH

x

={

x

0

} i

y

={

y

0

`Z\NRQ\ZDQDMHVWQDVWSXMFDQLeuszeregowalna historia

H

3

:

H

3

=(r

1

(x), r

2

(x), w

1

(x), r

1

(y), w

1

(y), r

2

(y), c

1

, c

2

).

=DSRPRFDOJRU\WPXZLHORZHUV\MQHJRKLVWRULDWD]RVWDQLH]PRG\ILNRZDQDGRSRVWDFL

H

3

’=(r

1

(x

0

), r

2

(x

0

), (1) w

1

(x

1

), r

1

(y

0

), w

1

(y

1

), (2) r

2

(y

0

), c

1

, c

2

).

+LVWRULDWDMHVWXV]HUHJRZDOQD-HVWRQDUyZQRZD*QDZHUVMLVHNZHQF\MQHMZNWyUHMWUDQVDNFMD

T

2

SRSU]HG]DWUDQVDNFM

T

1

. Transakcja

T

2

widzi bowiem stan danych

x

i

y

VSU]HGUR]SRF]FLDWUDQVDk-

cji

T

1

. W punkcie (1) transakcja

T

1

WZRU]\QRZZHUVM

x

1

danej

x

. W punkcie (2) algorytm wybiera

do odczytu ze zbioru wersji danej

x

={

x

0

, x

1

`VWDUV]QLHNRQIOLNWRZZHUVM

x

0

.

64

Tomasz Koszlajda

,VWQLHMH ZLHOH ZDULDQWyZ DOJRU\WPyZ ZLHORZHUV\MQ\FK %D]XM RQH QD NODV\F]Q\FK jednowersyj-

Q\FK DOJRU\WPDFK V\QFKURQL]XMF\FK : ZLHORZHUV\MQ\P DOJRU\WPLH EORNRZDQLD GZXID]RZHJR

PRJLVWQLHüW\ONRGZLHZHUVMHMHGQHMGDQHM2SHUDFMHRGF]\WXL]DSLV\QLHVNRQIOLNWRZHDZLF

EORNDG\ GR ]DSLVX L RGF]\WX V NRPSDW\ELOQH : SU]\SDGNX UyZQROHJáHJR Z\NRQ\ZDQLD SU]H]

Uy*QHWUDQVDNFMHRSHUDFMLRGF]\WXL]DSLVXRGF]\W\ZDQDMHVWVWDUV]DZHUVMDGDQHMDRSHUDFMD]DSLVX

WZRU]\ QRZ ZHUVM 'ZLH UyZQROHJáH RSHUDFMH ]DSLVX SR]RVWDM NRQIOLNWRZH 1D ]DNRF]HQLH

WUDQVDNFMLNWyUDXWZRU]\áDQRZZHUVMGDQHMQDVWSXMHXVXQLFLHVWDUHMZHrsji.
: ZLHORZHUV\MQ\P DOJRU\WPLH ]QDF]QLNyZ F]DVRZ\FK QLH RJUDQLF]HQLD QD OLF]E ZHUVML 7HUD]

]QDF]QLNL F]DVRZH WUDQVDNFML ]DSLVXMF\FK L RGF]\WXMF\FK V SDPLWDQH GOD ND*GHM ZHUVML GDQHM

'ODRSHUDFMLRGF]\WX]H]ELRUXZHUVMLZ\ELHUDQDMHVWWDNWyUHM]QDF]QLNF]DVRZ\WUDQVDNFMLNWyUDM

XWZRU]\áD MHVW QDMZLNV]\P ]QDF]QLNLHP PQLHMV]\P QL* ]QDF]QLN GDQHM WUDQVDNFML RGF]\WXMFHM

3U]\NáDGRZR]SRGDQHJRSRQL*HM]ELRUXZHUVMLGDQHMx, transakcja o znaczniku czasowym TS=12,

RGF]\WDZHUVM

x

2

:

x = {x

0

:WTS=1, RTS=3,

x

1

:WTS=6, RTS=6,

x

2

:WTS=9, RTS=18,

x

3

:WTS=19, RTS=21}.

:ZLHORZHUV\MQ\PDOJRU\WPLH]QDF]QLNyZF]DVRZ\FKRSHUDFMH]DSLVXQLHVNRQIOLNWRZH7ZRU]

RQHQRZHZHUVMHGDQ\FK-HG\Q\SU]\SDGHNNRQIOLNWXPDPLHMVFHJG\WUDQVDNFMD FKFH XWZRU]\ü

QRZZHUVMGDQ\FKNWyUDSRZLQQDE\üRGF]\WDQD]JRGQLH]SRU]GNLHP]QDF]QLNyZF]DVRZ\FK

SU]H]MX*Z\NRQDQRSHUDFMRGF]\WX'ODGDQHM

x

R]ELRU]HZHUVML]SRSU]HGQLHJRSU]\NáDGXWDNL

NRQIOLNWZ\VWSLQDSU]\NáDGSRGF]DVSUyE\RSHUDFML]DSLVXGDQHM

x

SU]H]WUDQVDNFMR]QDF]QLNX

czasowym TS=12, czyli podczas tworzenia nowej wersji

x

4

ze znacznikami WTS=RTS=12. W re-

DOL]DFMLXV]HUHJRZDOQHMQRZDZHUVMDSRZLQQDE\üRGF]\WDQDSU]H]WUDQVDNFMR]QDF]QLNXF]DVo-
wym TS=18. Tymczasem z historii danej

x

Z\QLND*HRSHUDFMDRGF]\WXGDQHM[SU]H]WUDQVDNFMR

]QDF]QLNX 76 PLDáD MX* PLHMVFH L WUDQVDNFMD WD RGF]\WDáD ZHUVM

x

2

. Wersji

x

4

transakcja o

]QDF]QLNX76 QLHPRJáDRGF]yWDüERZHUVMDWDZW\PF]DVLHMHV]F]HQLHLVWQLDáD

4.

=DU]G]DQLHWUDQVDNFMDPLZ6=%'25$&/(

6\VWHP ]DU]G]DQLD ED] GDQ\FK SURGXNFML ILUP\ 25$&/( UHDOL]XMH IXQNFMH ]DU]G]DQLD

ZVSyáELH*QRFLWUDQVDNFML,PSOHPHQWXMHRQDOJRU\WPV\QFKURQL]DFMLNWyU\MHVW]áR*HQLHPPHWRG

EORNRZDQLD GZXID]RZHJR ZLHORZHUV\MQHM PHWRG\ ]QDF]QLNyZ F]DVRZ\FK RUD] UHJXá\ pierwszy
zatwierdzony wygrywa (ang. first-committer-wins).

4.1. Metoda hierarchicznego blokowanie dwufazowego

0RGXá ]DU]G]DQLD ZVSyáELH*QRFL WUDQVDNFML V\VWHPX 25$&/( Z GRP\OQ\P WU\ELH SUDF\

X*\ZDGRV\QFKURQL]DFMLRSHUDFML]DSLVXDOJRU\WPXEORNRZDQLDGZXID]RZHJRRWU]HFKSR]LRPDFK

]LDUQLVWRFL ED]D GDQ\FK UHODFMD L NURWND 8*\WNRZQLN PR*H MDZQLH EORNRZDü FDá ED] GDQ\FK

Z\ELHUDMFVSHFMDOQ\WU\ERWZDUFLDED]\GDQ\FK-DZQHEORNRZDQLHUHODFMLMHVWUHDOL]RZDQH]DSo-

PRFSROHFHQLDLOCK TABLE nazwa_relacji IN typ_blokady'RZ\ERUXMHVWSLüW\SyZEORNDG

GZLH]Z\NáHZVSyáG]LHORQD L Z\áF]QD GZLH LQWHQF\MQH Z\áF]QRFL L ZVSyáG]LHOHQLD L MHGQD
mieszana.

2SHUDFMHRGF]\WXQLHVV\QFKURQL]RZDQH]DSRPRFEORNDG6\VWHP25$&/(QLH]DNáDGDEOo-

NDG ZVSyáG]LHORQ\FK GOD SRMHG\QF]\FK GDQ\FK ']LNL WHPX ]DS\WDQLD QLH V EORNRZDQH SU]H]

V\VWHP:\MWNLHPV]DS\WDQLD]NODX]XOFOR UPDATE OFGODNWyU\FK]DNáDGDQHVEORNDG\
wy

áF]QHLZ]ZL]NX]W\PLFKZ\NRQDQLHPR*HE\üRSy(QLRQHGRF]DVXX]\VNDQLDEORNDG\

4.2. Wielowersyjna metoda znaczników czasowych

Do synchronizacji operacji odczytu stosowany jest wielowersyjny algorytm znaczników czaso-

Z\FK5RO]QDF]QLNyZF]DVRZ\FKSHáQLWDN]ZDQ\6&1DQJSystem Change Number) pobierany

] V\VWHPRZHJR VHNZHQVHUD .D*GHM WUDQVDNFML Z PRPHQFLH MHM ]DWZLHUG]DQLD SU]\SLV\ZDQ\ MHVW

XQLNDOQ\ ]QDF]QLN F]DVRZ\ 6&1 =QDF]QLN WHQ VáX*\ QDVWSQLH GR R]QDNRZDQLD ZHUVML GDQ\FK

=DU]G]DQLHZVSyáELH*QRFLWUDQVDNFML

65

XWZRU]RQ\FK SU]H] GDQ WUDQVDNFM =QDF]QLN F]DVRZ\ Z\NRU]\VW\ZDQ\ GR LGHQW\ILNDFML ZHUVML

GDQ\FKZáDFLZ\FKGODGDQHJR]DS\WDQLDMHVWSRELHUDQ\]VHNZHQVHUD6&1*ZDUDQWXMHWRVSyMQRü

RSHUDFMLRGF]\WX:DUWRü]QDF]QLND6&1PR*HVL]PLHQLDüGODNROHMQ\FK]DS\WDWHMVDPHMWUDQs-
akcji.

'RP\OQ\WU\ESUDF\V\VWHPX25$&/(]DSHZQLDSR]LRPL]RODFML5($'&200,7('-HGQRVWN

V\QFKURQL]DFMLRSHUDFMLRGF]\WXVSRMHG\QF]H]DS\WDQLDDQLHFDáDWUDQVDNFMD7U\EWHQGRSXV]F]D

Z\VWSRZDQLHDQRPDOLLrozmytego odczytu, utraconej modyfikacji i fantomu.

4.3. Unikanie anomalii fantomów i utraty modyfikacji

:\*V]H SR]LRP\ L]RODFML Z\NOXF]DMFH DQRPDOLH UR]P\WHJR RGF]\WX XWUDFRQHM PRG\ILNDFML L

IDQWRPXVGRVWSQHRSFMRQDOQLHGODFDá\FKVHVMLOXESRMHG\QF]\FKWUDQVDNFML,VWQLHMGZDVSRVRE\

]ZLNV]HQLDSR]LRPXL]RODFMLWUDQVDNFMLXVWDZLHQLDWU\EXWUDQVDNFMLW\ONRGRRGF]\WXRUD]XVWDZLe-
nia poziomu izolacji SERIALIZA

%/(GODFDáHMVHVMLOXESRMHG\QF]HMWUDQVDNFML

:\EyUMHGQHM]W\FKRSFMLSRZRGXMH]PLDQVSRVREXLGHQW\ILNDFMLZHUVMLRELHNWyZSU]H]WUDQs-

DNFMH 7UDQVDNFMH Z W\P Z\SDGNX PDM SU]\G]LHODQH GZD ]QDF]QLNL F]DVRZH 6&1 ] SRF]WNX L

NRFDWUDQVDNFML.RFRZ\]QDF]QLNF]DVRZ\MHVWZ\NRU]\VW\ZDQ\WDNMDNZWU\ELHGRP\OQ\PGR

]QDNRZDQLDWZRU]RQ\FKZHUVMLGDQ\FK3RF]WNRZ\]QDF]QLNF]DVRZ\MHVWZ\NRU]\VW\ZDQ\SU]H]
wszystkie zapytania transakcji do identyfikacji odczytywanych wersji danych. Eliminuje anomalie
rozmytego odczytu i fantomu.

'ODXVXQLFLDDQRPDOLLXWUDFRQHMPRG\ILNDFMLV\VWHP25$&/(VWRVXMHUHJXápierwszy zatwier-

dzony wygrywa

-H*HOLGZLHWUDQVDNFMHNWyU\FKF]DV\UHDOL]DFMLRNUHORQHSU]H]]QDF]QLNLF]DVRZH

SRF]WNXLNRFDWUDQVDNFMLSRNU\ZDMVLSUyEXMPRG\ILNRZDüWVDPGDQWRWUDQVDNFMDNWyUD

MDNR SLHUZV]D ]DLQLFMRZDáD RSHUDFM PRG\ILNDFML Z Z\SDGNX SRP\OQHJR ]DNRF]HQLH Z\PXV]D

Z\FRIDQLHGUXJLHMWUDQVDNFML'UXJDWUDQVDNFMDQLHEG]LHPRJáDZ\NRQDüVZRMHMPRG\ILNDFMLQa-

ZHWSR]ZROQLHQLXEORNDG\Z\áF]QHMSU]H]WUDQVDNFMSLHUZV]:V]HONLHSUyE\PRG\ILNDFMLGDQHM

EG SU]H] V\VWHP RGU]XFRQH ']LNL WHPX PRG\ILNRZDQH PRJ E\ü MHG\QLH QDMZLH*V]H ZHUVMH
danych.

=DVWRVRZDQLHWU\EXL]RODFMLRP\OFHMQD]ZLH6(5,$/,=$%/(QLHJZDUDQWXMHSHáQHML]RODFML

WUDQVDNFML:GDOV]\PFLJXLVWQLHMHZLHOHQLHVWDQGDUGRZ\FKDQRPDOLLQLHZ\NU\ZDQ\FKSU]H]]a-
stosowane mechanizmy synchronizacji.

3RQL*HMSRGDQRSU]\NáDGQLHXV]HUHJRZDOQHMKLVWRULLWUDQVDNFMLEáGQLHV\QFKURQL]RZDQHMSU]H]

V\VWHP25$&/(ZWU\ELH6(5,$/,=$%/(=Dáy*P\*HPLG]\GDQ\PL

x

i

y

]DFKRG]L]DOH*QRü

x

>

y

=DOH*QRüWDMHVW]DFKRZ\ZDQDRGG]LHOQLHSU]H]ND*G]WUDQVDNFML

T

1

i

T

2

3RQL*V]DZVSyá-

ELH*QDUHDOL]DFMDPo*HMHGQDNVSRZRGRZDüQLH]DFKRZDQLHWHM]DOH*QRFL

H

7

= (r

1

(x), r

1

(y), r

2

(x), r

2

(y), w

2

(x), c

2

, w

1

(y), c

1

).

3U]\MPLMP\*HZDUWRFLSRF]WNRZHGDQ\FKZ\QRVLá\

x

=200 i

y

=150. Transakcja

T

1

RGF]\WDáD

ZDUWRFL

x

i

y

LSRVWDQRZLáD]PQLHMV]\üZDUWRüGDQHM

x

R-HGQDN]DQLPWRQDVWSLáRWUDQVDNFMD

T

2

UyZQLH*RGF]\WDáDGDQH

x

i

y

LSRVWDQRZLáD]ZLNV]\üGDQ

y

R.D*GDWUDQVDNFMDRVREQD

]DFKRZXMH SU]\MW ]DOH*QRü PLG]\ GDQ\PL 7UDQVDNFMD

T

1

FKFH ]RVWDZLü VWDQ GDQ\FK

x

=160 i

y

=150, a transakcja

T

2

FKFH]RVWDZLüVWDQGDQ\FK

x

=200 i

y

-HGQDNZVSyáELH*QHZ\NRQDQLH

tych transakcji pozostawia stan danych

x

=160 i

y

QLH]JRGQ\]SU]\MW]DOH*QRFL

:V\VWHPLH25$&/(X]\VNDQLHSHáQHMXV]HUHJRZDOQRFLZ\PDJD]DNáDGDQLDEORNDGSU]H]]a-

S\WDQLDSRSU]H]VWRVRZDQLHZ]DS\WDQLDFKNODX]XOL)2583'$7(-HGQDNZL*HVLWR]UDG\NDl-

Q\PRJUDQLF]HQLHPVWRSQLDZVSyáELH*QRFLV\VWHPX:VSyáELH*QRüMHVWZWDNLPZ\SDGNXQL*V]D

QL* Z NODV\F]Q\P DOJRU\WPLH EORNRZDQLD GZXID]RZHJR 6SRZRGRZDQH MHVW WR W\P *H V\VWHP
ORACLE nie roz

Uy*QLDEORNDGGRRGF]\WX]LQWHQFMPRG\ILNDFMLL]Z\Ná\FKEORNDGGR]DSLVX

66

Tomasz Koszlajda

5. Podsumowanie

=DVWRVRZDQLH V\VWHPRZHM V\QFKURQL]DFML ZVSyáELH*Q\FK WUDQVDNFML PLDáR UR]ZL]Dü SUREOHP

EáGyZ EGF\FK Z\QLNLHP ZVSyáELH*QHJR GRVWSX GR ED]\ GDQ\FK -HGQDN ]H Z]JOGX QD No-

QLHF]QRü ]QDOH]LHQLD NRPSURPLVX PLG]\ ]DSHZQLHQLHP SRSUDZQRFL GDQ\FK D Z\GDMQRFL

SU]HWZDU]DQLD VSRZRGRZDáR *H QLHNWyUH NRPHUF\MQH V\VWHP\ ED] GDQ\FK QLH JZDUDQWXM SHáQHM

XV]HUHJRZDOQRFLWUDQVDNFML3U]\NáDGHPMHVWV\VWHP25$&/(ZNWyU\P]DVWRVRZDQRDOJRU\WP\

V\QFKURQL]XMFH ]DSHZQLDMFH PDNV\PDOQ HIHNW\ZQRFL SURFHVX SU]HWZDU]DQLD GDQ\FK NRV]WHP
popraw

QRFLGDQ\FK

3RZRGXMHWRNRQVWUXNFMDRSURJUDPRZDQLDDSOLNDF\MQHJRPXVLXZ]JOGQLDüSUREOHP\V\QFKUo-

QL]DFMLWUDQVDNFMLZVSRVyEZáDFLZ\GODVSHF\ILNLGDQHJR]DVWRVRZDQLD%áG\EGFHZ\QLNLHP

QLHSHáQHM V\QFKURQL]DFML WUDQVDNFML UHDOL]RZDQHM SU]H] V\VWHP ]DU]G]DQLD ED] GDQ\FK QLe-

XZ]JOGQLRQHZNRG]LHDSOLNDFMLPRJPLHüWUXGQHGRRV]DFRZDQLDNRQVHNZHQFMHGODX*\WNRZQi-

NyZ DSOLNDFML ED]\ GDQ\FK 7\PF]DVHP WHPDW\ND V\QFKURQL]DFML ZVSyáELH*Q\FK WUDQVDNFML MHVW

PDáR]QDQDZUyGSURJUDPLVWyZWZRU]F\FKRSURJUDPRZDQLHDSOLNacyjne.

Literatura

1. ANSI

X3.135-1992,

American National Standard for Information Systems – Database Language - SQL,

listopad 1992.

2. P. A. Bernstein, V. Hadzilacos, N. Goodman, Concurrency Control and Recovery in Database Systems,

Addison_Wesley, 1987.

3. J. Gray, A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann 1993.

4. H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, P. O’Neil, A critique of ANSI SQL Levels, SIG-

MOD 1995, San Jose USA.

5. Dokumentacja techniczna Oracle8i.