[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.

1. Datamaskin kræsj/feil
2. Transaksjons eller systemfeil
3. Lokale feil eller exceptions som ikke går gjennom transaksjoner
4. Concurrency control enforcement (feil som oppstår om noe ødelegger concurrency)
5. Harddisk kræsj
6. 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

1. Det kan ikke være noen repeterende grupper.
2. All data må være atomisk
3. Alle felter må ha et unikt navn
4. Den har en primary key

2NF

1. Den er 1NF
2. 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

1. Den er på 2NF
2. Det er ingen transetive funksjonelle avhengigheter.

BCNF

1. Den er på 3NF
2. 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

1. Attributtbevaring
2. Normalform
3. Bevaring av funksjonelle avhengigheter
4. 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

1. Ekstra plass - marginal
2. Generering av indekser - medium
3. Vedlikeholding - Kan i teorien koste mer en det gir. (For eksempel i en database med mer skriving en lesing.

Fordeler er avhengig av:

1. Størrelsen på tabellen (og muligens designet)
2. Hvordan data er distribuert
3. 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.

1. Begynn transaksjon
2. Utførs spørringer
3. Om ingen feil skjer, commit og slutt.
4. 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.