====== 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ð =====

<WRAP box>

**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$.

</WRAP>

<WRAP box>

**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)$.

</WRAP>

<WRAP box>

**Eigindi** (e. attribute) 

Eigindi er nafn ásamt óðali. 

</WRAP>

<WRAP box>

**Óðal** (e. domain) 

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

</WRAP>

<figure>
{{:compsci:relational_model.png?600 }}
<caption>Hægt er að túlka vensli sem töflu, þar sem raðir svara til n-da og dálkar svara til eiginda.</caption>
</figure>
===== Fallaákveður =====

<WRAP box>

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

</WRAP>

<WRAP box>

**Setning** (samsetning fallaákveðna)

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

$$A_1 A_2 \ldots A_n -> B_1$$
$$A_1 A_2 \ldots A_n -> B_2$$
$$\vdots$$
$$A_1 A_2 \ldots A_n -> B_m$$
</WRAP>


==== Lokanir ====

<WRAP box>

**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 -> B$. Við táknum lokunina með $\{A_1, A_2, \ldots , A_n\}^+$

</WRAP>

<WRAP box>

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

</WRAP>

<WRAP box>

**Setning** (gegnvirkni á fallaákveðum)

Ef $A_1 A_2 \cdots A_n -> B_1 B_2 \cdots B_m$ og $B_1 B_2 \cdots B_m -> 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 -> C_1 C_2 \cdots C_k$$

</WRAP>


<WRAP box>

**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 -> A$ þar sem $A$ er bæði í $X^+$ og $R_1$.

</WRAP>

==== Lágþekjur ====

<WRAP box>

**Þ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$.

</WRAP>

<WRAP box>

**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 -> YZ$ verður $X -> Y$ og $X -> 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$.

</WRAP>
==== 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

<WRAP box>

**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 -> B_1 B_2 \cdots B_m$ á $R$ gildir að $\{A_1, A_2 , \ldots , A_n \}$ er yfirlykill fyrir $R$.

</WRAP>

<WRAP box>

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

</WRAP>

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

<WRAP box>

**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 -> 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$.

</WRAP>

<WRAP box>

**Reiknirit** (þáttun á 3NF form)

  - Finnum lágþekju fyrir $F$ og köllum hana $G$.
  - Fyrir hverja fallaákveðu $X -> 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)$.

</WRAP>
==== 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 =====

<WRAP box>

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

</WRAP>
<WRAP box>

**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$.

</WRAP>

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

<WRAP box>

**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)

</WRAP>

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 ====

<WRAP box>

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

</WRAP>
<WRAP box>

**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, ...,a_n}( R )$ þar sem $a_1,...,a_n$ eru þau eigindi sem standa eftir.

</WRAP>
<WRAP box>

**Földun** (e. product)

**Intersect**

**Union**

**Difference**

**Join**

**Divide**
</WRAP>

==== Tengingar ====

<WRAP box>
**Náttúruleg tenging**
</WRAP>

<WRAP box>
**Náttúruleg tenging**
</WRAP>

<WRAP box>
**Theta tenging**
</WRAP>

<WRAP box>
**Ytri tenging**

**Vinstri ytri tenging ($⟖$)** 

</WRAP>

===== 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)

<code sql>
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
</code>

=== Dæmi ===

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

<code sql>
CREATE TABLE salary (employee_id INT, salary DECIMAL(10,2));
</code>
<code sql>
CREATE TRIGGER salary_bonus
BEFORE INSERT ON salary
FOR EACH ROW 
    SET salary = salary + 0.1*NEW.salary;
</code>

===== 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>
{{ :compsci:er_diagram.png?600 |}}
<caption>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) </caption>
</figure>
===== 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.