Funkcionális függőség (programozás)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. június 30-án áttekintett verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

A funkcionális függőség egy bináris kapcsolat egy adott kapcsolat attribútumkészletei között , és valójában egy a többhez kapcsolat. Használata annak a ténynek köszönhető, hogy lehetővé teszi számos probléma formális és szigorú megoldását.

A funkcionális függőség olyan fogalom, amely számos, a relációs adatbázisokkal kapcsolatos kérdés hátterében áll , beleértve különösen a tervezésüket.

Definíciók

Funkcionális függőség

Legyen egy reláció adott sémával (fejléc) , és legyen a reláció attribútumkészletének néhány részhalmaza . Egy halmaz funkcionálisan attól függ , hogy a halmaz minden értéke pontosan a halmaz egy értékéhez van-e társítva . Kijelölve . $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $A-tól B-ig$

Más szóval, ha két sor azonos értékkel rendelkezik -ben , akkor azonos értéke van -ben . $A$ $B$

r\left(R\right),\ A\subseteq R,\ B\subseteq R

\left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t} _{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B \right)={{t}_{2}}\left(B\right)\right)\right)

Ebben az esetben a determináns a függő rész. $A$ $B$

A funkcionális függőséget triviálisnak mondjuk, ha a függő rész a determináns részhalmaza.

\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)

Függőségcsoport bezárása

Egyes funkcionális függőségek más funkcionális függőségekre is utalhatnak. Például funkcionális függőség,

\left(A\to B\right)\wedge \left(B\to C\jobbra)\Jobbra \balra(A\C\jobbra)

Az összes funkcionális függőség halmazát, amelyet a funkcionális függőségek adott halmaza tartalmaz , a halmaz lezárásának nevezzük . ${{S}^{+}}$ $S$ $S$

Attribútumkészlet lezárása

Legyen a reláció attribútumainak valamilyen halmaza , és legyen ennek a relációnak a funkcionális függőségeinek halmaza. Az attribútumhalmaz határokon belüli zárása a reláció összes attribútumának olyan halmaza, hogy a funkcionális függőség a zárás tagja . $Z$ $r$ $S$ ${{Z}^{+}}$ $Z$ $S$ ${{A}_{i))$ $r$ $Z\to {{A}_{i))$ ${{S}^{+}}$

r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}

{{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\jobbra)\in {{S }^{+}}\jobbra\}

A függőségek irreducibilis halmazai

Legyen és legyen néhány funkcionális függőségi halmaz. ${{S}_{1}}$ ${{S}_{2))$

Ha bármilyen funkcionális függőség -ból belép és -be , akkor a funkcionális függőségek halmazának fedőjét nevezzük . ${{S}_{1}}$ ${{S}_{2}^{+}}$ ${{S}_{2))$ ${{S}_{1}}$
Ha a borítója , és a borítója (vagyis ), akkor az ilyen halmazokat ekvivalensnek nevezzük . ${{S}_{2))$ ${{S}_{1}}$ ${{S}_{1}}$ ${{S}_{2))$ ${\displaystyle S_{1}^{+}=S_{2}^{+))$
A funkcionális függőségek egy halmazát akkor és csak akkor nevezzük redukálhatatlannak , ha a következő feltételek teljesülnek: $S$
- Minden funkcionális függőségben a függő rész csak egy elemet tartalmaz;
- Minden funkcionális függőség determinánsa irreducibilis (egy attribútum sem távolítható el a determinánsból a lezárás megváltoztatása nélkül ); ${{S}^{+}}$
- Egyik funkcionális függőség sem szüntethető meg a záróelem megváltoztatása nélkül . $S$ ${{S}^{+}}$
A funkcionális függőségek bármely halmazához van legalább egy ekvivalens halmaz, amely nem redukálható. Az ilyen ekvivalens halmazt irreducibilis borításnak nevezzük .

Lezárás értékelése

Armstrong következtetési szabályai

1974-ben William Armstrong egy olyan szabályrendszert javasolt, amellyel az adatokból új funkcionális függőségekre lehet következtetni.

Tegyük fel, hogy van egy relációnk és egy attribútumkészletünk . A rekord lerövidítéséhez egyszerűen ezt fogjuk írni . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Reflexivitás : $\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)$
Utánpótlás : $\left(A\to B\right)\Rightarrow \left(AC\to BC\right)$
Tranzitivitás : $\left(A\to B\right)\wedge \left(B\to C\jobbra)\Jobbra \balra(A\C\jobbra)$

Armstrong következtetési szabályai teljesek (felhasználásukból származtathatóak az adott halmaz összes többi funkcionális függősége) és megbízhatóak ("felesleges" funkcionális függőségek nem vezethetők le: a származtatott funkcionális függőség mindenhol érvényes, ahol az eredeti funkcionális függőségek (ahonnan származott származtatott) érvényesek).

Ezenkívül számos további szabály egész egyszerűen levezethető ezekből a szabályokból, amelyek leegyszerűsítik a funkcionális függőségek levezetésének feladatát.

Önrendelkezés : $A\to A$
Bomlás : $\left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)$
Konszolidáció : $\left(A\to B\right)\wedge \left(A\to C\right)\Rightarrow \left(A\to BC\right)$
Összetétel : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)$
Darwen univerzális egyesítési tétele : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(CB\right)\to BD\right)$

Tétel: A funkcionális függőségek adott halmazából az Armstrong-féle következtetési szabályok szerint akkor és csak akkor következtetünk funkcionális függőséget . $A-tól B-ig$ $S$ $B\subseteq {{A}^{+}}$

Attribútumkészlet lezárása

Ha az előző szakasz szabályait addig alkalmazzuk, amíg az új funkcionális függőségek létrehozása magától meg nem áll, akkor egy adott funkcionális függőségi halmazra egy lezárást kapunk. A gyakorlatban ritkán szükséges önmagában kiszámítani ezt a zárást, leggyakrabban sokkal inkább az érdekel minket, hogy ez vagy az a funkcionális függőség benne lesz-e a zárásban. Ehhez elég kiszámolnunk a determináns zárását. Erre van egy meglehetősen egyszerű algoritmus.

Legyen attribútumok halmaza, amely végül lezárássá válik. $x$
Megkeressük a , ahol és a formák funkcionális függőségeit . Minden talált függőség függő részét hozzáadjuk a -hoz . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\not \subset X$ $x$
Addig ismételje a 2. lépést, amíg nem lehet attribútumokat hozzáadni a készlethez. $x$
Az a készlet , amelyhez nem lehet attribútumokat hozzáadni, lezárás lesz. $x$

Alkalmazás

Adatbázis tervezés

A funkcionális függőségek integritási megkötések, és meghatározzák az adatbázisban tárolt adatok szemantikáját. A DBMS -nek minden frissítéskor ellenőriznie kell a megfelelőséget. Ezért a nagyszámú funkcionális függőség jelenléte nem kívánatos, ellenkező esetben lelassítja a munkát. A feladat egyszerűsítése érdekében szükséges a funkcionális függőségek halmazát a minimálisra csökkenteni.

Az If a funkcionális függőségek kezdeti halmazának redukálhatatlan fedője , akkor a funkcionális függőségek teljesülésének ellenőrzése -ból automatikusan garantálja az összes funkcionális függőség teljesülését -ból . Így a minimálisan szükséges halmaz megtalálásának feladata a funkcionális függőségek halmazának egy irreducibilis fedőjének megtalálására redukálódik, amelyet az eredeti halmaz helyett használunk. $én$ $S$ $én$ $S$

Lásd még

Relációs adatmodell
Adatbázis tervezés
normál forma
A többértékű függőség a funkcionális függőség általánosítása.

Irodalom

K. J. Dátum. Bevezetés az adatbázisrendszerekbe = Introduction to Database Systems. - 8. kiadás - M . : "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .