From 517c458f7490139646044303906be2e24e1cd958 Mon Sep 17 00:00:00 2001 From: navid Date: Wed, 17 Sep 2008 03:34:03 +0000 Subject: [PATCH] *** empty log message *** --- Robust/Transactions/Notes/sysgurantees.dvi | Bin 31984 -> 34812 bytes Robust/Transactions/Notes/sysgurantees.tex | 57 +++++++++++++++------ 2 files changed, 42 insertions(+), 15 deletions(-) diff --git a/Robust/Transactions/Notes/sysgurantees.dvi b/Robust/Transactions/Notes/sysgurantees.dvi index 777cab9529808c6e46daf608ff305f9f434f3b12..ad400e31ac9fefe82858ac94a5dbec86e9a9cdc8 100644 GIT binary patch delta 8537 zcmai34UiP&nI5Klc6JvQ{NqQ>LUz@-8+KQB!Ii9dz(Hab#6>{-2YY9FcN%B9hwffB zD`>|;y*mk`%_m(gZI0tK5DUDBM9(f#W^j!^QLYT8?n)>%2LCWz&eKcP#XF08-mkl7 zdRJ0s70C2_{eAEEzVGwA&->12f1dEa4<#SIcw%=?*X48OY)vE*6WF3}Tzp{Fsv2vN zE$mym+CDu^)+N=DGNz)bjdC60Ibh)U@hODl`Yo?rK zlHr;;nT-yV`*tjUcg40{6P~#1i*q+`x;dSwg}wAg%oOx_FLahXu`K#H=47WG9Nq)ufzCRuA+vA8ABP^ zoAbodr;;s}P7X7PjqqF1rvXiOB^3__6kTj_>_r@?hxLpB)B`Y1i#w}nCwjaAR7j9AAK`Di{ z&?b(sXCQv$#DzW(!L)uvYvWGXNH?Z?FnOY!0qP1;R)#l5_%nhV`*wY=l~n(uvz>i$ z;a7=EdlL0u%t_P(7d4rJsdQfc@+#SMl5ebqkNS$v>7tL!2mop)KAPe8*y3L|_r-DR zU^fZAHl;f$l~p#NYXyEDMRat)*JUZIO~i+mNqP7tqgzVR)b!T2@M6QdV#?71@?J&{ z7dWDxqPMe>DYYo7hOlSlHpbVsvAnDfnz`0C#y5!8xL6V82^|WAA3i@^%8{FDv_8L) zhzgNCG@6xF%>>{My+{WkOJa=VN(QSK&nSkGG4vsBJ;i0rt01DlEN&|;uUgq*m3D*8 z79=V?C>R>@I>Thc79Kt1cec}ui|phy73jvq#`GbAO;OpS2EjPO|SDvr#^22(g(M({1*5&;Q_;)n@%H>3i* zcyiICd@O<;c4|)^w?lC_d0EwWmYVg1lM5?h8}IedAeRiHa70H0hB?Bf`ZL&u+!$w_ zEo`bID3ECk*@Mhri>_N@3)Wqy={btaAeEtT`<5WBcql1x*z737*sx;e6u^uKCSYhi zFBJ`1N?#$_LF56cuz*oYyGy%fCKB7WC*E5;r?XW05mn11{?LEy>B--*5PqM>|M+Ed z$V16v|3e-c;|m6Gd&%P+nwqB?0F1$G?zRBgZa*=2@MO%3M(K%$M|bjy8HUq_t-2fp zv;+BPRT5CJj?QiO1nW01FV+eL#k7T2^1Z5IN~&p3sQZ)<|7(h%^=hmfgQym~ zV4trTl^kl$@NJr1_(b9Rz{rSD%VzkRRkDTbF))29b66R0QuR**BVMZhXZ)_pfD8K9 zVWf^?@#sg4pwbYyr~xKS~b{ye;{1&+^Yd2l!1jiI~{*M_+>rWAYPSs!Zyj(FBb zREM3beJKMJ5t0!;mv{=USrPgM>14W*SEyQS{LDvPWjS6)$9&V=S^g_q_{F7>3sG{0 z4nvC6G_GBwx@^|1Q_mAVJv!QD3!4vAq|1R*Z2rV1Ytn;FQH(s{)31M&XD$sCt@%2_6p zikw;{-GDz`cHo=~8{IIKu|w!bia2B(0gHWn&ZU;v{pA%P$Llm()K0CEJt{|zsQo*N z_4n-4t<#6hA>Ebj#L?YI)70tIBEuL058<`=MZCA@?x>SPDlViTydb-(w2YBCf9utM zIvm_v&Sp#YY^%#x)U1+`C@WGYoOw}5vr8+32T}*&9WPQx!7O6$U#}U*-p)Rr0=?G8U2G$@1$n^sS5m-3^F!H)Md0{ z!GA>+p8n1KIfe)-=Q-lsl+SsJ2mzU1rBG1VAVl0;vE0vmB1m!0`%>P}7=e1I-%fak z)&qw`$D9FqH2?tekY`Z7NbK+w5;Y3f@;$u5t+AUr!7Pw0k|Wgb9qnSc>$&UJmr8bn zIMZ(_uSe6+INI%B&B}`3>LTy4VU+nH!2lEK;sLxnJ~q%rsG>Li>~p`X-4lOxB@Pik z*^h;HFPL#vL-qkKy2_I4=a703poZJexGHqZ{VqaEB;l$OGDr%Awab+#yMF$;*LT=; z*Ob3U;n4H~a6ZDoRCiy7Gg7nC*b(W(@>C0knXJ<@Dyf>mZ%^ewML24svOs=in-|Tn z8eUlAUmZGY6fFwg2^){jlFi!@%KWhRaD%TZO-CdesA|~4?ia6Y$KQuvUZHb&K+=Fg z%;0~X@X=3JGC3cpwwzLQNs8l%#iVTejYMy5A3QQ%*B##)z=yU)g5n6kCbSj-{N3$( zP@iCR*s~FGY~gon%M#-Vt5hN`wV|}Z0e?JB{6Z@v)P24h?%+vS$w5}uE7gQog(z)t z>s@fA?m`c8EDNDA{_07>H{M}UU_gjg@0K{T`gjklBWH`ya0>{6Upf z0~S(T&8zqJqSx`Br(}P83zGfv#%Yj~ywY=_jgIQ$oph-P-}vmsZW9*WD?fssq4tB8 zQ*bDyshu3kn@SNiFY06rO*d?85z2^oq-w7<{g$lUepz@v329LG&mX{6mHGoRE$Tbw zhkX%tV+NbDdFpL1B@PeRiT7W@1N@V`J+J3Q^g8y+sgL@t2;B1xxP?kJ3GnlTpWh$o zs{+@n)M8M>h_M2Nfg>);nZBLu-Ua7bwY&PLkGyRgxoX}lAHhcDp$>1}%&_jnqpB5Q z!hutViFIHJ=crq+regZledRum#WP&xFWzF!+U3tv9Vb2`>!`I2QXD&n;eyK@VdPl~ z)*zsT@?x@3JcU)3v`KTIflYVVmC;2DBhOKb$4*b2K0DI;k;0G0DDmXv$t*Ee-`FIQ z_t{wu=UX;8r;@3dSx}ojfC`$`7t_23a{y@h13~wD^65@~1DDQ?rv*jA<;@;N0^~WS z@6L++mIScLp)dDS-V$vhN`5pukh7VjJX^fCNmx4~%G$<2!OHGLg zy$kNiYb2$#(2c-7VI}K`xxbIqU}%=~#ajYGtN30idFdm=zC~()G#M9VB*<(r_hX7t zRayl&5g(mheTJf8FjdaLEojX0BcTC^ohgyS9-B#5k3>y?5W zW*d9Gd8SqO43ZZ3mGV?IMnFfT<*_HmAmWN{N_t3hMrzuU3lOo# zm#$JU7DPVW^<;z<<)s7$b@n;-R?biK5=Tmu@IZ_s*k=d!#xMgJZ?KFTs3ew?+>PjK zHTqlE6=XLxt~>`RpEsrzZOA}{Xa4HO?4AKCS7r{-!x)m+ExG{ZX3TF?6L{uFcfdp| zA{eA>bTl9qYXiH&Hc+6UshCJip38nSdBy^21bbD``2!qp;^X&s1?J(pG{OSNBA|1C zhZy7*LETgV4cGntNE}MlCNL`x$SM~nj@T<=6f5=$F|dre+EeeKI`eU4&}h;1`AjEP zE8Qw}l8Cp=NWg3H(SnnFvjJtM63wXPOMZEZoQyI-5zR~BJ>Vl`OFQ}IWS*{IlSoEX zx^5l8GiY0Skye?qip;ZUG)y@5lHTIq- z@pdzmd^MNeQ=V@}RaVS{0KJoz?f4x40h8JS~PUH1^)>!-qAGrlZ=DK#*6;pj}%ueah}}oAJGTZ92 z{2maD(XLo14%9XGAnTCSMV+nF`kZ3XbSq>7A*tMdgIrZN&|2vpQ+;cUX zFl~BWL*rI-5Tbqu<{n*j4R21bd^*?S9merL`G}}^&-^H&Op22;SrMU~*M2nfp7`27 zo-vBm=7rj*hTP||V2=OpKcRv7;18UTA92Lj9>>QZlH-;>bkk^)Cw^8p{!21{@};)~ z^caN#c~RT3d9J1v-?^MQF*o}{7^V=dFKU_YF3QI|q1pn+DRaM@z3JO}-9 z>%dqdNcaAh@btl#oN$?R?)3A-rI*CkAopsQiL7;IqZRuC4cna{;MyP2^oV*m`f-uy zhkpSdO-WOWxbzZ=L8~0afX)x06gi&;EBICPzVFBL!WQql=4+9#sE-Wsbh0THg3y?~ z$9w~+>fqf9a^SY~`^y0*akCLT3>K#@+D`UCo*=gopvXX1IwQLG48WSX@5so!8bx>r3-)#QKx-KCEFs zSkjZ6e;?L=gZ*~Fs$gl$!WE*pt8wN1?AJ@mSXlb*j2iYg*Y_ls9^ni3FS|8ZSbMFN zN{8c?gD0+ESHrGa*OOfHWcB#(-xMCd_oheq@eoRkt?S0FN7l8c*+Ye%WahiH>-NEL z<+{PkD=R-P+<=t})pu&xEt`6h8@{5QQ#bEg=+9yQx?u~qg59Ebv!{n^4t_ASF%{kL gnN976;HF9+|j%8%W~J+YPl=WJGfliYbo_?p{1ojX*pVsRs`wnCEr}OO?K1W zO|Jo&fHOrA2wfh{tc}2+9ey|}v>hB*M+iMdz)^8TQLsS$F@uN-GFF*k#LxTgZY~99 z>>oGH?)$#)`|)|7_ujsLcl_=5rtLkep%Z4tvBNmHIqk~)KAKW~etc>PFP1&8a|2ce#VHm}6;Hxu(SKvxTK=`MMIj-?TDNU}ilhC#WE(zrCZ2e>O&4b+#sDGen#Pos%_hk7(B^C9U_*0kUN9+tgveHRG>$M-o@L0G(kCTT@=B zz>K=`!Y#IN2p&w^v&A29l~Z)04VxcMX2~CQKj;#c zX4qQV!E-IYPS1EW%WY}>*XpPJU zOnE3<&@uukJ=8*?3bHUcN=x;lEnXlVqYkGzd!<+`N04Q~w z?oH#TF)lK_o@sf#8fTq<*k&QRJEJ*TP02QF$10_rk|k>@ZCaMFmlXGJd=>s9Qm&GH z3c49B03GZb^Mu7%p~i@J6_R%Ft*3#s!C_iBYZm?e)H5ryChup|**8w)1T1#Q5;Jgn z1XMU*Q|wh~k4M$NKUJgY*;RV^$92Vi^6imQ2qj#pmpxBft zSsI|hQJoKbB9S$92+4?B*Oer1**&9lEs|~L;k)Cc;z%c>lxk|ou7BcB^ zCOyaWavC9z;cdN=AY?LY@#E*2Ry}_FTu!J!*260hFE2Z+GM5u&xiaOLy8B^&6Jw{pZNf=*70U}J%QYU=Pa3}BKnT&;Ld84!i54*y8L z2{?=GM@xX!G8~RDfC2}UpD&XH1!EYHsECNI0o62cnJ(*DwxX`2cgsr*HnO4AE?~Xf%X)UZcW{>lBu+=?zk}Q5apA11#_z@haK6!Ai(b&RQHRj>5~w@q<(lJI`dA4B z#Wr(=M{sR+Zf;OalgMvLrjd<=Ub;c1N$Nqv6u7rg0O#n2?a21*Aj3_l)|EG|Tav0N zZ+vz&+SdA3cUp^afS*c3qWoEa3zoesuB1Wc>FME16EF>MoATA0C zkIBPT#j4&WTnySTM7ajQ!r%(rLkIU}?!ooIc%%!ppHj?{Mmg zmA{XCMJGP#>wocqKFT2{no~=xJl67ZdiO6H7rKdq&rZdr{cGR%2i=nnTqU_+UqG!D zq|Tchg5-}IBNTNE#B=%Z5p-pD#?i%yHY*R=FHGT7P?^n@YZ4skx^hht721-lr2m>9 zM~Tnf@@1%wNeefsNSzDYc#-7G8)z zI9gN9b5Xi=)$He5;sTjsEX>cCjVetI+Kt&@2d{$;w2P@5 z-S%HC^=$!c;*E>DJ_JvmWNPX?ukbKauB-RF+&s&7{p$(8WPo^W5H~YDGq|i?Air5B zfsvT+QPD0m@W{q&63uS5*&MUi@w8g9V2Z`kEyd1saej)fE&=-)8)?f29GTOLR6%RV zh)x4(wDp3X*DMqr6t$8?E&j(#m!;_P>C9~lo-{_l_9qteb`*2xKfVR5q8OkK=sPWs$; zxq>`Ss}VZGH9wtK1V&NEDti02u5+GAyB`!Wb-U`#J40=3ey~TN-u!;|lc)TJY6~tI zX!d}bdiI9pDOWvvqhzV60g%nCDX*S0IYf_L*#HO+U;*Bm@02q^T1xM=HZ_C)mVn@gmBO743;Zx;Uo`y8WzW7G(eDF=jIBUo6ITW3+a{J_=ks zw`7#2W+fT+(|PKjT2$G0+L`F8giES-iIHhNqfd@|J}=zD!#a(x3h1yrat}xRvAKlR zRC%+EEiBl>narrD>HM+4Ro=X@)f=1oTGC+mOOD{cH0GoJ5mlUu=qCb+4H{yG0ujyW zm_4({AE3!I+{Do} z+;fj!EVnfN5)c*!x7<@7xy)zY<#i5|sb0(r7n+LT9;|#O*1Ns{8<}bab;F^xYwCd3 zEP6n>Xzg1OZqk@w?5aEP%=0KWbzn?FHE_B~=vboogN&8eiYy{DUhU*Z6SSC(uXCAm zUjtJ3H86uG1qRaDe7S{w^4u7Mqpm)e1~#A$0`kKTTGPm08tj{Wb>j4%hUPUp6P-|; zT$5fum1h7l!j#OySQ`3H;~e1EifiizoGuhJcr3^dk*$!%ArYl>%{)I>97nvjPS-W!#db4VCjd4mR=gfz;wX~dpV)oVt@zu&R~LX zU~31ue>uD7BwWj@oD4vBr3nyxGvh5VJM1R<=0ZhH`NLUpIbo z8%LF}#nDm^mG$CJgAX5Qj+QPzSlARvcuRQ(X;wFXA7MkJPGoHDLMU0>v_XPYeSgK0 z6t#>&9PUS#PY%@*Yq!yPeRF3fHXUqv%`@jWa&%qaC$=RvJs!OP+ICdk>ErLnb2o6q zU@*(a0P~)|qUE@_ieE_bm$!UsvL{S)cz)i`xUfR|=^On$o$Z}Pu1>?{coxq3#Nl`Q z4=c%_Q_z1>eRSWP*>v9EwrLL@t`074r-xF*@wvl*!d&{%vSTXmREHnF;Ad)d-IbuzZW)dj?#Ge2^yqD=_)R+f=C*~jXx2 E0Wl+Fd;kCd diff --git a/Robust/Transactions/Notes/sysgurantees.tex b/Robust/Transactions/Notes/sysgurantees.tex index 6c840770..83e9592e 100644 --- a/Robust/Transactions/Notes/sysgurantees.tex +++ b/Robust/Transactions/Notes/sysgurantees.tex @@ -14,38 +14,65 @@ Transaction is like below: This is adopted from dstm and can and may be changed. Within this block which represents a member of set $T$. The functions beginTransction and endTransaction are implicitly called by the system without the intervention of the programmer.However, the programmer can read and write from TransactionalFile Objects within the blocks of a member of $T$. To provide consisteny the read and write from ordinary Java object files should be prohibited, otherwise the semantics of transactions would not be preserved. Hence, the sequence of operations provided to the programmer within a member of $T$ is the set \{TransactionalFile.Read(), TransactionalFile.Write()i, TransactionalFile.Seek()\}. However, always a beginTransaction() and commitTransaction() (if the transaction does not abort prior to this point) are performed too. \\ -The flow of program should be in a manner that we could have an arbitrary serial order of the members of $T$ (e.g. $T_5,T_6,T_1$,...) or any other order. The serial order should be in such a way that for any given two members of the set $T$, either the effect of all opertaions of \{ TransactionalFile.Read, TransactionalFileWrite, TransactionalFile.Seek()\} within $T_i$ should be visible to $T_j$ or none should be visible. In the first case we would say the $T_i$ precedes $T_j$ and in the seconds case $T_j$ preceds $T_i$ and $T_i$ can observe all the effects made by the operations in $T_j$. \\ +A Transaction consists of a sequence of operations. Thus, a transaction can be represented as the \{$OP_1$, $OP_2$, ..., $OP_n$\}. The flow of program should be in a manner that we could have an arbitrary serial order of the members of $T$ (e.g. $T_5,T_6,T_1$,...) or any other order. The serial order should be in such a way that for any given two members of the set $T$, it looks all the operations of one occur before all the operation of the other. In the first case we would say the $T_i$ precedes $T_j$ and in the seconds case $T_j$ preceds $T_i$ and $T_i$ can observe all the effects made by the operations in $T_j$. \\ \subsection{Defenitions} -Def 1- 1-An operation in $T_i$ is said to have "changed" or "affected" some data structure in correspondece to all members of $OP_{T- T_i}$ , when it reflects the changes in the filesystem in such a way that the modification is durable and irreversible. A transaction with such an operation $T_i$ in its operation set is said to have changed the data 2- An operation in $T_i$ is said to have "changed or affeced the data in correspondence to all the operations in $OP_{T_i}$ as soon as the operation is encountered \\ +Def 1- \emph{Set of Operations}: Operations are taken from the set \{readoffset(fildescriptor), writeoffset(filedescriptor), readdata(inode, offset, length), writedata(inode, offset, length)\}. We denote read operations as readoffset and readdata and write operations as writeoffset and writedata.\\ -Def 2- An operation in $T_i$ is said to have "used" the data when it has read some data and has done some actions that is potentially irreversible. hence if the data in question was to change, $op$ would have different results. A transaction with such an operation in its operations set is said to have used that data. Any data read and used within a transaction at its commit instant does not count as using. "Use" can just be attributed to the operations actually reading data before commit instant. \\ +%Def 1- 1-An operation in $T_i$ is said to have "changed" or "affected" some data structure in correspondece to all members of $OP_{T- T_i}$ , when it reflects the changes in the filesystem in such a way that the modification is durable and irreversible. A transaction with such an operation $T_i$ in its operation set is said to have changed the data 2- An operation in $T_i$ is said to have "changed or affeced the data in correspondence to all the operations in $OP_{T_i}$ as soon as the operation is encountered \\ -Def 3- A transaction $T_i$ is said to "commit" at instant $t_i$, if and only if it reflects its "changes" in the filesystem or equivalently makes it changes visible to the whole system for all members of $T$ accesing the data at instant $t_j$ such that $t_j > t_i$ . An operation $\in OP_{T_i}$ is said to commit if and only if $T_i$ commits. Commit instant are not splittable, hence it appears to other transactions that all changes are refleted in the file system together.\\ +Def 2- \emph{Operations Sharing Resources} 1- A readoffset operation and writeoffset operations are said to be sharing resources if they both operate on the same filedescriptor. 2- A readdata and writedata operations are said to be sharing resources if they both operate on the same inode AND the range of (offset, offset + length) within one overlaps with that of the other.\\ -Def 4- $\forall op_i \in OP_{T_i}$, $\forall op_j in OP{T_i}$, $op_i$ precedes $op_j$ if and only if $op_j$ does not use the data changed by $op_i$ OR if it does, then $op_j$ sees the changes made by $op_i$ unless data has been changed by a more recent precedessor. Furthermore \\ +Def 3- A read operation can only see the writes made by write operations sharing reources.\\ -Def 5- Succeds relationship is defined similarly. \\ +Def 4- \emph{Commit Instant}: A transaction $T_i$ is said to "commit" at instant $t_i$, if and only if it reflects its "writes" mabe by write operations in the filesystem or equivalently makes it writes visible to the whole system for all members of $T$ accesing the data at instant $t_j$ such that $t_j > t_i$ . An operation $\in OP_{T_i}$ is said to commit if and only if $T_i$ commits. Commit instant are not splittable, hence it appears to other transactions that all writes are refleted in the file system together.\\ -Def 6- If operation $a$ both precedes and succeds operation $b$ since they do not share any resources so the changes can be made visible, $a$ both precedes and succeds $b$. \\ +Def 5- \emph{No See In Future}: Assume $T_i$ is an uncomiited transaction and $T_{commited}$ indicates the set of commited transaction. A read operation $b \in OP_{T_i}$ MAY ONLY see the writes(changes) made by write operation $b$ that shares resources with $b$ AND also is subject to one of the following conditions:\\ + +\hspace{7mm} 1- $a \in OP_{T_j}$ ($j \neq i$) such that $T_j \in T_{commited}$ \\ + +\hspace{7mm} 2- $a \in OP_{T_i}$ and $a$ happens before $b$ in the natural order of the transaction. Formally, $a$ has a lower position than that of $b$ in $OP_{T_i}$ = \{$OP_1$, ..., $OP_n$\} \\ + + +Def 7- \emph{Precedence Relationship for Read-Write Operations}: Assume $b$ is a read operation and $a$ is a write operation, and $a$ and $b$ share resource $r_i$, $a$ precedes $b$ ($a \rightarrow b$) if complying with Def 5, $b$ is allowed to see the writes to $r_i$ made by $a$. Otherwise, $b \rightarrow a$. \\ + + +Corrolary- \emph{Read Must See Most Recent Comitted Write}: If $a \in OP{T_i}$ reads the resource $r_i$, in case $a$ has multiple precedessors sharing $r_i$ (denoted as $OP_{precedessors-for-r_i}$), then if all of them are from sets other than $OP_{T_i}$, $a$ sees the writes made by $op_{T_j} \in OP_{precedessors-for-r_i}$ such that $T_j$ has the greatest "commit instant" between all transaction with such operations. Otherwise, $a$ sees the most recent precedessor in $OP_{T_i}$. \\ + +proof: Consider case 1 that all precedessors are from sets of operations other than that of $a$'s, according to Def 4 all these prcedessors belong to comitted transactions. Assume $T_i$ is accessing data at $t_i$, $t_i$ is neccasarily gretaer than all members of \{$committime_{T_1}, ..., commitime_{T_{i-1}}$\},and hence the writes to $r_i$ made by these commited transaction, have accroding to Def 1 been already reflected in the file system. Since, $T_{i-1}$ has the greatest commit instant its changes have overriiden that of previously commited transactions and thus, $a$ reading $r_i$ from file system sees these changes.\\ + +In case 2 that there are operations preceding $a$ in $OP_{T_i}$, according to defenition of transaction $r_i$ should be read from the writes made by write operations in $T_i$, and as the last of such write operation overrides the written data to $r_i$ by other operations, $a$ gets to see the most recent precedessor in $T_i$.\\ + + +Def 8- \emph{Precedence Relationship for Other Types of Operations}: Follwoing rules are ONLY enforced if precedence elationship is not etemined between two transactions by Def 6. 1-If $T_i$ and $T_j$ are two transactions both committed with commit instant of $T_j$ being greater than commit instant of $T_i$ then $\forall op_i \in OP_{T_i}, \forall op_j \in OP_{T_j} op_i \rightarrow op_j$. 2-If two operation belong to the same transaction, then the one that occurs earlier in natural order of transaction precedes the other. 3- If $T_i$ is committed and $T_j$ is not, $\forall op_i \in OP_{T_i}, \forall op_j \in OP_{T_j} op_i \rightarrow op_j$. 4- If neither $T_i$ has commited nor $T_j$, then $\forall op_i \in OP_{T_i}, \forall op_j \in OP_{T_j} op_i \rightarrow op_j$, if there is either not a precedence relationship between $op_i$ and $op_j$ or it is $op_i \rightarrow op_j$. 5- Otherwise, it means some operations in $T_i$ precede some of thos in $T_j$ and the other way around, for thos pairs not having such relationship it is assigned arbitrarily.\\ + +Def 9- $\forall$ $op_{T_i}$ $\in OP_{T_i}$ and $\forall op_{T_j}\in OP_{T_j}$ if there is a precedence relationship between $op_{T_i}$ and $op_{T_i}$ if and only if $op_{T_i} \rightarrow op_{T_j}$ then $T_i$ $\rightarrow T_j$ \hspace{8mm} (this defines precedes relationship for members of $T$) \\ + +%Def 2- An operation in $T_i$ is said to have "used" the data when it has read some data and has done some actions that is potentially irreversible. hence if the data in question was to change, $op$ would have different results. A transaction with such an operation in its operations set is said to have used that data. Any data read and used within a transaction at its commit instant does not count as using. "Use" can just be attributed to the operations actually reading data before commit instant. \\ + +%Def 4- $\forall op_i \in OP_{T_i}$, $\forall op_j in OP{T_i}$, $op_i$ precedes $op_j$ if and only if $op_j$ does not use the data changed by $op_i$ OR if it does, then $op_j$ sees the changes made by $op_i$ unless data has been changed by a more recent precedessor. Furthermore \\ + +%Def 5- Succeds relationship is defined similarly. \\ + +%Def 5- \emph{Precedence Relationship for Operations}: Assume $b$ is a read operation and $a$ is a write operation, and $a$ and $b$ share resource $r_i$, 1- if $b$ see the writes made by the $a$ to $r_i$ and their relationship conforms to Def 4, then $a$ precedes $b$ ($a \rightarrow b$) 2- if $b$ does not see the changes written by $a$, however their relatioship conforms to Def 4, $r_i$ has been changed by operation $c$ such that $t_{a-commit-instant}