Konseptet med relasjon er assosiert med utviklingen av en kjent amerikansk spesialist innen databasesystemer, en ansatt i selskapet IBM Drs. E. Codd (Codd E.F., A Relational Model of Data for Large Shared Data Banks. CACM 13: 6, June 1970), som først brukte begrepet «relasjonell datamodell».

I lang tid ble den relasjonelle tilnærmingen ansett som et praktisk formelt apparat for databaseanalyse, som ikke hadde noen praktiske utsikter, siden implementeringen krevde for mange maskinressurser. Først med advent personlige datamaskiner relasjonelle og relaterte systemer begynte å spre seg, og ga praktisk talt ikke plass til andre modeller.

Disse modellene er preget av enkel datastruktur, brukervennlig tabellrepresentasjon og evnen til å bruke det formelle apparatet til relasjonsalgebra og relasjonskalkulus for databehandling.

Relasjonsmodellen fokuserer på å organisere data i form av todimensjonale tabeller. Hver relasjonstabell er todimensjonal matrise og har følgende egenskaper:

• - hvert tabellelement er ett dataelement; det er ingen gjentakende grupper;
• - alle kolonnene i tabellen er homogene, dvs. alle elementene i en kolonne har samme type(numerisk, tegn osv.) og lengde;
• - hver kolonne har et unikt navn;
• - det er ingen identiske rader i tabellen;
• - rekkefølgen på rader og kolonner kan være vilkårlig. Denne typen tabeller kalles en relasjon.

En database bygget ved hjelp av relasjoner kalles en relasjonsdatabase.

Relasjoner presenteres i form av tabeller, hvis rader tilsvarer tupler eller poster, og kolonnene tilsvarer relasjonsattributter, domener og felt.

Et felt hvis hver verdi unikt identifiserer den tilsvarende posten kalles med en enkel nøkkel(nøkkelfelt). Hvis poster er unikt identifisert av verdiene til flere felt, har en slik databasetabell en sammensatt nøkkel.

For å koble sammen to relasjonstabeller, må du inkludere nøkkelen til den første tabellen som en del av nøkkelen til den andre tabellen (nøklene kan falle sammen); ellers må du legge inn en fremmednøkkel i strukturen til den første tabellen - nøkkelen til den andre tabellen.

Etter å ha foreslått en relasjonsdatamodell, har E.F. Codd laget også et verktøy for praktisk arbeid med relasjoner – relasjonsalgebra. Hver operasjon av denne algebraen bruker en eller flere tabeller (relasjoner) som sine operander og produserer en ny tabell som et resultat, dvs. lar deg "klippe" eller "lime" tabeller.

Hvordan relasjonsmodeller fundamentalt skiller seg fra nettverk og hierarkiske kan sies som følger: hierarkiske og nettverksmodeller Data - har en sammenheng ved struktur, og relasjonelle - har en sammenheng ved mening.

Databasedesign har tradisjonelt vært ansett som en svært vanskelig oppgave. Relasjonsteknologi gjør denne oppgaven mye enklere.

Ved å skille de logiske og fysiske lagene i et system, forenkler det prosessen med å kartlegge "den virkelige verden laget" til en struktur som systemet direkte kan støtte. Fordi selve relasjonsstrukturen er konseptuelt enkel, tillater den implementering av små og/eller enkle (og derfor enkle å lage) databaser, for eksempel personlige databaser, som aldri ville blitt ansett som mulige i eldre, mer komplekse systemer.

Teorien og disiplinen om normalisering kan hjelpe ved å vise hva som skjer når relasjoner ikke er naturlig strukturert.

Relasjonsdatamodellen er spesielt praktisk for bruk i distribuerte arkitekturdatabaser - den lar deg få tilgang til alle informasjonselementer, lagret i datanettverksnoder. Det er nødvendig å være spesielt oppmerksom på høynivåaspektet ved den relasjonelle tilnærmingen, som består av multippel postbehandling. Takket være dette øker potensialet til den relasjonelle tilnærmingen betydelig, noe som ikke kan oppnås ved behandling av én post om gangen, og fremfor alt handler dette om optimalisering.

Denne modellen lar deg bestemme:

• · operasjoner for å lagre og hente data;
• · restriksjoner knyttet til å sikre dataintegritet.

For å øke driftseffektiviteten vedtar mange relasjonelle DBMS-er begrensninger som tilsvarer en streng relasjonsmodell.

Mange relasjonelle DBMSer presenterer databasefiler til brukeren i et tabellformat - med poster som rader og feltene deres som kolonner. I tabellform oppfattes informasjon mye lettere. Imidlertid, i en database på fysisk nivå, lagres data vanligvis i filer som inneholder sekvenser av poster.

Hovedfordel relasjonell DBMS er muligheten til å koble basert på visse relasjoner av databasefiler.

Fra et strukturelt synspunkt er relasjonsmodeller enklere og mer homogene enn hierarkiske og nettverksmodeller. I relasjonsmodellen er hvert objekt fagområde samsvarer med en eller flere relasjoner. Hvis det er nødvendig å definere forholdet mellom objekter eksplisitt, uttrykkes det i form av en relasjon der identifikatorer av gjensidige objekter er tilstede som attributter. I relasjonsmodellen er objektene i fagområdet og forbindelsene mellom dem representert av de samme informasjonsstrukturene, noe som forenkler selve modellen betydelig.

En DBMS anses som relasjonell hvis følgende to betingelser, foreslått av E. Codd, er oppfylt:

• · støtter relasjonsdatastruktur;
• · implementerer minst operasjonene for utvelgelse, projeksjon og kobling av relasjoner.

Deretter ble den opprettet hele linjen relasjonell DBMS, i en eller annen grad møte denne definisjonen. Mange DBMS-er er betydelige utvidelser av relasjonsmodellen, mens andre er blandet, og støtter flere datamodeller.

I dag er relasjonsdatabaser fortsatt de vanligste på grunn av deres enkelhet og klarhet, både under opprettelsesprosessen og på brukernivå.

Den største fordelen med relasjonsdatabaser er deres kompatibilitet med det mest populære søkespråket, SQL.

Med en enkelt spørring på dette språket kan du slå sammen flere tabeller til en midlertidig tabell og kutte ut de nødvendige radene og kolonnene fra den (utvalg og projeksjon). Siden tabellstrukturen til en relasjonsdatabase er intuitiv for brukere, er SQL-språket enkelt og lett å lære. Relasjonsmodellen har et solid teoretisk fundament som utviklingen og implementeringen av relasjonsdatabaser var basert på. Som følge av popularitetsbølgen generert av suksessen til relasjonsmodellen, ble SQL det primære språket for relasjonsdatabaser.

Men ulempene med den vurderte databasemodellen har også blitt identifisert:

• - siden alle feltene i en tabell må inneholde et konstant antall felt av forhåndsdefinerte typer, er det nødvendig å lage flere tabeller som tar hensyn til de individuelle egenskapene til elementene ved hjelp av fremmednøkler. Denne tilnærmingen gjør det svært vanskelig å lage komplekse relasjoner i databasen;
• - høy kompleksitet ved å manipulere informasjon og endre forbindelser.

Database (DB) - Dette er et navngitt sett med strukturerte data knyttet til et spesifikt fagområde og beregnet for lagring, akkumulering og behandling ved hjelp av en datamaskin.

Relasjonell base Data (RBD) er et sett med relasjoner hvis navn sammenfaller med navnene på skjemarelasjoner i databaseskjemaet.

Enkle konsepter relasjonsdatabaser:

· Data-type– type verdier for en bestemt kolonne.

· Domene(domene) – settet av alle akseptable verdier Egenskap.

· Egenskap(attributt) – tabellkolonneoverskrift som karakteriserer en navngitt egenskap til et objekt, for eksempel elevens etternavn, ordredato, ansattes kjønn osv.

· Cortege– en tabellrad som representerer et sett med verdier av logisk relaterte attributter.

· Holdning(relasjon) – en tabell som gjenspeiler informasjon om gjenstander i den virkelige verden, for eksempel om studenter, bestillinger, ansatte, beboere, etc.

· Primærnøkkel(primærnøkkel) – et felt (eller sett med felt) i en tabell som unikt identifiserer hver av dens poster.

· Alternativ nøkkel er et felt (eller sett med felt) som ikke samsvarer primærnøkkel og unik identifisering av postforekomsten.

· Ekstern nøkkel er et felt (eller sett med felt) hvis verdier samsvarer med de eksisterende verdiene til primærnøkkelen til en annen tabell. Når du kobler to tabeller, er primærnøkkelen til den første tabellen koblet til fremmednøkkelen til den andre tabellen.

· Relasjonsdatamodell (RDM)- organisere data i form av todimensjonale tabeller.

Hver relasjonstabell må ha følgende egenskaper:

1. Hver tabellpost er unik, dvs. settet med verdier i feltene gjentas ikke.

2. Hver verdi skrevet i skjæringspunktet mellom en rad og en kolonne er atomær (uatskillelig).

3. Verdiene til hvert felt må være av samme type.

4. Hvert felt har et unikt navn.

5. Rekkefølgen på oppføringene er ikke viktig.

Hovedelementer i databasen:

Felt- en elementær enhet for logisk organisering av data. Følgende egenskaper brukes til å beskrive feltet:

· navn, for eksempel etternavn, fornavn, patronym, fødselsdato;

· skriv, for eksempel, streng, tegn, numerisk, dato;

· lengde, for eksempel i byte;

· presisjon for numeriske data, for eksempel to desimaler for å vise brøkdelen av et tall.

Ta opp- et sett med verdier av logisk relaterte felt.

Indeks– et middel for å fremskynde postsøkeoperasjonen, brukt til å etablere relasjoner mellom tabeller. En tabell som en indeks brukes til kalles indeksert. Når du arbeider med indekser, må du være oppmerksom på organiseringen av indeksene, som er grunnlaget for klassifisering. En enkel indeks er representert av et enkelt felt eller logisk uttrykk, behandler ett felt. En sammensatt indeks er representert av flere felt med mulighet til å bruke ulike funksjoner. Tabellindekser lagres i en indeksfil.

Dataintegritet– dette er et middel for å beskytte data på kommunikasjonsfelt, som lar deg opprettholde tabeller i en konsistent (konsistent) tilstand (det vil si at det ikke tillater eksistensen av poster i den underordnede tabellen som ikke har tilsvarende poster i overordnet bord).

Be om– et formulert spørsmål for en eller flere sammenkoblede tabeller som inneholder dataprøvekriterier. Spørringen utføres ved hjelp av det strukturerte spørringsspråket SQL (Structured Query Language). Henting av data fra én eller flere tabeller kan resultere i et sett med poster som kalles en visning.

Datapresentasjon– en navngitt spørring lagret i databasen for å hente data (fra en eller flere tabeller).

En visning er i hovedsak en midlertidig tabell opprettet som et resultat av en spørring. Selve forespørselen kan sendes til en egen fil, rapport, midlertidig tabell, tabell på disk, etc.

Rapportere– en systemkomponent som har som hovedformål å beskrive og skrive ut dokumenter basert på informasjon fra databasen.

generelle egenskaper jobber med RDB:

Den vanligste tolkningen av den relasjonelle datamodellen ser ut til å være den til Data, som gjengir den (med forskjellige forbedringer) i nesten alle bøkene hans. I følge Date består relasjonsmodellen av tre deler som beskriver ulike aspekter ved den relasjonelle tilnærmingen: den strukturelle delen, manipulasjonsdelen og den helhetlige delen.

Den strukturelle delen av modellen sier at den eneste datastrukturen som brukes i relasjonsdatabaser er den normaliserte n-ære relasjonen.

Manipulasjonsdelen av modellen bekrefter to grunnleggende mekanismer for å manipulere relasjonsdatabaser - relasjonsalgebra og relasjonskalkulus. Den første mekanismen er hovedsakelig basert på klassisk settteori (med noen forbedringer), og den andre er basert på det klassiske logiske apparatet til førsteordens predikatregning. Merk at hovedfunksjonen til manipulasjonsdelen av relasjonsmodellen er å gi et mål på relasjonaliteten til ethvert spesifikt relasjonsdatabasespråk: et språk kalles relasjonelt hvis det ikke har mindre uttrykksevne og kraft enn relasjonsalgebra eller relasjonskalkulus.

28. ALGORITMISKE SPRÅK. OVERSETTERE (TOLK OG KOMPILERINGER). ALGORITMISK SPRÅK GRUNNLEGGENDE. PROGRAMSTRUKTUR. IDENTIFIKASJONER. VARIABLER. OPERATØRER. BEHANDLING AV EN-DIMENSJONELLE OG TO-DIMENSJONELLE ARRAYS. BRUKERFUNKSJONER. SUBRUTINER. JOBBER MED DATAFILER.

Språk på høyt nivå- et programmeringsspråk hvis konsepter og struktur er praktiske for menneskelig oppfatning.

Algoritmisk språk(Algorithmic language) - et programmeringsspråk - et kunstig (formelt) språk designet for å skrive algoritmer. Et programmeringsspråk er definert av beskrivelsen og implementert i form av et spesielt program: en kompilator eller tolk. Eksempler på algoritmiske språk er Borland Pascal, C++, Basic, etc.

Grunnleggende konsepter for algoritmisk språk:

Sammensetningen av språket:

Vanlig talespråk består av fire grunnelementer: symboler, ord, setninger og setninger. Et algoritmisk språk inneholder lignende elementer, bare ord kalles elementære konstruksjoner, fraser kalles uttrykk, og setninger kalles operatorer.

Symboler, elementære konstruksjoner, uttrykk og operatorer utgjør hierarkisk struktur, siden elementære strukturer er dannet fra en sekvens av symboler.

Uttrykkene er en sekvens av elementære strukturer og symboler,

Operatør- en sekvens av uttrykk, elementære strukturer og symboler.

Språkbeskrivelse:

En tegnbeskrivelse består av å liste de gyldige tegnene i språket. Beskrivelsen av elementære strukturer betyr reglene for deres dannelse. Beskrivelse av uttrykk er reglene for dannelsen av alle uttrykk som gir mening i et gitt språk. Beskrivelsen av operatører består av en vurdering av alle typer operatører som er tillatt på språket. Beskrivelsen av hvert språkelement er gitt av dets SYNTAKS og SEMANTIKK.

Syntaktisk definisjoner etablerer regler for å konstruere språkelementer.

Semantikk definerer betydningen og bruksreglene for de språkelementene som det er gitt syntaktiske definisjoner for.

Språksymboler- dette er de grunnleggende udelelige tegnene som alle tekster på språket er skrevet ut fra.

Elementære strukturer- Dette minimumsenheter språk som har selvstendig betydning. De er dannet av språkets grunnleggende symboler.

Uttrykk i et algoritmisk språk består det av elementære strukturer og symboler; det spesifiserer en regel for å beregne en viss verdi.

Operatør settene Full beskrivelse noen handling som må utføres. En gruppe utsagn kan være nødvendig for å beskrive en kompleks handling.

I dette tilfellet er operatørene kombinert til Sammensatt operatør eller Blokkere. Handlinger, spesifisert av operatørene, utføres på dataene. Utsagn av et algoritmisk språk som gir informasjon om datatyper kalles deklarasjoner eller ikke-kjørbare utsagn. Et sett med beskrivelser og operatorer samlet av en enkelt algoritme danner et program på et algoritmisk språk. I prosessen med å studere et algoritmisk språk, er det nødvendig å skille det algoritmiske språket fra språket som beskrivelsen av det algoritmiske språket som studeres utføres med. Vanligvis kalles språket som studeres ganske enkelt et språk, og språket som beskrivelsen av språket som studeres er gitt - Metaspråk.

Oversettere - (Engelsk oversetter - oversetter) er et oversetterprogram. Den konverterer et program skrevet på et av høynivåspråkene til et program som består av maskininstruksjoner.

Et program skrevet på et hvilket som helst algoritmisk språk på høyt nivå kan ikke kjøres direkte på en datamaskin. Datamaskinen forstår bare språket til maskinkommandoer. Følgelig må et program på et algoritmisk språk oversettes (oversettes) til kommandospråket til en bestemt datamaskin. Slik oversettelse utføres automatisk av spesielle oversetterprogrammer laget for hvert algoritmespråk og for hver type datamaskin.

Det er to hovedkringkastingsmetoder - sammenstilling og tolkning.

1.Kompilering: Kompilator(engelsk kompilator - kompilator, samler) leser hele programmet, oversetter det og lager en komplett versjon av programmet på maskinspråk, som deretter kjøres.

På samling hele det originale programmet konverteres umiddelbart til en sekvens av maskininstruksjoner. Etter dette kjøres det resulterende programmet av en datamaskin med tilgjengelige kildedata. Fordelen med denne metoden er at oversettelsen utføres én gang, og (flere) utførelse av det resulterende programmet kan utføres i høy hastighet. Samtidig kan det resulterende programmet ta opp mye plass i datamaskinens minne, siden én språkoperatør erstattes av hundrevis eller til og med tusenvis av kommandoer under oversettelse. I tillegg er feilsøking og modifikasjoner av kringkastingsprogrammet svært vanskelig.

2. Tolkning: Tolk(Engelsk tolk - tolk, tolk) oversetter og utfører programmet linje for linje.

På tolkninger kildeprogrammet er lagret i datamaskinens minne nesten uendret. Tolkeprogrammet dekoder setningene til kildeprogrammet en om gangen og sikrer umiddelbart at de utføres med tilgjengelige data. Det tolkede programmet tar liten plass i datamaskinens minne og er enkelt å feilsøke og modifisere. Men gjennomføringen av programmet er ganske treg, siden tolkningen av alle operatører utføres på nytt med hver utførelse.

Kompilerte programmer kjører raskere, men tolkede programmer er lettere å fikse og endre.

Hvert spesifikt språk er orientert enten mot kompilering eller tolkning - avhengig av formålet det ble laget for. For eksempel brukes Pascal vanligvis til å løse ganske komplekse oppgaver, der hastigheten på programmer er viktig. Derfor gitt språk vanligvis implementert ved hjelp av en kompilator.

På den annen side ble BASIC opprettet som et språk for nybegynnere programmerere, for hvem linje-for-linje kjøring av et program har ubestridelige fordeler.

Noen ganger er det både en kompilator og en tolk for samme språk. I dette tilfellet kan du bruke en tolk til å utvikle og teste programmet, og deretter kompilere det feilsøkte programmet for å forbedre utførelseshastigheten.

Alle moderne databaser bruker CBO (Cost Based Optimization), kostnadsoptimalisering. Essensen ligger i det faktum at for hver operasjon bestemmes dens "kostnad", og deretter reduseres den totale kostnaden for forespørselen ved å bruke de "billigste" operasjonskjedene.

For å bedre forstå kostnadsoptimalisering, skal vi se på tre vanlige måter å slå sammen to tabeller på og se hvordan selv en enkel bli med-spørring kan bli til en optimizers mareritt. I diskusjonen vår vil vi fokusere på tidskompleksitet, selv om optimizeren beregner "kostnaden" i form av prosessorressurser, minne og I/O-operasjoner. Det er bare at tidskompleksitet er et omtrentlig konsept, og for å bestemme de nødvendige prosessorressursene, må du telle alle operasjonene, inkludert addisjon, if-setninger, multiplikasjon, iterasjon, etc.

I tillegg:

• For å utføre hver høynivåoperasjon, utfører prosessoren et annet antall lavnivåoperasjoner.
• Kostnaden for prosessoroperasjoner (i form av sykluser) varierer mellom ulike typer prosessorer, det vil si at den avhenger av den spesifikke CPU-arkitekturen.

Derfor vil det være lettere for oss å vurdere i form av kompleksitet. Men husk at databaseytelsen som oftest er begrenset av diskundersystemet, og ikke av prosessorressurser.

Vi snakket om dem da vi så på B-trær. Som du husker, er indeksene allerede sortert. Forresten, det finnes andre typer indekser, for eksempel punktgrafikkindeks. Men de gir ingen fordeler når det gjelder CPU, minne og diskutnyttelse sammenlignet med B-tree-indekser. I tillegg kan mange moderne databaser dynamisk lage midlertidige indekser for pågående spørringer hvis dette vil bidra til å redusere kostnadene ved å utføre planen.

4.4.2. Ankemetoder

Før du kan bruke fagforeningsoperatører, må du først innhente nødvendige data. Du kan gjøre dette på følgende måter.

• Full skanning. Databasen leser ganske enkelt hele tabellen eller indeksen. Som du forstår, for diskundersystemet er det billigere å lese en indeks enn en tabell.
• Rekkeviddeskanning. Brukes for eksempel når du bruker predikater som WHERE AGE > 20 AND AGE< 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.

  I den første delen av artikkelen fant vi allerede ut at tidskompleksiteten til en rekkeviddespørring er definert som M + log(N), der N er antall data i indeksen, og M er estimert antall rader innenfor utvalget. Vi kjenner verdiene til begge disse variablene takket være statistikk. En rekkeviddeskanning leser bare en del av indeksen, så operasjonen koster mindre enn en full skanning.

• Skann etter unike verdier. Brukes i tilfeller der du bare trenger å hente én verdi fra indeksen.
• Tilgang via rad-ID. Hvis databasen bruker en indeks, vil den mesteparten av tiden søke etter rader knyttet til den. For eksempel gjør vi følgende forespørsel:

  VELG ETTERNAVN, FORNAVN fra PERSON WHERE AGE = 28
  Hvis vi har en indeks på alderskolonnen, vil optimalisereren bruke indeksen til å finne alle 28-åringer og deretter spørre etter IDene til de tilsvarende radene i tabellen, siden indeksen kun inneholder aldersinformasjon.

  La oss si at vi har en annen forespørsel:

  VELG TYPE_PERSON.CATEGORY fra PERSON, TYPE_PERSON HVOR PERSON.AGE = TYPE_PERSON.AGE
  For å slå sammen med TYPE_PERSON, vil en indeks på PERSON-kolonnen bli brukt. Men siden vi ikke ba om informasjon fra PERSON-tabellen, vil ingen få tilgang til den via rad-ID-er.

  Denne tilnærmingen er bare bra for et lite antall samtaler fordi den er dyr med tanke på I/O. Hvis du trenger å få tilgang til ID-en din ofte, er det bedre å bruke en full skanning.

• andre metoder. Du kan lese om dem i Oracle-dokumentasjonen. Ulike databaser kan bruke forskjellige navn, men prinsippene er de samme overalt.

4.4.3. Fagforeningsdrift

Så vi vet hvordan vi skal få tak i dataene, det er på tide å kombinere dem. Men først, la oss definere noen nye termer: indre avhengigheter og eksterne avhengigheter. Avhengigheten kan være:

• bord,
• indeks,
• mellomresultatet av en tidligere operasjon (for eksempel en tidligere sammenføyning).

Når vi kombinerer to avhengigheter, håndterer flettealgoritmene dem annerledes. La oss si at A JOIN B er foreningen av A og B, der A er en ekstern avhengighet og B er en intern avhengighet.

Oftest er kostnaden for A JOIN B ikke lik kostnaden for B JOIN A.

La oss anta at den eksterne avhengigheten inneholder N elementer og den interne avhengigheten inneholder M. Som du husker, kjenner optimalisereren disse verdiene takket være statistikk. N og M er kardinalavhengighetstall.

• Union ved hjelp av nestede løkker. Dette er den enkleste måten å kombinere.

  

  Det fungerer slik: for hver streng av en ekstern avhengighet, finnes treff på tvers av alle strengene i den interne avhengigheten.

  Pseudokode eksempel:

  Nested_loop_join(array ytre, array indre) for hver rad a i ytre for hver rad b i indre if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for
  Siden dette er en dobbel iterasjon, er tidskompleksiteten definert som O(N*M).

  For hver av N eksterne avhengighetsrader må du telle M eksterne avhengighetsrader. Det vil si at denne algoritmen krever N + N*M lesing fra disk. Hvis den interne avhengigheten er liten nok, kan du legge den helt i minnet, og da vil diskundersystemet bare ha M + N-lesninger. Så det anbefales å gjøre den interne avhengigheten så kompakt som mulig for å passe den inn i minnet.

  Fra et tidskompleksitetssynspunkt er det ingen forskjell.

  Du kan også erstatte den interne avhengigheten med en indeks, dette vil lagre I/O-operasjoner.
  Hvis den interne avhengigheten ikke passer helt inn i minnet, kan du bruke en annen algoritme som bruker disk mer økonomisk.

  • I stedet for å lese begge avhengighetene linje for linje, leses de i grupper med linjer (haug), med en gruppe fra hver avhengighet som lagres i minnet.
  • Strenger fra disse gruppene sammenlignes med hverandre, og treffene som er funnet lagres separat.
  • Deretter lastes nye grupper inn i minnet og sammenlignes også med hverandre.
  Og så videre til gruppene går tom.

  Algoritme eksempel:

  // forbedret versjon for å redusere disk I/O. nested_loop_join_v2(fil ytre, fil indre) for hver haug ba i ytre // ba er nå i minnet for hver haug bb i indre // bb er nå i minnet for hver rad a i ba for hver rad b i bb if (match_join_condition( a,b)) write_result_in_output(a,b) end if end for end for end for end for
  I i dette tilfellet Tidskompleksiteten forblir den samme, men antall disktilganger reduseres: (antall eksterne grupper + antall eksterne grupper * antall interne grupper). Etter hvert som gruppestørrelsen øker, reduseres antallet disktilganger enda mer.

  Merk: i denne algoritmen leses mer data med hver tilgang, men dette spiller ingen rolle siden tilgangene er sekvensielle.

• Hash bli med. Dette er en mer kompleks operasjon, men i mange tilfeller er kostnadene lavere.

  

  Algoritmen er som følger:

  1. Alle elementer fra den interne avhengigheten leses.
  2. En hash-tabell opprettes i minnet.
  3. Alle elementer fra den eksterne avhengigheten leses en etter en.
  4. For hvert element beregnes en hash (ved hjelp av den tilsvarende funksjonen fra hashtabellen) slik at den tilsvarende blokken i den interne avhengigheten kan finnes.
  5. Elementer fra blokken sammenlignes med elementer fra den eksterne avhengigheten.
  For å evaluere denne algoritmen når det gjelder tidskompleksitet, må flere antakelser gjøres:
  • Den interne avhengigheten inneholder X-blokker.
  • Hash-funksjonen fordeler hashen nesten likt for begge avhengighetene. Det vil si at alle blokker har samme størrelse.
  • Kostnaden for å finne samsvar mellom elementer i en ekstern avhengighet og alle elementer inne i en blokk er lik antall elementer inne i blokken.
  Da vil tidskompleksiteten være lik:

  (M / X) * (N / X) + hash_table_creation_cost(M) + hash_function_cost * N

  Og hvis hash-funksjonen lager små nok blokker, vil tidskompleksiteten være O(M + N).

  Det er en annen hash join-metode som er mer minneeffektiv og ikke krever flere I/O-operasjoner:

  1. Hash-tabeller beregnes for begge avhengighetene.
  2. Plassert på disk.
  3. Og så sammenlignes de trinn for trinn med hverandre (en blokk lastes inn i minnet, og den andre leses linje for linje).
  Forening ved sammenslåing. Dette er den eneste sammenslåingsmetoden som resulterer i sorterte data. I denne artikkelen tar vi for oss et forenklet tilfelle når avhengigheter ikke er delt inn i eksterne og interne, siden de oppfører seg likt. Men i det virkelige liv kan de være forskjellige, for eksempel når du arbeider med duplikater.

  Sammenslåingsoperasjonen kan deles inn i to stadier:

  1. (Valgfritt) utføres først en sorteringssammenføyning, der begge settene med inndata sorteres etter sammenføyningsnøklene.
  2. Da skjer sammenslåingen.
  Sortering

  Sammenslåingssorteringsalgoritmen har allerede blitt diskutert ovenfor; i dette tilfellet er det ganske berettiget hvis det er viktig for deg å lagre minne.

  Men det hender at datasett kommer allerede sortert, for eksempel:

  • Hvis bordet er organisert naturlig.
  • Hvis avhengigheten er en indeks med en sammenføyningsbetingelse til stede.
  • Hvis foreningen oppstår med et mellomsortert resultat.
  Konsolidering ved fusjon

  

  Denne operasjonen er veldig lik fletteoperasjonen i merge sort. Men i stedet for å velge alle elementene i begge avhengighetene, velger vi bare like elementer.

  1. De to gjeldende elementene i begge avhengighetene sammenlignes.
  2. Hvis de er like, legges de inn i den resulterende tabellen, og deretter sammenlignes de neste to elementene, en fra hver avhengighet.
  3. Hvis de ikke er like, gjentas sammenligningen, men i stedet for det minste av de to elementene, tas det neste elementet fra samme avhengighet, siden sannsynligheten for en tilfeldighet i dette tilfellet er høyere.
  4. Trinn 1-3 gjentas til elementene i en av avhengighetene går tom.
  Hvis begge avhengighetene allerede er sortert, er tidskompleksiteten O(N + M).

  Hvis begge avhengighetene fortsatt må sorteres, er tidskompleksiteten O(N * Log(N) + M * Log(M)).

  Denne algoritmen fungerer bra fordi begge avhengighetene allerede er sortert og vi trenger ikke å gå frem og tilbake mellom dem. Det er imidlertid en viss forenkling her: Algoritmen håndterer ikke situasjoner der samme data forekommer flere ganger, det vil si når flere samsvar forekommer. I virkeligheten brukes en mer kompleks versjon av algoritmen. For eksempel:

  MergeJoin(relasjon a, relasjon b) relasjonsutgang heltall a_key:=0; heltall b_key:=0; mens (a!=null og b!=null) hvis (a< b) a_key++; else if (a >b) b_tast++; else //Join predicate satisfied write_result_in_output(a,b) //Vi må være forsiktige når vi øker pekerne heltall a_key_temp:=a_key; heltall b_key_temp:=b_key; if (a != b) b_key_temp:= b_key + 1; end if if (b != a) a_key_temp:= a_key + 1; end if if (b == a && b == a) a_key_temp:= a_key + 1; b_key_temp:= b_key + 1; end if a_key:= a_key_temp; b_key:= b_key_temp; slutt hvis slutt mens

Hvilken algoritme å velge?

Hvis det var den beste måten å kombinere på, ville ikke alle disse variantene eksistert. Så svaret på dette spørsmålet avhenger av en rekke faktorer:

• Mengde tilgjengelig minne. Hvis det ikke er nok, glem en kraftig hash-join. I det minste er utførelsen helt i minnet.
• Størrelsen på de to inndatasettene. Hvis du har en tabell som er stor og den andre veldig liten, vil en sammenføyning som bruker nestede løkker fungere raskest, fordi en hash-sammenføyning innebærer en kostbar prosedyre for å lage hasher. Hvis du har to veldig store tabeller, vil det å bli med ved hjelp av nestede løkker forbruke alle CPU-ressursene.
• Tilgjengelighet av indekser. Hvis du har to B-tre-indekser, er det bedre å bruke en sammenslåing.
• Trenger jeg å sortere resultatene? Det kan være lurt å bruke en dyr sammenslåing (med sortering) hvis du jobber med usorterte datasett. Deretter vil du ved utgangen motta sorterte data, som er mer praktisk å kombinere med resultatene fra en annen fagforening. Eller fordi spørringen implisitt eller eksplisitt forventer å motta data sortert etter ORDER BY/GROUP BY/DISTINCT-operatorer.
• Er utdataavhengigheter sortert?. I dette tilfellet er det bedre å bruke en sammenslåing.
• Hvilke typer avhengigheter bruker du?. Bli med etter ekvivalens (tabellA.kolonne1 = tabellB.kolonne2)? Interne avhengigheter, eksterne avhengigheter, kartesisk produkt eller selvtilknytning? I forskjellige situasjoner fungerer ikke noen sammenslåingsmetoder.
• Datadistribusjon. Hvis dataene avvises av join-betingelsen (for eksempel, du blir med personer med etternavn, men det er ofte navnebror), bør en hash-join aldri brukes. Ellers vil hash-funksjonen skape bøtter med svært dårlig intern distribusjon.
• Er det nødvendig å slå sammen til flere prosesser/tråder?

De som er sultne på kunnskap kan fordype seg i dokumentasjonen for DB2, ORACLE og SQL Server.

4.4.4. Forenklede eksempler

La oss si at vi må slå sammen fem bord for å få et fullstendig bilde av enkelte personer. Hver person kan ha:

• Flere mobiltelefonnumre.
• Flere e-postadresser.
• Flere fysiske adresser.
• Flere bankkontonumre.

Det vil si at du raskt må svare på denne forespørselen:

VELG * fra PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS WHERE PERSON.PERSON_ID = MOBILES.PERSON_ID AND PERSON.PERSON_ID = MAILS.PERSON_ID AND PERSON.PERSON_ID = ADRESSES.PERSON_ID AND PERSON.PERSON_ACCOUNT_IDS = BANK.PERSON_AC_IDS.
Optimalisatoren må finne beste måten databehandling. Men det er to problemer:

1. Hvilken sammenføyningsmetode bør jeg bruke? Det er tre alternativer (hash join, merge join, nestet loop join), med muligheten til å bruke 0, 1 eller 2 indekser. For ikke å snakke om at indeksene også kan være forskjellige.
2. I hvilken rekkefølge skal sammenslåingen utføres?

Nedenfor er for eksempel mulige planer for tre sammenføyninger av fire tabeller:

Basert på det som er beskrevet, hva er alternativene dine?

1. Bruk en brute force-tilnærming. Bruk statistikk, beregne kostnadene for hver av de mulige planene for utførelse av spørringer og velg den billigste. Men det er ganske mange alternativer. For hver sammenføyningsordre kan tre ulike sammenføyningsmetoder brukes, for totalt 34=81 mulige utførelsesplaner. Når det gjelder et binært tre, blir problemet med å velge sammenføyningsrekkefølgen et permutasjonsproblem, og antallet alternativer er (2 * 4)! / (4 + 1)!.. Som et resultat, i dette svært forenklede eksemplet, er det totale antallet mulige spørringsutførelsesplaner 34 * (2 * 4)! / (4 + 1)! = 27 216. Hvis vi legger til alternativene der en sammenslåing bruker 0, 1 eller 2 B-tre-indekser, stiger antallet mulige planer til 210 000. Nevnte vi at dette er en VELDIG ENKEL forespørsel?
2. Gråt og slutt. Veldig fristende, men uproduktivt, og du trenger penger.
3. Prøv flere planer og velg den billigste. Bare beregn kostnadene for alle mulige alternativer det fungerer ikke, du kan ta en vilkårlig testsett data og kjøre alle typer planer på det for å estimere kostnadene og velge den beste.
4. Bruk smarte regler for å redusere antall mulige planer.
   Det er to typer regler:
   1. "Logiske", ved hjelp av hvilke du kan eliminere ubrukelige alternativer. Men de er ikke alltid aktuelle. For eksempel, "Når du kobler sammen med nestede løkker, må den indre avhengigheten være det minste settet med data."
   2. Du trenger ikke å lete etter den mest lønnsomme løsningen og bruke strengere regler for å redusere antall mulige planer. Si: "hvis avhengigheten er liten, bruk nestede sløyfesammenføyninger, men aldri slå sammen sammenføyninger eller hashsammenføyninger."

Selv et så enkelt eksempel gir oss et stort utvalg. Og i virkelige spørringer kan det være andre relasjonsoperatorer: OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT, etc. Det vil si at antallet mulige gjennomføringsplaner vil bli enda større.

Så hvordan tar databasen valget?

4.4.5. Dynamisk programmering, grådig algoritme og heuristikk

En relasjonsdatabase bruker forskjellige tilnærminger, som ble nevnt ovenfor. Og optimalisererens oppgave er å finne en passende løsning innen en begrenset tid. I de fleste tilfeller er ikke optimalisereren ute etter den beste løsningen, men rett og slett en god løsning.

Brute force kan være egnet for små forespørsler. Og med måter å eliminere unødvendig beregning på, kan selv moderate søk bruke brute force. Dette kalles dynamisk programmering.

Hovedpoenget er at mange gjennomføringsplaner er veldig like.

I denne illustrasjonen bruker alle fire planene undertre A JOIN B. I stedet for å beregne kostnadene for hver plan, kan vi beregne den bare én gang og deretter bruke disse dataene så lenge det er nødvendig. Med andre ord, ved hjelp av memoisering løser vi overlappingsproblemet, det vil si at vi unngår unødvendige beregninger.

Takket være denne tilnærmingen, i stedet for tidskompleksitet (2*N)!/(N+1)! vi får "bare" 3 N. I det forrige eksempelet med fire sammenføyninger betyr dette å redusere antall alternativer fra 336 til 81. Hvis vi tar en spørring med 8 sammenføyninger (ikke stor forespørsel), så vil vanskelighetsgraden være fra 57 657 600 til 6 561.

Hvis du allerede er kjent med dynamisk programmering eller algoritmisering, kan du leke med denne algoritmen:

Prosedyre findbestplan(S) if (bestplan[S].cost infinite) return bestplan[S] // else bestplan[S] har ikke blitt beregnet tidligere, beregne den nå hvis (S inneholder bare 1 relasjon) sett bestplan[S]. plan og bestplan[S].kostnad basert på den beste måten å få tilgang til S /* Bruke valg på S og indekser på S */ annet for hver ikke-tom delmengde S1 av S slik at S1 != S P1= findbestplan(S1) P2= finnbestplan(S - S1) A = beste algoritme for å slå sammen resultater av P1 og P2 kostnad = P1.kostnad + P2.kostnad + kostnad for A hvis kostnad< bestplan[S].cost bestplan[S].cost = cost bestplan[S].plan = “execute P1.plan; execute P2.plan; join results of P1 and P2 using A” return bestplan[S]
Dynamisk programmering kan brukes for større forespørsler, men ytterligere regler (heuristikk) må innføres for å redusere antall mulige planer:


Grådige algoritmer

Men hvis forespørselen er veldig stor, eller hvis vi trenger å få svar ekstremt raskt, brukes en annen klasse algoritmer - grådige algoritmer.

I dette tilfellet bygges spørringsutførelsesplanen trinn for trinn ved hjelp av en bestemt regel (heuristikk). Takket være ham leter den grådige algoritmen etter beste løsningen for hvert trinn separat. Planen starter med en JOIN-setning og deretter ved hvert trinn legges en ny JOIN til i henhold til regelen.

La oss se på et enkelt eksempel. La oss ta et søk med 4 sammenføyninger av 5 tabeller (A, B, C, D og E). La oss forenkle problemet noe og forestille oss at det eneste alternativet er å kombinere ved å bruke nestede algoritmer. Vi bruker regelen «bruk sammenføyningen med lavest pris».

• Vi starter med en av tabellene, for eksempel A.
• Vi beregner kostnaden for hver fagforening med A (det vil være både en ekstern og en intern avhengighet).
• Vi finner at A JOIN B vil koste oss billigst.
• Deretter beregner vi kostnaden for hver sammenføyning med resultatet A JOIN B (vi vurderer det også i to roller).
• Vi finner at det mest lønnsomme alternativet vil være (A JOIN B) JOIN C.
• Igjen vurderer vi mulige alternativer.
• På slutten får vi følgende plan for utførelse av spørringen: (((A JOIN B) JOIN C) JOIN D) JOIN E)/

Den samme algoritmen kan brukes for å evaluere alternativer som starter med tabell B, deretter C osv. Som et resultat får vi fem planer, som vi velger den billigste fra.

Denne algoritmen kalles "nærmeste naboalgoritmen".

Vi vil ikke gå i detaljer, men god modellering sorteringskompleksitet N*log(N) dette problemet kan være . Tidskompleksiteten til algoritmen er O(N*log(N)) i stedet for O(3 N) for fullversjonen med dynamisk programmering. Hvis du har et stort søk med 20 sammenføyninger, vil det være 26 mot 3.486.784.401. En stor forskjell, Ikke sant?

Men det er en nyanse. Vi antar at hvis vi finner den beste måten å slå sammen to tabeller på, vil vi få den laveste kostnaden når vi slår sammen resultatet av tidligere sammenføyninger med følgende tabeller. Men selv om A JOIN B er det billigste alternativet, kan (A JOIN C) JOIN B ha en lavere kostnad enn (A JOIN B) JOIN C.

Så hvis du desperat trenger å finne det meste billig plan av alle tider og folkeslag, så er det tilrådelig å gjentatte ganger kjøre grådige algoritmer ved å bruke forskjellige regler.

Andre algoritmer

Hvis du allerede er lei av alle disse algoritmene, kan du hoppe over dette kapittelet. Det er ikke nødvendig å mestre resten av materialet.

Mange forskere jobber med problemet med å finne den beste planen for utførelse av spørringer. De prøver ofte å finne løsninger på spesifikke problemer og mønstre. For eksempel for stjernesammenføyninger, kjøring av parallelle spørringer, etc.

Det søkes etter alternativer for å erstatte dynamisk programmering for å utføre store spørringer. De samme grådige algoritmene er en undergruppe av heuristiske algoritmer. De handler i henhold til en regel, husker resultatet av ett trinn og bruker det til å søke beste alternativet for neste trinn. Og algoritmer som ikke alltid bruker løsningen som ble funnet for forrige trinn kalles heuristiske.

Et eksempel er genetiske algoritmer:

• Hver løsning representerer en plan for fullstendig utførelse av forespørselen.
• I stedet for én løsning (plan), genererer algoritmen X løsninger på hvert trinn.
• Først opprettes X-planer, dette gjøres tilfeldig.
• Av disse lagres bare de planene hvis verdi tilfredsstiller et visst kriterium.
• Disse planene blandes deretter for å lage X nye planer.
• Noen av de nye planene endres tilfeldig.
• De tre foregående trinnene gjentas Y ganger.
• Fra planene fra den siste syklusen får vi den beste.

Jo flere sykluser, jo billigere kan planen beregnes. Naturlig utvalg, konsolidering av egenskaper, det er alt.
Forresten, genetiske algoritmer er integrert i PostgreSQL.

Databasen bruker også heuristiske algoritmer som Simulert Annealing, Iterative Improvement og Two-Phase Optimization. Men det er ikke et faktum at de brukes i bedriftssystemer, kanskje deres skjebne er forskningsprodukter.

4.4.6. Ekte optimerere

Også et valgfritt kapittel, du kan hoppe over det.

La oss gå bort fra teoretisering og se på virkelige eksempler. For eksempel hvordan SQLite optimizer fungerer. Dette er en "lett" database som bruker enkel optimalisering basert på en grådig algoritme med tilleggsregler:

• SQLite endrer aldri rekkefølgen på tabellene i en CROSS JOIN-operasjon.
• Union ved hjelp av nestede løkker brukes.
• Ytre sammenføyninger blir alltid evaluert i den rekkefølgen de ble utført.
• Opp til versjon 3.8.0 brukes den grådige Nearest Neighbor-algoritmen for å finne den beste planen for utførelse av spørringer. Og siden versjon 3.8.0 brukes "N nærmeste naboer" (N3, N nærmeste naboer).

Her er et annet eksempel. Hvis vi leser IBM DB2-dokumentasjonen, finner vi ut at optimalisereren brukes 7 ulike nivåer optimaliseringer:

• Grådige algoritmer:
  • 0 - minimal optimalisering. Bruker indeksskanning, nestede loop-sammenføyninger og unngår å omskrive noen spørringer.
  • 1 - lav optimalisering
  • 2 - full optimalisering
• Dynamisk programmering:
  • 3 - middels optimalisering og grov tilnærming
  • 5 - full optimalisering, alle heuristiske teknikker brukes
  • 7 - det samme, men uten heuristikk
  • 9 - maksimal optimalisering for enhver pris, uten hensyn til innsatsen som brukes. Alle blir vurdert mulige måter fagforeninger, inkludert kartesiske produkter.

Standardnivået er 5. Dette inkluderer:

• Innsamling av all mulig statistikk, inkludert frekvensfordelinger og kvantiler.
• Bruk av alle regler for omskrivning av spørringer, inkludert opprettelse av en tabellrute for materialiserte spørringer). Unntaket er regler som krever intensive beregninger og brukes i et svært begrenset antall saker.
• Når du gjentar sammenkoblingsalternativer ved hjelp av dynamisk programmering:
  • Det er begrenset bruk av sammensatt intern avhengighet.
  • For stjernekretser med oppslagstabeller brukes kartesiske produkter i begrenset grad.
• Under vurdering bred rekkevidde tilgangsmetoder, inkludert forhåndshenting av liste (mer om dette nedenfor), spesiell ANDing av indekser og tabellruting for materialiserte spørringer.

Utviklerne deler selvfølgelig ikke detaljer om heuristikken som brukes i produktet deres, fordi optimizeren er kanskje den viktigste delen av databasen. Det er imidlertid kjent at dynamisk programmering, begrenset av heuristikk, som standard brukes til å bestemme sammenføyningsrekkefølgen.

Andre forhold (GRUPPE ETTER, DISTINKT osv.) behandles etter enkle regler.

4.4.7. Søk etter planbuffer

Fordi det tar tid å bygge en plan, lagrer de fleste databaser planen i en spørringsplanbuffer. Dette bidrar til å unngå unødvendige beregninger av de samme trinnene. Databasen må vite nøyaktig når den trenger å oppdatere utdaterte planer. For dette settes en viss terskel, og hvis endringer i statistikk overskrider den, fjernes planen knyttet til denne tabellen fra hurtigbufferen.

Request Executor

På sånn som det er nå planen vår er allerede optimalisert. Den blir rekompilert til kjørbar kode og, hvis det er nok ressurser, eksekveret. Operatørene i planen (BLI MED, SORTERT ETTER, etc.) kan behandles enten sekvensielt eller parallelt, avgjørelsen tas av utførende. Den samhandler med databehandleren for å motta og skrive data.

5. Databehandler

Spørringsbehandlingen utfører spørringen og trenger data fra tabeller og indekser. Den ber dem fra databehandleren, men det er to problemer:

• Relasjonsdatabaser bruker en transaksjonsmodell. Det er umulig å skaffe noen ønsket data på et bestemt tidspunkt, fordi det på dette tidspunktet kan brukes/modifiseres av noen.
• Datainnhenting er den tregeste operasjonen i en database. Derfor må databehandleren være i stand til å forutsi arbeidet sitt for å fylle minnebufferen i tide.

5.1. Cache Manager

Som det har blitt sagt mer enn en gang, er flaskehalsen i databasen diskundersystemet. Derfor brukes en cache manager for å forbedre ytelsen.

I stedet for å motta data direkte fra filsystem, kontakter eksekveren av forespørselen cache-behandleren for dem. Den bruker en bufferpool i minnet, som kan øke databaseytelsen radikalt. Det er vanskelig å sette et tall på dette fordi mye avhenger av hva du trenger:

• Sekvensiell tilgang (full skanning) eller tilfeldig (tilgang via rad-ID).
• Les eller skriv.

Også av stor betydning er typen stasjoner som brukes i disksystem: "Winchesters" med i forskjellige hastigheter spindelrotasjon, SSD, RAID i forskjellige konfigurasjoner. Men vi kan si at minnebruken er 100-100 000 ganger raskere enn diskbruken.

Men her står vi overfor et annet problem. Hurtigbufferen må legge dataene inn i minnet FØR spørringsutføreren trenger det. Ellers må han vente på at de blir mottatt fra den trege disken.

5.1.1. Forkjøpsrett

Spørringsutføreren vet hvilke data den vil trenge fordi den kjenner hele planen, hvilke data som er på disken og statistikk.

Når eksekveren behandler den første delen av data, ber den hurtigbufferbehandleren om å forhåndsinnlaste neste del. Og når den begynner å behandle den, ber den DC om å laste den tredje og bekrefter at den første delen kan slettes fra hurtigbufferen.

Bufferbehandleren lagrer disse dataene i en bufferpool. Den legger også til tjenesteinformasjon (trigger, latch) til dem for å vite om de fortsatt er nødvendige i bufferen.

Noen ganger vet ikke utøveren hvilke data han vil trenge, eller noen databaser har ikke slik funksjonalitet. Deretter brukes spekulativ forhåndshenting (for eksempel hvis eksekveren ber om data 1, 3, 5, så vil han sannsynligvis be om 7, 9, 11 i fremtiden) eller sekvensiell forhåndshenting (i dette tilfellet laster DC ganske enkelt den neste fra disk bestille et stykke data.

Vi må ikke glemme at bufferen er begrenset av mengden tilgjengelig minne. Det vil si at for å laste noen data må vi med jevne mellomrom slette andre. Å fylle og tømme hurtigbufferen bruker deler av diskundersystemet og nettverksressurser. Hvis du har et søk som kjører ofte, ville det være kontraproduktivt å laste og rydde opp i dataene den bruker hver gang. For å løse dette problemet bruker moderne databaser en buffererstatningsstrategi.

5.1.2. Buffererstatningsstrategier

De fleste databaser (minst SQL Server, MySQL, Oracle og DB2) bruker LRU-algoritme(Sist nylig brukt). Den er designet for å opprettholde data i cachen som nylig har blitt brukt, noe som betyr at det er stor sannsynlighet for at det kan bli nødvendig igjen.

For å gjøre det lettere å forstå hvordan algoritmen fungerer, vil vi anta at dataene i bufferen ikke er blokkert av triggere (latch), og derfor kan slettes. I vårt eksempel kan bufferen lagre tre datastykker:

1. Bufferbehandlingen bruker data 1 og legger den i en tom buffer.
2. Den bruker da data 4 og sender den til bufferen også.
3. Det samme gjøres med data 3.
4. Deretter tas data 9. Men bufferen er allerede full. Derfor fjernes data 1 fra den siden den har vært ubrukt i lengst tid. Etter dette blir data 9 plassert i bufferen.
5. Bufferbehandleren bruker igjen data 4. Den er allerede i bufferen, så den er merket som sist brukt.
6. Data 1 blir etterspurt igjen. For å plassere den i bufferen slettes data 3 fra den da den ikke har vært brukt på lengst tid.

Dette god algoritme, men det har noen begrensninger. Hva om vi gjør en fullstendig skanning av et stort bord? Hva skjer hvis tabell-/indeksstørrelsen overskrider bufferstørrelsen? I dette tilfellet vil algoritmen fjerne alt innholdet fra hurtigbufferen, så de fullstendige skannedataene vil mest sannsynlig bare brukes én gang.

Algoritmeforbedringer

For å forhindre at dette skjer, bruker noen databaser spesielle regler. I følge Oracle-dokumentasjonen:

"For veldig store tabeller brukes vanligvis direkte tilgang, noe som betyr at blokker med data leses direkte for å unngå bufferoverflyt. For mellomstore tabeller kan både direktetilgang og cache-lesing brukes. Hvis systemet bestemmer seg for å bruke hurtigbufferen, plasserer databasen datablokkene på slutten av LRU-listen for å forhindre buffertømming."

En forbedret versjon av LRU, LRU-K, brukes også. SQL Server bruker LRU-K med K = 2. Essensen av denne algoritmen er at når den vurderer situasjonen, tar den hensyn til mer informasjon om tidligere operasjoner, og husker ikke bare de sist brukte dataene. Bokstaven K i navnet betyr at algoritmen tar hensyn til hvilke data som ble brukt de siste K-gangene. De er tillagt en viss vekt. Når nye data lastes inn i hurtigbufferen, slettes ikke gamle, men ofte brukte data fordi vekten er høyere. Selvsagt, hvis dataene ikke lenger brukes, vil de fortsatt bli slettet. Og jo lenger dataene ikke er gjort krav på, jo mer synker vekten over tid.

Å beregne vekten er ganske dyrt, så SQL Server bruker LRU-K med K lik bare 2. Ettersom verdien av K øker litt, forbedres effektiviteten til algoritmen. Du kan bli bedre kjent med ham takket være.

Andre algoritmer

Selvfølgelig er ikke LRU-K den eneste løsningen. Det finnes også 2Q og CLOCK (begge lik LRU-K), MRU (Most Recently Used, som bruker LRU-logikk, men som bruker en annen regel, LRFU (Least Recently and Frequently Used), osv. I noen databaser kan du velge, hva algoritmen vil bli brukt.

5.1.3. Skrivebuffer

Vi snakket bare om lesebufferen, men databaser bruker også skrivebuffere, som akkumulerer data og skyller dem til disken i deler, i stedet for sekvensiell skriving. Dette sparer I/O-operasjoner.
Husk at buffere lagres sider(udelelige dataenheter), i stedet for rader fra tabeller. En side i bufferbasen sies å være skitten hvis den er endret, men ikke skrevet til disk. Det er mange forskjellige algoritmer som brukes til å velge skrivetiden for skitne sider. Men det har mye å gjøre med konseptet transaksjoner.

5.2. Transaksjonsleder

Hans ansvar er å sikre at hver forespørsel utføres ved hjelp av sin egen transaksjon. Men før vi snakker om avsenderen, la oss avklare konseptet med ACID-transaksjoner.

5.2.1. "On Acid" (lek med ord, hvis noen ikke forstår)

En ACID-transaksjon (Atomicitet, Isolasjon, Holdbarhet, Konsistens) er en elementær operasjon, en arbeidsenhet som tilfredsstiller 4 betingelser:

• Atomitet. Det er ingenting "mindre" enn en transaksjon, ingen mindre operasjon. Selv om transaksjonen varer i 10 timer. Hvis en transaksjon mislykkes, går systemet tilbake til "før"-tilstanden, det vil si at transaksjonen rulles tilbake.
• Isolering. Hvis to transaksjoner A og B utføres samtidig, bør ikke utfallet avhenge av om en av dem ble fullført før, under eller etter utførelsen av den andre.
• Varighet. Når en transaksjon er begått, det vil si vellykket fullført, forblir dataene den brukte i databasen, uavhengig av mulige hendelser (feil, krasj).
• Konsistens. Bare gyldige data blir registrert i databasen (fra et relasjons- og funksjonelle forbindelser). Konsistens avhenger av atomitet og isolasjon.

Under utførelsen av enhver transaksjon kan du utføre ulike SQL-spørringer for å lese, opprette, oppdatere og slette data. Problemer starter når to transaksjoner bruker samme data. Klassisk eksempel- overføring av penger fra konto A til konto B. La oss si at vi har to transaksjoner:

• T1 tar $100 fra konto A og sender det til konto B.
• T2 tar $50 fra konto A og sender det også til konto B.

La oss nå se på denne situasjonen fra synspunktet til ACID-egenskaper:

• Atomitet lar deg være sikker på at uansett hvilken hendelse som skjer under T1 (serverkrasj, nettverksfeil), kan det ikke skje at $100 vil bli debitert fra A, men ikke kommer til B (ellers snakker de om en "inkonsekvent tilstand").
• Isolering sier at selv om T1 og T2 utføres samtidig, vil som et resultat $100 bli debitert fra A og samme beløp vil gå til B. I alle andre tilfeller snakker de igjen om en inkonsistent tilstand.
• Pålitelighet lar deg ikke bekymre deg for at T1 forsvinner hvis databasen krasjer umiddelbart etter at T1 er utført.
• Konsistens hindrer muligheten for at penger opprettes eller ødelegges i systemet.

Du trenger ikke å lese nedenfor, det er ikke lenger viktig for å forstå resten av materialet.

Mange databaser gir ikke full isolasjon som standard, da dette medfører store ytelseskostnader. SQL bruker 4 isolasjonsnivåer:

• Serialiserbare transaksjoner. Det høyeste nivået av isolasjon. Standard i SQLite. Hver transaksjon utføres i sitt eget, fullstendig isolerte miljø.
• Repeterbar lesning. Standard i MySQL. Hver transaksjon har sitt eget miljø, bortsett fra én situasjon: hvis transaksjonen legger til nye data og fullføres, vil de være synlige for andre transaksjoner som fortsatt pågår. Men hvis transaksjonen endrer data og fullføres, vil disse endringene ikke være synlige for transaksjoner som fortsatt er i gang. Det vil si at for nye data brytes prinsippet om isolasjon.

  For eksempel utføres transaksjon A

  VELG antall(1) fra TABLE_X
  Deretter legger transaksjon B til tabell X og forplikter nye data. Og hvis A etter denne transaksjonen utfører telling(1) igjen, vil resultatet bli annerledes.

  Dette kalles fantomlesing.

• Les engasjerte data. Brukes som standard i Oracle, PostgreSQL og SQL Server. Dette er det samme som gjentatt lesing, men med ytterligere brudd på isolasjon. La oss si at transaksjon A leser data; de blir deretter endret eller slettet av transaksjon B, som utfører disse handlingene. Hvis A leser disse dataene på nytt, vil hun se endringene (eller slettingen) gjort av B.

  Dette kalles ikke-repeterbar lesing.

• Les uforpliktende data. Laveste nivå av isolasjon. Et nytt isolasjonsbrudd legges til avlesningen av de forpliktede dataene. La oss si at transaksjon A leser data; deretter blir de modifisert av transaksjon B (endringene er ikke forpliktet, B utfører fortsatt). Hvis A leser dataene på nytt, vil han se endringene som er gjort. Hvis B rulles tilbake, vil A ikke se noen endringer når det leses på nytt, som om ingenting hadde skjedd.

  Dette kalles skitten lesing.

De fleste databaser legger til sine egne nivåer av isolasjon (for eksempel basert på øyeblikksbilder, som i PostgreSQL, Oracle og SQL Server). Mange databaser implementerer heller ikke alle fire nivåene beskrevet ovenfor, spesielt lesing av uforpliktende data.

Brukeren eller utvikleren kan overstyre standard isolasjonsnivå umiddelbart etter at tilkoblingen er opprettet. Alt du trenger å gjøre er å legge til en veldig enkel kodelinje.

5.2.2. Samtidig kontroll

Det viktigste vi trenger isolasjon, konsistens og atomitet for er evnen til å utføre skriveoperasjoner på de samme dataene (legge til, oppdatere og slette).

Hvis alle transaksjoner kun leser data, kan de fungere samtidig uten å påvirke andre transaksjoner.
Hvis minst én transaksjon endrer data som leses av andre transaksjoner, må databasen finne en måte å skjule disse endringene for dem. Du må også sørge for at endringene som er gjort, ikke blir slettet av andre transaksjoner som ikke ser de endrede dataene.

Dette kalles samtidighetskontroll.

Den enkleste måten er å utføre transaksjoner én etter én. Men denne tilnærmingen er vanligvis ineffektiv (kun én kjerne av én prosessor brukes), og evnen til å skalere går også tapt.

Den ideelle måten å løse problemet på ser slik ut (hver gang en transaksjon opprettes eller kanselleres):

• Overvåk alle operasjoner for hver transaksjon.
• Hvis to eller flere transaksjoner er i konflikt på grunn av lesing/endring av de samme dataene, endre rekkefølgen på operasjoner innenfor partene i konflikten for å minimere antall årsaker.
• Utfør motstridende deler av transaksjoner i en bestemt rekkefølge. Ikke-motstridende transaksjoner utføres parallelt på dette tidspunktet.
• Vær oppmerksom på at transaksjoner kan bli kansellert.

Hvis vi nærmer oss saken mer formelt, er dette et problem med å planlegge konflikter. Å løse det er svært vanskelig, og optimalisering krever store prosessorressurser. Bedriftsdatabaser har ikke råd til å bruke timer på å søke beste timeplan for hver ny transaksjon. Derfor brukes mindre sofistikerte tilnærminger, der det brukes mer tid på konflikter.

5.2.3. Låsbehandler

For å løse problemet beskrevet ovenfor bruker mange databaser låser og/eller dataversjon.
Hvis en transaksjon trenger noen data, blokkerer den dem. Hvis en annen transaksjon også krevde dem, må den vente til den første transaksjonen frigjør låsen.

Dette kalles en eksklusiv lås.

Men det er for bortkastet å bruke eksklusive låser i tilfeller der transaksjoner bare trenger å lese data. Hvorfor forstyrre datalesing? I slike tilfeller brukes delte låser. Hvis en transaksjon trenger å lese data, bruker den en delt lås på den og leser den. Dette forhindrer ikke at andre transaksjoner også deler låser og leser dataene. Hvis en av dem trenger å endre data, må hun vente til alle leddlåser er utløst. Først da vil hun kunne bruke en eksklusiv lås. Og da må alle andre transaksjoner vente på at de blir trukket tilbake for å kunne lese disse dataene.

En låsbehandler er en prosess som bruker og frigjør låser. De er lagret i en hash-tabell (nøklene er dataene som låses). Lederen vet for alle data hvilke transaksjoner som har påført låser eller venter på at de skal frigis.

Dødlås

Bruk av låser kan føre til en situasjon der to transaksjoner venter på ubestemt tid på at låsene skal frigjøres:

Her har transaksjon A utelukkende låst data 1 og venter på frigivelse av data 2. Samtidig har transaksjon B utelukkende låst data 2 og venter på at data 1 skal frigis.

I en deadlock velger ekspeditøren hvilken transaksjon som skal kanselleres (rull tilbake). Og avgjørelsen er ikke så lett å ta:

• Ville det være bedre å drepe transaksjonen som endret det siste settet med data (og derfor vil tilbakeføring være minst smertefullt)?
• Ville det vært bedre å drepe den yngste transaksjonen siden brukere av andre transaksjoner har ventet lenger?
• Ville det være bedre å avslutte en transaksjon som tar kortere tid å fullføre?
• Hvor mange andre transaksjoner vil bli påvirket av tilbakeføringen?

Men før avgjørelsen tas, må avsenderen verifisere om det faktisk har oppstått en vranglås.

La oss forestille oss en hash-tabell i form av et diagram, som i illustrasjonen ovenfor. Hvis det er en syklisk sammenheng i diagrammet, bekreftes dødlåsen. Men siden det er ganske dyrt å sjekke for sykluser (tross alt vil diagrammet som viser alle låsene være ganske stort), brukes ofte en enklere tilnærming: bruk av tidsavbrudd. Hvis låsen ikke frigjøres innen en viss tid, har transaksjonen gått inn i en fastlåst tilstand.

Før du setter på en lås, kan ekspeditøren også sjekke om det vil forårsake vranglås. Men for å svare entydig på dette, må du også bruke penger på beregninger. Derfor presenteres slike forhåndskontroller ofte som et sett med grunnleggende regler.

To-fase blokkering

Den enkleste måten å oppnå fullstendig isolasjon på er når en lås brukes i begynnelsen og frigjøres ved slutten av transaksjonen. Dette betyr at en transaksjon må vente til alle låser er frigjort før den starter, og eventuelle låser den har brukt frigjøres først ved fullføring. Denne tilnærmingen kan brukes, men da går mye tid bort på å vente på at alle låsene skal frigjøres.

DB2 og SQL Server bruker en to-fase låseprotokoll, som deler en transaksjon i to faser:

• Voksende fase, når en transaksjon bare kan bruke låser, men ikke frigjøre dem.
• Krympende fase, når en transaksjon bare kan frigjøre låser (på data som allerede er behandlet og ikke vil bli behandlet igjen), men ikke bruke nye.

En vanlig konflikt som oppstår i fravær av tofaselåsing er:

Før transaksjon A, X = 1 og Y = 1. Den behandler data Y = 1, som ble endret av transaksjon B etter at transaksjon A startet. På grunn av prinsippet om isolasjon må transaksjon A behandle Y = 2.

Mål oppnådd ved å bruke disse to enkle regler:

• Frigjør låser som ikke lenger er nødvendige for å redusere ventetiden for andre transaksjoner.
• Forhindre tilfeller der en transaksjon mottar data modifisert av en tidligere pågående transaksjon. Slike data samsvarer ikke med de forespurte dataene.

Denne protokollen fungerer bra, bortsett fra situasjonen der transaksjonen endret dataene og fjernet låsen fra den, og deretter ble kansellert. I dette tilfellet kan en annen transaksjon lese og endre data, som deretter vil bli rullet tilbake. For å unngå denne situasjonen, må alle eksklusive låser frigjøres når transaksjonen er fullført.

Selvfølgelig bruker ekte databaser mer komplekse systemer, flere typer låser og med større granularitet (låser på rader, sider, partisjoner, tabeller, tabellplasser), men essensen er den samme.

Dataversjon

En annen måte å løse transaksjonskonfliktproblemet på er å bruke dataversjon.

• Alle transaksjoner kan endre de samme dataene samtidig.
• Hver transaksjon fungerer med sin egen kopi (versjon) av dataene.
• Hvis to transaksjoner endrer de samme dataene, vil bare én av modifikasjonene bli akseptert, den andre vil bli avvist, og transaksjonen som gjorde den vil bli rullet tilbake (og muligens restartet).

Dette gir økt produktivitet fordi:

• Lesetransaksjoner blokkerer ikke skrivetransaksjoner, og omvendt.
• Den klønete låsbehandleren har ingen innvirkning.

Generelt vil alt være bedre enn låser, med mindre to transaksjoner skriver de samme dataene. Dessuten kan dette føre til en enorm sløsing med diskplass.

Begge tilnærmingene - låsing og versjonskontroll - har fordeler og ulemper, mye avhenger av situasjonen de brukes i (flere avlesninger eller flere oppføringer). Du kan studere en veldig god presentasjon om implementering av multiversjon samtidighetskontroll i PostgreSQL.

Noen databaser (DB2 før versjon 9.7, SQL Server) bruker bare låser. Andre, som PostgreSQL, MySQL og Oracle, bruker kombinerte tilnærminger.

Merk: versjonsstyring har en interessant effekt på indekser. Noen ganger er det duplikater i en unik indeks, indeksen kan inneholde flere poster enn rader i tabellen osv.

Hvis en del av dataene leses på ett isolasjonsnivå, og deretter øker, øker antallet låser, noe som betyr at mer tid går tapt på å vente på transaksjoner. Derfor bruker de fleste databaser ikke standarden maksimalt nivå isolering.

Som vanlig, for mer detaljert informasjon se dokumentasjon: MySQL, PostgreSQL, Oracle.

5.2.4. Loggbehandler

Som vi allerede vet, lagrer databasen deler av dataene i bufferminnet for å øke ytelsen. Men hvis serveren krasjer under en transaksjonsbekreftelse, vil dataene i minnet gå tapt. Og dette bryter med prinsippet om transaksjonspålitelighet.

Selvfølgelig kan du skrive alt til disk, men hvis det krasjer vil du sitte igjen med uskrevne data, og dette er et brudd på atomitetsprinsippet.

Eventuelle endringer skrevet av transaksjonen må rulles tilbake eller fullføres.

Dette gjøres på to måter:

• Skyggekopier/sider. Hver transaksjon lager sin egen kopi av databasen (eller deler av den) og arbeider med denne kopien. Hvis det oppstår en feil, slettes kopien. Hvis alt gikk bra, bytter databasen øyeblikkelig til dataene fra kopien ved å bruke ett triks på filsystemnivå, og sletter deretter de "gamle" dataene.
• Transaksjonslogg. Dette er et spesielt lager. Før hver skriving til disk, skriver databasen informasjon til transaksjonsloggen. Så i tilfelle feil, vil databasen vite hvordan den skal slette eller fullføre den ventende transaksjonen.

WAL

I store databaser med mange transaksjoner tar skyggekopier/sider opp utrolig mye diskplass. Derfor bruker moderne databaser en transaksjonslogg. Den må plasseres i feilsikker lagring.

De fleste produktene (spesielt Oracle, SQL Server, DB2, PostgreSQL, MySQL og SQLite) fungerer med transaksjonslogger via WAL-protokollen (Write-Ahead Logging). Denne protokollen inneholder tre regler:

1. Hver endring av databasen må ledsages av en loggoppføring, og den må gjøres FØR dataene skrives til disk.
2. Innføringer i loggen bør ordnes i henhold til rekkefølgen på de aktuelle hendelsene.
3. Når en transaksjon er begått, må en registrering av dette skrives til loggen FØR transaksjonen er vellykket fullført.

Loggansvarlig overvåker implementeringen av disse reglene. Den er logisk plassert mellom bufferbehandleren og datatilgangsbehandleren. Loggbehandlingen logger hver operasjon som utføres av transaksjoner til den skrives til disken. Virker riktig?

FEIL! Etter alt vi har vært gjennom i denne artikkelen, er det på tide å huske at alt relatert til databasen er underlagt forbannelsen av "databaseeffekten". Seriøst, problemet er at du må finne en måte å skrive til loggen samtidig som du opprettholder god ytelse. Tross alt, hvis transaksjonsloggen er treg, bremser den alle andre prosesser.

VÆREN

I 1992 laget forskere ved IBM en utvidet versjon av WAL, som de kalte ARIES. I en eller annen form brukes ARIES av de fleste moderne databaser. Hvis du ønsker å studere denne protokollen mer i dybden, kan du studere det tilsvarende arbeidet.

Så ARIES står for EN algoritmer for R ecovery og Jeg solasjon E xutnytting S mantikk. Denne teknologien har to oppgaver:

1. Gi god ytelse når du skriver logger.
2. Sørg for rask og pålitelig gjenoppretting.

Det er flere grunner til at en database må tilbakestille en transaksjon:

1. Brukeren kansellerte den.
2. Server- eller nettverksfeil.
3. Transaksjonen krenket integriteten til databasen. For eksempel brukte du UNIQUE-betingelsen på en kolonne, og transaksjonen la til et duplikat.
4. Tilstedeværelse av vranglås.

Men noen ganger kan databasen også gjenopprette en transaksjon, for eksempel ved nettverksfeil.

Hvordan er dette mulig? For å svare på dette må du først forstå hvilken informasjon som er lagret i loggen.

Tømmerstokker
Hver operasjon (legge til/slette/endre) under utførelsen av en transaksjon fører til at det vises en oppføring i loggen. Innlegget inneholder:

• LSN (loggsekvensnummer). Dette er et unikt nummer hvis betydning bestemmes av kronologisk rekkefølge. Det vil si at hvis operasjon A skjedde før operasjon B, vil LSN for A være mindre enn LSN for B. I virkeligheten er metoden for å generere et LSN mer komplisert, siden den også er relatert til måten loggen er lagret på.
• TransID. ID for transaksjonen som utførte operasjonen.
• SideID. Plasseringen på disken hvor de endrede dataene er plassert.
• PrevLSN. En lenke til en tidligere loggoppføring opprettet av samme transaksjon.
• ANGRE. En metode for å rulle tilbake en operasjon.

  For eksempel, hvis en oppdateringsoperasjon ble utført, blir forrige verdi/tilstand for det endrede elementet (fysisk UNDO) eller den omvendte operasjonen som lar deg gå tilbake til forrige tilstand (logisk UNDO) skrevet til UNDO. ARIES bruker bare logiske; å jobbe med fysiske er veldig vanskelig.

• GJØRE OM. Metode for å gjenta operasjonen.

I tillegg inneholder hver side på disken (for lagring av data, ikke logger) LSN for den siste operasjonen som endret dataene der.

Så vidt vi vet, brukes ikke UNDO bare i PostgreSQL. I stedet brukes en søppelsamler for å rydde opp i gamle versjoner av dataene. Dette er på grunn av implementeringen av dataversjon i dette DBMS.

For å gjøre det lettere for deg å forestille deg sammensetningen av en loggoppføring, er her et visuelt forenklet eksempel der spørringen OPPDATERING FRA PERSON SET AGE = 18; utføres. La det utføres i transaksjonsnummer 18:

Hver logg har et unikt LSN. Koblede logger refererer til samme transaksjon, og de er koblet i kronologisk rekkefølge (den siste loggen i listen refererer til den siste operasjonen).

Loggbuffer
For å hindre at logging blir en systemflaskehals, brukes en loggbuffer.

Når spørringsløperen ber om modifiserte data:

1. Bufferbehandlingen lagrer dem i en buffer.
2. Loggbehandlingen lagrer den tilsvarende loggen i sin egen buffer.
3. Spørringsutføreren avgjør om operasjonen er fullført og følgelig om de endrede dataene kan forespørres.
4. Loggbehandleren lagrer nødvendig informasjon til transaksjonsloggen. Øyeblikket for å gjøre denne oppføringen bestemmes av algoritmen.
5. Bufferbehandlingen skriver endringer til disken. Opptaksøyeblikket er også satt av algoritmen.

Når en transaksjon forplikter seg, betyr det at alle trinn 1 til 5 er fullført. Det går raskt å skrive til transaksjonsloggen fordi det representerer «å legge loggen et sted til transaksjonsloggen». Samtidig er skriving av data til disk en mer kompleks prosedyre, tatt i betraktning at dataene senere må leses raskt.

STJEL og FORCE policyer

For å forbedre ytelsen, bør trinn nummer 5 gjøres etter forpliktelsen, siden i tilfelle feil er det fortsatt mulig å gjenopprette transaksjonen ved å bruke REDO. Dette kalles INGEN-KRAFT-politikken.

Men databasen kan også velge FORCE-policyen for å redusere belastningen under gjenoppretting. Deretter utføres trinn nummer 5 før commit.

Databasen velger også om data skal skrives inkrementelt til disk (STEAL policy) eller, hvis buffermanageren må vente på en commit, skrive alt på en gang (NO-STEAL). Valget avhenger av hva du trenger: rask opptak med lang gjenoppretting eller rask gjenoppretting?

Hvordan de nevnte retningslinjene påvirker gjenopprettingsprosessen:

• STEAL/NO-FORCE krever ANGRE og GJØR GJØR. Høyeste ytelse, men mer kompleks struktur logger og gjenopprettingsprosesser (som ARES). De fleste databaser bruker denne kombinasjonen av policyer.
• For STJEL/KRAFT trenger du bare ANGRE.
• For NO-STEAL/NO-force - bare GJØR OM.
• For NO-STEAL/FORCE trenger du ikke noe i det hele tatt. Ytelsen i dette tilfellet er den laveste, og den er påkrevd stor mengde hukommelse.

Gjenoppretting

Så hvordan kan vi bruke våre fantastiske logger? La oss anta at en ny ansatt har ødelagt databasen (regel #1: det er alltid nybegynnerens feil!). Du starter den på nytt og gjenopprettingsprosessen starter.
ARIES gjenoppretter i tre stadier:

1. Analyse. Hele transaksjonsloggen leses slik at kronologien av hendelser som skjedde under databasefallet kan gjenopprettes. Dette er med på å avgjøre hvilken transaksjon som må rulles tilbake. Alle transaksjoner uten en commit-ordre rulles tilbake. Systemet bestemmer også hvilke data som skal ha blitt skrevet til disken under feilen.
2. Gjenta. REDO brukes til å oppdatere databasen til tilstanden før krasj. Loggene behandles i kronologisk rekkefølge. For hver logg leses LSN for siden på disken som inneholder dataene som må endres.

   Hvis LSN(sider_på_disk)>=LSN(oppføringer_i_logg), var dataene allerede skrevet til disk før feilen. Men verdien ble overskrevet av en operasjon som ble utført etter skriving til loggen og før feilen. Så ingenting er gjort, egentlig.

   Hvis LSN(sider_på_disk)

   Omspillingen utføres selv for transaksjoner som vil bli rullet tilbake fordi det forenkler gjenopprettingsprosessen. Men moderne databaser gjør nok ikke dette.

3. Avbryt. På dette stadiet rulles alle transaksjoner som ikke ble fullført på tidspunktet for feilen tilbake. Prosessen starter med de siste loggene for hver transaksjon og behandler UNDOs i omvendt kronologisk rekkefølge ved hjelp av PrevLSN.

Under gjenopprettingsprosessen må transaksjonsloggen være klar over handlingene som utføres under gjenopprettingen. Dette er nødvendig for å synkronisere dataene som er lagret på disken med det som er registrert i transaksjonsloggen. Det er mulig å slette transaksjonsposter som rulles tilbake, men dette er svært vanskelig å gjøre. I stedet foretar ARIES kompenserende oppføringer i transaksjonsloggen som logisk ugyldiggjør oppføringene til de tilbakestilte transaksjonene.

Hvis transaksjonen kanselleres "manuelt", eller av en låseadministrator, eller på grunn av en nettverksfeil, er ikke analysetrinnet nødvendig. Tross alt er informasjon for REDO og UNDO inneholdt i to tabeller som ligger i minnet:

• I transaksjonstabellen (tilstandene til alle gjeldende transaksjoner lagres her).
• Tabellen med skitne sider (denne inneholder informasjon om hvilke data som må skrives til disken).

Så snart en ny transaksjon vises, oppdateres disse tabellene av cache-manageren og transaksjonsmanageren. Og siden tabellene er lagret i minnet, forsvinner de hvis databasen krasjer.

Analysestadiet er nødvendig bare for å gjenopprette begge tabellene ved hjelp av informasjon fra transaksjonsloggen. For å få fart på denne fasen, bruker ARIES sjekkpunkter. Innholdet i begge tabellene, samt siste LSN i skrivende stund, skrives til disk fra tid til annen. Så under gjenoppretting analyseres bare loggene etter dette LSN.

6. Konklusjon

Som en ekstra oversiktslesning om databaser kan vi anbefale artikkelen Architecture of a Database System. Dette er en god introduksjon til temaet, skrevet i et ganske tydelig språk.

Hvis du leser nøye gjennom alt materialet ovenfor, har du sannsynligvis fått en ide om hvor store kapasitetene til databaser er. Denne artikkelen tar imidlertid ikke opp andre viktige problemer:

• Hvordan administrere grupperte databaser og globale transaksjoner.
• Hvordan få et øyeblikksbilde hvis databasen fungerer.
• Hvordan lagre og komprimere data effektivt.
• Hvordan administrere minne.

Så tenk deg om to ganger før du velger mellom en buggy NoSQL og en solid relasjonsdatabase. Misforstå meg rett, noen NoSQL-databaser er veldig bra. Men de er fortsatt langt fra perfekte og kan bare bidra til å løse spesifikke problemer knyttet til visse applikasjoner.

Så hvis noen spør deg hvordan databaser fungerer, i stedet for å gi opp og gå bort, kan du svare:

Tags: Legg til tagger

• Oversettelse

Oversetterens notat: selv om artikkelen er ganske gammel (publisert for 2 år siden) og har en høy tittel, gir den fortsatt en god idé om forskjellene mellom relasjonsdatabaser og NoSQL-databaser, deres fordeler og ulemper, og gir også en kort oversikt av ikke-relasjonelle lagre.

Nylig har det dukket opp mange ikke-relasjonelle databaser. Dette antyder at hvis du trenger praktisk talt ubegrenset skalerbarhet på forespørsel, trenger du en ikke-relasjonell database.

Hvis dette stemmer, betyr dette at den mektige relasjonsdatabasen har blitt sårbar? Betyr dette at dagene med relasjonsdatabaser går og snart vil være helt borte? I denne artikkelen skal vi se på den populære ikke-relasjonelle databasebevegelsen som den gjelder for forskjellige situasjoner og se om den vil påvirke fremtiden til relasjonsdatabaser.

Relasjonsdatabaser har eksistert i omtrent 30 år. I løpet av denne tiden brøt det ut flere revolusjoner som ville sette en stopper for relasjonslagring. Selvfølgelig fant ingen av disse revolusjonene sted, og ingen av dem rokket ved posisjonen til relasjonsdatabaser.

La oss starte med det grunnleggende

En relasjonsdatabase er et sett med tabeller (entiteter). Tabeller består av kolonner og rader (tupler). Begrensninger kan defineres i tabeller, og det eksisterer relasjoner mellom tabeller. Ved å bruke SQL kan du kjøre spørringer som returnerer sett med data fra én eller flere tabeller. Innenfor en spørring hentes data fra flere tabeller ved å slå dem sammen (JOIN), oftest brukes de samme kolonnene som definerer relasjonene mellom tabellene for tilkoblingen. Normalisering er prosessen med å strukturere en datamodell for å sikre sammenheng og mangel på redundans i dataene.

Relasjonsdatabaser er tilgjengelig gjennom r(RDBMS). Nesten alle databasesystemene vi bruker er relasjonelle, som Oracle, SQL Server, MySQL, Sybase, DB2, TeraData og så videre.

Årsakene til denne dominansen er ikke åpenbare. Gjennom historien til relasjonsdatabaser har de konsekvent tilbudt den beste kombinasjonen av enkelhet, robusthet, fleksibilitet, ytelse, skalerbarhet og kompatibilitet innen databehandling.

Men for å gi alle disse funksjonene, er relasjonsbutikker utrolig komplekse under panseret. For eksempel kan en enkel SELECT-spørring ha hundrevis av potensielle utførelsesbaner som optimalisereren vil evaluere direkte under utførelse av spørringen. Alt dette er skjult for brukere, men internt lager RDBMS en utførelsesplan basert på ting som kostnadsestimater for best mulig å møte spørringen.

Relasjonsdatabaseproblemer

Mens relasjonslagre gir den beste blandingen av enkelhet, robusthet, fleksibilitet, ytelse, skalerbarhet og kompatibilitet, presterer de ikke nødvendigvis bedre på hvert av disse punktene enn sammenlignbare systemer som fokuserer på en enkelt funksjon. Dette var ikke et stort problem, siden den generelle dominansen til relasjonelle DBMS-er oppveide eventuelle mangler. Men hvis konvensjonelle RDB-er ikke dekket behovene, fantes det alltid alternativer.

I dag er situasjonen litt annerledes. Variasjonen av applikasjoner vokser, og med det øker betydningen av disse funksjonene. Og etter hvert som antallet databaser vokser, begynner én funksjon å overgå alle andre. Dette er skalerbarhet. Ettersom flere applikasjoner kjører under høy belastning, for eksempel webtjenester, kan deres skalerbarhetskrav endres og vokse veldig raskt. Det første problemet kan være svært vanskelig å løse hvis du har en relasjonsdatabase på din egen server. La oss si at serverbelastningen tredobles over natten. Hvor raskt kan du oppgradere maskinvaren din? Å løse det andre problemet forårsaker også vanskeligheter ved bruk av relasjonsdatabaser.

Relasjonsdatabaser skaleres godt bare hvis de er plassert på en enkelt server. Når ressursene til denne serveren går tom, må du legge til flere maskiner og fordele belastningen mellom dem. Og det er her kompleksiteten til relasjonsdatabaser begynner å spille mot skalerbarhet. Hvis du prøver å øke antallet servere ikke til noen få, men til hundrevis eller tusenvis, vil kompleksiteten øke med en størrelsesorden, og egenskapene som gjør relasjonsdatabaser så attraktive reduserer raskt sjansene for å bruke dem som plattform for store distribuerte systemer til null.

For å forbli konkurransedyktige, må leverandører av skytjenester på en eller annen måte håndtere denne begrensningen, for hva slags skyplattform er det uten skalerbar datalagring. Dette gir leverandører bare ett alternativ hvis de ønsker å gi brukerne skalerbar lagringsplass. Det er nødvendig å bruke andre typer databaser som har høyere skalerbarhet, om enn på bekostning av andre funksjoner tilgjengelig i relasjonsdatabaser.

Disse fordelene, så vel som den eksisterende etterspørselen etter dem, har ført til en bølge av nye databasestyringssystemer.

Ny bølge

Denne typen database kalles vanligvis et nøkkelverdilager. Faktisk er det ikke noe offisielt navn, så du kan se det i sammenheng med dokumentorienterte, attributtorienterte, distribuerte databaser (selv om de også kan være relasjonelle), sharded sorterte arrays, distribuerte hashtabeller og lagringsnøkkelverdi type. Selv om hvert av disse navnene refererer til spesifikke funksjoner i systemet, er de alle varianter av et tema vi vil kalle nøkkelverdilagring.

Uansett hva du kaller det, er denne "nye" typen database ikke så ny og har alltid vært brukt hovedsakelig for applikasjoner som bruk av relasjonsdatabaser ikke ville vært egnet for. Men uten behov for skalerbarhet på nettet og skyen, var disse systemene fortsatt i liten etterspørsel. Nå er utfordringen å finne ut hvilken type lagring som er best egnet for et bestemt system.
Relasjonsdatabaser og nøkkelverdilagre er fundamentalt forskjellige og er designet for å løse ulike problemer. Å sammenligne egenskapene vil bare tillate deg å forstå forskjellen mellom dem, men la oss starte med dette:

Lagringsegenskaper

Relasjonsdatabase	Nøkkelverdibutikk
En database består av tabeller, tabeller inneholder kolonner og rader, og rader består av kolonneverdier. Alle rader i en tabell har samme struktur.	For domener kan det trekkes en analogi med tabeller, men i motsetning til tabeller er ikke datastrukturen for domener definert. Et domene er en boks der du kan legge hva du vil. Poster innenfor samme domene kan ha forskjellige strukturer.
Datamodell 1 er forhåndsdefinert. Den er sterkt skrevet og inneholder begrensninger og relasjoner for å sikre dataintegritet.	Poster identifiseres med en nøkkel, der hver post har et dynamisk sett med attributter knyttet til seg.
Datamodellen er basert på den naturlige representasjonen av de inneholdte dataene i stedet for på funksjonaliteten til applikasjonen.	I noen implementeringer kan attributter bare være strenger. I andre implementeringer har attributter enkle datatyper som gjenspeiler typene som brukes i programmering: heltall, strengmatriser og lister.
Datamodellen er normalisert for å unngå dataduplisering. Normalisering skaper relasjoner mellom tabeller. Relasjoner kobler sammen data fra forskjellige tabeller.	Mellom domener, så vel som innenfor ett domene, er relasjoner ikke eksplisitt definert.

Ingen sammenføyninger

Nøkkelverdibutikker er rekordorienterte. Dette betyr at all informasjon knyttet til en gitt post lagres med den. Et domene (som du kan tenke på som en tabell) kan inneholde utallige forskjellige oppføringer. Et domene kan for eksempel inneholde informasjon om kunder og bestillinger. Dette betyr at data har en tendens til å dupliseres mellom ulike domener. Dette er en akseptabel tilnærming fordi diskplass er billig. Hovedsaken er at den lar deg lagre alle relaterte data på ett sted, noe som forbedrer skalerbarheten siden det ikke er behov for å slå sammen data fra forskjellige tabeller. Når du bruker en relasjonsdatabase, vil det være nødvendig å bruke sammenføyninger for å gruppere nødvendig informasjon på ett sted.

Selv om behovet for relasjoner for å lagre nøkkelverdi-par synker kraftig, er det fortsatt behov for relasjoner. Slike forhold eksisterer vanligvis mellom underliggende enheter. For eksempel vil et bestillingssystem ha poster som inneholder data om kunder, produkter og bestillinger. Det spiller ingen rolle om disse dataene er i ett eller flere domener. Poenget er at når en kunde legger inn en bestilling, vil du sannsynligvis ikke lagre både kunden og ordreinformasjonen i samme post.
I stedet må ordreposten inneholde nøkler som peker til de tilsvarende kunde- og produktpostene. Siden poster kan lagre all informasjon, og relasjonene ikke er definert i selve datamodellen, vil ikke databasestyringssystemet kunne verifisere integriteten til relasjonene. Dette betyr at du kan slette kunder og produktene de har bestilt. Å sikre dataintegritet faller utelukkende på applikasjonen.

Datatilgang

Relasjonsdatabase	Nøkkelverdibutikk
Data opprettes, oppdateres, slettes og spørres ved hjelp av Structured Query Language (SQL).	Data opprettes, oppdateres, slettes og spørres ved hjelp av API-metodekall.
SQL-spørringer kan hente data fra enten en enkelt tabell eller flere tabeller ved å bruke sammenføyninger.	Noen implementeringer gir SQL-lignende syntaks for å spesifisere filterbetingelser.
SQL-spørringer kan inkludere aggregeringer og komplekse filtre.	Ofte kan du bare bruke grunnleggende sammenligningsoperatorer (=, !=,<, >, <= и =>).
En relasjonsdatabase inneholder vanligvis innebygd logikk som triggere, lagrede prosedyrer og funksjoner.	All forretnings- og dataintegritetslogikk er inneholdt i applikasjonskoden.

Interaksjon med applikasjoner

Nøkkelverdibutikker: fordeler

Det er to klare fordeler med slike systemer fremfor relasjonsbutikker.

Egnet for skytjenester

Den første fordelen med nøkkelverdilagre er at de er enklere og derfor mer skalerbare enn relasjonsdatabaser. Hvis du er vert for ditt eget system og planlegger å plassere et dusin eller hundre servere som må håndtere økende belastning bak datalageret ditt, er nøkkelverdilagre ditt valg.

Fordi slik lagring er lett og dynamisk utvidbar, er den også nyttig for leverandører som tilbyr en nettbasert lagringsplattform med flere leietakere. En slik database representerer et relativt billig middel for datalagring med stort skalerbarhetspotensial. Brukere betaler vanligvis bare for det de bruker, men behovene deres kan vokse. Leverandøren vil dynamisk og praktisk uten begrensninger kunne øke størrelsen på plattformen basert på belastningen.

Mer naturlig integrasjon med kode

Den relasjonsdatamodellen og kodeobjektmodellen er vanligvis konstruert annerledes, noe som fører til en viss inkompatibilitet. Utviklere løser dette problemet ved å skrive kode som kartlegger relasjonsmodellen til objektmodellen. Denne prosessen har ikke en klar og raskt oppnåelig verdi og kan ta ganske betydelig tid som kunne vært brukt på å utvikle selve applikasjonen. I mellomtiden lagrer mange nøkkelverdilagre data i en struktur som kartlegges til objekter mer naturlig. Dette kan redusere utviklingstiden betydelig.

Andre argumenter for å bruke nøkkelverdilagre, som "Relasjonsdatabaser kan bli klønete" (jeg aner forresten ikke hva det betyr), er mindre overbevisende. Men før du blir en talsmann for slik lagring, les neste avsnitt.

Nøkkelverdibutikker: ulemper

Begrensninger i relasjonsdatabaser sikrer dataintegritet på laveste nivå. Data som ikke tilfredsstiller begrensningene kan ikke fysisk komme inn i databasen. I nøkkelverdibutikker er det ingen slike begrensninger, så overvåking av dataintegritet hviler utelukkende på applikasjoner. Enhver kode har imidlertid feil. Mens feil i en godt utformet relasjonsdatabase vanligvis ikke fører til dataintegritetsproblemer, gjør feil i nøkkelverdilagre vanligvis det.

En annen fordel med relasjonsdatabaser er at de tvinger deg til å gå gjennom prosessen med å utvikle en datamodell. Hvis du har designet modellen godt, vil databasen inneholde en logisk struktur som fullt ut reflekterer strukturen til de lagrede dataene, men er i strid med strukturen til applikasjonen. Dette gjør dataene uavhengige av applikasjonen. Dette betyr at en annen applikasjon kan bruke samme data og applikasjonslogikken kan endres uten endringer i databasemodellen. For å gjøre det samme med et nøkkelverdilager, prøv å erstatte relasjonsmodelldesignprosessen med klassedesign, som lager generiske klasser basert på den naturlige strukturen til dataene.

Og ikke glem kompatibiliteten. I motsetning til relasjonsdatabaser har skybasert lagring langt færre vanlige standarder. Selv om de ikke er konseptuelt forskjellige, har de alle forskjellige APIer, forespørselsgrensesnitt og sine egne spesifikasjoner. Derfor bør du stole på leverandøren din, for hvis noe skjer, vil du ikke enkelt kunne bytte til en annen tjenesteleverandør. Og gitt det faktum at nesten alle moderne nøkkelverdibutikker er i beta 2, blir tillit enda mer risikabelt enn ved bruk av relasjonsdatabaser.

Begrenset dataanalyse

Vanligvis er all skylagring bygget på multi-tenancy basis, noe som betyr at et stort antall brukere og applikasjoner bruker samme system. For å forhindre at det overordnede systemet blir kapret, begrenser leverandørene vanligvis utførelsen av forespørsler på en eller annen måte. For eksempel, i SimpleDB kan en spørring ikke ta mer enn 5 sekunder å fullføre. I Google AppEngine Datastore kan du ikke få mer enn 1000 poster i én forespørsel 3.

Disse begrensningene er ikke forferdelige for enkel logikk (opprette, oppdatere, slette og hente et lite antall poster). Men hva om appen din blir populær? Du har fått mange nye brukere og mye ny data, og nå vil du gjøre nye opplevelser tilgjengelige for brukere eller på en eller annen måte dra nytte av dataene. Her kan du ha vanskeligheter med å utføre selv enkle spørringer for dataanalyse. Funksjoner som sporing av appbruksmønstre eller et anbefalingssystem basert på brukerhistorikk kan i beste fall være vanskelig å implementere. Og i verste fall er de rett og slett umulige.

I dette tilfellet, for analyse, er det bedre å lage en egen database, som vil bli fylt med data fra nøkkelverdilageret ditt. Tenk på forhånd hvordan dette kan gjøres. Vil du være vert for serveren i skyen eller internt? Vil det oppstå problemer på grunn av signalforsinkelser mellom deg og leverandøren din? Støtter lagringen din denne dataoverføringen? Hvis du har 100 millioner poster, og du kan ta 1000 poster om gangen, hvor mye vil det ta å migrere alle dataene?

Ikke prioriter skalerbarhet over alt annet. Det vil være ubrukelig hvis brukerne dine bestemmer seg for å bruke tjenestene til en annen tjeneste fordi den gir flere funksjoner og innstillinger.

Skylagring

Mange nettjenesteleverandører tilbyr nøkkelverdibutikker med flere leietakere. De fleste av dem oppfyller kriteriene som er oppført ovenfor, men hver har sine egne særtrekk og skiller seg fra standardene beskrevet ovenfor. La oss ta en titt på spesifikke lagringseksempler som SimpleDB, Google AppEngine Datastore og SQL Data Services.

Amazon: SimpleDB

SimpleDB er en attributtorientert nøkkelverdibutikk inkludert i Amazon WebServices. SimpleDB er i beta; brukere kan bruke det gratis - så lenge deres behov ikke overskrider en viss grense.

SimpleDB har flere begrensninger. For det første er utføringstiden for spørringen begrenset til 5 sekunder. For det andre er det ingen andre datatyper enn strenger. Alt lagres, hentes og sammenlignes som en streng, så for å sammenligne datoer må du konvertere dem til ISO8601-format. For det tredje er den maksimale størrelsen på en streng 1024 byte, noe som begrenser størrelsen på tekst (for eksempel en produktbeskrivelse) som du kan lagre som et attributt. Men siden datastrukturen er fleksibel, kan du omgå denne begrensningen ved å legge til attributtene "Produktbeskrivelse1", "Produktbeskrivelse2" osv. Men antallet attributter er også begrenset – maksimalt 256 attributter. Mens SimpleDB er i beta, er domenestørrelsen begrenset til 10 gigabyte, og hele databasen kan ikke oppta mer enn 1 terabyte.

En av hovedtrekkene til SimpleDB er bruken av en eventuell konsistensmodell. Denne modellen er egnet for flertrådsarbeid, men vær oppmerksom på at når du endrer verdien til et attributt i en post, kan det hende at etterfølgende lesninger ikke ser disse endringene. Sannsynligheten for en slik utvikling av hendelser er ganske lav, men det må huskes. Du vil ikke selge den siste billetten til fem kjøpere bare fordi dataene dine var inkonsekvente på salgstidspunktet.

Google AppEngine Data Store

Googles AppEngine Datastore er bygget på toppen av BigTable, Googles interne strukturerte datalagringssystem AppEngine Datastore gir ikke direkte tilgang til BigTable, men kan tenkes på som et forenklet grensesnitt for samhandling med BigTable.

AppEngine Datastore støtter flere datatyper innenfor en enkelt post enn SimpleDB. For eksempel lister som kan inneholde samlinger i en post.

Dette er datalageret du mest sannsynlig vil bruke når du utvikler med Google AppEngine. I motsetning til SimpleDB vil du imidlertid ikke kunne bruke AppEngine Datastore (eller BigTable) utenfor Google Web Services.

Microsoft: SQL Data Services

SQL Data Services er en del av Microsoft Azure-plattformen. SQL Data Services er gratis, i beta, og har grenser for databasestørrelse. SQL Data Services er en egen applikasjon – et tillegg over mange SQL-servere som lagrer data. Disse butikkene kan være relasjonelle, men for deg er SDS en nøkkelverdibutikk, akkurat som produktene beskrevet ovenfor.

Ikke-skylagring

Det finnes også en rekke lagringsalternativer som du kan bruke utenfor skyen ved å installere dem selv. Nesten alle disse prosjektene er unge, i alfa eller beta, og åpen kildekode. Med åpen kildekode kan du være mer oppmerksom på potensielle problemer og begrensninger enn med proprietære produkter.

CouchDB

CouchDB er en fritt tilgjengelig, åpen kildekode, dokumentorientert database. JSON brukes som et datalagringsformat. CouchDB har som mål å bygge bro mellom dokumentorienterte og relasjonsdatabaser ved å bruke "visninger." Slike visninger inneholder data fra dokumenter i en tabelllignende form og lar deg bygge indekser og kjøre spørringer.

Foreløpig er ikke CouchDB en virkelig distribuert database. Den har replikeringsfunksjoner som lar deg synkronisere data mellom servere, men dette er ikke distribusjonen som trengs for å bygge et svært skalerbart miljø. CouchDB-utviklere jobber imidlertid med dette.

Prosjekt Voldemort

Voldemort-prosjektet er en distribuert nøkkelverdi-database designet for å skalere horisontalt på tvers av et stort antall servere. Den ble født ut av LinkedIns utviklingsprosess og har blitt brukt til flere systemer med høye skalerbarhetskrav. Voldemort-prosjektet bruker også en finitt konsistensmodell.

Mongo

Mongo er en database utviklet på 10gen av Geir Magnusson og Dwight Merriman (som du kanskje kjenner fra DoubleClick). Som CouchDB er Mongo en dokumentorientert database som lagrer data i JSON-format. Imidlertid er Mongo mer en objektbase enn en ren nøkkelverdibutikk.

Duskregn

Drizzle representerer en helt annen tilnærming til å løse problemene som nøkkelverdibutikker er designet for å bekjempe. Drizzle startet som en gaffel av MySQL 6.0. Senere fjernet utviklere en rekke funksjoner (inkludert visninger, triggere, kompilerte uttrykk, lagrede prosedyrer, spørringsbuffer, ACLer og noen datatyper) for å lage en enklere og raskere DBMS. Imidlertid kan Drizzle fortsatt brukes til å lagre relasjonsdata. Målet til utviklerne er å bygge en semi-relasjonell plattform designet for web- og skyapplikasjoner som kjører på systemer med 16 eller flere kjerner.

Løsning

Til syvende og sist er det fire grunner til at du kan velge en ikke-relasjonell nøkkelverdi-butikk for applikasjonen din:

1. Dataene dine er svært dokumentorienterte, og er mer egnet til en nøkkelverdi-datamodell enn en relasjonsmodell.
2. Domenemodellen din er svært objektorientert, så bruk av et nøkkelverdilager vil redusere mengden ekstra kode som kreves for å transformere dataene.
3. Datavarehuset er billig og kan enkelt integreres med leverandørens webtjenester.
4. Hovedproblemet ditt er høy skalerbarhet etter behov.

Men når du bestemmer deg, vær oppmerksom på begrensningene til spesifikke databaser og risikoen du vil møte hvis du går ned på veien med å bruke ikke-relasjonelle databaser.

For alle andre krav er det bedre å velge den gode gamle relasjonelle DBMS. Så er de dømt? Selvfølgelig ikke. I hvert fall for nå.

1 - etter min mening er begrepet "datastruktur" mer passende her, men jeg forlot den opprinnelige datamodellen.
2 - mest sannsynlig mente forfatteren at når det gjelder deres evner, er ikke-relasjonelle databaser dårligere enn relasjonelle.
3 - dataene kan allerede være utdaterte; artikkelen dateres tilbake til februar 2009.

Legg til merkelapper

En datamodell er et sett med datastrukturer og operasjoner for deres behandling. Ved å bruke en datamodell kan du visuelt representere strukturen til objekter og relasjonene som er etablert mellom dem. Datamodellterminologi er preget av begrepene «dataelement» og «bindende regler». Et dataelement beskriver ethvert sett med data, og tilknytningsregler definerer algoritmer for sammenkobling av dataelementer. Til dags dato er det utviklet mange ulike datamodeller, men i praksis brukes tre hovedmodeller. Det finnes hierarkiske, nettverks- og relasjonsdatamodeller. Følgelig snakker de om hierarkiske, nettverks- og relasjonelle DBMS-er.

O Hierarkisk datamodell. Hierarkisk organisert data er svært vanlig i hverdagen. For eksempel er strukturen til en høyere utdanningsinstitusjon en hierarkisk struktur på flere nivåer. En hierarkisk (tre) database består av et ordnet sett med elementer. I denne modellen gir startelementer opphav til andre elementer, og disse elementene gir opphav til ytterligere elementer. Hvert underordnede element har bare ett overordnet element.

Organisasjonsstrukturer, materiallister, innholdsfortegnelser i bøker, prosjektplaner og mange andre sett med data kan presenteres i hierarkisk form. Integriteten til koblinger mellom forfedre og etterkommere opprettholdes automatisk. Grunnregel: intet barn kan eksistere uten sin forelder.

Den største ulempen med denne modellen er behovet for å bruke hierarkiet som var grunnlaget for databasen under utformingen. Behovet for konstant omorganisering av data (og ofte umuligheten av denne omorganiseringen) førte til opprettelsen av en mer generell modell - en nettverksmodell.

O Nettverksdatamodell. Nettverkstilnærmingen til dataorganisering er en utvidelse av den hierarkiske tilnærmingen. Denne modellen skiller seg fra den hierarkiske ved at hvert generert element kan ha mer enn ett genererende element. ■

Fordi en nettverksdatabase direkte kan representere alle slags relasjoner som er iboende i dataene til den tilsvarende organisasjonen, kan disse dataene navigeres, utforskes og spørres på forskjellige måter, det vil si at nettverksmodellen ikke er bundet av bare ett hierarki. Men for å sende en forespørsel til en nettverksdatabase, er det nødvendig å gå dypt inn i strukturen (ha skjemaet til denne databasen for hånden) og utvikle en mekanisme for å navigere i databasen, noe som er en betydelig ulempe med denne databasemodellen .

O Relasjonsdatamodell. Den grunnleggende ideen med en relasjonsdatamodell er å representere ethvert sett med data som en todimensjonal tabell. I sin enkleste form beskriver en relasjonsmodell en enkelt todimensjonal tabell, men som oftest beskriver modellen strukturen og sammenhengene mellom flere forskjellige tabeller.

Relasjonsdatamodell

Så formålet med informasjonssystemet er å behandle data Om gjenstander virkelige verden, tatt i betraktning forbindelser mellom objekter. I databaseteori kalles data ofte attributter, og gjenstander - enheter. Objekt, attributt og sammenheng er grunnleggende begreper i I.S.

En gjenstand(eller essens) er noe som eksisterer og skilles ut, det vil si at et objekt kan kalles det "noe" som det er et navn for og en måte å skille ett lignende objekt fra et annet. For eksempel er hver skole et objekt. Objekter er også en person, en klasse på skolen, en bedrift, en legering, en kjemisk forbindelse osv. Objekter kan ikke bare være materielle objekter, men også mer abstrakte begreper som gjenspeiler den virkelige verden. For eksempel arrangementer, regioner, kunstverk; bøker (ikke som trykte produkter, men som verk), teaterforestillinger, filmer; juridiske normer, filosofiske teorier mv.

Egenskap(eller gitt)- dette er en viss indikator som karakteriserer et bestemt objekt og tar en viss numerisk, tekst eller annen verdi for en bestemt forekomst av objektet. Informasjonssystemet opererer med sett med objekter designet i forhold til et gitt fagområde, ved hjelp av spesifikke attributtverdier(data) av visse objekter. La oss for eksempel ta klasser på en skole som et sett med objekter. Antall elever i en klasse er et datum som får en numerisk verdi (en klasse har 28, en annen har 32). Klassenavnet er et gitt navn som tar en tekstverdi (en har 10A, en annen har 9B osv.).

Utviklingen av relasjonsdatabaser begynte på slutten av 60-tallet, da de første verkene dukket opp som diskuterte; muligheten for å bruke kjente og naturlige måter å presentere data på – de såkalte tabelldatalogiske modellene – ved utforming av databaser.

Grunnleggeren av teorien om relasjonsdatabaser anses å være en IBM-ansatt, Dr. E. Codd, som publiserte en artikkel 6. juni 1970 En relasjonsmodell av data for store delte databanker(Relasjonsdatamodell for store kollektive databanker). Denne artikkelen var den første som brukte begrepet "relasjonsdatamodell." Teorien om relasjonsdatabaser, utviklet på 70-tallet i USA av Dr. E. Codd, har et kraftig matematisk grunnlag som beskriver reglene for effektiv organisering av data. Det teoretiske rammeverket utviklet av E. Codd ble grunnlaget for utviklingen av teorien om databasedesign.

E. Codd, som er matematiker av utdannelse, foreslo å bruke settteoriens apparat (union, skjæringspunkt, forskjell, kartesisk produkt) for databehandling. Han beviste at ethvert sett med data kan representeres i form av todimensjonale tabeller av en spesiell type, kjent i matematikk som "relasjoner".

Relasjonell En database anses å være en der alle data presenteres for brukeren i form av rektangulære tabeller med dataverdier, og alle operasjoner på databasen er redusert til manipulasjoner med tabellene.

Bordet består av kolonner (felt) Og linjer (poster); har et navn som er unikt i databasen. Bord reflekterer Objekttype virkelige verden (enhet), og hver av henne streng er et spesifikt objekt. Hver tabellkolonne er en samling av verdier for et spesifikt attributt til et objekt. Verdiene velges fra settet med alle mulige verdier for et objektattributt, som kalles domene.

I sin mest generelle form er et domene definert ved å spesifisere en basedatatype som elementene i domenet tilhører, og et vilkårlig boolsk uttrykk brukt på dataelementene. Hvis du evaluerer en boolsk tilstand på et dataelement og resultatet er sant, tilhører det elementet domenet. I det enkleste tilfellet er et domene definert som et gyldig potensielt sett med verdier av samme type. For eksempel utgjør innsamlingen av fødselsdatoene til alle ansatte «fødselsdatodomenet», og navnene på alle ansatte utgjør «ansattnavnsdomenet». Fødselsdatodomenet må ha en datatype på tidspunktet, og domenet for ansattnavnet må ha en karakterdatatype.

Hvis to verdier kommer fra samme domene, kan det gjøres en sammenligning mellom de to verdiene. For eksempel, hvis to verdier er hentet fra domenet til fødselsdatoer, kan du sammenligne dem og finne ut hvilken ansatt som er eldre. Hvis verdiene er hentet fra forskjellige domener, er sammenligningen deres ikke tillatt, siden det etter all sannsynlighet ikke gir mening. For eksempel vil det ikke komme noe sikkert ut av å sammenligne en ansatts navn og fødselsdato.

Hver kolonne (felt) har et navn, som vanligvis skrives øverst i tabellen. Når du designer tabeller innenfor et spesifikt DBMS, er det mulig å velge for hvert felt sitt type, det vil si å definere et sett med regler for visningen, samt å bestemme operasjonene som kan utføres på dataene som er lagret i dette feltet. Sett med typer kan variere mellom ulike DBMS-er.

Feltnavnet må være unikt i tabellen, men ulike tabeller kan ha felt med samme navn. Enhver tabell må ha minst ett felt; Feltene er plassert i tabellen i samsvar med rekkefølgen navnene deres dukket opp i da den ble opprettet. I motsetning til felt har ikke strenger navn; rekkefølgen deres i tabellen er ikke definert, og antallet er logisk ubegrenset.

Siden radene i tabellen ikke er sortert, er det umulig å velge en rad etter posisjon - det er ingen "første", "andre" eller "siste" blant dem. Enhver tabell har en eller flere kolonner, verdiene som identifiserer hver av radene. En slik kolonne (eller kombinasjon av kolonner) kalles primærnøkkel. Et kunstig felt introduseres ofte til tallposter i en tabell. Et slikt felt kan for eksempel være dets ordinære felt, som kan sikre unikheten til hver post i tabellen. Nøkkelen må ha følgende egenskaper.

Unikhet. Til enhver tid har ingen to forskjellige relasjonstupler samme verdi for kombinasjonen av attributter som er inkludert i nøkkelen. Det vil si at det ikke kan være to rader i tabellen som har samme identifikasjonsnummer eller passnummer.

Minimalisme. Ingen av attributtene som er inkludert i nøkkelen kan ekskluderes fra nøkkelen uten å krenke unikhet. Det betyr at du ikke skal opprette en nøkkel som inneholder både passnummer og identifikasjonsnummer. Det er nok å bruke noen av disse attributtene for å identifisere en tuppel unikt. Du bør heller ikke inkludere et ikke-unikt attributt i nøkkelen, det vil si at det er forbudt å bruke en kombinasjon av et identifikasjonsnummer og en ansatts navn som nøkkel. Ved å ekskludere den ansattes navn fra nøkkelen, kan hver rad fortsatt identifiseres unikt.

Hver relasjon har minst én mulig nøkkel, siden totaliteten av alle dens attributter tilfredsstiller betingelsen om unikhet - dette følger av selve definisjonen av relasjonen.

En av de mulige nøklene er tilfeldig valgt i som primærnøkkel. De resterende mulige nøklene, hvis noen, tas som alternative nøkler. Hvis du for eksempel velger et identifikasjonsnummer som primærnøkkel, vil passnummeret være den alternative nøkkelen.

Relasjonen mellom tabeller er det viktigste elementet i relasjonsdatamodellen. Det støttes fremmednøkler.

Når en relasjonsdatabasemodell skal beskrives, brukes ofte ulike termer for samme konsept, avhengig av beskrivelsesnivået (teori eller praksis) og systemet (Access, SQL Server, dBase). I tabellen 2.3 gir et sammendrag av begrepene som brukes.

Tabell 2.3. Databaseterminologi

Databaseteori____________ Relasjonsdatabaser_________ SQL Server __________

Relasjonstabell Tabell

Tuple Record Row

Attributtfelt_______________Kolonne

Relasjonelle databaser

Relasjonsdatabase er et sett med relasjoner som inneholder all informasjon som må lagres i databasen. Det vil si at databasen representerer et sett med tabeller som er nødvendig for å lagre alle dataene. Tabellene i en relasjonsdatabase er logisk relatert til hverandre Kravene til utforming av en relasjonsdatabase generelt kan reduseres til flere regler.

О Hver tabell har et unikt navn i databasen og består av rader av samme type.

O Hver tabell består av et fast antall kolonner og verdier. Mer enn én verdi kan ikke lagres i én enkelt radkolonne. Hvis det for eksempel er en tabell med informasjon om forfatter, utgivelsesdato, opplag osv., kan ikke kolonnen med forfatterens navn lagre mer enn ett etternavn. Hvis boken er skrevet av to eller flere forfattere, må du bruke tilleggstabeller.

O Ikke på noe tidspunkt vil det være to rader i tabellen som dupliserer hverandre. Rader må avvike i minst én verdi for å kunne identifisere en hvilken som helst rad i tabellen unikt.

О Hver kolonne er tildelt et unikt navn i tabellen; en spesifikk datatype er satt for det slik at homogene verdier plasseres i denne kolonnen (datoer, etternavn, telefonnumre, pengebeløp, etc.).

O Det fullstendige informasjonsinnholdet i en database er representert som eksplisitte verdier av selve dataene, og dette er den eneste representasjonsmetoden. For eksempel er relasjoner mellom tabeller basert på dataene som er lagret i de tilsvarende kolonnene, og ikke på grunnlag av noen pekere som kunstig definerer relasjoner.

О Når du behandler data, har du fritt tilgang til hvilken som helst rad eller kolonne i tabellen. Verdiene som er lagret i tabellen pålegger ingen begrensninger på rekkefølgen dataene blir aksessert i. Beskrivelse av kolonnene,