Gagnasafnsfræði

Gagnasafnsfræði

Bækur

A First Course in Database Systems (Ullman et al.)
Database in Depth: Relational Theory for Practitioners (C. J. Date)
An Introduction to Database Systems (C. J. Date)
Databases, Types and the Relational Model: The Third Manifesto (C. J. Date)

Venslalíkanið

Vensl (e. relation)

Vensl er mengi n-da $(d_1, d_2, \ldots , d_n)$ þar sem hvert stak $d_j$ tilheyrir tilteknu óðali $D_j$.

N-d (e. tuple)

N-d (borið fram sem “ennd”) er endanlegur raðaður listi af $N$ stökum $(d_1, d_2, \ldots , d_N)$.

Eigindi (e. attribute)

Eigindi er nafn ásamt óðali.

Óðal (e. domain)

Óðal er mengi allra þeirra gilda sem tiltekið stak má innihalda.

Figure 1: Hægt er að túlka vensli sem töflu, þar sem raðir svara til n-da og dálkar svara til eiginda.

Fallaákveður

Fallaákveða (e. functional dependency) á vensli $R$ er skilyrði sem segir að allar n-dir í $R$ sem hafa sömu gildi á einindunum $A_1 \cdots A_n$ verða að hafa sömu gildi á einindunum $B_1 \cdots B_m$. Slík fallaákveða er rituð $A_1 A_2 \ldots A_n \rightarrow B_1 B_2 \ldots B_m$ þar sem $A_i$ og $B_i$ eru einindi í $R$.

Ef $\{B_1, B_2 \ldots B_m\} \subseteq \{A_1, A_2 \ldots A_n\}$ þá er talað um ómarkverða (e. trivial) fallaákveðu.

Setning (samsetning fallaákveðna)

Fallaákveðan $A_1 A_2 \ldots A_n \rightarrow B_1 B_2 \ldots B_m$ er jafngild eftirfarandi fallaákveðum

$$A_1 A_2 \ldots A_n \rightarrow B_1$$ $$A_1 A_2 \ldots A_n \rightarrow B_2$$ $$\vdots$$ $$A_1 A_2 \ldots A_n \rightarrow B_m$$

Lokanir

Lokun af eigindum $\{A_1, A_2, \ldots , A_n\}$ undir mengi af fallaákveðum $S$ er mengi allra eiginda $B$ þannig að sérhvert vensl sem uppfyllir fallaákveðurnar í $S$ uppfyllir einnig $A_1 A_2\cdots A_n \rightarrow B$. Við táknum lokunina með $\{A_1, A_2, \ldots , A_n\}^+$

Reiknirit (lokun af mengi fallaákveða)

Finna má lokunina $\{A_1, A_2, \ldots , A_n\}^+$ undir mengi fallaákveðna $S$ með eftirfarandi aðferð

Skiptum fallaákveðunum niður þannig að hver þeirra hafi aðeins eitt eigindi á hægri hlið.
Látum $X$ tákna mengi sem verður á endanum að lokuninni. Setjum fyrst $X = \{A_1, A_2, \ldots , A_n\}$
Leitum í $S$ að öllum fallaákveðum $B_1 B_2 \cdots B_m \rightarrow C$ þannig að $\{B_1, B_2, \ldots, B_m\} \subseteq X$ og bætum þá $C$ við $X$. Endurtökum skref þar til engin eigindi bætast við $X$.

Þá er $X$ lokunin.

Setning (gegnvirkni á fallaákveðum)

Ef $A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m$ og $B_1 B_2 \cdots B_m \rightarrow C_1 C_2 \cdots C_k$ eru fallaákveður sem gilda á vensli $R$. Þá gildir einnig fallaákveðan

$$A_1 A_2 \cdots A_n \rightarrow C_1 C_2 \cdots C_k$$

Reiknirit (vörpun á fallaákveðum)

Höfum vensl $R$ og mengi fallaákveða $F$. Vörpum fallaákveðunum úr $F$ yfir á vensl $R_1$.

Fyrir sérhverja samantekt af eigindum $X$ í $R_1$ reiknum við $X^+$.
Bætum við öllum markverðum fallaákveðum $X \rightarrow A$ þar sem $A$ er bæði í $X^+$ og $R_1$.

Lágþekjur

Þekja (e. basis) fyrir mengi fallaákveða $S$ er mengi af fallaákveðum $F$ þannig að sérhver fallaákveða í $S$ sé afleiðing af fallaákveðunum í $F$.

Lágþekja (e. minimal basis) fyrir $S$ er mengi af fallaákveðum $F$ þannig að sérhvert hlutmengi í $F$ er ekki þekja fyrir $S$.

Reiknirit (lágþekja fyrir mengi fallaákveða)

Byrjum með þekju $G$ og finnum lágþekju $F$, setjum fyrst $F = G$.
Brjótum allar fallaákveður upp þannig að alltaf sé aðeins eitt eigindi á hægri hönd. þ.e. $X \rightarrow YZ$ verður $X \rightarrow Y$ og $X \rightarrow Z$.
Fjarlægjum eigindi úr vinstri hlið fallaákveðna ef $F$ er ennþá þekja. Ef aðeins eitt eigindi á vinstri hlið þá fjarlægjum við fallaákveðuna.

Þá stendur eftir lágþekja $F$.

Frávik

Frávik (e. anomalies) eru óæskilegir eiginleikar sem koma upp þegar reynt er að koma of mörgum eigindum fyrir í einu vensli.

Endurtekningar (e. redundancy)
Uppfærslufrávik (e. update anomalies)
Eyðingafrávik (e. deletion anomalies)

BCNF þáttun

Þegar vensli $R$ er skipt niður í nokkur vensli $R_1, R_2, \ldots , R_n$ er talað um þáttun. Til dæmis má þátta $R(A,B,C)$ niður í $R_1(A,B)$ og $R_2(A,C)$. Þegar vensli er þáttað er mögulegt að einhverjar upplýsingar um uppbyggingu á $R$ glatist. Þáttanir eru vanalega gerðar með eina eða fleiri af eftirfarandi kröfum í huga.

Útrýming á frávikum
Varðveiting upplýsinga við tengingu (e. lossless join)
Varðveiting fallaákveðna

BCNF (Boyce Codd Normal Form)

Vensli $R$ er á Boyce Codd staðalformi ef og aðeins ef eftirfarandi gildir.

Fyrir sérhverja markverða fallaákveðu $A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m$ á $R$ gildir að $\{A_1, A_2 , \ldots , A_n \}$ er yfirlykill fyrir $R$.

Reiknirit (þáttun á BCNF form)

Byrjum með vensli $R$ og mengi fallaákveða $S$. Framkvæmum eftirfarandi skref endurkvæmt.

Athugum hvort $R$ sé á BCNF formi. Ef svo er þarf ekki að fara lengra.
Finnum fallaákveðu $X \rightarrow Y$ sem brýtur á BCNF. Setjum $R_1 = X^+$ og $R_2 = (R \setminus X^+) \cup \{X\}$.
Vörpum fallaákveðunum í $S$ yfir á $R_1$ og $R_2$, táknum mengi tilsvarandi fallaákveða með $S_1$ og $S_2$.
Framkvæmum BCNF þáttun á $R_1, S_1$ og $R_2, S_2$ hvort fyrir sig.

Þegar vensli $R$ er þáttað á BCNF form er ekki víst að allar fallaákveður muni varðveitast. Hinsvegar munu engin frávik birtast í þáttuninni og BCNF þáttun er ávallt taplaus.

3NF þáttun

Við þáttun þarf stundum að velja á milli þess að varðveita allar fallaákveður eða halda þáttuninni á BCNF formi. 3NF er slakari útgáfa af BCNF sem varðveitir alltaf fallaákveður.

3NF (Third Normal Form)

Vensli $R$ er á þriðja staðalformi ef og aðeins ef eftirfarandi gildir.

Fyrir sérhverja markverða fallaákveðu $A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m$ á $R$ gildir að

$$\{A_1, A_2 , \ldots , A_n \}$$

er annað hvort yfirlykill eða einindin í $A \setminus B$ tilheyra einhverjum lykli í $R$.

Reiknirit (þáttun á 3NF form)

Finnum lágþekju fyrir $F$ og köllum hana $G$.
Fyrir hverja fallaákveðu $X \rightarrow A$ í $F$ búum við til vensl $R_n(XA)$.
Ef ekkert venslana er yfirlykill fyrir $R$ þá finnum við lykil $A$ fyrir $R$ og bætum við vensli $R_n(A)$.

Taplausar tengingar

Eftir að vensl $R$ hefur verið þáttað niður í vensl $R_1, R_2, \ldots , R_n$ er ekki víst að hægt sé að endurbyggja $R$ út frá þáttuninni. Ef það er hægt er talað um taplausa tengingu (e. lossless join)

Chase prófið

Chase reikniritið

Varðveiting fallaákveða

Lyklar

Mögulegur lyklill (e. candidate key)

Mengi eiginda $A = \{A_1, A_2, \ldots , A_n\}$ er sagt vera mögulegur lykill (stundum bara lykill) fyrir vensl $R$ ef

Eigindin ákvarða öll önnur eigindi í $R$ út frá gefnum fallaákveðum, þ.e. $A^+ = R$
Ekkert hlutmengi $A$ ákvarðar öll önnur eigindi í $R$, þ.a. $A$ er minnsti mögulegi lykill.

Yfirlykill (e. superkey)

Mengi eiginda $A = \{A_1, A_2, \ldots , A_n\}$ er sagt vera yfirlykill ef það uppfyllir fyrra skilyrðið á mögulegum lykli, þ.e. $A^+ = R$.

Af þessu er ljóst að allir mögulegir lyklar eru yfirlyklar, en yfirlykill þarf ekki að vera mögulegur lykill.

Aðallykill (e. primary key)

Aðallykill er einn af mögulegum lyklum fyrir vensl $R$. Vensl $R$ getur aðeins haft einn aðallykil. Aðrir mögulegir lyklar eru stundum nefndir varalyklar (e. alternate key)

Aðallykill er með öðrum orðum einhver einn mögulegur lykill sem hefur verið valinn af handahófi.

Þrígild rökfræði

Í SQL geta eigindi tekið gildið NULL, sem er ekki það sama og 0 (ef eigindið er INTEGER) eða tómur strengur (ef eigindið er TEXT). Það getur haft nokkrar merkingar, tökum sem dæmi eigindi phoneNumber

Óþekkt gildi - símanúmer viðkomandi er ekki vitað
Gildi sem á ekki við - viðkomandi á ekki síma
Óaðgengilegt gildi - símanúmer sem er haldið leyndu

Reikniaðgerðir

Þegar reikniaðgerð er beitt á NULL er útkoman alltaf NULL. Til dæmis ef x = NULL þá er bæði 0*x = NULL og x-x = NULL.

Þrígild rökfræði

Þegar eigindi taka gildið NULL þýðir það í vissum skilningi að gildið er ekki vitað. Þar með getur yrðing á borð við NULL == “strengur” hvorki tekið gildi TRUE né FALSE, heldur tekur hún gildið UNKNOWN.

Þrígild rökfræði vinnur með TRUE, FALSE og UNKNOWN. Mikilvægt er að vita hvernig aðgerðir eins og AND, OR og NOT hegða sér með UNKNOWN.

Venslaalgebra

Aðgerðir

Skorðun (e. restrict)

Skilar vensli sem inniheldur allar n-dir úr vensli sem uppfylla ákveðið skilyrði. Táknað með $\sigma_{a \theta b}( R )$ eða $\sigma_{a \theta v}( R )$ þar sem

$R$ er vensl
$\theta$ er tvíundavensl sem virkar á tag eigindanna, t.d. $<, \le, =, \ne, \ge$
$a$ og $b$ eru eiginleikar (e. attributes) í $R$
$v$ er fast gildi.

Vörpun (e. projection)

Skilar vensli sem inniheldur allar hlut n-dir sem verða eftir þegar ákveðin eigindi eru fjarlægð úr vensli $R$. Táknað með $\Pi_{a_1, \ldots,a_n}( R )$ þar sem $a_1,\ldots,a_n$ eru þau eigindi sem standa eftir.

Földun (e. product)

Intersect

Union

Difference

Join

Divide

Tengingar

Náttúruleg tenging

Theta tenging

Ytri tenging

Vinstri ytri tenging ($⟖$)

Skorður og gikkir

Skorður

Skorður (e. contraints) eru notaðar til að takmarka hvaða gildi eindir mega taka.

Skorður á eindir

NOT NULL

UNIQUE

CHECK

Assertions

CREATE ASSERTION

Policies

Hafna aðgerðum
Cascade
Set NULL

Gikkir

Gikkir (e. triggers) eru aðgerðir sem eru framkvæmdar við ákveðna atburði (e. events)

CREATE
    [DEFINER = USER]
    TRIGGER trigger_name
    trigger_time trigger_event
    ON tbl_name FOR EACH ROW
    [trigger_order]
    trigger_body
 
trigger_time: { BEFORE | AFTER }
 
trigger_event: { INSERT | UPDATE | DELETE }
 
trigger_order: { FOLLOWS | PRECEDES } other_trigger_name

Dæmi

Í hvert sinn sem starfsmanni er bætt við fá núverandi starfsmenn launahækkun sem jafngildir 10% af launum nýja starfsmannsins.

CREATE TABLE salary (employee_id INT, salary DECIMAL(10,2));

CREATE TRIGGER salary_bonus
BEFORE INSERT ON salary
FOR EACH ROW 
    SET salary = salary + 0.1*NEW.salary;

Eininda-vensla líkön

Við hönnun á gagnagrunni er algengt að setja fram almennt líkan áður en það er útfært í ákveðnu SQL kerfi. Eininda-vensla líkön (e. entity-relation model) eru eitt dæmi um slíkt, gjarnan sett fram með einindavenslariti (e. E/R diagram)

Framsetning

Eininda-vensla líkön eru samansett úr eftirfarandi einingum

Einindi (e. entity) eru eins konar hlutir (e. objects) og eru táknuð með rétthyrningi
Eiginleikar (e. attribute) eru táknaðir með hringjum
Vensl (e. relationship) eru táknuð með tigli

Aðallykill er táknaður með undirstrikuðum nöfnum á eiginleikum.

Vensl

Vensl hafa vanalega skorður á fjölda. Algengasta gerðin af venslum eru tvíundarvensl sem eru sambönd á milli tveggja eininda.

1:1 tvíundarvensl (e. one-one binary relationship) eru táknuð með ör í báðar áttir
1:N tvíundarvensl (e. one-many binary relationship) eru táknuð með ör í átt að one einindinu
N:M tvíundarvensl (e. many-many binary relationship) eru táknuð án örva

Figure 2: Dæmi um einindavenslarit. Hér eru lyklar undirstrikaðir, tvöfaldi rétthyrningurinn er veikt einindi (e. weak entity) og tvöföldu tiglarnir eru skilgreinandi vensl (e. defining relationships)

Gagnagrunnskerfi

Hér verður farið í ýmsar tæknilegar hliðar á útfærslum gagnagrunnskerfa.

Færslur

Færslur (e. transactions)

Lásar

Lásar (e. locks).

Sjálfhelda

Sjálfhelda (e. dead-lock)

Ágæðun fyrirspurna

Lyklar

Aðgangsstýring

SQL fyrirspurnir

ANSI SQL

JDBC forritun

Connection

Statement createStatement()

Skilar Statement klasa.

PreparedStatement prepareStatement(String sql)

Tekur inn sql fyrirspurn sem inniheldur eitt eða fleiri spurningarmerki. Skilar PreparedStatement klasa.

Statement

ResultSet executeQuery(String sql)

Keyrir sql fyrirspurn og skilar niðurstöðum sem ResultSet klasa.

int executeUpdate(String sql)

Keyrir sql fyrirspurn sem skilar engu, t.d. INSERT, UPDATE eða DELETE. Skilar fjölda raða í niðurstöðu, vanalega núll.

void close()

Lokar á Statement og sleppir takinu af gagnagrunninum.

PreparedStatement

void setInt(int n, int x)

Gerir spurningarmerki númer $n$ að gildinu $x$. Skilar engu.

void setString(int n, String x)

Gerir spurningarmerki númer $n$ að gildinu $x$. Skilar engu.

ResultSet executeQuery()

Keyrir fyrirspurnina og skilar niðurstöðum.

int executeUpdate()

Keyrir fyrirspurnina og skilar fjölda raða í niðurstöðu. Yfirleitt notað fyrir INSERT, UPDATE og DELETE sem skila engu.

ResultSet

String getString(String columnLabel)

Skilar strengnum í dálki columnLabel úr núverandi röð.

int getInt(String columnLabel)

Skilar tölunni í dálki columnLabel úr núverandi röð.

boolean next()

Færir bendilinn (e. cursor) yfir á næstu röð og skilar true, annars false ef engin röð er eftir.

void close()

Lokar ResultSet og sleppir gagnagrunni.

Table of Contents

Gagnasafnsfræði

Bækur

Venslalíkanið

Fallaákveður

Lokanir

Lágþekjur

Frávik

BCNF þáttun

3NF þáttun

Taplausar tengingar

Chase prófið

Chase reikniritið

Varðveiting fallaákveða

Lyklar

Þrígild rökfræði

Reikniaðgerðir

Þrígild rökfræði

Venslaalgebra

Aðgerðir

Tengingar

Skorður og gikkir

Skorður

Skorður á eindir

Assertions

Policies

Gikkir

Dæmi

Eininda-vensla líkön

Framsetning

Vensl

Gagnagrunnskerfi

Færslur

Lásar

Sjálfhelda

Ágæðun fyrirspurna

Lyklar

Aðgangsstýring

SQL fyrirspurnir

JDBC forritun

Connection

Statement

PreparedStatement

ResultSet