Etusijakaavio - Precedence graph

Etusija kaavio , myös nimeltään konflikti kaavio ja serializability kaavio , jota käytetään yhteydessä samanaikaisuuden hallinta on tietokantoihin .

Aikataulun S etusijakaavio sisältää:

• Solmu jokaiselle suoritetulle tapahtumalle S: ssä
• Kaari T _i: stä T _{j: een,} jos T _{i: n toiminta} edeltää ja on ristiriidassa jonkin T _j : n toiminnan kanssa. Toisin sanoen toiminnot kuuluvat eri tapahtumiin, ainakin yksi toiminnoista on kirjoitusoperaatio ja toiminnot käyttävät samaa objektia (luku tai kirjoitus).

Esimerkkejä prioriteettikaavioista

Esimerkki 1

Esimerkki 2

${\ displaystyle S = {\ begin {bmatrix} T1 & T2 \\ R (A) & R (A) \\ A = A * 5 & R (B) \\ W (A) & B = B + A \\ R (B) & W (B) \\ B = B * 10 & \\ W (B) & \\\ end {bmatrix}}}$

Esimerkki 2

${\ displaystyle D = R1 (A)}$ ${\ displaystyle R2 (B)}$ ${\ displaystyle W2 (A)}$ ${\ displaystyle Com.2}$ ${\ displaystyle W1 (A)}$ ${\ displaystyle Com.1}$ ${\ displaystyle W3 (A)}$ ${\ displaystyle Com.3}$

Aikataulun D etusijakaavio, 3 tapahtumaa. Koska sitoutuneiden tapahtumien T1 ja T2 läpi on jakso (pituus 2; kaksi reunaa), tämä aikataulu (historia) ei ole ristiriitaisuussarjoitettavissa . Huomaa, että tapahtuman 2 suorittamisella ei ole merkitystä prioriteettikaavion luomisessa.

Serialisoitavuuden testaaminen prioriteettikaavion avulla

Serialisoitavuuden testaus Esimerkki

Algoritmi S-aikataulun konfliktiserialisoitavuuden testaamiseksi yhdessä esimerkki-aikataulun kanssa.

${\ displaystyle S = {\ begin {bmatrix} T1 & T2 & T3 \\ R (A) && \\ & W (A) & \\ & Com. & \\ W (A) && \\ Com. && \\ && W (A) \ \ && Com. \\\ end {bmatrix}}}$

tai

${\ displaystyle S = R1 (A)}$ ${\ displaystyle W2 (A)}$ ${\ displaystyle Com.2}$ ${\ displaystyle W1 (A)}$ ${\ displaystyle Com.1}$ ${\ displaystyle W3 (A)}$ ${\ displaystyle Com.3}$

1. Jokaista tapahtuman T _x osallistuvien aikataulussa S, luoda solmu merkitty T _i on etusija kuvaaja. Näin ollen etusija kuvaaja sisältää T ₁ , T ₂ , T ₃ .
2. Luo kullekin S: n tapaukselle, jossa T _j suorittaa read_item (X) sen jälkeen, kun T _i suorittaa kirjoitusalueen (X), prioriteettikaavioon reuna (T _i → T _j ). Tätä ei tapahdu missään yllä olevassa esimerkissä, koska lukemista kirjoituksen jälkeen ei ole.
3. Kullekin S: n tapaukselle, jossa T _j suorittaa kirjoitusalueen (X) sen jälkeen, kun T _i suorittaa lukulauseen (X), luo reuna (T _i → T _j ) etusijakaavioon . Tämä johtaa suunnatun reunan T ₁ -T ₂ (kuten T- ₁ on R (A) ennen kuin T ₂ , jossa W (A) ).
4. Kullekin S: n tapaukselle, jossa T _j suorittaa kirjoitusalueen (X) sen jälkeen, kun T _i suorittaa kirjoitusalueen (X), luo reuna (T _i → T _j ) etusijakaavioon . Tämä johtaa ulottuvat reunat T ₂ -T ₁ , T ₂ T ₃ ja T ₁ -T ₃ .
5. Aikataulu S on sarjoitettavissa vain ja vain, jos etusijakaaviossa ei ole syklejä. Kuten T ₁ ja T ₂ muodostavat syklin, yllä olevassa esimerkissä ei ole (ristiriita) sarjoittaa.

Viitteet

Ulkoiset linkit

• Tietokantajärjestelmien perusteet, 5. painos, etusijakaavioiden käyttöä käsitellään luvussa 17, koska ne liittyvät konfliktien sarjallisuuden testeihin .
• Abraham Silberschatz, Henry Korth ja S. Sudarshan. 2005. Database Systems Concepts (5 toim.), PP. 628–630. McGraw-Hill, Inc., New York, NY, Yhdysvallat.