[nastava:2003] - Re: Baze - Transakcije - Brzo :) by "Nikola Novakovic" <houraboom@ptt.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.

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.

Primeri:

vreme      T7                T8                T9
-----------------------------------------------------------------------
   t1      Read(Q)
   t2                         Write(Q)
   t3      Write(Q)
   t4                                             Write(Q


vreme      T7                T8               T9
-----------------------------------------------------------------------
   t1      Read(Q)
   t2                         Write(Q)
   t3                         Write(P)
   t4      Write(Q)
   t5      Write(P)
   t6                                             Write(Q)

Prvi primer je iz Bojoviceve skripte, i na njemu algoritam funkcionise.

Drugi primer sam bio konstruisao dok sam spremao ispit, i znam da se nesto nije slagalo. 

Ipak, proveri ovo sto sam napisao, ili sacekaj da se oglasi jos neko.


Pozdrav,
Nikola
  ----- Original Message ----- 
  From: Milan Potocnik 
  To: nastava@titan.etf.bg.ac.yu 
  Sent: Wednesday, February 26, 2003 11:17 AM
  Subject: [nastava] Baze - Transakcije - Brzo :)


  1. Kako glase pravila za redukciju suvisnih potega u Oznacenom grafu
  redosleda (onom sto ne postuje citanje pre upisa, naravno). Imam to u
  bojovicevim predavanjima, ali je tako iskonstruisana recenica da nista
  ne razumem. Dakle, moze onako debilno :)
   
  2. Kako se u Protokolu vremenskog markiranja vrsi provera i sve ostalo
  kada transakcija radi write. To nemam u predavanjima.
   
  Pozdrav,
  Milan