Konfliktigraafi

Konfliktigraafi (englanniksi precedence graph, conflict graph tai serializability graph) on graafi, jota käytetään tietokantojen transaktioiden konflikti-sarjallistuvuuden havaitsemiseen.

Vastaavaa menetelmää käytetään myös lukkiutumien (deadlock) havaitsemiseen. Tällaista graafia kutsutaan Wait-for -graafiksi.

Konfliktigraafi. Ajoituksessa on silmukka transaktioiden 1 ja 2 välillä. Se ei ole sarjallistuva.

Nimensä mukaisesti kyseessä on graafi. Yksi graafi kuvastaa aina yhtä ajoitusta (engl. schedule, joukkoa transaktioita). Graafi koostuu kahdenlaisista elementistä:

• Solmukohdat (kuvassa sininen ympyrä). Solmukohtia on yksi jokaista transaktiota kohden. Siihen merkitään transaktion numero ja usein myös kirjain T.
• Nuolet. Lisätään, kun transaktioiden operaatiot ovat ns. konfliktissa. Mikäli konfliktitilanne löytyy (yksi tai useampi), piirretään nuoli aikaisemmin suoritettavan operaation transaktiosta vanhempaan transaktioon.

Konfliktin määritelmä

Operaatiot konfliktoivat, jos kaikki kolme ehtoa täyttyvät:

• ne kuuluvat eri transaktioihin
• ne kohdistuvat samaan tietoalkioon
• ainakin toinen operaatio on kirjoitus-operaatio.

Esimerkiksi operaatiot R1(X), W2(X) konfliktoituvat.

Sarjallistuvuuden löytäminen

1. Etsitään konfliktoituvat operaatiot. Tehdään nuolet aina jos konflikteja (yksi tai useampi) löytyy. Yksi nuoli riittää. Piirretään ensimmäiseksi olevasta tapahtumasta (T_i) nuoli myöhempään operaatioon (T_j). Riittää, että nuoli piirretään vain kerran. Mahdollisia konfliktitilanteita on siis:
   1. Ti on kirjoitusoperaatio, Tj lukuoperaatio
   2. Ti on lukuoperaatio, Tj kirjoitusoperaatio
   3. Ti ja Tj ovat molemmat kirjoitusoperaatioita
2. Lopuksi tarkastellaan, muodostuuko kahden solmukohdan välille silmukka (myös nimellä sykli). Jos verkossa on sykli/silmukka, vastaava ajoitus ei ole sarjallistuva, muuten on. Kuvan esimerkki ei ole konfliktisarjallistuva. Sarjallistuva aikataulu on aikataulu, jossa Ti tulee ennen Tj:tä. Syklillisessä graafissa tämä ei ole mahdollista.

Huom. Sykli voi syntyä useamman kohteen välille. Esimerkiksi T1 -> T2 -> T3 -> T1.

Esimerkki

Esimerkki sarjallistuvasta aikataulusta S1. Huomataan seuraavat konfliktit:

• T1 kirjoittaa kohteeseen X, jota T2 käsittelee myöhemmin. Nuoli T1->T2. Myös resurssiin Y kohdistuu konflikti.
• T3 kirjoittaa Z:aan, jota T2 lukee heti seuraavaksi. Nuoli T3 -> T2. Myös resurssiin Y kohdistuu konflikti.
• T3 -> T1 (resurssi Y)

Todetaan lopuksi, ettei sykliä ole. Esimerkki sarjallistuvasta aikataulusta voisi olla esimerkiksi T3, T2, T1

S1

T1	T2	T3
		R(Y)
		R(Z)
R(X)
W(X)
		W(Y)
		W(Z)
	R(Z)
R(Y)
W(Y)
	R(Y)
	W(Y)
	R(X)
	W(X)