Toiminnallinen riippuvuus (ohjelmointi)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. kesäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 13 muokkausta .

Funktionaalinen riippuvuus on binäärisuhde tietyn suhteen attribuuttijoukkojen välillä ja on itse asiassa yksi-moneen-suhde. Sen käyttö johtuu siitä, että sen avulla voit muodollisesti ja tiukasti ratkaista monia ongelmia.

Toiminnallinen riippuvuus on käsite, joka on monien relaatiotietokantoihin liittyvien ongelmien taustalla , mukaan lukien erityisesti niiden suunnittelu.

Määritelmät

Toiminnallinen riippuvuus

Olkoon relaatio annettu skeemalla (otsikko) , ja se on joitain alijoukkoja suhteen attribuuttijoukosta . Joukko on toiminnallisesti riippuvainen siitä, jos ja vain jos jokainen joukon arvo liittyy täsmälleen yhteen joukon arvoon . Nimetty . $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $A:sta B:hen$

Toisin sanoen, jos kahdella monikolla on sama arvo kohdassa , niin niillä on sama arvo . $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)

Tässä tapauksessa determinantti on riippuvainen osa. $A$ $B$

Toiminnallisen riippuvuuden sanotaan olevan triviaali , jos riippuvainen osa on determinantin osajoukko.

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

Riippuvuusjoukon sulkeminen

Jotkut toiminnalliset riippuvuudet voivat tarkoittaa muita toiminnallisia riippuvuuksia. Esimerkiksi toiminnallinen riippuvuus,

\left(A\to B\oikea)\kiila \vasen(B\C\oikealle)\Oikeanuoli \vasen(A\C\oikealle)

Kaikkien funktionaalisten riippuvuuksien joukkoa , jotka tietty funktionaalisten riippuvuuksien joukko sisältää, kutsutaan joukon sulkemiseksi . ${{S}^{+}}$ $S$ $S$

Attribuuttijoukon sulkeminen

Antaa olla jokin joukko attribuutteja suhteessa , ja olla joukko toiminnallisia riippuvuuksia tämän suhteen. Attribuuttijoukon sulkeminen rajojen sisällä on sellainen joukko suhteen kaikkia attribuutteja, että funktionaalinen riippuvuus on sulkemisen jäsen . $Z$ $r$ $S$ ${{Z}^{+}}$ $Z$ $S$ ${\näyttötyyli {{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}}\oikealle)\in {{S }^{+}}\oikea\}

Redusoitumattomat riippuvuusjoukot

Olkoon ja joitain funktionaalisten riippuvuuksien joukkoja. ${{S}_{1}}$ ${{S}_{2))$

Jos jokin toiminnallinen riippuvuus tulee sisään ja sisään , niin funktionaalisten riippuvuuksien joukon peittoa kutsutaan . ${{S}_{1}}$ ${{S}_{2}^{+}}$ ${{S}_{2))$ ${{S}_{1}}$
Jos on kansi , ja on kansi (eli ), niin tällaisia joukkoja kutsutaan vastaaviksi . ${{S}_{2))$ ${{S}_{1}}$ ${{S}_{1}}$ ${{S}_{2))$ ${\displaystyle S_{1}^{+}=S_{2}^{+))$
Joukon toiminnallisia riippuvuuksia sanotaan olevan redusoitumattomia , jos ja vain, jos seuraavat ehdot täyttyvät: $S$
- Jokaisessa toiminnallisessa riippuvuudessa riippuvainen osa sisältää vain yhden elementin;
- Jokaisen toiminnallisen riippuvuuden determinantti on redusoitumaton (mitään attribuuttia ei voida poistaa determinantista muuttamatta sulkemista ); ${{S}^{+}}$
- Mitään toiminnallisista riippuvuuksista ei voida poistaa muuttamatta sulkemista . $S$ ${{S}^{+}}$
Jokaiselle toiminnallisten riippuvuuksien joukolle on vähintään yksi vastaava joukko, joka on redusoitumaton. Tällaista vastaavaa joukkoa kutsutaan redusoitumattomaksi kanneksi .

Sulkemisen arviointi

Armstrongin päättelysäännöt

William Armstrong ehdotti vuonna 1974 sääntöjä uusien toiminnallisten riippuvuuksien päättelemiseksi tiedoista.

Oletetaan, että meillä on relaatio ja joukko attribuutteja . Tietueen lyhentämiseksi kirjoitamme sen sijaan yksinkertaisesti . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Heijastuskyky : $\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)$
Täydennys : $\left(A\to B\right)\Rightarrow \left(AC\to BC\right)$
Transitiivisuus : $\left(A\to B\oikea)\kiila \vasen(B\C\oikealle)\Oikeanuoli \vasen(A\C\oikealle)$

Armstrongin päättelysäännöt ovat täydellisiä (niitä käyttämällä voidaan johtaa kaikki muut annetun joukon sisältämät toiminnalliset riippuvuudet) ja luotettavia ("ylimääräisiä" toiminnallisia riippuvuuksia ei voida päätellä: johdettu toiminnallinen riippuvuus pätee kaikkialla, missä alkuperäiset toiminnalliset riippuvuudet (joista se on peräisin) johdettu) ovat voimassa).

Lisäksi näistä säännöistä johdetaan yksinkertaisesti useita lisäsääntöjä, jotka yksinkertaistavat toiminnallisten riippuvuuksien johtamista.

Itsemääräämisoikeus : $A\to A$
Hajoaminen : $\left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)$
Konsolidointi : $\left(A\to B\oikealle)\kiila \vasen(A\C\oikealle)\Oikeanuoli \vasen(A\BC\oikealle)$
Koostumus : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)$
Darwenin universaali yhdistämislause : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(CB\right)\to BD\right)$

Lause: Funktionaalinen riippuvuus päätellään tietystä funktionaalisten riippuvuuksien sarjasta Armstrongin päättelysääntöjen mukaisesti silloin ja vain jos . $A:sta B:hen$ $S$ $B\subseteq {{A}^{+}}$

Attribuuttijoukon sulkeminen

Jos käytämme edellisen osan sääntöjä, kunnes uusien toiminnallisten riippuvuuksien luominen pysähtyy itsestään, saamme sulkemisen tietylle toiminnallisten riippuvuuksien joukolle. Käytännössä tätä sulkeutumista on harvoin tarpeen laskea itsestään, useimmiten olemme paljon kiinnostuneempia siitä, sisällytetäänkö tämä tai toinen toiminnallinen riippuvuus sulkemiseen. Tätä varten riittää, että laskemme determinantin sulkemisen. Tähän on olemassa melko yksinkertainen algoritmi.

Antaa olla joukko attribuutteja, joista tulee lopulta sulkeminen. $X$
Etsimme funktionaalisia riippuvuuksia muodoista , missä ja . Lisäämme jokaisen löydetyn riippuvuuden riippuvaisen osan arvoon . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\not \subset X$ $X$
Toista vaihetta 2, kunnes määritteiden lisääminen joukkoon on mahdotonta. $X$
Joukko , johon ei voi lisätä määritteitä, on sulkeminen. $X$

Sovellus

Tietokannan suunnittelu

Toiminnalliset riippuvuudet ovat eheysrajoituksia ja määrittävät tietokantaan tallennetun tiedon semantiikan. DBMS :n on jokaisen päivityksen yhteydessä tarkistettava niiden yhteensopivuus. Siksi suuren määrän toiminnallisia riippuvuuksia ei ole toivottavaa, muuten se hidastaa työtä. Tehtävän yksinkertaistamiseksi on tarpeen vähentää toiminnallisten riippuvuuksien joukko vaadittuun vähimmäismäärään.

If on toiminnallisten riippuvuuksien alkujoukon redusoitumaton peite , niin toiminnallisten riippuvuuksien täyttymisen tarkistaminen osoitteesta takaa automaattisesti kaikkien toiminnallisten riippuvuuksien täyttymisen kohteesta . Siten tehtävä löytää tarvittava vähimmäisjoukko rajoittuu toiminnallisten riippuvuuksien joukolle pelkistymättömän peitteen löytämiseen, jota käytetään alkuperäisen joukon sijaan. $minä$ $S$ $minä$ $S$

Katso myös

Relaatiotietomalli
Tietokannan suunnittelu
normaali muoto
Moniarvoinen riippuvuus on yleistys toiminnallisesta riippuvuudesta.

Kirjallisuus

K. J. Päivämäärä. Johdatus tietokantajärjestelmiin = Tietokantajärjestelmien esittely. - 8. painos - M . : "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .