26
adalah
sebuah
directed
graph
G
=
(N,E)
yang
berisi
sekumpulan node
N
dan sekumpulan directed edges E yang dibangun seperti berikut :
•
Buat sebuah node untuk setiap transaksi.
•
Buat
sebuah
directed
edge
T
i
->
T
j
,
jika
T
j
membaca
nilai
dari
sebuah item yang telah ditulis oleh T
i
.
•
Buat sebuah directed edge T
i
-> T
j,
jika T
j
menulis nilai dari sebuah
item yang telah dibaca oleh T
i
.
•
Buat sebuah directed edge T
i
-> T
j
,
jika T
j
menulis nilai dari sebuah
item yang telah ditulis oleh T
i.
Jika sebuah edge
T
i
->
T
j
sudah
ada
pada precedence
graph
untuk S,
maka
didalam serial
schedule
S’
yang
ekivalen
dengan
S,
T
i
harus
muncul
sebelum
T
j.
Jika
precedence
graph
berisi
sebuah
cycle,
maka
schedule
itu
menjadi tidak conflict serializable.
Perhatikan
dua
transaksi
pada
tabel
2.6.
Transaksi
T
9
mentransfer
£100 dari sebuah rekening dengan saldo bal
x
ke rekening
lain dengan saldo
bal
y
,
sedangkan
T1
0
menambah
saldo
dari
dua
rekening
ini
sebesar
10%.
Precedence
graph
untuk schedule
ini
seperti ditunjukkan oleh
gambar 2.1,
mempunyai sebuah cycle, jadi tidak bersifat conflict serializable.
Time
T
9
T
10
t1
begin_transaction
t2
read ( bal
x
)
t3
bal
x
=
bal
x
+
100
 |