Functionele afhankelijkheid - Functional dependency

In relationele databasetheorie is een functionele afhankelijkheid een beperking tussen twee sets attributen in een relatie uit een database. Met andere woorden, een functionele afhankelijkheid is een beperking tussen twee sleutels. Gegeven een verhouding R en sets attributen , X wordt gezegd functioneel bepalen op Y (schriftelijke X → Y ) dan en slechts dan indien elke X waarde R is geassocieerd met precies één Y waarde R ; Er wordt dan gezegd dat R voldoet aan de functionele afhankelijkheid X → Y . Op equivalente wijze is de projectie een Functie , dwz Y is een functie van X . In eenvoudige bewoordingen, als de waarden voor de X- attributen bekend zijn (zeg dat ze x zijn ), dan kunnen de waarden voor de Y- attributen die overeenkomen met x worden bepaald door ze op te zoeken in een tupel van R die x bevat . Gewoonlijk wordt X de determinantenverzameling genoemd en Y de afhankelijke verzameling. Een functionele afhankelijkheid FD: X → Y wordt triviaal genoemd als Y een subset is van X . ${\ Displaystyle X, Y \ subseteq R}$ ${\displaystyle \Pi _{X,Y}R}$

Met andere woorden, een afhankelijkheid FD: X → Y betekent dat de waarden van Y worden bepaald door de waarden van X . Twee tupels die dezelfde waarden van X delen, zullen noodzakelijkerwijs dezelfde waarden van Y hebben .

Het bepalen van functionele afhankelijkheden is een belangrijk onderdeel van het ontwerpen van databases in het relationele model , en bij databasenormalisatie en denormalisatie . Een eenvoudige toepassing van functionele afhankelijkheden is de stelling van Heath ; er staat dat een relatie R over een attribuutverzameling U en die voldoet aan een functionele afhankelijkheid X → Y veilig kan worden gesplitst in twee relaties met de lossless-join decomposition- eigenschap, namelijk in waar Z = U − XY de rest van de attributen zijn. ( Unionen van attributensets worden gewoonlijk aangeduid met louter nevenschikkingen in databasetheorie.) Een belangrijk begrip in deze context is een kandidaatsleutel , gedefinieerd als een minimale set attributen die functioneel alle attributen in een relatie bepaalt. De functionele afhankelijkheden, samen met de attribuutdomeinen , zijn zodanig geselecteerd dat er beperkingen worden gegenereerd die zoveel mogelijk gegevens die ongepast zijn voor het gebruikersdomein uit het systeem zouden uitsluiten . ${\ Displaystyle \ Pi _ {XY} (R) \ vlinderdas \ Pi _ {XZ} (R) = R}$

Een notie van logische implicatie wordt als volgt gedefinieerd voor functionele afhankelijkheden: een reeks functionele afhankelijkheden impliceert logischerwijs een andere reeks afhankelijkheden , als een relatie R die voldoet aan alle afhankelijkheden van ook voldoet aan alle afhankelijkheden van ; dit is meestal geschreven . De notie van logische implicatie voor functionele afhankelijkheden laat een degelijke en volledige eindige axiomatisering toe , bekend als de axioma's van Armstrong . ${\displaystyle \Sigma}$${\displaystyle \gamma}$${\displaystyle \Sigma}$${\displaystyle \gamma}$${\ Displaystyle \ Sigma \ modellen \ Gamma }$

Voorbeelden

auto's

Stel dat men een systeem ontwerpt om voertuigen en de capaciteit van hun motoren te volgen. Elk voertuig heeft een uniek voertuigidentificatienummer (VIN). Men zou VIN → EngineCapacity schrijven omdat het ongepast zou zijn voor de motor van een voertuig om meer dan één capaciteit te hebben. (Ervan uitgaande dat in dit geval voertuigen maar één motor hebben.) Aan de andere kant is EngineCapacity → VIN onjuist omdat er veel voertuigen kunnen zijn met hetzelfde motorvermogen.

Deze functionele afhankelijkheid kan erop wijzen dat het attribuut EngineCapacity in een relatie wordt geplaatst met kandidaatsleutel VIN. Dat is echter niet altijd gepast. Als die functionele afhankelijkheid bijvoorbeeld optreedt als gevolg van de transitieve functionele afhankelijkheden VIN → VehicleModel en VehicleModel → EngineCapacity, dan zou dat niet resulteren in een genormaliseerde relatie.

lezingen

Dit voorbeeld illustreert het concept van functionele afhankelijkheid. De gemodelleerde situatie is die van studenten die een of meer colleges bezoeken waarin ze elk een onderwijsassistent (TA) krijgen toegewezen. Laten we verder aannemen dat elke student in een bepaald semester zit en wordt geïdentificeerd door een uniek geheel getal-ID.

We merken dat wanneer twee rijen in deze tabel dezelfde StudentID bevatten, ze ook noodzakelijkerwijs dezelfde Semester-waarden hebben. Dit basisfeit kan worden uitgedrukt door een functionele afhankelijkheid:

• StudentID → Semester.

Merk op dat als een rij werd toegevoegd waar de student een andere waarde van semester had, de functionele afhankelijkheid FD niet langer zou bestaan. Dit betekent dat de FD wordt geïmpliceerd door de gegevens, aangezien het mogelijk is om waarden te hebben die de FD ongeldig maken.

Andere niet-triviale functionele afhankelijkheden kunnen worden geïdentificeerd, bijvoorbeeld:

• {StudentID, Lezing} → TA
• {StudentID, College} → {TA, Semester}

Dit laatste drukt het feit uit dat de verzameling {StudentID, Lecture} een supersleutel is van de relatie.

Medewerker afdelingsmodel

Een klassiek voorbeeld van functionele afhankelijkheid is het werknemersafdelingsmodel.

Dit geval vertegenwoordigt een voorbeeld waarbij meerdere functionele afhankelijkheden zijn ingebed in een enkele representatie van gegevens. Houd er rekening mee dat, omdat een medewerker slechts lid kan zijn van één afdeling, de unieke ID van die medewerker de afdeling bepaalt.

• Werknemers-ID → Naam werknemer
• Werknemers-ID → Afdelings-ID

Naast deze relatie heeft de tabel ook een functionele afhankelijkheid door middel van een niet-sleutelattribuut

• Afdelings-ID → Afdelingsnaam

Dit voorbeeld laat zien dat, hoewel er een FD Werknemers-ID → Afdelings-ID bestaat, het werknemers-ID geen logische sleutel zou zijn voor het bepalen van het afdelings-ID. Het proces van normalisatie van de gegevens zou alle FD's herkennen en de ontwerper in staat stellen tabellen en relaties te construeren die logischer zijn op basis van de gegevens.

Eigenschappen en axiomatisering van functionele afhankelijkheden

Gegeven dat X , Y en Z sets attributen zijn in een relatie R , kan men verschillende eigenschappen van functionele afhankelijkheden afleiden. Een van de belangrijkste zijn de volgende, gewoonlijk de axioma's van Armstrong genoemd :

• Reflexiviteit : Als Y een deelverzameling is van X , dan is X → Y
• Augmentatie : Als X → Y , dan XZ → YZ
• Transitiviteit : Als X → Y en Y → Z , dan is X → Z

"Reflexiviteit" kan worden afgezwakt tot gewoon , dwz het is een feitelijk axioma , waarbij de andere twee juiste inferentieregels zijn , die meer bepaald aanleiding geven tot de volgende regels van syntactische consequentie: ${\displaystyle X\rightarrow \varnothing}$

${\displaystyle \vdash X\rightarrow \varnothing}$
${\displaystyle X\rightarrow Y\vdash XZ\rightarrow YZ}$
${\ Displaystyle X \ rightarrow Y, Y \ rightarrow Z \ vdash X \ rightarrow Z}$.

Deze drie regels zijn een degelijke en volledige axiomatisering van functionele afhankelijkheden. Deze axiomatisering wordt soms beschreven als eindig omdat het aantal afleidingsregels eindig is, met het voorbehoud dat het axioma en de afleidingsregels allemaal schema's zijn , wat betekent dat de X , Y en Z variëren over alle grondtermen (attribuutverzamelingen).

Door augmentatie en transitiviteit toe te passen, kan men twee aanvullende regels afleiden:

• Pseudotransitiviteit : Als X → Y en YW → Z , dan XW → Z
• Samenstelling : Als X → Y en Z → W , dan is XZ → YW

Men kan de unie- en decompositieregels ook afleiden uit de axioma's van Armstrong:

X → Y en X → Z als en slechts als X → YZ

Sluiting van functionele afhankelijkheid

De sluiting is in wezen de volledige reeks waarden die kan worden bepaald uit een reeks bekende waarden voor een gegeven relatie met behulp van de functionele afhankelijkheden. Men gebruikt de axioma's van Armstrong om een ​​bewijs te leveren - dwz reflexiviteit, augmentatie, transitiviteit.

Gegeven en een set FD's die geldt in : De sluiting van in (aangeduid met ⁺ ) is de verzameling van alle FD's die logisch worden geïmpliceerd door . ${\displaystyle R}$${\displaystyle F}$${\displaystyle R}$${\displaystyle F}$${\displaystyle R}$${\displaystyle F}$${\displaystyle F}$

Sluiting van een set attributen

Afsluiting van een set attributen X ten opzichte van is de set X ⁺ van alle attributen die functioneel bepaald worden door X met behulp van ⁺ . ${\displaystyle F}$${\displaystyle F}$

Voorbeeld

Stel je de volgende lijst met FD's voor. Uit deze relatie gaan we een afsluiting voor A berekenen.

1. A → B
2. B → C 3. AB → D

De sluiting zou als volgt zijn:

a) A → A (door de reflexiviteit van Armstrong)
b) A → AB (door 1. en (a))
c) A → ABD (door (b), 3 en de transitiviteit van Armstrong)
d) A → ABCD (door (c ), en 2)

De sluiting is dus A → ABCD. Door de sluiting van A te berekenen, hebben we gevalideerd dat A ook een goede kandidaatsleutel is, aangezien de sluiting elke afzonderlijke gegevenswaarde in de relatie is.

Omslagen en gelijkwaardigheid

Hoezen

Definitie : dekt als elke FD in kan worden afgeleid . covers if ⁺ ⊆ ⁺ Elke reeks functionele afhankelijkheden heeft een canonieke dekking . ${\displaystyle F}$${\displaystyle G}$${\displaystyle G}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle G}$${\displaystyle F}$

Gelijkwaardigheid van twee sets FD's

Twee sets FD's en meer schema's zijn equivalent, geschreven ≡ , als ⁺ = ⁺ . Als ≡ , dan is een dekking voor en vice versa. Met andere woorden, equivalente sets van functionele afhankelijkheden worden deklagen van elkaar genoemd. ${\displaystyle F}$${\displaystyle G}$${\displaystyle R}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$

Niet-redundante covers

Een set van FDs is redundante als er geen goede deelverzameling van met ≡ . Als een dergelijke bestaat, is overbodig. is een niet-redundante dekking voor if is een dekking voor en is niet-overtollig. Een andere karakterisering van nonredundancy dat is redundante als er geen FD X → Y in dat - { X → Y } X → Y . Bel een FD X → Y in overbodig indien - { X → Y } X → Y . ${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$
${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle \modellen}$ ${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle \modellen}$

Toepassingen op normalisatie

stelling van Heath

Een belangrijke eigenschap (hetgeen een onmiddellijke toepassing) functionele afhankelijkheden is dat als R een relatie met zuilen genoemd van enkele set attributen U en R voldoet aantal functionele afhankelijkheid X → Y dan waarin Z = U - XY . Intuïtief, als een functionele afhankelijkheid X → Y geldt in R , dan kan de relatie veilig worden gesplitst in twee relaties naast de kolom X (wat een sleutel is voor ) om ervoor te zorgen dat wanneer de twee delen worden samengevoegd, er geen gegevens verloren gaan, dwz een functionele afhankelijkheid biedt een eenvoudige manier om een lossless join-decompositie van R in twee kleinere relaties te construeren . Dit feit wordt soms de stelling van Heath genoemd ; het is een van de eerste resultaten in de databasetheorie. ${\displaystyle R=\Pi _{XY}(R)\vlinderdas \Pi _{XZ}(R)}$${\ Displaystyle \ Pi _ {XY} (R) \ vlinderdas \ Pi _ {XZ} (R)}$

De stelling van Heath zegt in feite dat we de waarden van Y uit de grote relatie R kunnen halen en ze in één kunnen opslaan , die geen waardeherhalingen in de rij voor X heeft en in feite een opzoektabel is voor Y gesleuteld door X en bijgevolg slechts één heeft plaats om de Y bij te werken die overeenkomt met elke X, in tegenstelling tot de "grote" relatie R waar er mogelijk veel kopieën van elke X zijn , elk met zijn kopie van Y die bij updates gesynchroniseerd moet worden gehouden. (Deze eliminatie van redundantie is een voordeel in OLTP- contexten, waar veel veranderingen worden verwacht, maar niet zozeer in OLAP- contexten, die voornamelijk vragen bevatten.) Heath's decompositie laat alleen X als externe sleutel fungeren in de rest van de grote tabel . ${\displaystyle \Pi _{XY}(R)}$${\displaystyle \Pi _{XZ}(R)}$

Functionele afhankelijkheden moeten echter niet worden verward met inclusieafhankelijkheden , wat het formalisme is voor externe sleutels; hoewel ze worden gebruikt voor normalisatie, drukken functionele afhankelijkheden beperkingen uit over één relatie (schema), terwijl inclusieafhankelijkheden beperkingen uitdrukken tussen relatieschema's in een databaseschema . Bovendien kruisen de twee begrippen elkaar niet eens in de classificatie van afhankelijkheden : functionele afhankelijkheden zijn afhankelijkheden die gelijkheid genereren, terwijl inclusie-afhankelijkheden tupel-genererende afhankelijkheden zijn . Het afdwingen van referentiële beperkingen na ontleding van relatieschema's (normalisatie) vereist een nieuw formalisme, namelijk inclusie-afhankelijkheden. In de ontleding die voortvloeit uit de stelling van Heath, is er niets dat het invoegen van tupels verhindert met een waarde van X die niet wordt gevonden in . ${\displaystyle \Pi _{XZ}(R)}$${\displaystyle \Pi _{XY}(R)}$

Normale vormen

Normale vormen zijn databasenormalisatieniveaus die de "goedheid" van een tabel bepalen. Over het algemeen wordt de derde normaalvorm beschouwd als een "goede" standaard voor een relationele database.

Normalisatie is bedoeld om de database te bevrijden van anomalieën bij het bijwerken, invoegen en verwijderen. Het zorgt er ook voor dat wanneer een nieuwe waarde in de relatie wordt geïntroduceerd, dit een minimaal effect heeft op de database en dus minimaal effect op de toepassingen die de database gebruiken.

Onherleidbare functie afhankelijk set

Een verzameling S van functionele afhankelijkheden is irreducibel als de verzameling de volgende drie eigenschappen heeft:

1. Elke set rechten van een functionele afhankelijkheid van S bevat slechts één attribuut.
2. Elke linker set van een functionele afhankelijkheid van S is onherleidbaar. Het betekent dat het verminderen van een attribuut uit de linkerset de inhoud van S zal veranderen (S zal wat informatie verliezen).
3. Het verminderen van functionele afhankelijkheid zal de inhoud van S.

Sets van functionele afhankelijkheden met deze eigenschappen worden ook wel canoniek of minimaal genoemd . Het vinden van zo'n verzameling S van functionele afhankelijkheden die equivalent is aan een invoerverzameling S' die als invoer wordt geleverd, wordt het vinden van een minimale dekking van S' genoemd: dit probleem kan in polynomiale tijd worden opgelost.

Zie ook

• Achtervolging (algoritme)
• afhankelijkheid van inclusie
• Deelnemen aan afhankelijkheid
• Meerwaardige afhankelijkheid (MVD)
• Database normalisatie
• Eerste normaalvorm

Referenties

Externe links

• Gary Burt (zomer 1999). "CS 461 (Database Management Systems) collegeaantekeningen" . Universiteit van Maryland Baltimore County Afdeling Computerwetenschappen en Elektrotechniek.
• Jeffrey D.Ullman. "CS345 Lecture Notes" ( PostScript ) . Stanford universiteit.
• Osmar Zaiane (9 juni 1998). "Hoofdstuk 6: Integriteitsbeperkingen" . CMPT 354 (Database Systems I) collegeaantekeningen . Simon Fraser University Afdeling Informatica.