TDT4145 - Datamodellering og databasesystemer
[TOC]
Intro
Mine notater for TDT4145. De er på norsk, er fulle av skrivefeil, og sikkert litt faktafeil. Disse er beregnet på personlig bruk, så jeg går ikke inn for noe mer en det jeg forstår og som hjelper meg å huske.
Hvorfor er de her?
Fordi det er digg å skrive Markdown, og her var det enkelt å gjøre de tilgjenglig som pene kompilerte html sider.
Ord og utrykk
Database
En database er en samling med data
Data
Informasjon som har en mening alene
Miniverden
En database representerer informasjon fra deler av vår verden, den lille delen databasen inneholder informasjon om kaller vi miniverden
Database modell
En model som gjengir den logiske strukturen til en database, for eksempel et ER-diagram
DBMS
En samling programvare som lar en bruker lage og håndtere en database. Eks. MySQL, PostgreSQL.
Database system
En felles betegnelse for database, database modell og DBMS.
Typer feil
Det er mange typer feil. Feil 1-4 er mest vanlig, 5 og 6 er mindre vanlig og vanskligere å gjennopprette.
- Datamaskin kræsj/feil
- Transaksjons eller systemfeil
- Lokale feil eller exceptions som ikke går gjennom transaksjoner
- Concurrency control enforcement (feil som oppstår om noe ødelegger concurrency)
- Harddisk kræsj
- Fysiske problemer og katastrofer
Relasjonsalgebra
Seleksjon σ Velge ut rader med data basert på kriterie.
Prosjeksjon π Velge ut kolonner med data basert på kolonnenavn
Union ⋃ Gir en liste med alle verdier fra to datasett
Snitt ⋂ Gir en liste med kun de verdiene som er like i to datasett
Differanse - Gir en liste med det som er forskjellig fra lista A og B. Returnerer A - B.
Naturlig forening * Antar hvilke like rader som skal slås sammen slik at den kan returnere en god sammenslått liste. Bruk Forening
Forening ⨝ Gir en sammensatt liste fra to datasett hvor resultater er basert på en felles kolonne.
Kartesisk produkt X Gir en gigantisk kryss liste, med mindre man ikke kan, bruk heller Forening.
Divisjon / Lar deg velge ut hente ut data fra en stor liste hvor den kun returnerer data som har fullført alle kriterier.
Funksjoner F Man kan bruke funksjoner i Relasjonsalgebra, dette er normale SQL funksjoner.
Mye brukt: Sum, Avg, Count
Grupperingsoperasjon/Aggregation ∑ Man kan bruke grupperingsoperasjoner for å foreksempel kalle funksjoner på flere ting i et dataset.
SQL
Uthenting
SELECT
Velge attributter som skal skrives ut.
FROM
Fra hvilken tabell skal radene hentes.
WHERE
Gi en betingelse som kan brukes til å hente ut spesielle rader.
AS
Gi nytt navn til kolonnen/attributten i en spørring.
GROUP BY
Velg en attributt som resultatene skal sorteres på.
HAVING
Betingelse for grupper.
ORDER BY
Velg en attributt dataen skal sorteres på. ASC/DESC
NB: WHERE tar betingelse for en kolonne, mens HAVING for en gruppe.
Distinct
Velg kun en av hver slik at output har kun unike verdier.
Order by
Sorterer på kolonne, med ASC eller DESC
Count()
Teller antall forekomster av alt(*) eller av en gitt verdi. Kan navngi kolonne ved bruk av AS.
AS
Gi noe et annet navn/alias.
Inner join
Kan brukes for å fylle ut en verdi fra en hjelpe tabell, foreksempel en poststeder tabell ved hjelp av postnummer select kid, navn, adresse, kunde.postnr, poststed from kunde inner join poststeder on kunde.postnr = poststeder.postnr;
Like
Brukes for å sammenlinge verdier, litt løsere en =.
Union
Sette sammen kolonner, foreksempel legge alle fornavn og etternavn i samme kolonne og kalle den alle navn.
Left outer join
Slår sammen tabell A og B, og vil alltid ha med alle rader fra den venstre (A) siden. Om den ikke finner et matchende sett når den kjører ON vil den fortsatt ta med raden, men fylle ut med NULL.
Wildcard %
Brukes for å matche alt mulig. Kan brukes til å finne alle ting som begynner på K%.
Normalisering
Nøkler
Supernøkkel
Unik identifikator for rad.
Kandidatnøkkel
unik, minimal identifikator.
Primærnøkkel
Den viktigste blant kandidatnøklene.
Alternaltiv nøkkel
kandidatnøkkel som ikke er primærnøkkel.
Nøkkelattributt
Attributt som er med i en eller flere kandidatnøkler.
Ikke-Nøkkelattributt
Attributt som ikke er med i noen kandidatnøkkel.
Antar at et kjøretøy har en bestemt fører på en bestemt dag og tid. Antar også at en person kan føre bare et kjøretøy på en bestemt dag og tid. Vi får da to funksjonelle avhengigheter:
• Regnr, Dato, Tid -> FørerPnr
• FørerPnr, Dato, Tid -> RegNr
Det kan være flere skadede personer i en ulykke. Kandidatnøklene for tabellen blir da:
• RegNr, Dato, Tid, SkadetPn
FørerPnr, Dato, Tid, SkadetPnr
Normalform
1NF
- Det kan ikke være noen repeterende grupper.
- All data må være atomisk
- Alle felter må ha et unikt navn
- Den har en primary key
2NF
- Den er 1NF
- Alle ikke nøkkelattributter er avhengig av alle deler av primærnøkkelen.
Tabellen er på 2NF siden nøkkelen består av et enkelt attributt, det kan da ikke oppstå noen delvise funksjonelle avhengigheter.
3NF
- Den er på 2NF
- Det er ingen transetive funksjonelle avhengigheter.
BCNF
- Den er på 3NF
- For alle A -> B er A en nøkkel
Fordeler med høy NF
Unngår redundans og problemer med innsettning, oppdatering, sletting.
Ulemper med høy NF
Flere tabeller, må joine mer, mer kompliserte spørringer.
Huskeliste ved oppsplitting
- Attributtbevaring
- Normalform
- Bevaring av funksjonelle avhengigheter
- Taps-løs-join-egenskap
Closure
We have a set of functional dependencies F. The closure of F is a set of functional dependencies F' that are logically implied by F.
Lagring og indeksering
Lagringsstrukturer
Heapfile
Simple lagringsstruktur, innsettning gjøres bakerst i filen, kostnad O(1). Søk og uthenting krever linært søk gjennom filen, kostnad O(n). Sletting merker noe for sletting, kostnad O(1) + kostnaden for å finne elementet.
Hash buckets
En hash funksjon vil la deg kalkulere en nøkkel for en addresse basert på verdien av dataene. En god hash funksjon vil fordele data gjevnt over det tilgjenglige området. Det er lov å anta 60% fyll. Om vi ser bort fra krasj, har hash buckets en kostnad på O(1) for alt. Hash er dårlig for søk på rekkevidde.
B+ tree
Awesome tre struktur, trygt å anta høyde på 3 eller 4. Kostnad O(log n). Om filer er stabile, bruk ISAM.
ISAM
Index Sequential Access Method
Hash skjemaer
Extendible hashing
Ganske bra, behandler hashen som en bitstreng. Re-hashing skjer underveis, en bøtte av gangen. Både LSB og MSB er vanlig.
Linear hashing
Gjør det mulig å ekspandere tabellen en slot av gangen, round robin.
Formler
Static hash søketid kan regnes ut som:
antall poster i rad * blokk nummer + antall poster i rad * blokk / antall poster
Gjennomsnittlig antall blokker aksessert: 10 poster1 blokk + 3 poster 2 blokker = 16 blokker. 16 blokker/13 poster = 1,23 blokker/post
Indekser
Ulemper
- Ekstra plass - marginal
- Generering av indekser - medium
- Vedlikeholding - Kan i teorien koste mer en det gir. (For eksempel i en database med mer skriving en lesing.
Fordeler er avhengig av:
- Størrelsen på tabellen (og muligens designet)
- Hvordan data er distribuert
- Query vs update loads
Transaksjoner
En transaksjon er en enhet av arbeid som utføres i en DBMS.
ACID
Atomicity
En transaksjon er alltid gjennomført i en helhet, om det er en crash underveis i en transaksjon vil den heller fjerne de spørringene som er blitt kjørt.
Consistency
En transaksjon skal kjøre fra start til slutt uten å bli forstyrret av en annen transaksjon. En database skal tas fra en konsistent tilstand til en annen konsistent tilstand.
Isolation
En transaksjon skal gi inntrykk av å kjøre som om den blir kjørt isolert selvom den blir kjørt i parralell med andre transaksjoner.
Durability
Hvis det er et systemkræsj og en tranaksjon er commited vil den garantere at dataene er i databasen.
Transaksjonens livsykel.
- Begynn transaksjon
- Utførs spørringer
- Om ingen feil skjer, commit og slutt.
- Om feil skjer, rull tilbake og slutt.
Protokoller for samtidighetskontroll
Samtidighetskontroll protokollene er en samling regler som garanterer serialiserbarhet.
To fase lås (2PL)
En lås er en variable assosiert med et sett data. Den beskriver hva som er lov å gjøre på settet.
En transaksjon følger protokollen hvis alle låse operasjoner følger den første opplåsnings operasjonen.
2PL kan implementeres som binær og shared/executive. Noen shared-exclusive implementasjoner er:
Binary locks
Binær lås, 1 er låst, 0 er ulåst. Hvis noen vil bruke et låst sett vil den måtte vente til den blir ulåst.
Shared/executive (or Read/Write) locks
Multilås. Leselås/shared lock, skrivelås/executive lås.
En 2PL transaksjon som følger protokollen: 1. Utvidelse, eller voksing: Nye låser kan bli opprettet, men ingen kan slippes. 2. Krymping: Eksisterende låser kan bli sluppet, og ingen nye kan opprettes.
Oppgradering og nedgradering betyr å gjøre en lås fra lese til skrive og fra skrive til lese. Om det er lov kan det kun gjøres i oppgradering i fase 1 og nedgradering i fase 2.
Variasjoner
Basic
Som beskrevet over.
Konservativ/statisk
Alle låser må settes før en transaksjon begynner, ellers feil og prøve igjen senere.
Strict
En transaksjon vil ikke slippe noen skrivelåser før den har committed eller abortert.
Rigorous
En transaksjon vil ikke slippe noen låser før den har committed eller abortert.
Problemer
Vranglås
Enkelt å greit at to prosesser har låst samme sett, altså at to ting venter på det samme.
Konservativ 2PL ungår vranglås. Vranglås deteksjon kan finne vranglåser. Timeout kan fikse det, men krever venting, og kan drepe prosesser ved feil.
Sulting
Problem når transaksjoner ikke får kjørt før etter en lang periode. For eksempel på grunn av prioritetskøer. Det vil være enkelt å løse ved å ha gode skjemaer for venting, prioritering, og førestemann til mølla.
Buffering av disk blokker
Pages som skal bli oppdatert av en transaksjon ligger gjerne bufferet i minne frem til de er oppdatert og commitet slik at de kan bli skrevet tilbake til disk. Når systemet krever mer plass i mellomlageret vil bytte dem ut med nye. Dette kalles flushing.
Dirty bit
Sier noe om bufferen er modifisert. Om man flusher vil det bare skrives data til disk om dirty bit er 1. Man kan også lagre transaksjons iden til transaksjonen som modifiserte blokken.
Pin-Unpin bit
En page i bufferet er pinned, biten er 1, hvis den ikke kan skrives til disk enda. For eksempel om en transaksjon ikke har commited.
Flush strategier
In-place updating
Data i buffer blir skrevet tilbake til den orginale lokasjonen på disk.
Shadowing
Skriver en oppdatert buffer på et annet sted på disken. Det kan eksistere flere versjoner av et dataset. Brukes skjelden i praksis.
BFIM (Before image) - Gammel verdi av data AFIM (After image) - Ny verdi av data
Policies brukt i Transaksjonskontroll
Dette er de fire policies som kan bestemme når en blokk fra buffer kan bli skrevet tilbake til disk.
NO-FORCE
Endringer må ikke skrives til disk med en gang, men de må logges til disk med en gang. Gjør at man slipper å søke etter elementet på disk. Det er også billigere å kun lage endringen til disk enn hele elementet. REDO
FORCE
Endringer blir skrevet til disk med en gang. Suger.
STEAL
Lar en transaksjon skrive til disk før den er committed. Rask, men gjør det vanskligere å rulle tilbake. UNDO
NO-STEAL
Lar ikke transaksjoner skrive til disk før de er commited. Suger.
Bruk STEAL NO-FORCE, bruker REDO og UNDO logging under gjennopprettning.
System loggen
Et DBMS har en system logg som lagerer alle hendelser. Den vil gjøre det mulig å gjennopprette fra feil. Loggen må ligge på disk.
En logg kan se slik ut: 1. [start_transaction, transaction_id] 2. [write_item, transaction_id, item_id, old_value, new_value] 3. [read_item, transaction_id, item_id] 4. [commit, transaction_id] 5. [abort, transaction_id]
ARIES (Algorithms for Recovery and Isolation Exploting Semantics)
Er en algoritme for gjennopprettning som er laget for å virke på STEAL NO-FORCE databaser.
Prinsipper:
Write ahead logging
Endringer på et objekt er først skrevet til logg, loggen må skrives til disk før det kan endres noe på objektet.
Repeating history during redo
Når man restarter etter et kræsj vil ARIES se gjennom loggen for å finne stegene som er nødvendig for å bygge databasen tilbake til steget den var i når det kræsjet. ARIES vil fjerne transaksjoner som var aktive når kræsjen skjedde.
Logging changes during undo
Endringene som blir gjort mens man kjører undo vil bli logget for å unngå at noe blir gjort flere ganger. CLR (Compensating log record)
Datastrukturer:
Dirty page table
Holder styr på pages som har blitt modifisert og ikke er skrevet til disk. Den lagrer sekvensnummeret for den siste sekvensen som gjorde den dirty.
Transaction table
Holder styr på alle transaksjoner som kjører.
ARIES lagrer periodisk DPT og TT til loggfilen, og lager et sjekkpunkt. Dette gjør at den ikke trenger å skanne hele logfilen, men kun fra det forrige sjekkpunktet når den skal kjøre gjenopprettning. This allows for skipping blocks that are not in the DPT, or that are in the DPT but have a recLSN that is greater than the logg post LSN.
Historie
Seriell
En transaksjon vil ikke begynne å kjøre før den forrige transaksjonen har commited. Det er ingen concurrency.
Serialiserbar
Har ekvivalent utfall som en seriell historie, men vil kjøre asynkront og muligens i tilfeldig rekkefølge. Har concurrency.
Recoverable
En transaksjon vil commite når alle transaksjoner de har lest endringer fra vil commite.
Unrecoverable
En historie som ikke kan gjennopprettes.
ACA (Avoids Cascading Aborts, aka Cascadeless)
Transaksjoner kan ikke lese uncommitted endringer fra andre transaksjoner. RAW er ikke lov. ACA er gjenopprettbar.
Strict Lar ikke en transaksjon lese eller skrive uncommited verdier. All Strict er ACA. RAW og WAW er ikke lov.
Konflikt
En to transaksjoner er i konflikt om: 1. De hører til to forskjellige transaksjoner. 2. De bruker begge samme element X. 3. Minst en av dem prøver å bruke en skrive operasjon på X.
Fantomer - rader som dukker opp andre gangen man leser en liste.
Join algoritmer
Join er kostbart, i tid og IO. Mange måter å gjøre det. Natural Join og Equijoin.
Nested-loop join
Standard bruteforce algoritme. Krever ingen spesiell tilgang. En ytre og en indre loop.
O = Blokker i ytre loop
I = Blokker i indre loop
b = Størrelsen på buffer
I/O = O+( ceil( O/( b-2 ))*I)
Single-loop join
i = Mengde index levler for attributten vi joiner på.
r = Mengde blokker vi leter etter
b = Antall blokker vi de er delt på
I/O = b + (r (i + 3))
Sort-merge join
Gitt at alle rader er fysisk sotert på attributtet det skal joines på, kan vi implementere join på den mest effektive måten. Begge filene blir skannet samtidig. Deretter blir de joinet på treff.
b = antall blokker
nb = antall blokker i buffer
nr = ceil(b/nb) aka antall runder i buffer
pass = ceil(log_nb-1(nr))
(2 * b) + (2 * b * p)
Formler
Antall blokker
Heapfil
Antall poster / poster per blokk = antall blokker
Clustered B+tree
Antall blokker i heap / fyllgrad = antall blokker på løvnivå Hvor mange nivåer trenger vi? Om det er en root node legger vi til 1.
Clustered hash-indeks
Antall blokker i heap / fyllgrad = antall blokker på løvnivå.
Unclustered B+tree med heap
Antall poster i heap + antall blokker i B+tree Blokker i B+tree regnes ved å regne ut hvor mange blokker med pekere. (Poster * Størrelsen på post) / (størrelse på indeksblokk * fyllgrad) Husk å peke på rot blokker.
I/O
Heap
Alle blokker må leses om det søkes etter mer en en ting. Om man søker etter en ting kan man anta at man finner den ved å søke gjennom halve blokken.
Clustered B+tree
Antall blokker * poster som tilfrestiller betingelse Pluss eventuelle rotnoder
Unclustered B+tree
Antall blokker * poster som tilfrestiller betingelse Her må det også ganges med hvor mange poster det er i en blokk. Dette fordi man må lese dem fra heapfilen.