Gagnasafnsfræði

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.

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

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ð

1. Skiptum fallaákveðunum niður þannig að hver þeirra hafi aðeins eitt eigindi á hægri hlið.
2. Látum $X$ tákna mengi sem verður á endanum að lokuninni. Setjum fyrst $X = \{A_1, A_2, \ldots , A_n\}$
3. 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$.

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

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

1. Byrjum með þekju $G$ og finnum lágþekju $F$, setjum fyrst $F = G$.
2. 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$.
3. 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$.

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.

1. Athugum hvort $R$ sé á BCNF formi. Ef svo er þarf ekki að fara lengra.
2. Finnum fallaákveðu $X \rightarrow Y$ sem brýtur á BCNF. Setjum $R_1 = X^+$ og $R_2 = (R \setminus X^+) \cup \{X\}$.
3. 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$.
4. Framkvæmum BCNF þáttun á $R_1, S_1$ og $R_2, S_2$ hvort fyrir sig.

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)

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

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

1. Eigindin ákvarða öll önnur eigindi í $R$ út frá gefnum fallaákveðum, þ.e. $A^+ = R$
2. 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$.

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)

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

Náttúruleg tenging

Náttúruleg tenging

Theta tenging

Ytri tenging

Vinstri ytri tenging ($⟖$)