Schema (datavetenskap)

Inom områdena databaser och transaktionsbearbetning (transaktionshantering) är ett schema (eller historik ) för ett system en abstrakt modell för att beskriva exekvering av transaktioner som körs i systemet. Ofta är det en lista över operationer (åtgärder) ordnade efter tid, utförda av en uppsättning transaktioner som exekveras tillsammans i systemet. Om ordningen i tid mellan vissa operationer inte bestäms av systemet, används en delordning . Exempel på sådana operationer är att begära en läsoperation, läsa, skriva, avbryta, utföra , begära låsning , låsning, etc. Alla transaktionsoperationstyper ska inte inkluderas i ett schema, och vanligtvis bara utvalda operationstyper (t.ex. dataåtkomstoperationer) ) ingår, efter behov för att resonera kring och beskriva vissa fenomen. Scheman och schemaegenskaper är grundläggande begrepp inom databasens samtidighetskontrollteori .

Formell beskrivning

Följande är ett exempel på ett schema:

D

T1	T2	T3
R(X)
W(X)
Kom.
	R(Y)
	W(Y)
	Com.
		R(Z)
		W(Z)
		Kom.

I det här exemplet representerar den horisontella axeln de olika transaktionerna i schemat D. Den vertikala axeln representerar tidsordningen för operationer. Schema D består av tre transaktioner T1, T2, T3. Schemat beskriver transaktionernas åtgärder som ses av DBMS . Först T1 läser och skriver till objekt X och sedan Commits. Sedan T2 läser och skriver till objekt Y och Commits, och slutligen T3 läser och skriver till objekt Z och Commits. Detta är ett exempel på ett seriellt schema, dvs. sekventiellt utan överlappning i tid eftersom åtgärderna för alla tre transaktioner är sekventiella och transaktionerna inte interfolieras i tid.

Att representera schemat D ovan med en tabell (snarare än en lista) är bara för bekvämligheten att identifiera varje transaktions operationer i ett ögonkast. Denna notation används i hela artikeln nedan. Ett vanligare sätt i den tekniska litteraturen för att representera ett sådant schema är genom en lista:

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

Vanligtvis, i syfte att resonera om samtidighetskontroll i databaser, modelleras en operation som atomic , som inträffar vid en tidpunkt, utan varaktighet. När detta inte är tillfredsställande anges start- och sluttidspunkter och eventuellt andra punkthändelser (sällan). Verkliga utförda operationer har alltid en viss varaktighet och specificerade respektive tidpunkter för inträffande av händelser inom dem (t.ex. "exakta" tider för början och slutförande), men för samtidighetskontrollresonemang vanligtvis bara företrädet i tid för hela operationen (utan att titta på ganska komplicerade detaljer för varje operation) spelar roll, dvs vilken operation som är före eller efter en annan operation. I många fall spelar dessutom före/efter-relationerna mellan två specifika operationer ingen roll och bör inte specificeras, samtidigt som de specificeras för andra operationspar.

I allmänhet kan operationer av transaktioner i ett schema interfoliera (dvs. transaktioner kan utföras samtidigt), medan tidsorder mellan operationer i varje transaktion förblir oförändrade, vilket antyds av transaktionens program. Eftersom inte alltid tidsorder mellan alla operationer av alla transaktioner spelar roll och behöver specificeras, är ett schema i allmänhet en delorder mellan operationer snarare än en total order (där order för varje par bestäms, som i en lista över operationer ). Också i det allmänna fallet kan varje transaktion bestå av flera processer och i sig själv representeras av en delorder av operationer snarare än en total order. Sålunda, i allmänhet, är ett schema en delorder av operationer, som innehåller ( inbäddning ) delorder av alla dess transaktioner.

Tidsordning mellan två operationer kan representeras av ett ordnat par av dessa operationer (t.ex. förekomsten av ett par (OP1, OP2) betyder att OP1 alltid är före OP2), och ett schema i det allmänna fallet är en uppsättning av sådana beställda par. En sådan uppsättning, ett schema, är en delordning som kan representeras av en acyklisk riktad graf (eller riktad acyklisk graf , DAG) med operationer som noder och tidsordning som en riktad flank (inga cykler är tillåtna eftersom en cykel betyder att en första (valfri) operation på en cykel kan vara både före och efter (vilken som helst) ytterligare en andra operation på cykeln, vilket motsäger vår uppfattning om Tid ). I många fall används en grafisk representation av en sådan graf för att visa ett schema.

Kommentar: Eftersom en lista med operationer (och tabellnotationen som används i den här artikeln) alltid representerar en total ordning mellan operationer, kan scheman som inte är en total ordning inte representeras av en lista (men kan alltid representeras av en DAG).

Typer av schema

Serie

Transaktionerna exekveras icke-interfolierade (se exempel ovan), dvs ett seriellt schema är ett där ingen transaktion startar förrän en pågående transaktion har avslutats.

Serialiserbar

Ett schema som är likvärdigt (i sitt resultat) med ett seriellt schema har egenskapen serialiserbarhet .

I schema E är ordningen i vilken transaktionernas åtgärder utförs inte densamma som i D, men i slutändan ger E samma resultat som D.

E

T1	T2	T3
R(X)
	R(Y)
		R(Z)
W(X)
	W(Y)
		W(Z)
Com.	Com.	Com.

Motstridiga handlingar

Två handlingar sägs vara i konflikt (konfliktpar) om:

Åtgärderna hör till olika transaktioner.
Minst en av åtgärderna är en skrivoperation.
Åtgärderna kommer åt samma objekt (läs eller skriv).

Följande uppsättning åtgärder är motstridiga:

R1(X), W2(X), W3(X) (3 motstridiga par)

Även om följande uppsättningar åtgärder inte är:

R1(X), R2(X), R3(X)
R1(X), W2(Y), R3(X)

Konfliktlikvärdighet

Schema S1 och S2 sägs vara konfliktlikvärdiga om följande två villkor är uppfyllda:

Båda scheman S1 och S2 involverar samma uppsättning transaktioner (inklusive ordningen av åtgärder inom varje transaktion).
Båda scheman har samma uppsättning motstridiga operationer.

Konflikt-serialiserbar

Ett schema sägs vara konfliktserialiserbart när schemat är konfliktekvivalent med ett eller flera seriescheman.

En annan definition för konfliktserialiserbarhet är att ett schema är konfliktserialiserbart om och endast om dess prioritetsgraf /serialiserbarhetsgraf, när endast genomförda transaktioner beaktas, är acyklisk (om grafen är definierad att även inkludera icke-åtagande transaktioner, då cykler som involverar icke-åtaganden transaktioner kan ske utan konflikt serialiseringsbrott).

G

T1	T2
R(A)
	R(A)
W(B)
Kom.
	W(A)
	Com.

Vilket är konfliktmotsvarande med serieschemat , men inte .

Engagemang beställt

Ett schema sägs vara åtagandebeställt (beställ-beställt) eller åtagande-order-serialiserbart, om det följer schemaegenskapen Commitment order (CO; även commit-order eller commit-order-serializability). Detta innebär att ordningen i tid för transaktionernas åtagandehändelser är förenlig med prioritetsordningen (delvis) för respektive transaktioner, som induceras av deras schemas acykliska prioritetsgraf (serialiseringsgraf, konfliktgraf). Detta innebär att det också är konfliktserialiserbart. CO-egenskapen är särskilt effektiv för att uppnå global serialiserbarhet i distribuerade system.

Kommentar: Commitment ordering , som upptäcktes 1990, nämns uppenbarligen inte i ( Bernstein et al. 1987) . Dess korrekta definition visas i ( Weikum och Vossen 2001 ), men beskrivningen av dess relaterade tekniker och teori är partiell, felaktig och missvisande. ^{[ enligt vem? ]} För en omfattande täckning av åtagandebeställning och dess källor, se Åtagandebeställning och The History of Commitment Ordering .

Se likvärdighet

Två scheman S1 och S2 sägs vara visningsekvivalenta när följande villkor är uppfyllda:

Om transaktionen $T_{i}}$ $T_{i}$ i S1 läser ett initialvärde för objekt X, så gör transaktionen i S2 det också.
Om transaktionen $T_{i}$ i S1 läser värdet skrivet av transaktion $T_{j}$ i S1 för objekt X, så gör transaktionen $T_{i}$ i S2.
Om transaktionen $T_{i}$ $T_{i}$ S1 är den slutliga transaktionen för att skriva värdet för ett objekt X, så är transaktionen i S2.

View-serialiserbar

Ett schema sägs vara visningsserialiserbart om det är visningsekvivalent med något seriellt schema. Observera att per definition är alla konfliktserialiserbara scheman visningsserialiserbara.

G

T1	T2
R(A)
	R(A)
W(B)

Lägg märke till att exemplet ovan (som är detsamma som exemplet i diskussionen om konfliktserialiserbart) är både visningsserialiserbart och konfliktserialiserbart på samma gång. Det finns dock visningsserialiserbara scheman som inte är konfliktserialiserbara: de scheman med en transaktion som utför en blind skriver :

H

T1	T2	T3
R(A)
	W(A)
	Com.
W(A)
Com.
		W(A)
		Com.

Ovanstående exempel är inte konfliktserialiserbart, men det är visningsserialiserbart eftersom det har ett visningsekvivalent seriellt schema .

Eftersom att avgöra om ett schema är visningsserialiserbart är NP-komplett , har visningsserialiserbarhet lite praktiskt intresse. ^{[ citat behövs ]}

Återvinningsbar

Transaktioner commit först efter att alla transaktioner vars ändringar de läser, commit.

F

T1	T2
R(A)
W(A)
	R(A)
	W(A)
Kom.
	Com.

F2

T1	T2
R(A)
W(A)
	R(A)
	W(A)
Avbryt
	Avbryt

Dessa scheman är återvinningsbara. F är återvinningsbart eftersom T1 commits före T2, vilket gör att värdet som läses av T2 blir korrekt. Då kan T2 begå sig. I F2, om T1 avbröts, måste T2 avbryta eftersom värdet på A som den läste är felaktigt. I båda fallen lämnas databasen i ett konsekvent tillstånd.

Oåterställbar

Om en transaktion T1 avbryts och en transaktion T2 begår, men T2 förlitade sig på T1, har vi ett schema som inte går att återställa.

G

T1	T2
R(A)
W(A)
	R(A)
	W(A)
	Kom.
Avbryta

I det här exemplet är G omöjlig att återställa, eftersom T2 läste värdet på A skrivet av T1 och begått. T1 avbröts senare, därför är värdet som läses av T2 felaktigt, men eftersom T2 begicks är detta schema omöjligt att återställa.

Kaskadlös

Även "Avoiding Cascading Aborts (ACA)". Undviker att en enda transaktion avbryts leder till en serie återkallade transaktioner. En strategi för att förhindra kaskadavbrott är att inte tillåta en transaktion att läsa obekräftade ändringar från en annan transaktion i samma schema.

Följande exempel är desamma som i diskussionen om återvinningsbart:

F

T1	T2
R(A)
W(A)
	R(A)
	W(A)
Kom.
	Com.

F2

T1	T2
R(A)
W(A)
	R(A)
	W(A)
Avbryt
	Avbryt

I det här exemplet, även om F2 är återställbart, undviker det inte kaskadavbrott. Det kan ses att om T1 avbryts, måste T2 också avbrytas för att bibehålla korrektheten i schemat eftersom T2 redan har läst det obekräftade värdet skrivet av T1.

Följande är ett återställbart schema som undviker kaskadavbrott. Observera dock att uppdateringen av A av T1 alltid går förlorad (eftersom T1 avbryts).

F3

T1	T2
	R(A)
R(A)
W(A)
	W(A)
Avbryt
	åtagande

Observera att detta schema inte skulle kunna serialiseras om T1 skulle begås. Att undvika kaskadavbrott är tillräckligt men inte nödvändigt för att ett schema ska kunna återställas.

Sträng

Ett schema är strikt - har egenskapen strictness - om för två transaktioner T1, T2, om en skrivoperation av T1 föregår en motstridig operation av T2 (antingen läs eller skriv), så föregår commit eller abort-händelsen för T1 också den konflikten drift av T2.

Varje strikt schema är kaskadfritt, men inte tvärtom. Strikthet tillåter effektiv återställning av databaser från fel.

Hierarkiskt förhållande mellan serialiserbarhetsklasser

Följande uttryck illustrerar de hierarkiska (inneslutnings-) förhållandena mellan serialiserings- och återvinningsklasser :

Seriell ⊂ engagemang-ordnad ⊂ konflikt-serialiserbar ⊂ visning-serialiserbar ⊂ alla scheman
Seriell ⊂ strikt ⊂ kaskadlös (ACA) ⊂ återvinningsbar ⊂ alla scheman

Venn -diagrammet (nedan) illustrerar ovanstående klausuler grafiskt.

Venn-diagram för serialiserings- och återvinningsklasser

Praktiska implementeringar

I praktiken använder de flesta generella databassystem konfliktserialiserbara och återställningsbara (främst strikta) scheman.

Se även

schema (projektledning)

Philip A. Bernstein , Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems , Addison Wesley Publishing Company, 1987, ISBN 0-201-10715-5
Gerhard Weikum , Gottfried Vossen: Transactional Information Systems , Elsevier, 2001, ISBN 1-55860-508-8