[nastava:2003] - Re: Baze - Transakcije - Brzo :) by "Damjan S. Vujnovic" <damjan@galeb.etf.bg.ac.yu>

Ja sam algoritam shvatio (i donekle proveravao) ovako:
Iz oznacenog grafa redosleda su uklanja w_w poteg koji ide od cvora A do cvora B pod sledecim uslovima:
1.w_w poteg ne sme da se poklapa ni sa w_r, ni sa r_w potegom (koji takodje idu od A ka B), dakle ni sa jednim od ta dva
2.Iz cvora B mora polaziti w_w poteg ka nekom trecem cvoru C, i on se ne sme poklapati sa w_r potegom (od B do C)
3.Ako ima osnova za uklanjanje w_w potega (od A ka B) onda se mogu ukloniti i svi w_r i r_w potezi, koji se zavrsavaju u cvoru B.

Sa ovim se slažem.

Proverio sam, ovo je tacno kad postoji samo jedna promenljiva, ali kad ima vise promenljivih, algoritam nije bio dovoljno precizan. Najpre, treba naglasiti da se w_w potezi A->B i B->C moraju odnositi na ISTU promenljivu. Osim toga bio sam dosao do zakljucka da se mora naglasiti jos nesto, da li w_r poteg iz tacke 1. ili w_r poteg iz tacke 2. ili oba, a mozda i r_w poteg, ne secam se, mozda i sva tri, moraju odnositi na isti podatak za koji je konstruisan w_w poteg.

Kada se transakcije izvršavaju nad više promenljivih, za svaku promenljivu konstruišeš poseban graf. Da bi redosled izvršavanja odgovarao nekom zadatom serijskom redosledu izvršavanja, potrebno je da svaki od dobijenih (redukovanih) grafova odgovara tom serijskom redosledu

Pozdrav,
Damjan S. Vujnović