Tidsplan (informatikk) - Schedule (computer science)

Innen databaser og transaksjonsbehandling (transaksjonsadministrasjon) er en tidsplan (eller historie ) for et system en abstrakt modell for å beskrive kjøring av transaksjoner som kjører i systemet. Ofte er det en liste over operasjoner (handlinger) ordnet etter tid, utført av et sett med transaksjoner som utføres sammen i systemet. Hvis rekkefølgen i tid mellom visse operasjoner ikke bestemmes av systemet, brukes en delvis ordre . Eksempler på slike operasjoner er å be om en leseoperasjon, lese, skrive, avbryte, begå, be om en lås, låse osv. Ikke alle transaksjonsoperasjonstyper skal inkluderes i en tidsplan, og vanligvis bare utvalgte operasjonstyper (f.eks. Datatilgangsoperasjoner ) er inkludert, etter behov for å resonnere om og beskrive visse fenomener. Tidsplaner og tidsplanegenskaper er grunnleggende begreper i databasens samtidighetskontrollteori .

Formell beskrivelse

Følgende er et eksempel på en tidsplan:

I dette eksemplet representerer den horisontale aksen de forskjellige transaksjonene i tidsplanen D. Den vertikale aksen representerer tidsrekkefølgen for operasjoner. Tidsplan D består av tre transaksjoner T1, T2, T3. Tidsplanen beskriver handlingene til transaksjonene som DBMS ser . Først T1 leser og skriver for å motsette X, og deretter forplikter. Deretter T2 leser og skriver for å motsette seg Y og forplikter seg, og til slutt, T3 leser og skriver for å motsette Z og forplikter. Dette er et eksempel på en serieplan , dvs. sekvensiell uten overlapping i tid fordi handlingene til alle de tre transaksjonene er sekvensielle, og transaksjonene ikke er sammenflettet i tid.

Å representere tidsplanen D ovenfor med en tabell (i stedet for en liste) er bare for å gjøre det enkelt å identifisere hver transaksjon. Denne notasjonen brukes gjennom artikkelen nedenfor. En mer vanlig måte i teknisk litteratur for å representere en slik tidsplan er ved en liste:

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

Vanligvis, med det formål å resonnere om samtidighetskontroll i databaser, blir en operasjon modellert som atomisk , og forekommer på et tidspunkt, uten varighet. Når dette ikke er tilfredsstillende, spesifiseres start- og sluttidspunkt og muligens andre punkthendelser (sjelden). Virkelig utførte operasjoner har alltid en viss varighet og spesifiserte respektive tidspunkter for forekomst av hendelser i dem (f.eks. "Eksakte" tidspunkter for begynnelse og fullføring), men for resonnering av samtidighetskontroll er vanligvis bare forrang i tid for hele operasjonen (uten å se på ganske kompliserte detaljer om hver operasjon) betyr noe, dvs. hvilken operasjon som er før eller etter en annen operasjon. Videre, i mange tilfeller, spiller ikke før / etter-forholdet mellom to spesifikke operasjoner noe og bør ikke spesifiseres mens de spesifiseres for andre operasjonspar.

Generelt kan operasjoner av transaksjoner i en tidsplan flettes inn (dvs. transaksjoner kan utføres samtidig), mens tidsordrer mellom operasjoner i hver transaksjon forblir uendret slik det er underforstått av transaksjonens program. Siden ikke alltid tidsordrer mellom alle operasjoner av alle transaksjoner har betydning og må spesifiseres, er en tidsplan generelt en delvis ordre mellom operasjonene i stedet for en total ordre (der ordren for hvert par bestemmes, som i en liste over operasjoner ). Også generelt sett kan hver transaksjon bestå av flere prosesser, og i seg selv være riktig representert av en delvis rekkefølge av operasjoner, snarere enn en total ordre. Generelt sett er en tidsplan en delvis operasjonsrekkefølge som inneholder ( innebygd ) delordrene til alle sine transaksjoner.

Tidsrekkefølge mellom to operasjoner kan representeres av et ordnet par av disse operasjonene (for eksempel eksistensen av et par (OP1, OP2) betyr at OP1 alltid er før OP2), og en tidsplan er generelt sett et sett av slike bestilte par. Et slikt sett, en tidsplan, er en delvis rekkefølge som kan representeres av en asyklisk rettet graf (eller rettet asyklisk graf , DAG) med operasjoner som noder og tidsrekkefølge som en rettet kant (ingen sykluser er tillatt siden en syklus betyr at en første (hvilken som helst) operasjon på en syklus kan være både før og etter (hvilken som helst) annen operasjon på syklusen, som strider mot vår oppfatning av tid ). I mange tilfeller brukes en grafisk fremstilling av en slik graf for å demonstrere en tidsplan.

Kommentar: Siden en liste over operasjoner (og tabellnotasjonen som brukes i denne artikkelen) alltid representerer en total rekkefølge mellom operasjonene, kan tidsplaner som ikke er en total ordre ikke representeres av en liste (men kan alltid representeres av en DAG).

Typer tidsplan

Seriell

Transaksjonene utføres ikke sammenflettet (se eksemplet ovenfor), dvs. en serieplan er en der ingen transaksjoner starter før en pågående transaksjon er avsluttet.

Serialiserbar

En tidsplan som tilsvarer (i utfallet) en serieplan har egenskapen serializability .

I tidsplan E er ikke rekkefølgen som handlingene til transaksjonene utføres den samme som i D, men til slutt gir E det samme resultatet som D.

Motstridende handlinger

To handlinger sies å være i konflikt (motstridende par) hvis:

1. Handlingene tilhører forskjellige transaksjoner.
2. Minst en av handlingene er en skriveoperasjon.
3. Handlingene får tilgang til det samme objektet (lese eller skrive).

Følgende sett med handlinger er motstridende:

• R1 (X), W2 (X), W3 (X) (3 motstridende par)

Mens følgende sett med handlinger ikke er:

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

Konfliktekvivalens

Tidsplanene S1 og S2 sies å være konfliktekvivalente dersom følgende to betingelser er oppfylt:

1. Begge planene S1 og S2 involverer det samme settet med transaksjoner (inkludert bestilling av handlinger i hver transaksjon).
2. Begge rutene har samme sett med motstridende operasjoner.

Konflikt-serierbar

En tidsplan sies å være konfliktserialiserbar når tidsplanen tilsvarer en eller flere serielle tidsplaner.

En annen definisjon for konfliktserialiserbarhet er at en tidsplan kan konfliktserialiseres, hvis og bare hvis dens forrangsgraf / serielliserbarhetsgraf, når bare engasjerte transaksjoner blir vurdert, er syklisk (hvis grafen er definert til å inkludere også ikke-forpliktede transaksjoner, så er sykluser som involverer uforpliktende transaksjoner kan forekomme uten brudd på konfliktserialisering)

Som er konfliktekvivalent med serieplanen <T1, T2>, men ikke <T2, T1>.

Forpliktelse bestilt

En tidsplan sies å være forpliktelsesbestilt (forpliktelsesbestilt) eller forpliktelsesbestillingsserierbar, hvis den overholder forpliktelsesbestillingen (CO; også forpliktelsesbestilling eller forpliktelsesrekkefølgen) tidsplanegenskapen. Dette betyr at rekkefølgen på tidspunktet for transaksjonenes forpliktelseshendelser er kompatibel med forrangsrekkefølgen (delvis) for de respektive transaksjonene, som indusert av tidsplanens acykliske forrangsgraf (serialiserbarhetsgraf, konfliktgraf). Dette innebærer at den også kan konfliktserialiseres. CO-egenskapen er spesielt effektiv for å oppnå global seriabilitet i distribuerte systemer.

Kommentar: Forpliktelsesbestilling , som ble oppdaget i 1990, er åpenbart ikke nevnt i ( Bernstein et al. 1987 ). Den riktige definisjonen vises i ( Weikum og Vossen 2001 ), men beskrivelsen av dens relaterte teknikker og teori er delvis, unøyaktig og misvisende. For en omfattende dekning av forpliktelsesbestilling og dens kilder, se Forpliktelsesbestilling og Historien om forpliktelsesbestilling .

Se ekvivalens

To planer S1 og S2 sies å være visningsekvivalente når følgende betingelser er oppfylt:

1. Hvis transaksjonen i S1 leser en startverdi for objekt X, gjør også transaksjonen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$
2. Hvis transaksjonen i S1 leser verdien skrevet av transaksjonen i S1 for objekt X, gjør også transaksjonen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {j}}$${\ displaystyle T_ {i}}$
3. Hvis transaksjonen i S1 er den siste transaksjonen for å skrive verdien for et objekt X, er også transaksjonen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$

Serier kan vises

En tidsplan sies å være serieserierbar hvis den tilsvarer en seriell tidsplan. Vær oppmerksom på at per definisjon er alle tidsplaner som kan seriekonflikter, serieseriserbare.

Legg merke til at eksemplet ovenfor (som er det samme som eksemplet i diskusjonen om konfliktserialiserbar) er både serieserialiserbar og konfliktserialiserbar samtidig. Det er imidlertid tidsplaner som kan vises som ikke kan konfliktserialiseres: tidsplanene med en transaksjon som utfører en blind skriv :

Ovennevnte eksempel er ikke konfliktserialiserbart, men det kan serieseriseres siden det har en seriekvivalent seriell tidsplan <T1, | T2, | T3>.

Siden å bestemme om en tidsplan kan viseserialiserbar er NP-komplett , har visningsserialiserbarhet liten praktisk interesse.

Gjenopprettelig

Transaksjoner begås bare etter at alle transaksjoner hvis endringer de leser, begår.

Disse tidsplanene er utvinnbare. F kan gjenopprettes fordi T1 forplikter seg før T2, noe som gjør at verdien som blir lest av T2 er korrekt. Da kan T2 forplikte seg. I F2, hvis T1 ble avbrutt, må T2 avbrytes fordi verdien av A den ble lest er feil. I begge tilfeller er databasen igjen i en konsistent tilstand.

Uopprettelig

Hvis en transaksjon T1 avbrytes, og en transaksjon T2 forplikter, men T2 er avhengig av T1, har vi en uopprettelig tidsplan.

I dette eksemplet er G ikke gjenopprettelig, fordi T2 leser verdien av A skrevet av T1 og begått. T1 senere avbrutt, derfor er verdien som ble lest av T2 feil, men siden T2 ble begått, er denne tidsplanen ikke gjenopprettelig.

Cascadeless

Også "Unngå Cascading Aborts (ACA)". Unngår at en enkelt transaksjon avbryter, fører til en rekke tilbakeføringer av transaksjoner. En strategi for å forhindre kaskadeavbrudd er å tillate at en transaksjon ikke leser uforpliktede endringer fra en annen transaksjon i samme tidsplan.

Følgende eksempler er de samme som i diskusjonen om utvinnbar:

I dette eksemplet, selv om F2 kan gjenopprettes, unngår det ikke kaskadeavbrudd. Det kan sees at hvis T1 avbryter, må T2 også avbrytes for å opprettholde korrektheten av tidsplanen, ettersom T2 allerede har lest den uforpliktede verdien skrevet av T1.

Følgende er en gjenopprettbar tidsplan som unngår kaskadeavbrudd. Vær imidlertid oppmerksom på at oppdateringen av A av T1 alltid er tapt (siden T1 er avbrutt).

Vær oppmerksom på at denne tidsplanen ikke kan serienummeres hvis T1 blir forpliktet. Å unngå å kaste bort er tilstrekkelig, men ikke nødvendig for at en tidsplan skal kunne gjenopprettes.

Streng

En tidsplan er streng - har strenghetsegenskapen - hvis for to transaksjoner T1, T2, hvis en skriveoperasjon av T1 går foran en motstridende operasjon av T2 (enten lese eller skrive), så begår eller avbryter hendelsen av T1 også før den motstridende drift av T2.

Enhver streng tidsplan er kaskadeløs, men ikke omvendt. Strenghet tillater effektiv gjenoppretting av databaser fra feil.

Hierarkisk forhold mellom seriabilitetsklasser

Følgende uttrykk illustrerer de hierarkiske (inneslutnings-) forholdene mellom serialiserbarhet og utvinnbarhetsklasser :

• Seriell ⊂ forpliktelsesbestilt ⊂ konfliktserialiserbar ⊂ visningsserialiserbar ⊂ alle tidsplaner
• Seriell ⊂ streng ⊂ cascadeless (ACA) ⊂ gjenopprettelig ⊂ alle tidsplaner

Den Venn-diagram (nedenfor) illustrerer de ovenfor nevnte punktene grafisk.

Praktiske implementeringer

I praksis bruker de fleste generelle databasesystemer konflikt-serierbare og utvinnbare (primært strenge) tidsplaner.

Se også

• tidsplan (prosjektledelse)

Referanser

• 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