Begrebet relationel er forbundet med udviklingen af ​​en berømt amerikansk specialist inden for databasesystemer, en ansat i virksomheden IBM Drs. E. Codd (Codd E.F., A Relational Model of Data for Large Shared Data Banks. CACM 13: 6, juni 1970), som først brugte udtrykket "relationel datamodel".

I lang tid blev den relationelle tilgang betragtet som et praktisk formelt apparat til databaseanalyse, som ikke havde nogen praktiske udsigter, da implementeringen krævede for mange maskinressourcer. Først med adventen personlige computere relationelle og relaterede systemer begyndte at brede sig, hvilket stort set ikke efterlod plads til andre modeller.

Disse modeller er kendetegnet ved enkelhed af datastruktur, brugervenlig tabelrepræsentation og evnen til at bruge det formelle apparat af relationel algebra og relationel calculus til databehandling.

Relationsmodellen fokuserer på at organisere data i form af todimensionelle tabeller. Hver relationel tabel er todimensionelt array og har følgende egenskaber:

• - hvert tabelelement er et dataelement; der er ingen gentagne grupper;
• - alle kolonner i tabellen er homogene, dvs. alle elementer i en kolonne har samme type(numerisk, tegn osv.) og længde;
• - hver kolonne har et unikt navn;
• - der er ingen identiske rækker i tabellen;
• - rækkefølgen af ​​rækker og kolonner kan være vilkårlig. Denne form for tabel kaldes en relation.

En database bygget ved hjælp af relationer kaldes en relationsdatabase.

Relationer præsenteres i form af tabeller, hvis rækker svarer til tupler eller poster, og kolonnerne svarer til relationsattributter, domæner og felter.

Et felt, hvis hver værdi entydigt identificerer den tilsvarende post, kaldes med en simpel nøgle(nøglefelt). Hvis poster er unikt identificeret af værdierne af flere felter, så har en sådan databasetabel en sammensat nøgle.

For at forbinde to relationelle tabeller skal du inkludere nøglen til den første tabel som en del af nøglen til den anden tabel (nøglerne kan falde sammen). ellers skal du indtaste en fremmednøgle i strukturen af ​​den første tabel - nøglen til den anden tabel.

Efter at have foreslået en relationel datamodel, E.F. Codd skabte også et værktøj til praktisk arbejde med relationer – relationel algebra. Hver operation af denne algebra bruger en eller flere tabeller (relationer) som sine operander og producerer en ny tabel som et resultat, dvs. giver dig mulighed for at "klippe" eller "lime" borde.

Hvordan relationelle modeller fundamentalt adskiller sig fra netværk og hierarkiske, kan siges som følger: hierarkiske og netværksmodeller Data - har en sammenhæng ved struktur, og relationel - har en sammenhæng ved mening.

Databasedesign er traditionelt blevet betragtet som en meget vanskelig opgave. Relationel teknologi gør denne opgave meget lettere.

Ved at adskille de logiske og fysiske lag i et system, forenkler det processen med at kortlægge "den virkelige verden lag" til en struktur, som systemet direkte kan understøtte. Fordi selve relationsstrukturen er begrebsmæssigt simpel, tillader den implementering af små og/eller simple (og derfor nemme at skabe) databaser, såsom personlige databaser, som aldrig ville have været anset for mulige i ældre, mere komplekse systemer.

Teorien og disciplinen om normalisering kan hjælpe ved at vise, hvad der sker, når relationer ikke er naturligt strukturerede.

Den relationelle datamodel er især praktisk til brug i distribuerede arkitekturdatabaser - den giver dig adgang til evt informationselementer, gemt i computernetværksknuder. Det er nødvendigt at være særlig opmærksom på det høje niveau af den relationelle tilgang, som består af multipel registreringsbehandling. Takket være dette øges potentialet i den relationelle tilgang betydeligt, hvilket ikke kan opnås ved behandling af én post ad gangen og frem for alt handler det om optimering.

Denne model giver dig mulighed for at bestemme:

• · operationer til lagring og genfinding af data;
• · restriktioner relateret til at sikre dataintegritet.

For at øge den operationelle effektivitet vedtager mange relationelle DBMS'er begrænsninger, der svarer til en streng relationel model.

Mange relationelle DBMS'er præsenterer databasefiler for brugeren i et tabelformat - med poster som rækker og deres felter som kolonner. I tabelform opfattes information meget lettere. Men i en database på det fysiske niveau lagres data normalt i filer, der indeholder sekvenser af poster.

Hovedfordel relationel DBMS er evnen til at linke baseret på bestemte relationer af databasefiler.

Fra et strukturelt synspunkt er relationelle modeller enklere og mere homogene end hierarkiske modeller og netværksmodeller. I den relationelle model er hvert objekt emneområde matcher en eller flere relationer. Hvis det er nødvendigt at definere forholdet mellem objekter eksplicit, udtrykkes det i form af en relation, hvor identifikatorer af indbyrdes forbundne objekter er til stede som attributter. I den relationelle model er genstandsområdets objekter og forbindelserne mellem dem repræsenteret af de samme informationsstrukturer, hvilket væsentligt forenkler selve modellen.

Et DBMS betragtes som relationelt, hvis følgende to betingelser, foreslået af E. Codd, er opfyldt:

• · understøtter relationel datastruktur;
• · implementerer i det mindste operationerne med udvælgelse, projektion og forbindelse af relationer.

Efterfølgende blev den oprettet hele linjen relationel DBMS, i en eller anden grad møde denne definition. Mange DBMS'er er væsentlige udvidelser af den relationelle model, mens andre er blandede og understøtter flere datamodeller.

I dag er relationsdatabaser fortsat de mest almindelige på grund af deres enkelhed og overskuelighed, både under oprettelsesprocessen og på brugerniveau.

Den største fordel ved relationelle databaser er deres kompatibilitet med det mest populære forespørgselssprog, SQL.

Med en enkelt forespørgsel på dette sprog kan du samle flere tabeller til en midlertidig tabel og skære de nødvendige rækker og kolonner ud fra den (udvælgelse og projektion). Da tabelstrukturen i en relationsdatabase er intuitiv for brugerne, er SQL-sproget enkelt og nemt at lære. Relationsmodellen har et solidt teoretisk fundament, som udviklingen og implementeringen af ​​relationelle databaser var baseret på. Som følge af den bølge af popularitet, der blev genereret af den relationelle models succes, blev SQL det primære sprog for relationelle databaser.

Men ulemperne ved den overvejede databasemodel er også blevet identificeret:

• - da alle felterne i en tabel skal indeholde et konstant antal felter af foruddefinerede typer, er det nødvendigt at oprette yderligere tabeller, der tager højde for elementernes individuelle karakteristika ved hjælp af fremmednøgler. Denne tilgang gør det meget vanskeligt at skabe komplekse relationer i databasen;
• - høj kompleksitet i at manipulere information og ændre forbindelser.

Database (DB) - Dette er et navngivet sæt af strukturerede data relateret til et specifikt emneområde og beregnet til lagring, akkumulering og behandling ved hjælp af en computer.

Relationel base Data (RBD) er et sæt af relationer, hvis navne falder sammen med navnene på skemarelationer i databaseskemaet.

Basale koncepter relationelle databaser:

· Datatype– type værdier for en specifik kolonne.

· Domæne(domæne) – sættet af alle acceptable værdier attribut.

· Attribut(attribut) – tabelkolonneoverskrift, der karakteriserer en navngivet egenskab for et objekt, for eksempel elevens efternavn, ordredato, medarbejders køn osv.

· Cortege– en tabelrække, der repræsenterer et sæt værdier af logisk relaterede attributter.

· Holdning(relation) – en tabel, der afspejler information om objekter i den virkelige verden, for eksempel om studerende, ordrer, medarbejdere, beboere osv.

· Primærnøgle(primær nøgle) – et felt (eller sæt af felter) i en tabel, der unikt identificerer hver af dens poster.

· Alternativ nøgle er et felt (eller et sæt af felter), der ikke stemmer overens primærnøgle og unik identifikation af registreringsforekomsten.

· Ekstern nøgle er et felt (eller et sæt af felter), hvis værdier matcher de eksisterende værdier af den primære nøgle i en anden tabel. Når du sammenkæder to tabeller, er den primære nøgle i den første tabel knyttet til den fremmede nøgle i den anden tabel.

· Relationel datamodel (RDM)- organisering af data i form af todimensionelle tabeller.

Hver relationstabel skal have følgende egenskaber:

1. Hver tabelpost er unik, dvs. værdisættet i felterne gentages ikke.

2. Hver værdi skrevet i skæringspunktet mellem en række og en kolonne er atomisk (uadskillelig).

3. Værdierne for hvert felt skal være af samme type.

4. Hvert felt har et unikt navn.

5. Rækkefølgen af ​​indtastningerne er ikke væsentlig.

Hovedelementer i databasen:

Mark- en elementær enhed for logisk organisering af data. Følgende egenskaber bruges til at beskrive feltet:

· navn, for eksempel efternavn, fornavn, patonym, fødselsdato;

· indtast f.eks. streng, tegn, numerisk, dato;

· længde, for eksempel i bytes;

· præcision for numeriske data, såsom to decimaler for at vise brøkdelen af ​​et tal.

Optage- et sæt værdier af logisk relaterede felter.

Indeks– et middel til at fremskynde registreringssøgningen, der bruges til at etablere relationer mellem tabeller. En tabel, som et indeks bruges til, kaldes indekseret. Når du arbejder med indekser, skal du være opmærksom på organiseringen af ​​indeksene, som er grundlaget for klassificering. Et simpelt indeks er repræsenteret af et enkelt felt eller logisk udtryk, behandler ét felt. Et sammensat indeks er repræsenteret af flere felter med mulighed for at bruge forskellige funktioner. Tabelindekser gemmes i en indeksfil.

Dataintegritet– dette er et middel til at beskytte data på kommunikationsfelter, som giver dig mulighed for at vedligeholde tabeller i en konsistent (konsistent) tilstand (det vil sige, det tillader ikke eksistensen af ​​poster i den underordnede tabel, der ikke har tilsvarende poster i den overordnede tabel bord).

Anmodning– et formuleret spørgsmål til en eller flere indbyrdes forbundne tabeller, der indeholder datastikprøvekriterier. Forespørgslen udføres ved hjælp af det strukturerede forespørgselssprog SQL (Structured Query Language). Hentning af data fra en eller flere tabeller kan resultere i et sæt poster kaldet en visning.

Datapræsentation– en navngivet forespørgsel gemt i databasen for at hente data (fra en eller flere tabeller).

En visning er i bund og grund en midlertidig tabel, der er oprettet som et resultat af en forespørgsel. Selve anmodningen kan sendes til en separat fil, rapport, midlertidig tabel, tabel på disk mv.

Rapport– en systemkomponent, hvis hovedformål er at beskrive og udskrive dokumenter baseret på information fra databasen.

generelle karakteristika arbejder med RDB:

Den mest almindelige fortolkning af den relationelle datamodel synes at være Data, som gengiver den (med forskellige justeringer) i næsten alle hans bøger. Ifølge Date består den relationelle model af tre dele, der beskriver forskellige aspekter af den relationelle tilgang: den strukturelle del, manipulationsdelen og den holistiske del.

Den strukturelle del af modellen siger, at den eneste datastruktur, der anvendes i relationelle databaser, er den normaliserede n-ære relation.

Manipulationsdelen af ​​modellen bekræfter to grundlæggende mekanismer til at manipulere relationelle databaser - relationel algebra og relationel calculus. Den første mekanisme er hovedsageligt baseret på klassisk mængdeteori (med nogle justeringer), og den anden er baseret på det klassiske logiske apparat af førsteordens prædikatregning. Bemærk, at hovedfunktionen af ​​manipulationsdelen af ​​relationsmodellen er at give et mål for relationaliteten af ​​ethvert specifikt relationsdatabasesprog: et sprog kaldes relationelt, hvis det ikke har mindre udtryksevne og magt end relationel algebra eller relationel calculus.

28. ALGORITMISKE SPROG. OVERSÆTTERE (TOLK OG KOMPILERE). ALGORITMISK SPROG BASIC. PROGRAMMETS STRUKTUR. IDENTIFIKATIONER. VARIABLER. OPERATØRER. BEHANDLING AF EN-DIMENSIONELLE OG TO-DIMENSIONALE ARRAYS. BRUGERFUNKTIONER. SUBRUTINER. ARBEJDER MED DATAFILER.

sprog på højt niveau- et programmeringssprog, hvis begreber og struktur er praktiske for menneskelig opfattelse.

Algoritmisk sprog(Algorithmic language) - et programmeringssprog - et kunstigt (formelt) sprog designet til at skrive algoritmer. Et programmeringssprog er defineret ved dets beskrivelse og implementeret i form af et særligt program: en compiler eller tolk. Eksempler på algoritmiske sprog er Borland Pascal, C++, Basic osv.

Grundlæggende begreber i algoritmisk sprog:

Sprogets sammensætning:

Almindelig talesprog består af fire grundelementer: symboler, ord, sætninger og sætninger. Et algoritmisk sprog indeholder lignende elementer, kun ord kaldes elementære konstruktioner, sætninger kaldes udtryk, og sætninger kaldes operatorer.

Symboler, elementære konstruktioner, udtryk og operatorer udgør hierarkisk struktur, da elementære strukturer er dannet ud fra en sekvens af symboler.

Udtryk er en sekvens af elementære strukturer og symboler,

Operatør- en sekvens af udtryk, elementære strukturer og symboler.

Sprogbeskrivelse:

En karakterbeskrivelse består af at angive sprogets gyldige tegn. Beskrivelsen af ​​elementære strukturer betyder reglerne for deres dannelse. Beskrivelse af udtryk er reglerne for dannelsen af ​​ethvert udtryk, der har betydning i et givet sprog. Beskrivelsen af ​​operatører består af en overvejelse af alle typer operatører tilladt på sproget. Beskrivelsen af ​​hvert sprogelement er givet af dets SYNTAX og SEMANTIK.

Syntaktisk definitioner fastlægger regler for konstruktion af sprogelementer.

Semantik definerer betydningen og brugsreglerne for de sprogelementer, for hvilke der er givet syntaktiske definitioner.

Sprog symboler- det er de grundlæggende udelelige tegn, som alle tekster på sproget er skrevet ud fra.

Elementære strukturer- Det her minimumsenheder sprog, der har selvstændig betydning. De er dannet ud fra sprogets grundlæggende symboler.

Udtryk i et algoritmisk sprog består det af elementære strukturer og symboler; det specificerer en regel for beregning af en bestemt værdi.

Operatør sæt Fuld beskrivelse en handling, der skal udføres. En gruppe af udsagn kan være påkrævet for at beskrive en kompleks handling.

I dette tilfælde kombineres operatørerne til Sammensat operatør eller Blok. Handlinger, specificeret af operatørerne, udføres på dataene. Udsagn fra et algoritmisk sprog, der giver information om datatyper, kaldes deklarationer eller ikke-eksekverbare udsagn. Et sæt beskrivelser og operatorer forenet af en enkelt algoritme danner et program i et algoritmisk sprog. I processen med at studere et algoritmisk sprog er det nødvendigt at skelne det algoritmiske sprog fra det sprog, hvormed beskrivelsen af ​​det algoritmiske sprog, der studeres, udføres. Normalt kaldes det sprog, der studeres blot et sprog, og det sprog, som beskrivelsen af ​​det studerede sprog er givet - Metasprog.

Oversættere - (English translator - translator) er et oversætterprogram. Det konverterer et program skrevet på et af højniveausprogene til et program bestående af maskininstruktioner.

Et program skrevet i et hvilket som helst algoritmisk sprog på højt niveau kan ikke udføres direkte på en computer. Computeren forstår kun sproget for maskinkommandoer. Følgelig skal et program i et algoritmisk sprog oversættes (oversættes) til kommandosproget på en bestemt computer. En sådan oversættelse udføres automatisk af specielle oversætterprogrammer, der er oprettet for hvert algoritmisk sprog og for hver type computer.

Der er to hovedudsendelsesmetoder - kompilering og fortolkning.

1.Compilation: Compiler(engelsk compiler - compiler, collector) læser hele programmet, oversætter det og laver en komplet version af programmet på maskinsprog, som derefter udføres.

På samling hele det originale program konverteres straks til en sekvens af maskininstruktioner. Herefter udføres det resulterende program af en computer med de tilgængelige kildedata. Fordelen ved denne metode er, at oversættelsen udføres én gang, og den (flere) udførelse af det resulterende program kan udføres med høj hastighed. Samtidig kan det resulterende program optage meget plads i computerens hukommelse, da en sprogoperator bliver erstattet af hundredvis eller endda tusindvis af kommandoer under oversættelse. Derudover er fejlfinding og ændringer af det udsendte program meget vanskeligt.

2. Tolkning: Tolk(Engelsk tolk - tolk, tolk) oversætter og udfører programmet linje for linje.

På fortolkninger kildeprogrammet er gemt i computerens hukommelse næsten uændret. Tolkeprogrammet afkoder kildeprogrammets udsagn én ad gangen og sikrer straks deres eksekvering med de tilgængelige data. Det fortolkede program fylder lidt i computerens hukommelse og er let at fejlfinde og ændre. Men udførelsen af ​​programmet er ret langsom, da fortolkningen af ​​alle operatører udføres på ny med hver udførelse.

Kompilerede programmer kører hurtigere, men fortolkede programmer er nemmere at rette og ændre.

Hvert specifikt sprog er orienteret enten mod kompilering eller fortolkning - afhængigt af formålet, som det er skabt til. For eksempel bruges Pascal normalt til at løse ganske komplekse opgaver, hvor hastigheden af ​​programmer er vigtig. Derfor givet sprog normalt implementeret ved hjælp af en compiler.

På den anden side blev BASIC skabt som et sprog for begyndere programmører, for hvem linje-for-linje eksekvering af et program har ubestridelige fordele.

Nogle gange er der både en compiler og en tolk til det samme sprog. I dette tilfælde kan du bruge en fortolker til at udvikle og teste programmet og derefter kompilere det fejlrettede program for at forbedre dets eksekveringshastighed.

Alle moderne databaser bruger CBO (Cost Based Optimization), omkostningsoptimering. Dens essens ligger i, at for hver operation bestemmes dens "omkostninger", og derefter reduceres de samlede omkostninger ved anmodningen ved at bruge de "billigste" operationskæder.

For bedre at forstå omkostningsoptimering vil vi se på tre almindelige måder at forbinde to tabeller på og se, hvordan selv en simpel joinforespørgsel kan blive til en optimeringsmareridt. I vores diskussion vil vi fokusere på tidskompleksitet, selvom optimizeren beregner "omkostningen" i form af processorressourcer, hukommelse og I/O-operationer. Det er bare, at tidskompleksitet er et omtrentligt begreb, og for at bestemme de nødvendige processorressourcer skal du tælle alle operationerne, inklusive additioner, hvis udsagn, multiplikationer, iterationer osv.

Udover:

• For at udføre hver højniveauoperation udfører processoren et forskelligt antal lavniveauoperationer.
• Omkostningerne ved processoroperationer (i form af cyklusser) varierer mellem forskellige typer processorer, det vil sige, det afhænger af den specifikke CPU-arkitektur.

Derfor bliver det lettere for os at vurdere i form af kompleksitet. Men husk, at databasens ydeevne oftest er begrænset af diskens undersystem og ikke af processorressourcer.

Vi talte om dem, da vi så på B-træer. Som du husker, er indeksene allerede sorteret. Forresten er der andre typer indekser, for eksempel bitmapindeks. Men de giver ikke nogen fordele med hensyn til CPU, hukommelse og diskudnyttelse sammenlignet med B-tree indekser. Derudover kan mange moderne databaser dynamisk oprette midlertidige indekser til igangværende forespørgsler, hvis dette vil hjælpe med at reducere omkostningerne ved at eksekvere planen.

4.4.2. Ankemetoder

Før du kan bruge fagforeningsoperatører, skal du først indhente de nødvendige data. Du kan gøre dette på følgende måder.

• Fuld scanning. Databasen læser simpelthen hele tabellen eller indekset. Som du forstår, er det for diskundersystemet billigere at læse et indeks end en tabel.
• Rækkevidde scanning. Bruges f.eks. når du bruger prædikater som WHERE AGE > 20 AND AGE< 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.

  I den første del af artiklen fandt vi allerede ud af, at tidskompleksiteten af ​​en intervalforespørgsel er defineret som M + log(N), hvor N er antallet af data i indekset, og M er det estimerede antal rækker inden for rækkevidden. Vi kender værdierne af begge disse variabler takket være statistik. En rækkeviddescanning læser kun en del af indekset, så operationen koster mindre end en fuld scanning.

• Scan for unikke værdier. Bruges i tilfælde, hvor du kun skal have én værdi fra indekset.
• Adgang via række-id. Hvis databasen bruger et indeks, vil den det meste af tiden søge efter rækker, der er knyttet til det. For eksempel fremsætter vi følgende anmodning:

  VÆLG EFTERNAVN, FORNAVN fra PERSON WHERE AGE = 28
  Hvis vi har et indeks på alderskolonnen, vil optimeringsværktøjet bruge indekset til at finde alle 28-årige og derefter forespørge på ID'erne for de tilsvarende rækker i tabellen, da indekset kun indeholder aldersoplysninger.

  Lad os sige, at vi har en anden anmodning:

  VÆLG TYPE_PERSON.CATEGORY fra PERSON, TYPE_PERSON HVOR PERSON.AGE = TYPE_PERSON.AGE
  For at flette med TYPE_PERSON vil der blive brugt et indeks på PERSON-kolonnen. Men da vi ikke har anmodet om oplysninger fra PERSON-tabellen, vil ingen få adgang til dem via række-id'er.

  Denne tilgang er kun god til et lille antal opkald, fordi den er dyr med hensyn til I/O. Hvis du ofte har brug for at få adgang til dit ID, er det bedre at bruge en fuld scanning.

• andre metoder. Du kan læse om dem i Oracle-dokumentationen. Forskellige databaser kan bruge forskellige navne, men principperne er de samme overalt.

4.4.3. Fagforeningsdrift

Så vi ved, hvordan vi får dataene, det er tid til at kombinere dem. Men lad os først definere nogle nye termer: indre afhængigheder og ydre afhængigheder. Afhængigheden kan være:

• bord,
• indeks,
• mellemresultatet af en tidligere operation (f.eks. en tidligere joinforbindelse).

Når vi kombinerer to afhængigheder, håndterer flettealgoritmerne dem forskelligt. Lad os sige, at A JOIN B er foreningen af ​​A og B, hvor A er en ekstern afhængighed og B er en intern afhængighed.

Oftest er prisen på A JOIN B ikke lig med prisen på B JOIN A.

Lad os antage, at den eksterne afhængighed indeholder N elementer, og den interne afhængighed indeholder M. Som du husker, kender optimeringsværktøjet disse værdier takket være statistik. N og M er kardinalafhængighedstal.

• Forening ved hjælp af indlejrede løkker. Dette er den nemmeste måde at kombinere.

  

  Det fungerer sådan her: for hver streng af en ekstern afhængighed findes matches på tværs af alle strenge af den interne afhængighed.

  Pseudokode eksempel:

  Nested_loop_join(array ydre, array indre) for hver række a i ydre for hver række b i indre if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for
  Da dette er en dobbelt iteration, er tidskompleksiteten defineret som O(N*M).

  For hver af N eksterne afhængighedsrækker skal du tælle M eksterne afhængighedsrækker. Det vil sige, at denne algoritme kræver N + N*M læsninger fra disk. Hvis den interne afhængighed er lille nok, så kan du lægge den helt i hukommelsen, og så vil diskens undersystem kun have M+N-læsninger. Så det anbefales at gøre den interne afhængighed så kompakt som muligt for at passe den ind i hukommelsen.

  Fra et tidskompleksitetssynspunkt er der ingen forskel.

  Du kan også erstatte den interne afhængighed med et indeks, dette vil gemme I/O-operationer.
  Hvis den interne afhængighed ikke passer helt ind i hukommelsen, kan du bruge en anden algoritme, der bruger disk mere økonomisk.

  • I stedet for at læse begge afhængigheder linje for linje, læses de i grupper af linjer (bund), hvor en gruppe fra hver afhængighed gemmes i hukommelsen.
  • Strenge fra disse grupper sammenlignes med hinanden, og de fundne matches gemmes separat.
  • Derefter indlæses nye grupper i hukommelsen og sammenlignes også med hinanden.
  Og så videre, indtil grupperne løber tør.

  Algoritme eksempel:

  // forbedret version for at reducere disk I/O. nested_loop_join_v2(fil ydre, fil indre) for hver bundt ba i ydre // ba er nu i hukommelsen for hver bundt bb i indre // bb er nu i hukommelsen for hver række a i ba for hver række b i bb if (match_join_condition( a,b)) write_result_in_output(a,b) ende hvis ende for ende for ende for ende for
  I I dette tilfælde Tidskompleksiteten forbliver den samme, men antallet af diskadgange falder: (antal eksterne grupper + antal eksterne grupper * antal interne grupper). Efterhånden som gruppestørrelsen øges, falder antallet af diskadgange endnu mere.

  Bemærk: i denne algoritme læses flere data ved hver adgang, men det betyder ikke noget, da adgangene er sekventielle.

• Hash join. Dette er en mere kompleks operation, men i mange tilfælde er omkostningerne lavere.

  

  Algoritmen er som følger:

  1. Alle elementer fra den interne afhængighed læses.
  2. En hash-tabel oprettes i hukommelsen.
  3. Alle elementer fra den eksterne afhængighed læses én efter én.
  4. For hvert element beregnes en hash (ved hjælp af den tilsvarende funktion fra hash-tabellen), så den tilsvarende blok i den interne afhængighed kan findes.
  5. Elementer fra blokken sammenlignes med elementer fra den eksterne afhængighed.
  For at evaluere denne algoritme med hensyn til tidskompleksitet skal der foretages flere antagelser:
  • Den interne afhængighed indeholder X blokke.
  • Hash-funktionen fordeler hasherne næsten ligeligt for begge afhængigheder. Det vil sige, at alle blokke har samme størrelse.
  • Omkostningerne ved at finde et match mellem elementer af en ekstern afhængighed og alle elementer inde i en blok er lig med antallet af elementer inde i blokken.
  Så vil tidskompleksiteten være lig med:

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

  Og hvis hash-funktionen skaber små nok blokke, så vil tidskompleksiteten være O(M + N).

  Der er en anden hash join-metode, der er mere hukommelseseffektiv og ikke kræver flere I/O-operationer:

  1. Hash-tabeller beregnes for begge afhængigheder.
  2. Placeret på disk.
  3. Og så sammenlignes de trin for trin med hinanden (en blok indlæses i hukommelsen, og den anden læses linje for linje).
  Forening ved sammenlægning. Dette er den eneste flettemetode, der resulterer i sorterede data. I denne artikel betragter vi et forenklet tilfælde, hvor afhængigheder ikke er opdelt i eksterne og interne, da de opfører sig ens. Men i det virkelige liv kan de afvige, f.eks. når du arbejder med dubletter.

  Sammenlægningsoperationen kan opdeles i to faser:

  1. (Valgfrit) udføres først en sorteringssammenføjning, hvor begge sæt inputdata sorteres efter sammenkædningstasterne.
  2. Så sker fusionen.
  Sortering

  Fletningssorteringsalgoritmen er allerede blevet diskuteret ovenfor; i dette tilfælde er det ret berettiget, hvis det er vigtigt for dig at gemme hukommelse.

  Men det sker, at datasæt ankommer allerede sorteret, for eksempel:

  • Hvis bordet er organiseret indbygget.
  • Hvis afhængigheden er et indeks med en joinbetingelse til stede.
  • Hvis sammenslutningen sker med et mellemsorteret resultat.
  Konsolidering ved fusion

  

  Denne operation minder meget om fletteoperationen i flettesortering. Men i stedet for at vælge alle elementer i begge afhængigheder, vælger vi kun lige store elementer.

  1. De to nuværende elementer i begge afhængigheder sammenlignes.
  2. Hvis de er ens, så indtastes de i den resulterende tabel, og derefter sammenlignes de næste to elementer, en fra hver afhængighed.
  3. Hvis de ikke er ens, så gentages sammenligningen, men i stedet for det mindste af de to elementer, tages det næste element fra samme afhængighed, da sandsynligheden for en tilfældighed i dette tilfælde er højere.
  4. Trin 1-3 gentages, indtil elementerne i en af ​​afhængighederne løber tør.
  Hvis begge afhængigheder allerede er sorteret, så er tidskompleksiteten O(N + M).

  Hvis begge afhængigheder stadig skal sorteres, så er tidskompleksiteten O(N * Log(N) + M * Log(M)).

  Denne algoritme fungerer godt, fordi begge afhængigheder allerede er sorteret, og vi behøver ikke at gå frem og tilbage mellem dem. Der er dog en vis forenkling her: Algoritmen håndterer ikke situationer, hvor de samme data forekommer flere gange, det vil sige når der forekommer flere matches. I virkeligheden bruges en mere kompleks version af algoritmen. For eksempel:

  MergeJoin(relation a, relation b) relation output heltal a_key:=0; heltal b_key:=0; mens (a!=nul og b!=nul) hvis (a< b) a_key++; else if (a >b) b_tast++; else //Join predicate satisfied write_result_in_output(a,b) //Vi skal være forsigtige, når vi øger pointers heltal a_key_temp:=a_key; heltal b_key_temp:=b_key; hvis (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; ende hvis ende mens

Hvilken algoritme skal man vælge?

Hvis der var den bedste måde at kombinere, så ville alle disse varianter ikke eksistere. Så svaret på dette spørgsmål afhænger af en række faktorer:

• Mængden af ​​tilgængelig hukommelse. Hvis det ikke er nok, så glem alt om en kraftfuld hash-join. I det mindste er dens udførelse helt i hukommelsen.
• Størrelsen af ​​de to inputdatasæt. Hvis du har en tabel, der er stor, og den anden meget lille, så vil en joinforbindelse ved hjælp af indlejrede loops fungere hurtigst, fordi en hash-join involverer en dyr procedure til at oprette hashes. Hvis du har to meget store tabeller, vil tilslutning ved hjælp af indlejrede sløjfer forbruge alle CPU-ressourcerne.
• Tilgængelighed af indekser. Hvis du har to B-træ-indekser, er det bedre at bruge en flette-join.
• Skal jeg sortere resultaterne? Det kan være en god ide at bruge en dyr sammenføjning (med sortering), hvis du arbejder med usorterede datasæt. Så ved udgangen vil du modtage sorterede data, som er mere praktisk at kombinere med resultaterne af en anden fagforening. Eller fordi forespørgslen implicit eller eksplicit forventer at modtage data sorteret efter ORDER BY/GROUP BY/DISTINCT operatorer.
• Er outputafhængigheder sorteret?. I dette tilfælde er det bedre at bruge en flettesammenføjning.
• Hvilke typer afhængigheder bruger du?. Deltage efter ækvivalens (tabelA.kolonne1 = tabelB.kolonne2)? Interne afhængigheder, eksterne afhængigheder, kartesisk produkt eller selvtilslutning? I forskellige situationer virker nogle flettemetoder ikke.
• Data distribution. Hvis dataene afvises af join-betingelsen (f.eks. slutter du dig til personer med efternavn, men der er ofte navnebrødre), så bør en hash-join aldrig bruges. Ellers vil hash-funktionen skabe buckets med meget dårlig intern fordeling.
• Er det nødvendigt at flette ind i flere processer/tråde?

De, der er sultne efter viden, kan dykke ned i dokumentationen til DB2, ORACLE og SQL Server.

4.4.4. Forenklede eksempler

Lad os sige, at vi skal samle fem borde for at få et komplet billede af bestemte personer. Hver person kan have:

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

Det vil sige, du skal hurtigt besvare denne anmodning:

VÆLG * fra PERSON, MOBILES, MAILS,ADRESSER, 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_COUNT_IDS = BANK.PERSON_COUNT_IDS.
Optimizeren skal finde bedste måde databehandling. Men der er to problemer:

1. Hvilken sammenføjningsmetode skal jeg bruge? Der er tre muligheder (hash join, merge join, nestet loop join), med mulighed for at bruge 0, 1 eller 2 indekser. For ikke at nævne, at indekserne også kan være forskellige.
2. I hvilken rækkefølge skal fusionen udføres?

Nedenfor er for eksempel mulige planer for tre sammenføjninger af fire borde:

Baseret på det beskrevne, hvad er dine muligheder?

1. Brug en brute force tilgang. Ved hjælp af statistik beregnes prisen for hver af de mulige forespørgselsudførelsesplaner, og vælg den billigste. Men der er rigtig mange muligheder. For hver joinordre kan der anvendes tre forskellige joinmetoder, til i alt 34=81 mulige udførelsesplaner. I tilfælde af et binært træ bliver problemet med at vælge join-rækkefølgen et permutationsproblem, og antallet af muligheder er (2 * 4)! / (4 + 1)!.. Som et resultat, i dette meget forenklede eksempel, er det samlede antal mulige forespørgselsudførelsesplaner 34 * (2 * 4)! / (4 + 1)! = 27 216. Hvis vi tilføjer valgmulighederne, hvor en sammenføjning bruger 0, 1 eller 2 B-træ-indekser, stiger antallet af mulige planer til 210.000. Fik vi nævnt, at dette er en MEGET ENKEL forespørgsel?
2. Græd og hold op. Meget fristende, men uproduktivt, og du har brug for penge.
3. Prøv flere planer og vælg den billigste. Bare beregn prisen for alle mulige muligheder det virker ikke, du kan tage en vilkårlig test sæt data og køre alle typer planer på det for at estimere deres omkostninger og vælge den bedste.
4. Anvend smarte regler for at reducere antallet af mulige planer.
   Der er to typer regler:
   1. "Logiske", ved hjælp af hvilke du kan eliminere ubrugelige muligheder. Men de er ikke altid anvendelige. For eksempel, "Når du forbinder med indlejrede sløjfer, skal den indre afhængighed være det mindste sæt data."
   2. Du behøver ikke lede efter den mest rentable løsning og anvende strengere regler for at reducere antallet af mulige planer. Sig, "hvis afhængigheden er lille, skal du bruge indlejrede loop joins, men aldrig flette join eller hash join."

Selv et så simpelt eksempel efterlader os med et stort valg. Og i reelle forespørgsler kan der være andre relationelle operatorer: YDRE JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT osv. Det vil sige, at antallet af mulige udførelsesplaner bliver endnu større.

Så hvordan træffer databasen valget?

4.4.5. Dynamisk programmering, grådig algoritme og heuristik

En relationel database bruger forskellige tilgange, som blev nævnt ovenfor. Og optimizerens opgave er at finde en passende løsning inden for en begrænset tid. I de fleste tilfælde leder optimizeren ikke efter den bedste løsning, men blot en god løsning.

Brute force kan være velegnet til små anmodninger. Og med måder at eliminere unødvendig beregning på, kan selv moderate forespørgsler bruge brute force. Dette kaldes dynamisk programmering.

Kernen i det er, at mange udførelsesplaner er meget ens.

I denne illustration bruger alle fire planer undertræ A JOIN B. I stedet for at beregne omkostningerne for hver plan, kan vi beregne det én gang og derefter bruge disse data, så længe det er nødvendigt. Med andre ord, ved hjælp af memoization løser vi overlapningsproblemet, det vil sige, at vi undgår unødvendige beregninger.

Takket være denne tilgang, i stedet for tidskompleksitet (2*N)!/(N+1)! vi får "kun" 3 N. I det foregående eksempel med fire joinforbindelser betyder det at reducere antallet af muligheder fra 336 til 81. Hvis vi tager en forespørgsel med 8 joins (ikke stor anmodning), så vil sværhedsgradsfaldet være fra 57.657.600 til 6.561.

Hvis du allerede er fortrolig med dynamisk programmering eller algoritmisering, kan du lege med denne algoritme:

Procedure findbedsteplan(S) if (bedsteplan[S].pris uendelig) returner bedsteplan[S] // ellers er bedsteplan[S] ikke blevet beregnet tidligere, beregne den nu hvis (S indeholder kun 1 relation) sæt bedsteplan[S]. plan og bedsteplan[S].pris baseret på den bedste måde at få adgang til S /* Brug af valg på S og indekser på S */ andet for hver ikke-tom delmængde S1 af S, således at S1 != S P1= findbedsteplan(S1) P2= findbedsteplan(S - S1) A = bedste algoritme til at forbinde resultaterne af P1 og P2 omkostninger = P1.cost + P2.cost + cost of A if cost< 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 bruges til større forespørgsler, men der skal indføres yderligere regler (heuristik) for at reducere antallet af mulige planer:


Grådige algoritmer

Men hvis anmodningen er meget stor, eller hvis vi skal have et svar ekstremt hurtigt, bruges en anden klasse af algoritmer - grådige algoritmer.

I dette tilfælde bygges forespørgselsudførelsesplanen trin for trin ved hjælp af en bestemt regel (heuristik). Takket være ham søger den grådige algoritme bedste løsning for hver etape separat. Planen starter med en JOIN-erklæring og derefter ved hvert trin tilføjes en ny JOIN i henhold til reglen.

Lad os se på et simpelt eksempel. Lad os tage en forespørgsel med 4 joins af 5 tabeller (A, B, C, D og E). Lad os forenkle problemet lidt og forestille os, at den eneste mulighed er at kombinere ved hjælp af indlejrede algoritmer. Vi vil bruge reglen "brug sammenføjningen med de mindste omkostninger."

• Vi starter med en af ​​tabellerne, for eksempel A.
• Vi beregner omkostningerne ved hver fagforening med A (det vil være både en ekstern og en intern afhængighed).
• Vi oplever, at A JOIN B vil koste os billigst.
• Derefter beregner vi prisen på hver sammenføjning med resultatet A JOIN B (vi betragter det også i to roller).
• Vi finder, at den mest rentable mulighed vil være (A JOIN B) JOIN C.
• Igen vurderer vi mulige muligheder.
• Til sidst får vi følgende plan for udførelse af forespørgsler: (((A JOIN B) JOIN C) JOIN D) JOIN E)/

Den samme algoritme kan anvendes til at evaluere muligheder begyndende med tabel B, derefter C osv. Som et resultat får vi fem planer, hvorfra vi vælger den billigste.

Denne algoritme kaldes "nærmeste nabo-algoritmen".

Vi vil ikke gå i detaljer, men god modellering sorteringskompleksitet N*log(N) dette problem kan være . Algoritmens tidskompleksitet er O(N*log(N)) i stedet for O(3 N) for den fulde version med dynamisk programmering. Hvis du har en stor forespørgsel med 20 joins, vil det være 26 mod 3.486.784.401. En stor forskel, højre?

Men der er en nuance. Vi antager, at hvis vi finder den bedste måde at forbinde to tabeller på, vil vi få den laveste pris, når vi samler resultatet af tidligere sammenføjninger med de følgende tabeller. Men selvom A JOIN B er den billigste løsning, så kan (A JOIN C) JOIN B have en lavere pris end (A JOIN B) JOIN C.

Så hvis du har desperat brug for at finde det meste billig plan af alle tider og folk, så er det tilrådeligt at gentagne gange køre grådige algoritmer ved hjælp af forskellige regler.

Andre algoritmer

Hvis du allerede er træt af alle disse algoritmer, kan du springe dette kapitel over. Det er ikke nødvendigt at mestre resten af ​​materialet.

Mange forskere arbejder på problemet med at finde den bedste plan for udførelse af forespørgsler. De forsøger ofte at finde løsninger på specifikke problemer og mønstre. For eksempel til stjernesammenføjninger, parallel forespørgselsudførelse osv.

Der søges efter muligheder for at erstatte dynamisk programmering til udførelse af store forespørgsler. De samme grådige algoritmer er en delmængde af heuristiske algoritmer. De handler efter en regel, husker resultatet af et trin og bruger det til at søge bedste mulighed til næste etape. Og algoritmer, der ikke altid bruger den løsning, der blev fundet for det foregående trin, kaldes heuristiske.

Et eksempel er genetiske algoritmer:

• Hver løsning repræsenterer en plan for den fuldstændige eksekvering af anmodningen.
• I stedet for én løsning (plan) genererer algoritmen X løsninger på hvert trin.
• Først oprettes X-planer, dette gøres tilfældigt.
• Af disse gemmes kun de planer, hvis værdi opfylder et bestemt kriterium.
• Disse planer blandes derefter for at skabe X nye planer.
• Nogle af de nye planer ændres tilfældigt.
• De foregående tre trin gentages Y gange.
• Fra planerne fra den sidste cyklus får vi den bedste.

Jo flere cyklusser, jo billigere kan planen beregnes. Naturlig udvælgelse, konsolidering af egenskaber, det er alt.
I øvrigt er genetiske algoritmer integreret i PostgreSQL.

Databasen bruger også heuristiske algoritmer såsom simuleret annealing, iterativ forbedring og to-faset optimering. Men det er ikke et faktum, at de bruges i virksomhedssystemer, måske er deres skæbne forskningsprodukter.

4.4.6. Rigtige optimizere

Også et valgfrit kapitel, du kan springe det over.

Lad os gå væk fra teoretisering og se på virkelige eksempler. For eksempel hvordan SQLite optimizer fungerer. Dette er en "letvægts" database, der bruger simpel optimering baseret på en grådig algoritme med yderligere regler:

• SQLite ændrer aldrig rækkefølgen af ​​tabeller i en CROSS JOIN-operation.
• Forening ved hjælp af indlejrede løkker anvendes.
• Ydre sammenføjninger vurderes altid i den rækkefølge, de blev udført.
• Op til version 3.8.0 bruges den grådige Nearest Neighbor-algoritme til at finde den bedste plan for udførelse af forespørgsler. Og siden version 3.8.0 bruges "N nærmeste naboer" (N3, N nærmeste naboer).

Her er endnu et eksempel. Hvis vi læser IBM DB2-dokumentationen, finder vi ud af, at dens optimizer bruges 7 forskellige niveauer optimeringer:

• Grådige algoritmer:
  • 0 - minimal optimering. Bruger indeksscanning, indlejrede loop joins og undgår at omskrive nogle forespørgsler.
  • 1 - lav optimering
  • 2 - fuld optimering
• Dynamisk programmering:
  • 3 - medium optimering og grov tilnærmelse
  • 5 - fuld optimering, alle heuristiske teknikker bruges
  • 7 - det samme, men uden heuristik
  • 9 - maksimal optimering for enhver pris, uden hensyntagen til den brugte indsats. Alle bliver vurderet mulige måder fagforeninger, herunder kartesiske produkter.

Standardniveauet er 5. Dette inkluderer:

• Indsamling af al mulig statistik, herunder frekvensfordelinger og kvantiler.
• Anvendelse af alle regler for omskrivning af forespørgsler, herunder oprettelse af en tabelrute for materialiserede forespørgsler). Undtagelsen er regler, der kræver intensive beregninger og anvendes i et meget begrænset antal sager.
• Når du gentager sammenkoblingsmuligheder ved hjælp af dynamisk programmering:
  • Der er begrænset brug af sammensat intern afhængighed.
  • Til stjernekredsløb med opslagstabeller anvendes i begrænset omfang kartesiske produkter.
• Under overvejelse bredt udvalg adgangsmetoder, herunder listeforhåndshentning (mere om dette nedenfor), speciel ANDing af indekser og tabelrouting for materialiserede forespørgsler.

Udviklerne deler selvfølgelig ikke detaljer om heuristikken, der bruges i deres produkt, fordi optimeringsværktøjet er måske den vigtigste del af databasen. Det er dog kendt, at dynamisk programmering, begrænset af heuristik, som standard bruges til at bestemme sammenføjningsrækkefølgen.

Øvrige forhold (GROUP BY, DISTINCT, etc.) behandles efter simple regler.

4.4.7. Forespørge plan cache

Fordi det tager tid at bygge en plan, gemmer de fleste databaser planen i en forespørgselsplan-cache. Dette hjælper med at undgå unødvendige beregninger af de samme trin. Databasen skal vide præcis, hvornår den skal opdatere forældede planer. Til dette sættes en vis tærskel, og hvis ændringer i statistik overskrider den, fjernes planen relateret til denne tabel fra cachen.

Request Executor

På på dette tidspunkt vores plan er allerede blevet optimeret. Det er rekompileret til eksekverbar kode og, hvis der er nok ressourcer, eksekveret. De operatører, der er indeholdt i planen (JOIN, SORT BY, etc.) kan behandles enten sekventielt eller parallelt; beslutningen træffes af eksekveren. Den interagerer med dataadministratoren for at modtage og skrive data.

5. Datamanager

Forespørgselsmanageren udfører forespørgslen og har brug for data fra tabeller og indekser. Den anmoder om dem fra dataadministratoren, men der er to problemer:

• Relationelle databaser bruger en transaktionsmodel. Det er umuligt at få de ønskede data på et bestemt tidspunkt, fordi de på nuværende tidspunkt kan bruges/modificeres af nogen.
• Datahentning er den langsomste operation i en database. Derfor skal dataadministratoren være i stand til at forudsige sit arbejde for at fylde hukommelsesbufferen rettidigt.

5.1. Cache Manager

Som det er blevet sagt mere end én gang, er flaskehalsen i databasen diskundersystemet. Derfor bruges en cache-manager til at forbedre ydeevnen.

I stedet for at modtage data direkte fra filsystem, kontakter anmodningsudøveren cache-manageren for dem. Den bruger en bufferpulje indeholdt i hukommelsen, som radikalt kan øge databasens ydeevne. Det er svært at sætte et tal på dette, fordi meget afhænger af, hvad du har brug for:

• Sekventiel adgang (fuld scanning) eller tilfældig (adgang via række-id).
• Læs eller skriv.

Også af stor betydning er typen af ​​drev, der anvendes i disk system: "Winchesters" med ved forskellige hastigheder spindelrotation, SSD, RAID i forskellige konfigurationer. Men vi kan sige, at hukommelsesforbruget er 100-100.000 gange hurtigere end diskforbruget.

Men her står vi med et andet problem. Cache-manageren skal lægge dataene ind i hukommelsen, FØR forespørgselseksekutoren har brug for det. Ellers bliver han nødt til at vente på, at de bliver modtaget fra den langsomme disk.

5.1.1. Forkøbsret

Forespørgselsudøveren ved, hvilke data den skal bruge, fordi den kender hele planen, hvilke data der er på disken og statistik.

Når eksekveren behandler den første chunk af data, beder den cache-manageren om at forudindlæse den næste chunk. Og når den begynder at behandle den, beder den DC om at indlæse den tredje og bekræfter, at den første del kan slettes fra cachen.

Cache-manageren gemmer disse data i en bufferpulje. Det tilføjer også serviceoplysninger (trigger, lås) til dem for at vide, om de stadig er nødvendige i bufferen.

Nogle gange ved kunstneren ikke, hvilke data han skal bruge, eller nogle databaser har ikke en sådan funktionalitet. Derefter bruges spekulativ præfetching (hvis f.eks. eksekveren anmoder om data 1, 3, 5, så vil han sandsynligvis anmode om 7, 9, 11 i fremtiden) eller sekventiel prefetching (i dette tilfælde indlæser DC blot den næste fra disk bestille et stykke data.

Vi må ikke glemme, at bufferen er begrænset af mængden af ​​tilgængelig hukommelse. Det vil sige, at for at indlæse nogle data skal vi med jævne mellemrum slette andre. Fyldning og rydning af cachen bruger en del af diskens undersystem og netværksressourcer. Hvis du har en forespørgsel, der kører ofte, ville det være kontraproduktivt at indlæse og rydde op i de data, den bruger hver gang. For at løse dette problem bruger moderne databaser en buffererstatningsstrategi.

5.1.2. Bufferudskiftningsstrategier

De fleste databaser (mindst SQL Server, MySQL, Oracle og DB2) bruger LRU algoritme(Sidst brugt). Den er designet til at vedligeholde data i den cache, der for nylig er blevet brugt, hvilket betyder, at der er stor sandsynlighed for, at det kan blive nødvendigt igen.

For at gøre det lettere at forstå, hvordan algoritmen fungerer, vil vi antage, at dataene i bufferen ikke er blokeret af triggere (latch), og derfor kan slettes. I vores eksempel kan bufferen gemme tre stykker data:

1. Cache-manageren bruger data 1 og lægger dem i en tom buffer.
2. Det bruger derefter data 4 og sender det også til bufferen.
3. Det samme gøres med data 3.
4. Derefter tages data 9. Men bufferen er allerede fuld. Derfor fjernes data 1 fra den, da den har været ubrugt i længst tid. Herefter placeres data 9 i bufferen.
5. Cache-manageren bruger igen data 4. Den er allerede i bufferen, så den er markeret som sidst brugt.
6. Data 1 bliver igen efterspurgt. For at placere den i bufferen slettes data 3 fra den, da den ikke har været brugt i længst tid.

Det her god algoritme, men det har nogle begrænsninger. Hvad hvis vi laver en fuld scanning af et stort bord? Hvad sker der, hvis tabel-/indeksstørrelsen overstiger bufferstørrelsen? I dette tilfælde vil algoritmen fjerne alt dens indhold fra cachen, så de fulde scanningsdata vil højst sandsynligt kun blive brugt én gang.

Algoritmeforbedringer

For at forhindre dette i at ske, bruger nogle databaser særlige regler. Ifølge Oracle dokumentation:

"For meget store tabeller bruges der typisk direkte adgang, hvilket betyder, at datablokke læses direkte for at undgå cachebufferoverløb. For mellemstore tabeller kan både direkte adgang og cache-læsninger bruges. Hvis systemet beslutter at bruge cachen, placerer databasen datablokkene i slutningen af ​​LRU-listen for at forhindre buffertømning."

En forbedret version af LRU, LRU-K, bruges også. SQL Server bruger LRU-K med K = 2. Essensen af ​​denne algoritme er, at når den vurderer situationen, tager den hensyn til flere oplysninger om tidligere operationer, og husker ikke kun de sidst anvendte data. Bogstavet K i navnet betyder, at algoritmen tager højde for, hvilke data der er brugt de sidste K gange. De tillægges en vis vægt. Når nye data indlæses i cachen, slettes gamle, men ofte brugte data ikke, fordi deres vægt er højere. Hvis dataene ikke længere bruges, vil de selvfølgelig stadig blive slettet. Og jo længere dataene forbliver uopkrævet, jo mere falder dens vægt over tid.

At beregne vægten er ret dyrt, så SQL Server bruger LRU-K med K lig med kun 2. Da værdien af ​​K stiger lidt, forbedres effektiviteten af ​​algoritmen. Du kan lære ham bedre at kende takket være.

Andre algoritmer

Selvfølgelig er LRU-K ikke den eneste løsning. Der er også 2Q og CLOCK (begge ligner LRU-K), MRU (Most Recently Used, som bruger LRU-logik, men anvender en anden regel, LRFU (Last Recently and Frequently Used) osv. I nogle databaser kan du vælge, hvad algoritme vil blive brugt.

5.1.3. Skriv buffer

Vi talte kun om læsebufferen, men databaser bruger også skrivebuffere, som akkumulerer data og skyller dem til disken i portioner i stedet for sekventiel skrivning. Dette sparer I/O-operationer.
Husk at buffere gemmer sider(udelelige dataenheder), i stedet for rækker fra tabeller. En side i bufferpuljen siges at være beskidt, hvis den er ændret, men ikke skrevet til disken. Der er mange forskellige algoritmer, der bruges til at vælge skrivetiden for beskidte sider. Men det har meget at gøre med begrebet transaktioner.

5.2. Transaktionsleder

Hans ansvar er at sikre, at hver anmodning udføres ved hjælp af sin egen transaktion. Men før vi taler om afsenderen, lad os præcisere begrebet ACID-transaktioner.

5.2.1. "On Acid" (spil med ord, hvis nogen ikke forstår)

En ACID-transaktion (Atomicitet, Isolation, Holdbarhed, Konsistens) er en elementær operation, en arbejdsenhed, der opfylder 4 betingelser:

• Atomicitet. Der er intet "mindre" end en transaktion, ingen mindre operation. Også selvom transaktionen varer 10 timer. Hvis en transaktion mislykkes, vender systemet tilbage til "før"-tilstanden, det vil sige, at transaktionen rulles tilbage.
• Isolation. Hvis to transaktioner A og B udføres på samme tid, bør deres udfald ikke afhænge af, om den ene af dem blev gennemført før, under eller efter udførelsen af ​​den anden.
• Holdbarhed. Når en transaktion er begået, det vil sige vellykket gennemført, forbliver de data, den brugte, i databasen, uanset mulige hændelser (fejl, nedbrud).
• Konsistens. Kun gyldige data registreres i databasen (ud fra et relationelt og funktionelle forbindelser). Konsistens afhænger af atomicitet og isolation.

Under udførelsen af ​​enhver transaktion kan du udføre forskellige SQL-forespørgsler for at læse, oprette, opdatere og slette data. Problemer starter, når to transaktioner bruger de samme data. Klassisk eksempel- overførsel af penge fra konto A til konto B. Lad os sige, at vi har to transaktioner:

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

Lad os nu se på denne situation fra synspunktet om ACID-egenskaber:

• Atomicitet giver dig mulighed for at være sikker på, at uanset hvilken hændelse der opstår under T1 (servernedbrud, netværksfejl), kan det ikke ske, at $100 bliver debiteret fra A, men ikke kommer til B (ellers taler de om en "inkonsekvent tilstand").
• Isolation siger, at selvom T1 og T2 udføres samtidigt, vil der som følge heraf blive debiteret $100 fra A, og det samme beløb vil gå til B. I alle andre tilfælde taler de igen om en inkonsistent tilstand.
• Pålidelighed giver dig mulighed for ikke at bekymre dig om, at T1 forsvinder, hvis databasen går ned umiddelbart efter, at T1 er blevet begået.
• Konsistens forhindrer muligheden for, at penge bliver skabt eller ødelagt i systemet.

Du behøver ikke læse nedenfor, det er ikke længere vigtigt for at forstå resten af ​​materialet.

Mange databaser giver ikke fuld isolation som standard, da dette medfører en enorm ydeevne. SQL bruger 4 isolationsniveauer:

• Serialiserbare transaktioner. Det højeste niveau af isolation. Standard i SQLite. Hver transaktion udføres i sit eget, fuldstændigt isolerede miljø.
• Gentagelig læsning. Standard i MySQL. Hver transaktion har sit eget miljø, bortset fra én situation: hvis transaktionen tilføjer nye data og fuldføres med succes, vil de være synlige for andre transaktioner, der stadig er i gang. Men hvis transaktionen ændrer data og fuldføres med succes, vil disse ændringer ikke være synlige for transaktioner, der stadig er i gang. Det vil sige, at for nye data er princippet om isolation overtrådt.

  For eksempel udføres transaktion A

  VÆLG antal(1) fra TABLE_X
  Så tilføjer transaktion B tabel X og begår nye data. Og hvis A efter denne transaktion udfører count(1) igen, så vil resultatet være anderledes.

  Dette kaldes fantomlæsning.

• Læs forpligtede data. Anvendes som standard i Oracle, PostgreSQL og SQL Server. Dette er det samme som gentagen læsning, men med yderligere krænkelse af isolation. Lad os sige, at transaktion A læser data; de bliver derefter ændret eller slettet af transaktion B, som begår disse handlinger. Hvis A læser disse data igen, vil hun se ændringerne (eller sletningen) foretaget af B.

  Dette kaldes ikke-gentagelig læsning.

• Læs uforpligtende data. Laveste niveau af isolation. En ny isolationsovertrædelse føjes til læsningen af ​​de forpligtede data. Lad os sige, at transaktion A læser data; derefter modificeres de af transaktion B (ændringerne er ikke begået, B udfører stadig). Hvis A læser dataene igen, vil han se ændringerne. Hvis B rulles tilbage, vil A, når den læses igen, ikke se nogen ændringer, som om intet var hændt.

  Dette kaldes beskidt læsning.

De fleste databaser tilføjer deres egne niveauer af isolation (f.eks. baseret på snapshots, som i PostgreSQL, Oracle og SQL Server). Desuden implementerer mange databaser ikke alle fire niveauer beskrevet ovenfor, især læsning af ikke-forpligtede data.

Brugeren eller udvikleren kan tilsidesætte standardisolationsniveauet umiddelbart efter, at forbindelsen er etableret. Alt du skal gøre er at tilføje en meget simpel kodelinje.

5.2.2. Samtidighedskontrol

Det vigtigste, vi har brug for isolation, konsistens og atomicitet til, er evnen til at udføre skriveoperationer på de samme data (tilføj, opdater og slet).

Hvis alle transaktioner kun læser data, kan de arbejde samtidigt uden at påvirke andre transaktioner.
Hvis mindst én transaktion ændrer data læst af andre transaktioner, skal databasen finde en måde at skjule disse ændringer for dem. Du skal også sikre dig, at de foretagne ændringer ikke bliver slettet af andre transaktioner, der ikke kan se de ændrede data.

Dette kaldes samtidighedskontrol.

Den nemmeste måde er blot at udføre transaktioner én efter én. Men denne tilgang er normalt ineffektiv (kun én kerne af én processor bruges), og evnen til at skalere går også tabt.

Den ideelle måde at løse problemet på ser sådan ud (hver gang en transaktion oprettes eller annulleres):

• Overvåg alle operationer af hver transaktion.
• Hvis to eller flere transaktioner er i konflikt på grund af læsning/ændring af de samme data, skal du ændre rækkefølgen af ​​operationer inden for parterne i konflikten for at minimere antallet af årsager.
• Udfør modstridende dele af transaktioner i en bestemt rækkefølge. Ikke-modstridende transaktioner udføres parallelt på dette tidspunkt.
• Vær opmærksom på, at transaktioner kan blive annulleret.

Hvis vi griber spørgsmålet mere formelt an, så er dette et problem med at planlægge konflikter. At løse det er meget vanskeligt, og optimering kræver store processorressourcer. Virksomhedsdatabaser har ikke råd til at bruge timer på at søge bedste tidsplan for hver ny transaktion. Derfor anvendes mindre sofistikerede tilgange, hvor der bruges mere tid på konflikter.

5.2.3. Låsemanager

For at løse problemet beskrevet ovenfor bruger mange databaser låse og/eller dataversionering.
Hvis en transaktion har brug for nogle data, blokerer den dem. Hvis en anden transaktion også krævede dem, så skal den vente, indtil den første transaktion frigiver låsen.

Dette kaldes en eksklusiv lås.

Men det er for spild at bruge eksklusive låse i tilfælde, hvor transaktioner kun skal læse data. Hvorfor forstyrre datalæsningen? I sådanne tilfælde bruges fælles låse. Hvis en transaktion skal læse data, anvender den en delt lås på den og læser den. Dette forhindrer ikke andre transaktioner i også at dele låse og læse dataene. Hvis en af ​​dem skal ændre data, så må hun vente, indtil alle ledlåse er udløst. Først da vil hun være i stand til at anvende en eksklusiv lås. Og så skal alle andre transaktioner vente på, at de bliver trukket tilbage for at kunne læse disse data.

En låsemanager er en proces, der anvender og frigiver låse. De er gemt i en hash-tabel (nøglerne er de data, der låses). Manageren ved for alle data, hvilke transaktioner der har anvendt låse eller venter på at de bliver frigivet.

dødvande

Brug af låse kan føre til en situation, hvor to transaktioner venter på ubestemt tid på, at låsene bliver frigivet:

Her har transaktion A udelukkende låst data 1 og venter på frigivelse af data 2. Samtidig har transaktion B udelukkende låst data 2 og venter på at data 1 bliver frigivet.

I en deadlock vælger afsenderen, hvilken transaktion der skal annulleres (rulle tilbage). Og beslutningen er ikke så let at tage:

• Ville det være bedre at dræbe den transaktion, der ændrede det sidste sæt data (og derfor ville tilbagerulning være den mindst smertefulde)?
• Ville det være bedre at dræbe den yngste transaktion, da brugere af andre transaktioner har ventet længere?
• Ville det være bedre at aflive en transaktion, der tager kortere tid at gennemføre?
• Hvor mange andre transaktioner vil blive påvirket af tilbagerulningen?

Men før der træffes en beslutning, skal afsenderen kontrollere, om der rent faktisk er opstået et dødvande.

Lad os forestille os en hash-tabel i form af et diagram, som i illustrationen ovenfor. Hvis der er en cyklisk sammenhæng i diagrammet, bekræftes dødvandet. Men da det er ret dyrt at tjekke for cyklusser (trods alt vil diagrammet, der viser alle låsene, være ret stort), bruges der ofte en enklere tilgang: brug af timeouts. Hvis låsen ikke frigives inden for en vis tid, er transaktionen gået i en deadlock-tilstand.

Inden du anvender en lås, kan afsenderen også kontrollere, om den vil forårsage dødvande. Men for at svare entydigt på dette skal du også bruge penge på beregninger. Derfor præsenteres sådanne forhåndskontroller ofte som et sæt grundlæggende regler.

To-faset blokering

Den nemmeste måde at opnå fuldstændig isolation på er, når en lås anvendes i begyndelsen og frigives i slutningen af ​​transaktionen. Det betyder, at en transaktion skal vente, indtil alle låse er frigivet, før de starter, og eventuelle låse, den har anvendt, frigives først efter afslutning. Denne fremgangsmåde kan bruges, men så spildes der en masse tid på at vente på, at alle låsene bliver udløst.

DB2 og SQL Server bruger en to-faset låseprotokol, som opdeler en transaktion i to faser:

• Vækstfase, når en transaktion kun kan anvende låse, men ikke frigive dem.
• Krympende fase, når en transaktion kun kan frigive låse (på data, der allerede er blevet behandlet og ikke vil blive behandlet igen), men ikke anvende nye.

En almindelig konflikt, der opstår i fravær af to-faset låsning, er:

Før transaktion A, X = 1 og Y = 1. Den behandler data Y = 1, som blev ændret af transaktion B, efter transaktion A startede. På grund af princippet om isolation skal transaktion A behandle Y = 2.

Mål opnået ved hjælp af disse to simple regler:

• Frigør låse, der ikke længere er nødvendige for at reducere ventetider for andre transaktioner.
• Undgå tilfælde, hvor en transaktion modtager data, der er ændret af en tidligere kørende transaktion. Sådanne data stemmer ikke overens med de ønskede data.

Denne protokol fungerer godt, bortset fra den situation, hvor transaktionen ændrede dataene og fjernede låsen fra den og derefter blev annulleret. I dette tilfælde kan en anden transaktion læse og ændre data, som derefter vil blive rullet tilbage. For at undgå denne situation skal alle eksklusive låse frigives efter gennemførelse af transaktionen.

Selvfølgelig bruger rigtige databaser mere komplekse systemer, flere typer låse og med større granularitet (låse på rækker, sider, partitioner, tabeller, tablespaces), men essensen er den samme.

Dataversionering

En anden måde at løse transaktionskonflikten på er at bruge dataversionering.

• Alle transaktioner kan ændre de samme data på samme tid.
• Hver transaktion fungerer med sin egen kopi (version) af dataene.
• Hvis to transaktioner ændrer de samme data, vil kun en af ​​ændringerne blive accepteret, den anden vil blive afvist, og den transaktion, der gjorde det, vil blive rullet tilbage (og muligvis genstartet).

Dette giver mulighed for øget produktivitet, fordi:

• Læsning af transaktioner blokerer ikke skrivetransaktioner og omvendt.
• Den klodsede låsemanager har ingen indflydelse.

Generelt vil alt være bedre end låse, medmindre to transaktioner skriver de samme data. Desuden kan dette føre til et enormt spild af diskplads.

Begge tilgange - låsning og versionering - har fordele og ulemper, meget afhænger af situationen, hvor de bruges (flere aflæsninger eller flere poster). Du kan studere en meget god præsentation om implementeringen af ​​multiversion samtidighedskontrol i PostgreSQL.

Nogle databaser (DB2 før version 9.7, SQL Server) bruger kun låse. Andre, som PostgreSQL, MySQL og Oracle, bruger kombinerede tilgange.

Bemærk: versionering har en interessant effekt på indekser. Nogle gange er der dubletter i et unikt indeks, indekset kan indeholde flere poster end rækker i tabellen osv.

Hvis en del af dataene læses på ét isolationsniveau, og så stiger det, så stiger antallet af låse, hvilket betyder, at der går mere tid tabt på at vente på transaktioner. Derfor bruger de fleste databaser ikke standarden maksimalt niveau isolation.

Som sædvanlig, for mere detaljeret information se dokumentation: MySQL, PostgreSQL, Oracle.

5.2.4. Log Manager

Som vi allerede ved, lagrer databasen en del af dataene i bufferhukommelsen for at øge ydeevnen. Men hvis serveren går ned under en transaktionsbekræftelse, vil dataene i hukommelsen gå tabt. Og dette overtræder princippet om transaktionspålidelighed.

Selvfølgelig kan du skrive alt til disk, men hvis det går ned vil du stå tilbage med uskrevne data, og det er en overtrædelse af atomicitetsprincippet.

Eventuelle ændringer skrevet af transaktionen skal rulles tilbage eller fuldføres.

Dette gøres på to måder:

• Skyggekopier/sider. Hver transaktion opretter sin egen kopi af databasen (eller en del af den) og arbejder med denne kopi. Hvis der opstår en fejl, slettes kopien. Hvis alt gik godt, skifter databasen øjeblikkeligt til dataene fra kopien ved hjælp af et trick på filsystemniveau og sletter derefter de "gamle" data.
• Transaktionslog. Dette er en speciel opbevaringsfacilitet. Før hver skrivning til disk, skriver databasen information til transaktionsloggen. Så i tilfælde af fejl, vil databasen vide, hvordan man sletter eller fuldfører den afventende transaktion.

WAL

I store databaser med talrige transaktioner optager skyggekopier/sider en utrolig stor mængde diskplads. Derfor bruger moderne databaser en transaktionslog. Den skal placeres i fejlsikker opbevaring.

De fleste produkter (især Oracle, SQL Server, DB2, PostgreSQL, MySQL og SQLite) arbejder med transaktionslogfiler via WAL-protokollen (Write-Ahead Logging). Denne protokol indeholder tre regler:

1. Hver ændring af databasen skal ledsages af en logindtastning, og den skal foretages, FØR dataene skrives til disken.
2. Indtastninger i loggen bør arrangeres i overensstemmelse med rækkefølgen af ​​de relevante begivenheder.
3. Når en transaktion er begået, skal en registrering af dette skrives til loggen, FØR transaktionen gennemføres.

Logmanageren overvåger implementeringen af ​​disse regler. Det er logisk placeret mellem cache-manageren og dataadgangsmanageren. Logmanageren logger hver operation, der udføres af transaktioner, indtil den skrives til disken. Synes det er rigtigt?

FORKERT! Efter alt, hvad vi har været igennem i denne artikel, er det tid til at huske, at alt relateret til databasen er underlagt "databaseeffektens" forbandelse. Seriøst, problemet er, at du skal finde en måde at skrive til loggen på, mens du bevarer en god ydeevne. Når alt kommer til alt, hvis transaktionsloggen er langsom, bremser den alle andre processer.

VÆDDER

I 1992 skabte forskere ved IBM en udvidet version af WAL, som de kaldte ARIES. I en eller anden form bruges ARIES af de fleste moderne databaser. Hvis du ønsker at studere denne protokol mere i dybden, kan du studere det tilsvarende arbejde.

Så ARIES står for EN algoritmer til R ecovery og jeg solation E xudnyttelse S mantik. Denne teknologi har to opgaver:

1. Giv god ydeevne, når du skriver logs.
2. Sikre hurtig og pålidelig genopretning.

Der er flere grunde til, at en database skal rulle en transaktion tilbage:

1. Brugeren har annulleret det.
2. Server- eller netværksfejl.
3. Transaktionen krænkede databasens integritet. For eksempel anvendte du betingelsen UNIQUE på en kolonne, og transaktionen tilføjede en dublet.
4. Tilstedeværelse af dødvande.

Men nogle gange kan databasen også gendanne en transaktion, for eksempel i tilfælde af en netværksfejl.

Hvordan er det muligt? For at besvare dette skal du først forstå, hvilke oplysninger der er gemt i loggen.

Logs
Hver operation (tilføj/sletning/ændring) under udførelsen af ​​en transaktion fører til fremkomsten af ​​en post i loggen. Indlægget indeholder:

• LSN (Log Sequence Number). Dette er et unikt nummer, hvis betydning er bestemt af kronologisk rækkefølge. Det vil sige, at hvis operation A fandt sted før operation B, vil LSN for A være mindre end LSN for B. I virkeligheden er metoden til at generere et LSN mere kompliceret, da den også er relateret til den måde, hvorpå loggen er lagret.
• TransID. ID for den transaktion, der udførte handlingen.
• Side-id. Det sted på disken, hvor de ændrede data er placeret.
• PrevLSN. Et link til en tidligere logpost oprettet af den samme transaktion.
• FORTRYD. En metode til at rulle en operation tilbage.

  For eksempel, hvis en opdateringsoperation blev udført, så skrives den tidligere værdi/tilstand for det ændrede element (fysisk FORTRYD) eller den omvendte handling, der giver dig mulighed for at vende tilbage til den tidligere tilstand (logisk FORTRYD), til FORTRYD. ARIES bruger kun logiske; at arbejde med fysiske er meget vanskeligt.

• GØR OM. Metode til at gentage operationen.

Derudover indeholder hver side på disken (til lagring af data, ikke logfiler) LSN for den sidste operation, der modificerede dataene der.

Så vidt vi ved, bruges UNDO ikke kun i PostgreSQL. I stedet bruges en skraldemand til at rydde op i gamle versioner af dataene. Dette skyldes implementeringen af ​​dataversionering i dette DBMS.

For at gøre det lettere for dig at forestille dig sammensætningen af ​​en logpost, er her et visuelt forenklet eksempel, hvor forespørgslen OPDATERING FRA PERSON INDSTILLET ALDER = 18; udføres. Lad det udføres i transaktion nummer 18:

Hver log har et unikt LSN. Sammenkædede logfiler refererer til den samme transaktion, og de er forbundet i kronologisk rækkefølge (den sidste log på listen refererer til den sidste operation).

Log buffer
For at forhindre logning i at blive en systemflaskehals, bruges en logbuffer.

Når forespørgselsløberen anmoder om ændrede data:

1. Cache-manageren gemmer dem i en buffer.
2. Logmanageren gemmer den tilsvarende log i sin egen buffer.
3. Forespørgselsudøveren afgør, om operationen er fuldført, og i overensstemmelse hermed, om de ændrede data kan anmodes om.
4. Logmanageren gemmer nødvendige oplysninger til transaktionsloggen. Tidspunktet for denne indtastning bestemmes af algoritmen.
5. Cache-manageren skriver ændringer til disken. Optagelsesøjeblikket indstilles også af algoritmen.

Når en transaktion forpligtes, betyder det, at alle trin 1 til 5 er blevet gennemført. Det er hurtigt at skrive til transaktionsloggen, fordi det repræsenterer "at tilføje loggen et sted til transaktionsloggen." Samtidig er skrivning af data til disk en mere kompleks procedure, idet man tager højde for, at data efterfølgende hurtigt skal læses.

STJÆL og FORCE politikker

For at forbedre ydeevnen skal trin nummer 5 udføres efter commit, da det i tilfælde af fejl stadig er muligt at gendanne transaktionen ved hjælp af REDO. Dette kaldes NO-FORCE-politikken.

Men databasen kan også vælge FORCE-politikken for at reducere belastningen under gendannelse. Derefter udføres trin nummer 5 før commit.

Databasen vælger også, om den skal skrive data til disken trinvist (STEAL-politik), eller, hvis buffermanageren skal vente på en commit, skrive det hele på én gang (NO-STEAL). Valget afhænger af, hvad du har brug for: hurtig optagelse med lang genopretning eller hurtig genopretning?

Hvordan de nævnte politikker påvirker gendannelsesprocessen:

• STEAL/NO-FORCE kræver FORTRYD og REDO. Højeste ydeevne, men mere kompleks struktur logfiler og gendannelsesprocesser (som ARES). De fleste databaser bruger denne kombination af politikker.
• For STJÆL/KRAFT behøver du kun FORTRYD.
• For NO-STEAL/NO-FORCE - kun GENTAG.
• Til NO-STEAL/FORCE behøver du ikke noget som helst. Ydelsen i dette tilfælde er den laveste, og den er påkrævet stor mængde hukommelse.

Genopretning

Så hvordan kan vi bruge vores fantastiske logfiler? Lad os antage, at en ny medarbejder har ødelagt databasen (regel #1: det er altid nybegynderens skyld!). Du genstarter den, og gendannelsesprocessen begynder.
ARIES genopretter i tre faser:

1. Analyse. Hele transaktionsloggen læses, så kronologien af ​​hændelser, der fandt sted under databasefaldet, kan gendannes. Dette hjælper med at bestemme, hvilken transaktion der skal rulles tilbage. Alle transaktioner uden en commit-ordre rulles tilbage. Systemet bestemmer også, hvilke data der skal være skrevet til disken under fejlen.
2. Gentage. REDO bruges til at opdatere databasen til tilstanden før nedbruddet. Dens logfiler behandles i kronologisk rækkefølge. For hver log læses LSN for siden på disken, der indeholder de data, der skal ændres.

   Hvis LSN(pages_on_disk)>=LSN(entries_in_log), så var dataene allerede skrevet til disken før fejlen. Men værdien blev overskrevet af en operation, der blev udført efter skrivning til loggen og før fejlen. Så der er faktisk ikke gjort noget.

   Hvis LSN(sider_på_disk)

   Genafspilningen udføres selv for transaktioner, der vil blive rullet tilbage, fordi det forenkler gendannelsesprocessen. Men moderne databaser gør det nok ikke.

3. Afbestille. På dette stadium rulles alle transaktioner, der ikke blev gennemført på tidspunktet for fejlen, tilbage. Processen starter med de seneste logfiler for hver transaktion og behandler UNDOs i omvendt kronologisk rækkefølge ved hjælp af PrevLSN.

Under gendannelsesprocessen skal transaktionsloggen være opmærksom på de handlinger, der udføres under gendannelsen. Dette er nødvendigt for at synkronisere de data, der er gemt på disken, med dem, der er registreret i transaktionsloggen. Det er muligt at slette transaktionsposter, der er rullet tilbage, men det er meget svært at gøre. I stedet laver ARIES kompenserende poster i transaktionsloggen, der logisk ugyldiggør indtastningerne af de tilbagerullede transaktioner.

Hvis transaktionen annulleres "manuelt", eller af en låseadministrator, eller på grund af en netværksfejl, er analysetrinnet ikke nødvendigt. Når alt kommer til alt er information om REDO og UNDO indeholdt i to tabeller placeret i hukommelsen:

• I transaktionstabellen (tilstandene for alle aktuelle transaktioner gemmes her).
• Tabellen med beskidte sider (denne indeholder information om, hvilke data der skal skrives til disken).

Så snart en ny transaktion vises, opdateres disse tabeller af cache-manageren og transaktionsmanageren. Og da tabellerne er gemt i hukommelsen, forsvinder de, hvis databasen går ned.

Analysefasen er nødvendig bare for at gendanne begge tabeller ved hjælp af information fra transaktionsloggen. For at fremskynde denne fase bruger ARIES checkpoints. Indholdet af begge tabeller, såvel som den seneste LSN i skrivende stund, skrives til disk fra tid til anden. Så under gendannelsen analyseres kun logfilerne efter denne LSN.

6. Konklusion

Som yderligere oversigtslæsning om databaser kan vi anbefale artiklen Arkitektur af et databasesystem. Dette er en god introduktion til emnet, skrevet i et ret tydeligt sprog.

Hvis du omhyggeligt læser alt ovenstående materiale, har du sandsynligvis en idé om, hvor store mulighederne i databaser er. Denne artikel behandler dog ikke andre vigtige spørgsmål:

• Sådan administrerer du klyngede databaser og globale transaktioner.
• Sådan får du et øjebliksbillede, hvis databasen fungerer.
• Hvordan man effektivt gemmer og komprimerer data.
• Sådan administrerer du hukommelse.

Så tænk dig om to gange, før du vælger mellem en buggy NoSQL og en solid relationel database. Misforstå mig ikke, nogle NoSQL-databaser er meget gode. Men de er stadig langt fra perfekte og kan kun hjælpe med at løse specifikke problemer forbundet med bestemte applikationer.

Så hvis nogen spørger dig, hvordan databaser fungerer, så i stedet for at give op og gå væk, kan du svare:

Tags: Tilføj tags

• Oversættelse

Oversætterens note: selvom artiklen er ret gammel (udgivet for 2 år siden) og har en høj titel, giver den stadig en god idé om forskellene mellem relationelle databaser og NoSQL-databaser, deres fordele og ulemper, og giver også et kort overblik af ikke-relationelle lagre.

For nylig er der dukket mange ikke-relationelle databaser op. Dette tyder på, at hvis du har brug for praktisk talt ubegrænset skalerbarhed efter behov, har du brug for en ikke-relationel database.

Hvis dette er sandt, betyder det så, at den mægtige relationsdatabase er blevet sårbar? Betyder det, at dagene med relationelle databaser går forbi og snart vil være helt væk? I denne artikel vil vi se på den populære ikke-relationelle databasebevægelse, som den gælder for forskellige situationer og se, om den vil påvirke fremtiden for relationelle databaser.

Relationelle databaser har eksisteret i omkring 30 år. I løbet af denne tid brød flere revolutioner ud, der ville sætte en stopper for relationel lagring. Selvfølgelig fandt ingen af ​​disse revolutioner sted, og ingen af ​​dem rystede relationsdatabasernes position en tøddel.

Lad os starte med det grundlæggende

En relationsdatabase er et sæt tabeller (entiteter). Tabeller består af kolonner og rækker (tupler). Begrænsninger kan defineres i tabeller, og der eksisterer relationer mellem tabeller. Ved hjælp af SQL kan du køre forespørgsler, der returnerer datasæt fra en eller flere tabeller. Inden for én forespørgsel indhentes data fra flere tabeller ved at forbinde dem (JOIN), oftest bruges de samme kolonner, der definerer relationerne mellem tabellerne, til forbindelsen. Normalisering er processen med at strukturere en datamodel for at sikre sammenhæng og manglende redundans i dataene.

Relationelle databaser tilgås gennem relationelle databasestyringssystemer (RDBMS). Næsten alle de databasesystemer, vi bruger, er relationelle, såsom Oracle, SQL Server, MySQL, Sybase, DB2, TeraData og så videre.

Årsagerne til denne dominans er ikke indlysende. Gennem relationsdatabasernes historie har de konsekvent tilbudt den bedste kombination af enkelhed, robusthed, fleksibilitet, ydeevne, skalerbarhed og kompatibilitet inden for datahåndtering.

Men for at give alle disse funktioner er relationelle butikker utroligt komplekse under motorhjelmen. For eksempel kan en simpel SELECT-forespørgsel have hundredvis af potentielle udførelsesstier, som optimeringsværktøjet vil evaluere direkte under udførelse af forespørgsel. Alt dette er skjult for brugerne, men internt opretter RDBMS en eksekveringsplan baseret på ting som for bedst at imødekomme forespørgslen.

Relationelle databaseproblemer

Mens relationelle lagre giver den bedste blanding af enkelhed, robusthed, fleksibilitet, ydeevne, skalerbarhed og kompatibilitet, yder de ikke nødvendigvis bedre på hvert af disse punkter end sammenlignelige systemer, der fokuserer på en enkelt funktion. Dette var ikke et stort problem, da den generelle dominans af relationelle DBMS'er opvejede eventuelle mangler. Men hvis konventionelle RDB'er ikke opfyldte behovene, var der altid alternativer.

I dag er situationen lidt anderledes. Udvalget af applikationer vokser, og med det vokser betydningen af ​​disse funktioner. Og efterhånden som antallet af databaser vokser, begynder én funktion at overstråle alle andre. Dette er skalerbarhed. Efterhånden som flere applikationer kører under høj belastning, såsom webtjenester, kan deres krav til skalerbarhed ændre sig og vokse meget hurtigt. Det første problem kan være meget svært at løse, hvis du har en relationsdatabase placeret på din egen server. Lad os sige, at serverbelastningen tredobles i løbet af natten. Hvor hurtigt kan du opgradere din hardware? Løsning af det andet problem forårsager også vanskeligheder ved brug af relationelle databaser.

Relationelle databaser skaleres kun godt, hvis de er placeret på en enkelt server. Når denne servers ressourcer løber tør, bliver du nødt til at tilføje flere maskiner og fordele belastningen mellem dem. Og det er her kompleksiteten af ​​relationelle databaser begynder at spille mod skalerbarhed. Hvis du forsøger at øge antallet af servere ikke til kun få, men til hundreder eller tusinder, vil kompleksiteten stige med en størrelsesorden, og de egenskaber, der gør relationsdatabaser så attraktive, reducerer hurtigt chancerne for at bruge dem som platform for store distribuerede systemer til nul.

For at forblive konkurrencedygtige skal leverandører af cloud-tjenester på en eller anden måde håndtere denne begrænsning, for hvilken slags cloud-platform er det uden skalerbar datalagring. Dette efterlader leverandører med kun én mulighed, hvis de ønsker at give brugerne skalerbar lagerplads. Det er nødvendigt at bruge andre typer databaser, der har en højere skalerbarhed, dog på bekostning af andre funktioner, der er tilgængelige i relationelle databaser.

Disse fordele, såvel som den eksisterende efterspørgsel efter dem, har ført til en bølge af nye databasestyringssystemer.

Ny bølge

Denne type database kaldes almindeligvis et nøgleværdilager. Faktisk er der ikke noget officielt navn, så du kan se det i sammenhæng med dokumentorienterede, attributorienterede, distribuerede databaser (selvom de også kan være relationelle), sharded sorterede arrays, distribuerede hashtabeller og lagernøgleværdi type. Selvom hvert af disse navne refererer til specifikke funktioner i systemet, er de alle variationer af et tema, vi vil kalde nøgleværdi-lagring.

Men uanset hvad du kalder det, er denne "nye" type database ikke så ny og har altid været brugt hovedsageligt til applikationer, hvor brugen af ​​relationelle databaser ikke ville være egnet. Uden nettets og skyens behov for skalerbarhed var disse systemer dog ikke efterspurgte. Nu er udfordringen at afgøre, hvilken type opbevaring der er bedst egnet til et bestemt system.
Relationelle databaser og nøgleværdilagre er fundamentalt forskellige og er designet til at løse forskellige problemer. Sammenligning af egenskaberne vil kun give dig mulighed for at forstå forskellen mellem dem, men lad os starte med dette:

Opbevaringsegenskaber

Relationel database	Nøgleværdi butik
En database består af tabeller, tabeller indeholder kolonner og rækker, og rækker består af kolonneværdier. Alle rækker i en tabel har samme struktur.	For domæner kan der tegnes en analogi med tabeller, men i modsætning til tabeller er datastrukturen for domæner ikke defineret. Et domæne er en boks, hvori du kan lægge alt, hvad du vil. Poster inden for samme domæne kan have forskellige strukturer.
Datamodel 1 er foruddefineret. Det er stærkt skrevet og indeholder begrænsninger og relationer for at sikre dataintegritet.	Poster identificeres med en nøgle, hvor hver post har et dynamisk sæt attributter tilknyttet.
Datamodellen er baseret på den naturlige repræsentation af de indeholdte data snarere end på applikationens funktionalitet.	I nogle implementeringer kan attributter kun være strenge. I andre implementeringer har attributter simple datatyper, der afspejler de typer, der bruges i programmering: heltal, strengmatrixer og lister.
Datamodellen er normaliseret for at undgå dataduplikering. Normalisering skaber relationer mellem tabeller. Relationer forbinder data fra forskellige tabeller.	Mellem domæner såvel som inden for ét domæne er relationer ikke eksplicit defineret.

Ingen joinforbindelser

Nøgleværdibutikker er rekordorienterede. Det betyder, at alle oplysninger relateret til en given post gemmes med den. Et domæne (som du kan tænke på som en tabel) kan indeholde utallige forskellige poster. For eksempel kan et domæne indeholde oplysninger om kunder og ordrer. Det betyder, at data har en tendens til at blive duplikeret mellem forskellige domæner. Dette er en acceptabel tilgang, fordi diskplads er billig. Det vigtigste er, at det giver dig mulighed for at gemme alle relaterede data ét sted, hvilket forbedrer skalerbarheden, da der ikke er behov for at samle data fra forskellige tabeller. Når du bruger en relationsdatabase, vil det være nødvendigt at bruge joins til at gruppere de nødvendige oplysninger ét sted.

Selvom behovet for relationer til at gemme nøgle-værdi-par falder kraftigt, er der stadig brug for relationer. Sådanne relationer eksisterer normalt mellem underliggende enheder. For eksempel vil et bestillingssystem have poster, der indeholder data om kunder, produkter og ordrer. Det er ligegyldigt, om disse data er i ét domæne eller i flere. Den nederste linje er, at når en kunde afgiver en ordre, vil du sandsynligvis ikke gemme både kunden og ordreoplysningerne i samme post.
I stedet skal ordreposten indeholde nøgler, der peger på de tilsvarende kunde- og produktposter. Da poster kan lagre enhver information, og relationerne ikke er defineret i selve datamodellen, vil databasestyringssystemet ikke være i stand til at verificere integriteten af ​​relationerne. Det betyder, at du kan slette kunder og de produkter, de har bestilt. Sikring af dataintegritet falder udelukkende på applikationen.

Dataadgang

Relationel database	Nøgleværdi butik
Data oprettes, opdateres, slettes og forespørges ved hjælp af Structured Query Language (SQL).	Data oprettes, opdateres, slettes og forespørges ved hjælp af API-metodekald.
SQL-forespørgsler kan hente data fra enten en enkelt tabel eller flere tabeller ved hjælp af joins.	Nogle implementeringer giver SQL-lignende syntaks til angivelse af filterbetingelser.
SQL-forespørgsler kan omfatte aggregeringer og komplekse filtre.	Ofte kan du kun bruge grundlæggende sammenligningsoperatorer (=, !=,<, >, <= и =>).
En relationsdatabase indeholder typisk indbygget logik såsom triggere, lagrede procedurer og funktioner.	Al forretnings- og dataintegritetslogik er indeholdt i applikationskoden.

Interaktion med applikationer

Nøgleværdibutikker: fordele

Der er to klare fordele ved sådanne systemer i forhold til relationelle lagre.

Velegnet til cloud-tjenester

Den første fordel ved nøgleværdi-lagre er, at de er enklere og derfor mere skalerbare end relationelle databaser. Hvis du co-hoster dit eget system og planlægger at placere et dusin eller hundrede servere, der skal håndtere stigende belastninger bag dit datalager, så er nøgleværdi-lagre dit valg.

Fordi sådan lagerplads er let og dynamisk udvidelsesbar, er den også nyttig for leverandører, der leverer en weblagringsplatform med flere lejere. En sådan database repræsenterer et relativt billigt middel til datalagring med stort skalerbarhedspotentiale. Brugere betaler typisk kun for det, de bruger, men deres behov kan vokse. Sælgeren vil dynamisk og praktisk uden begrænsninger kunne øge platformens størrelse baseret på belastningen.

Mere naturlig integration med kode

Den relationelle datamodel og kodeobjektmodellen er normalt konstrueret forskelligt, hvilket fører til en vis inkompatibilitet. Udviklere løser dette problem ved at skrive kode, der kortlægger den relationelle model til objektmodellen. Denne proces har ikke en klar og hurtigt opnåelig værdi og kan tage ret betydelig tid, der kunne have været brugt på at udvikle selve applikationen. I mellemtiden gemmer mange nøgleværdi-lagre data i en struktur, der kortlægges til objekter mere naturligt. Dette kan reducere udviklingstiden betydeligt.

Andre argumenter for at bruge nøgleværdi-lagre, som "Relationelle databaser kan blive klodsede" (jeg aner i øvrigt ikke, hvad det betyder), er mindre overbevisende. Men før du bliver en fortaler for sådan opbevaring, skal du læse næste afsnit.

Nøgleværdibutikker: ulemper

Begrænsninger i relationelle databaser sikrer dataintegritet på det laveste niveau. Data, der ikke opfylder begrænsningerne, kan ikke fysisk komme ind i databasen. I nøgleværdibutikker er der ingen sådanne begrænsninger, så overvågning af dataintegritet hviler udelukkende på applikationer. Enhver kode har dog fejl. Mens fejl i en veldesignet relationsdatabase normalt ikke fører til dataintegritetsproblemer, gør fejl i nøgleværdi-lagre normalt.

En anden fordel ved relationelle databaser er, at de tvinger dig til at gennemgå processen med at udvikle en datamodel. Hvis du har designet modellen godt, vil databasen indeholde en logisk struktur, der fuldt ud afspejler strukturen af ​​de lagrede data, men er i modstrid med strukturen af ​​applikationen. Dette gør dataene uafhængige af applikationen. Det betyder, at en anden applikation kan bruge de samme data, og applikationslogikken kan ændres uden ændringer i databasemodellen. For at gøre det samme med et nøgleværdilager, prøv at erstatte den relationelle modeldesignproces med klassedesign, som opretter generiske klasser baseret på dataens naturlige struktur.

Og glem ikke kompatibiliteten. I modsætning til relationelle databaser har cloud-baseret lagring langt færre fælles standarder. Selvom de ikke er konceptuelt forskellige, har de alle forskellige API'er, anmodningsgrænseflader og deres egne detaljer. Derfor skal du bedre stole på din leverandør, for hvis der sker noget, vil du ikke nemt kunne skifte til en anden tjenesteudbyder. Og i betragtning af det faktum, at næsten alle moderne nøgleværdibutikker er i beta 2, bliver tillid endnu mere risikabelt end i tilfælde af at bruge relationelle databaser.

Begrænset dataanalyse

Typisk er al cloud storage bygget på multi-tenancy basis, hvilket betyder, at et stort antal brugere og applikationer bruger det samme system. For at forhindre det overordnede system i at blive kapret, begrænser leverandører normalt udførelsen af ​​anmodninger på en eller anden måde. For eksempel i SimpleDB kan en forespørgsel ikke tage længere end 5 sekunder at fuldføre. I Google AppEngine Datastore kan du ikke få mere end 1000 poster i én anmodning 3.

Disse begrænsninger er ikke forfærdelige for simpel logik (oprettelse, opdatering, sletning og hentning af et lille antal poster). Men hvad hvis din app bliver populær? Du har fået en masse nye brugere og en masse nye data, og nu vil du gøre nye oplevelser tilgængelige for brugerne eller på en eller anden måde drage fordel af dataene. Her kan du have svært ved at udføre selv simple forespørgsler til dataanalyse. Funktioner som sporing af appbrugsmønstre eller et anbefalingssystem baseret på brugerhistorik kan i bedste fald være vanskelige at implementere. Og i værste fald er de simpelthen umulige.

I dette tilfælde er det til analyse bedre at lave en separat database, som vil blive fyldt med data fra dit nøgleværdilager. Tænk på forhånd over, hvordan det kan lade sig gøre. Vil du hoste serveren i skyen eller internt? Vil der være problemer på grund af signalforsinkelser mellem dig og din udbyder? Understøtter dit lager denne dataoverførsel? Hvis du har 100 millioner poster, og du kan tage 1000 poster ad gangen, hvor meget vil det så tage at migrere alle data?

Prioriter dog ikke skalerbarhed over alt andet. Det vil være ubrugeligt, hvis dine brugere beslutter sig for at bruge tjenesterne fra en anden tjeneste, fordi den giver flere funktioner og indstillinger.

Sky lagring

Mange webtjenesteudbydere tilbyder butikker med nøgleværdi til flere lejere. De fleste af dem opfylder ovenstående kriterier, men hver har sine egne særpræg og adskiller sig fra de ovenfor beskrevne standarder. Lad os tage et kig på specifikke lagringseksempler såsom SimpleDB, Google AppEngine Datastore og SQL Data Services.

Amazon: SimpleDB

SimpleDB er en egenskabsorienteret nøgleværdibutik inkluderet i Amazon WebServices. SimpleDB er i beta; brugere kan bruge det gratis - så længe deres behov ikke overstiger en vis grænse.

SimpleDB har flere begrænsninger. For det første er forespørgselsudførelsestiden begrænset til 5 sekunder. For det andet er der ingen andre datatyper end strenge. Alt gemmes, hentes og sammenlignes som en streng, så for at sammenligne datoer skal du konvertere dem til ISO8601-format. For det tredje er den maksimale størrelse af enhver streng 1024 bytes, hvilket begrænser størrelsen af ​​tekst (for eksempel en produktbeskrivelse), som du kan gemme som en attribut. Men da datastrukturen er fleksibel, kan du omgå denne begrænsning ved at tilføje attributterne "Produktbeskrivelse1", "Produktbeskrivelse2" osv. Men antallet af attributter er også begrænset - maksimalt 256 attributter. Mens SimpleDB er i beta, er domænestørrelsen begrænset til 10 gigabyte, og hele databasen kan ikke optage mere end 1 terabyte.

Et af de vigtigste funktioner i SimpleDB er brugen af ​​en eventuel konsistensmodel. Denne model er velegnet til flertrådsarbejde, men vær opmærksom på, at når du ændrer værdien af ​​en attribut i en post, vil efterfølgende læsninger muligvis ikke se disse ændringer. Sandsynligheden for en sådan udvikling af begivenheder er ret lav, men det skal huskes. Du ønsker ikke at sælge den sidste billet til fem købere, bare fordi dine data var inkonsekvente på salgstidspunktet.

Google AppEngine Data Store

Googles AppEngine Datastore er bygget oven på BigTable, Googles interne strukturerede datalagringssystem AppEngine Datastore giver ikke direkte adgang til BigTable, men kan opfattes som en forenklet grænseflade til interaktion med BigTable.

AppEngine Datastore understøtter flere datatyper inden for en enkelt post end SimpleDB. For eksempel lister, der kan indeholde samlinger i en post.

Dette er det datalager, du højst sandsynligt vil bruge, når du udvikler med Google AppEngine. I modsætning til SimpleDB vil du dog ikke være i stand til at bruge AppEngine Datastore (eller BigTable) uden for Google Web Services.

Microsoft: SQL Data Services

SQL Data Services er en del af Microsoft Azure-platformen. SQL Data Services er gratis, i beta, og har grænser for databasestørrelse. SQL Data Services er en separat applikation - en tilføjelse over mange SQL-servere, der gemmer data. Disse butikker kan være relationelle, men for dig er SDS en nøgle-værdi butik, ligesom produkterne beskrevet ovenfor.

Ikke-sky opbevaring

Der er også en række lagermuligheder, som du kan bruge uden for skyen ved selv at installere dem. Næsten alle disse projekter er unge, i alfa eller beta, og open source. Med open source er du måske mere opmærksom på potentielle problemer og begrænsninger end med proprietære produkter.

CouchDB

CouchDB er en frit tilgængelig, open source, dokumentorienteret database. JSON bruges som et datalagringsformat. CouchDB sigter mod at bygge bro mellem dokumentorienterede og relationelle databaser ved hjælp af "visninger." Sådanne visninger indeholder data fra dokumenter i en tabellignende form og giver dig mulighed for at bygge indekser og køre forespørgsler.

I øjeblikket er CouchDB ikke en virkelig distribueret database. Den har replikeringsfunktioner, der giver dig mulighed for at synkronisere data mellem servere, men det er ikke den distribution, der er nødvendig for at bygge et meget skalerbart miljø. CouchDB-udviklere arbejder dog på dette.

Projekt Voldemort

Voldemort-projektet er en distribueret nøgleværdidatabase designet til at skalere horisontalt på tværs af et stort antal servere. Det blev født ud af LinkedIn udviklingsprocessen og er blevet brugt til flere systemer med høje skalerbarhedskrav. Voldemort-projektet bruger også en endelig konsistensmodel.

Mongo

Mongo er en database udviklet hos 10gen af ​​Geir Magnusson og Dwight Merriman (som du måske kender fra DoubleClick). Ligesom CouchDB er Mongo en dokumentorienteret database, der gemmer data i JSON-format. Mongo er dog mere en objektbase end en ren nøgleværdibutik.

Støvregn

Drizzle repræsenterer en meget anderledes tilgang til at løse de problemer, som nøgleværdibutikker er designet til at bekæmpe. Drizzle startede som en gaffel af MySQL 6.0. Senere fjernede udviklere en række funktioner (inklusive visninger, triggere, kompilerede udtryk, lagrede procedurer, forespørgselscache, ACL'er og nogle datatyper) for at skabe et enklere og hurtigere DBMS. Dog kan Drizzle stadig bruges til at gemme relationelle data. Målet for udviklerne er at bygge en semi-relationel platform designet til web- og cloud-applikationer, der kører på systemer med 16 eller flere kerner.

Løsning

I sidste ende er der fire grunde til, at du måske vælger et ikke-relationelt nøgleværdilager til din applikation:

1. Dine data er meget dokumentorienterede og er mere velegnede til en nøgleværdi-datamodel end en relationel model.
2. Din domænemodel er meget objektorienteret, så brug af et nøgleværdilager vil reducere mængden af ​​yderligere kode, der kræves for at transformere dataene.
3. Datavarehuset er billigt og kan nemt integreres med din leverandørs webtjenester.
4. Dit største problem er høj on-demand skalerbarhed.

Men når du træffer din beslutning, skal du være opmærksom på begrænsningerne ved specifikke databaser og de risici, du vil støde på, hvis du går ned ad vejen med at bruge ikke-relationelle databaser.

Til alle andre krav er det bedre at vælge det gode gamle relationelle DBMS. Så er de dømt? Selvfølgelig ikke. I hvert fald for nu.

1 - efter min mening er udtrykket "datastruktur" mere passende her, men jeg forlod den oprindelige datamodel.
2 - mest sandsynligt mente forfatteren, at ikke-relationelle databaser med hensyn til deres muligheder er ringere end relationelle.
3 - dataene kan allerede være forældede; artiklen går tilbage til februar 2009.

Tilføj tags

En datamodel er et sæt af datastrukturer og operationer til deres behandling. Ved hjælp af en datamodel kan du visuelt repræsentere strukturen af ​​objekter og de etablerede relationer mellem dem. Datamodelterminologi er karakteriseret ved begreberne "dataelement" og "bindende regler". Et dataelement beskriver ethvert sæt data, og tilknytningsregler definerer algoritmer til sammenkobling af dataelementer. Til dato er der udviklet mange forskellige datamodeller, men i praksis anvendes tre hovedmodeller. Der er hierarkiske, netværks- og relationelle datamodeller. Derfor taler de om hierarkiske, netværks- og relationelle DBMS'er.

O Hierarkisk datamodel. Hierarkisk organiseret data er meget almindeligt i hverdagen. For eksempel er strukturen af ​​en videregående uddannelsesinstitution en hierarkisk struktur på flere niveauer. En hierarkisk (træ) database består af et ordnet sæt af elementer. I denne model giver initiale elementer anledning til andre elementer, og disse elementer giver igen anledning til yderligere elementer. Hvert underordnede element har kun ét overordnet element.

Organisationsstrukturer, materialelister, indholdsfortegnelser i bøger, projektplaner og mange andre datasæt kan præsenteres i hierarkisk form. Integriteten af ​​forbindelser mellem forfædre og efterkommere opretholdes automatisk. Grundregel: intet barn kan eksistere uden sin forælder.

Den største ulempe ved denne model er behovet for at bruge det hierarki, der var grundlaget for databasen under design. Behovet for konstant omorganisering af data (og ofte umuligheden af ​​denne omorganisering) førte til skabelsen af ​​en mere generel model - en netværksmodel.

O Netværksdatamodel. Netværkstilgangen til dataorganisering er en forlængelse af den hierarkiske tilgang. Denne model adskiller sig fra den hierarkiske ved, at hvert genereret element kan have mere end ét genererende element. ■

Fordi en netværksdatabase direkte kan repræsentere alle slags relationer, der er iboende i den tilsvarende organisations data, kan disse data navigeres, udforskes og forespørges på forskellige måder, det vil sige, at netværksmodellen ikke er bundet af kun ét hierarki. Men for at sende en anmodning til en netværksdatabase er det nødvendigt at dykke dybt ned i dens struktur (have skemaet for denne database ved hånden) og udvikle en mekanisme til at navigere i databasen, hvilket er en væsentlig ulempe ved denne databasemodel. .

O Relationel datamodel. Den grundlæggende idé med en relationel datamodel er at repræsentere ethvert datasæt som en todimensionel tabel. I sin enkleste form beskriver en relationsmodel en enkelt todimensionel tabel, men som oftest beskriver modellen strukturen og sammenhængene mellem flere forskellige tabeller.

Relationel datamodel

Så formålet med informationssystemet er at behandle data om genstande virkelige verden under hensyntagen forbindelser mellem objekter. I databaseteori kaldes data ofte egenskaber, og genstande - enheder. Objekt, egenskab og forbindelse er grundlæggende begreber i I.S.

Et objekt(eller essens) er noget, der eksisterer og skelnelig, det vil sige, at et objekt kan kaldes det "noget", for hvilket der er et navn og en måde at skelne et lignende objekt fra et andet. For eksempel er enhver skole et objekt. Objekter er også en person, en klasse i skolen, en virksomhed, en legering, en kemisk forbindelse osv. Objekter kan ikke kun være materielle genstande, men også mere abstrakte begreber, der afspejler den virkelige verden. For eksempel begivenheder, regioner, kunstværker; bøger (ikke som trykte produkter, men som værker), teaterforestillinger, film; juridiske normer, filosofiske teorier mv.

Attribut(eller givet)- dette er en bestemt indikator, der karakteriserer et bestemt objekt og tager en bestemt numerisk, tekst eller anden værdi for en bestemt forekomst af objektet. Informationssystemet opererer med sæt af objekter, der er designet i forhold til et givet emneområde, ved hjælp af specifikke attributværdier(data) af visse objekter. Lad os for eksempel tage klasser på en skole som et sæt objekter. Antallet af elever i en klasse er et datum, der antager en numerisk værdi (en klasse har 28, en anden har 32). Klassenavnet er et givet navn, der tager en tekstværdi (en har 10A, en anden har 9B osv.).

Udviklingen af ​​relationelle databaser begyndte i slutningen af ​​60'erne, da de første værker dukkede op, der diskuterede; muligheden for at anvende velkendte og naturlige måder at præsentere data på - de såkaldte tabelformede datalogiske modeller - ved design af databaser.

Grundlæggeren af ​​teorien om relationelle databaser anses for at være en IBM-medarbejder, Dr. E. Codd, som publicerede en artikel den 6. juni 1970 En relationel model af data for store delte databanker(Relationel datamodel for store kollektive databanker). Denne artikel var den første, der brugte udtrykket "relationel datamodel." Teorien om relationelle databaser, udviklet i 70'erne i USA af Dr. E. Codd, har et stærkt matematisk grundlag, der beskriver reglerne for effektiv organisering af data. Den teoretiske ramme udviklet af E. Codd blev grundlaget for udviklingen af ​​teorien om databasedesign.

E. Codd, som er matematiker af uddannelse, foreslog at bruge mængdeteoriens apparat (forening, skæringspunkt, forskel, kartesisk produkt) til databehandling. Han beviste, at ethvert sæt data kan repræsenteres i form af todimensionelle tabeller af en særlig art, kendt i matematik som "relationer".

Relationel En database anses for at være en, hvor alle data præsenteres for brugeren i form af rektangulære tabeller med dataværdier, og alle operationer på databasen er reduceret til manipulationer med tabellerne.

Bordet består af kolonner (felter) Og linjer (optegnelser); har et navn, der er unikt i databasen. Bord afspejler Objekttype virkelige verden (enhed), og hver af hende streng er et bestemt objekt. Hver tabelkolonne er en samling af værdier for en specifik attribut for et objekt. Værdierne vælges fra sættet af alle mulige værdier for en objektattribut, som kaldes domæne.

I sin mest generelle form er et domæne defineret ved at specificere en eller anden basisdatatype, som elementerne i domænet tilhører, og et vilkårligt boolsk udtryk anvendt på dataelementerne. Hvis du evaluerer en boolsk betingelse på et dataelement, og resultatet er sandt, hører det element til domænet. I det enkleste tilfælde er et domæne defineret som et gyldigt potentielt sæt værdier af samme type. For eksempel udgør indsamlingen af ​​fødselsdatoerne for alle ansatte "fødselsdato-domænet", og navnene på alle medarbejdere udgør "medarbejdernavnsdomænet". Fødselsdato-domænet skal have en tidspunkt-datatype, og medarbejdernavnsdomænet skal have en karakterdatatype.

Hvis to værdier kommer fra samme domæne, kan der foretages en sammenligning mellem de to værdier. For eksempel, hvis to værdier er taget fra domænet for fødselsdatoer, kan du sammenligne dem og bestemme, hvilken medarbejder der er ældre. Hvis værdierne er taget fra forskellige domæner, er deres sammenligning ikke tilladt, da det efter al sandsynlighed ikke giver mening. For eksempel vil der ikke komme noget bestemt ud af at sammenligne en medarbejders navn og fødselsdato.

Hver kolonne (felt) har et navn, som normalt skrives øverst i tabellen. Når du designer tabeller inden for et specifikt DBMS, er det muligt at vælge for hvert felt sit type, det vil sige at definere et sæt regler for dets visning, samt at bestemme de operationer, der kan udføres på de data, der er gemt i dette felt. Sæt af typer kan variere mellem forskellige DBMS'er.

Feltnavnet skal være unikt i tabellen, men forskellige tabeller kan have felter med samme navn. Enhver tabel skal have mindst ét ​​felt; Felterne er placeret i tabellen i overensstemmelse med den rækkefølge, som deres navne optrådte i, da den blev oprettet. I modsætning til felter har strenge ikke navne; deres rækkefølge i tabellen er ikke defineret, og deres antal er logisk ubegrænset.

Da rækkerne i tabellen ikke er ordnet, er det umuligt at vælge en række efter dens position - der er ingen "første", "anden" eller "sidste" blandt dem. Enhver tabel har en eller flere kolonner, hvis værdier entydigt identificerer hver af dens rækker. En sådan kolonne (eller kombination af kolonner) kaldes primærnøgle. Et kunstigt felt introduceres ofte til talposter i en tabel. Et sådant felt kunne for eksempel være dets ordinalfelt, som kan sikre det unikke ved hver post i tabellen. Nøglen skal have følgende egenskaber.

Unikhed. På et givet tidspunkt er der ikke to forskellige relationstupler, der har den samme værdi for kombinationen af ​​attributter inkluderet i nøglen. Det vil sige, at der ikke kan være to rækker i tabellen, der har samme identifikationsnummer eller pasnummer.

Minimalisme. Ingen af ​​attributterne inkluderet i nøglen kan udelukkes fra nøglen uden at krænke unikheden. Det betyder, at du ikke skal oprette en nøgle, der indeholder både pasnummer og identifikationsnummer. Det er nok at bruge nogen af ​​disse attributter til entydigt at identificere en tupel. Du bør heller ikke inkludere en ikke-unik attribut i nøglen, det vil sige, at det er forbudt at bruge en kombination af et identifikationsnummer og en medarbejders navn som nøgle. Ved at ekskludere medarbejderens navn fra nøglen, kan hver række stadig identificeres entydigt.

Enhver relation har mindst én mulig nøgle, eftersom helheden af ​​alle dens attributter opfylder betingelsen om unikhed - dette følger af selve definitionen af ​​relationen.

En af de mulige nøgler er tilfældigt valgt i som den primære nøgle. De resterende mulige nøgler, hvis nogen, tages som alternative nøgler. For eksempel, hvis du vælger et identifikationsnummer som den primære nøgle, så vil pasnummeret være den alternative nøgle.

Relationen mellem tabeller er det vigtigste element i den relationelle datamodel. Det er understøttet fremmednøgler.

Når man beskriver en relationel databasemodel, bruges der ofte forskellige termer for det samme koncept, afhængigt af beskrivelsesniveauet (teori eller praksis) og systemet (Access, SQL Server, dBase). I tabel 2.3 giver en oversigt over de anvendte udtryk.

Tabel 2.3. Databaseterminologi

Databaseteori____________ Relationelle databaser_________ SQL Server __________

Relationstabel Tabel

Tuple Record Row

AttributField_______________ Kolonne

Relationelle databaser

Relationel database er et sæt af relationer, der indeholder al den information, der skal gemmes i databasen. Det vil sige, at databasen repræsenterer et sæt tabeller, der er nødvendige for at gemme alle data. Tabellerne i en relationsdatabase er logisk relateret til hinanden Kravene til at designe en relationsdatabase generelt kan reduceres til flere regler.

О Hver tabel har et unikt navn i databasen og består af rækker af samme type.

O Hver tabel består af et fast antal kolonner og værdier. Mere end én værdi kan ikke gemmes i en enkelt række kolonne. Hvis der for eksempel er en tabel med oplysninger om forfatter, udgivelsesdato, oplag osv., så kan kolonnen med forfatterens navn ikke gemme mere end ét efternavn. Hvis bogen er skrevet af to eller flere forfattere, skal du bruge yderligere tabeller.

O På intet tidspunkt vil der være to rækker i tabellen, der dublerer hinanden. Rækker skal afvige i mindst én værdi for entydigt at kunne identificere enhver række i tabellen.

О Hver kolonne er tildelt et unikt navn i tabellen; en specifik datatype er indstillet til det, så homogene værdier placeres i denne kolonne (datoer, efternavne, telefonnumre, pengebeløb osv.).

O Det fuldstændige informationsindhold i en database er repræsenteret som eksplicitte værdier af selve dataene, og dette er den eneste repræsentationsmetode. For eksempel er relationer mellem tabeller baseret på de data, der er gemt i de tilsvarende kolonner, og ikke på grundlag af nogen pointere, der kunstigt definerer relationer.

О Når du behandler data, har du fri adgang til enhver række eller kolonne i tabellen. Værdierne, der er gemt i tabellen, pålægger ingen begrænsninger for rækkefølgen, hvori dataene tilgås. Beskrivelse af kolonnerne,