Thomas skriver regel

Inom datavetenskap , särskilt inom området databaser , är Thomas-skrivregeln en regel i tidsstämpelbaserad samtidighetskontroll . Det kan sammanfattas som ignorera föråldrade skriverier .

Den anger att om en senare transaktion redan har skrivit värdet på ett objekt, behöver en mindre nyligen transaktion inte utföra sin egen skrivning eftersom den så småningom kommer att skrivas över av den nyare.

Thomas-skrivregeln tillämpas i situationer där en fördefinierad logisk ordning tilldelas transaktioner när de startar. Till exempel kan en transaktion tilldelas en monotont ökande tidsstämpel när den skapas. Regeln förhindrar att ändringar i den ordning i vilken transaktionerna utförs skapar olika utdata: Utgångarna kommer alltid att överensstämma med den fördefinierade logiska ordningen.

Tänk till exempel på en databas med 3 variabler (A, B, C) och två atomoperationer C := A (T1) och C := B (T2). Varje transaktion innefattar en läsning (A eller B) och en skrivning (C). Den enda konflikten mellan dessa transaktioner är skrivningen på C. Följande är ett möjligt schema för operationerna för dessa transaktioner:

${\begin{bmatrix}T_{ 1}&T_{2}\\&Läs(A)\\Läs(B)&\\&Skriv(C)\\Skriv(C)&\\Bekräfta&\\&Befästa\end{bmatrix}}\Longleftrightarrow {\begin{ bmatrix}T_{1}&T_{2}\\&Läs(A)\\Läs(B)&\\&Skriv(C)\\&\\Bekräfta&\\&Befästa\\\slut{bmatrix}}$

Om (när transaktionerna skapas) T1 tilldelas en tidsstämpel som föregår T2 (dvs. enligt den logiska ordningen kommer T1 först), så ska endast T2:s skrivning vara synlig. Om däremot T1:s skrivning exekveras efter T2:s skrivning, behöver vi ett sätt att upptäcka detta och kassera skrivningen.

Ett praktiskt tillvägagångssätt för detta är att märka varje värde med en skrivtidsstämpel (WTS) som anger tidsstämpeln för den senaste transaktionen för att ändra värdet. Att upprätthålla Thomas-skrivregeln kräver endast kontroll för att se om objektets skrivtidsstämpel är större än tidsstämpeln för transaktionen som utför en skrivning. Om så är fallet kasseras skrivningen

I exemplet ovan, om vi kallar TS(T) tidsstämpeln för transaktionen T, och WTS(O) skrivtidsstämpeln för objektet O, så sätter T2:s skrivning WTS(C) till TS(T2). När T1 försöker skriva C, ser den att TS(T1) < WTS(C), och kasserar skrivningen. Om en tredje transaktion T3 (med TS(T3) > TS(T2)) sedan skulle skriva till C, skulle den få TS(T3) > WTS(C), och skrivningen skulle tillåtas.

• Robert H. Thomas (1979). "En majoritetskonsensusstrategi för samtidighetskontroll för databaser med flera kopior" . ACM-transaktioner på databassystem . 4 (2): 180–209. doi : 10.1145/320071.320076 .

©