Zależność funkcjonalna

W teorii relacyjnych baz danych zależność funkcjonalna to ograniczenie między dwoma zestawami atrybutów w relacji z bazy danych. Innymi słowy, zależność funkcjonalna to ograniczenie między dwoma atrybutami w relacji. Biorąc pod uwagę relację R i zestawy atrybutów $każda$ mówi się, że X funkcjonalnie określa Y (zapisane X → Y wtedy i tylko wtedy , gdy wartość R jest z dokładnie jedna wartość Y w R ; Mówi się wtedy, że R spełnia zależność funkcyjną X → Y . Równoważnie projekcja jest funkcją , tj $Y$ _ _ _ Mówiąc prościej, jeśli znane są wartości X (powiedzmy, że są to x ), to wartości atrybutów Y odpowiadające x można określić, wyszukując je w dowolnej krotce R zawierającej x . Zwyczajowo X nazywa się zbiorem wyznacznikowym , a Y zbiorem zależnym . Zależność funkcjonalną FD: X → Y nazywamy trywialną , jeśli Y jest podzbiorem X .

Innymi słowy, zależność FD: X → Y oznacza, że wartości Y są określone przez wartości X . Dwie krotki dzielące te same wartości X będą koniecznie miały te same wartości Y .

Określenie zależności funkcjonalnych jest ważną częścią projektowania baz danych w modelu relacyjnym oraz normalizacji i denormalizacji baz danych . Prostym zastosowaniem zależności funkcyjnych jest twierdzenie Heatha ; mówi, że relację R nad zbiorem atrybutów U i spełniającą zależność funkcyjną X → Y można bezpiecznie podzielić na dwie relacje mające właściwość dekompozycji bezstratnego łączenia , a mianowicie na ${\ Displaystyle \ Pi _ {XY} (R) \ muszka \ Pi _ {XZ} (R) = R}$ gdzie Z = U - XY to pozostałe atrybuty. ( sumy zestawów atrybutów są zwykle oznaczane przez zwykłe zestawienia). Ważnym pojęciem w tym kontekście jest klucz kandydujący , definiowany jako minimalny zestaw atrybutów, który funkcjonalnie określa wszystkie atrybuty w relacji. Zależności funkcjonalne wraz z domenami atrybutów są dobierane tak, aby generować ograniczenia, które wykluczałyby z systemu jak najwięcej danych nieodpowiednich dla domeny użytkownika.

Pojęcie implikacji logicznej definiuje się dla zależności funkcjonalnych w następujący sposób: zbiór zależności funkcjonalnych $Σ$ ${\ displaystyle \ Sigma}$ inny zestaw zależności , jeśli jakakolwiek relacja $R$ wszystkie zależności od również spełnia wszystkie zależności od ${\ displaystyle \ Gamma}$ ; zwykle jest to napisane ${\ Displaystyle \ Sigma \ modele \ Gamma}$ . Pojęcie implikacji logicznych dla zależności funkcyjnych dopuszcza solidną i pełną skończoną aksjomatyzację , znaną jako aksjomaty Armstronga .

Przykłady

Samochody

Załóżmy, że ktoś projektuje system do śledzenia pojazdów i pojemności ich silników. Każdy pojazd posiada unikalny numer identyfikacyjny pojazdu (VIN). Można by napisać VIN → EngineCapacity , ponieważ byłoby niewłaściwe, aby silnik pojazdu miał więcej niż jedną pojemność. (Zakładając w tym przypadku, że pojazdy mają tylko jeden silnik.) Z drugiej strony, EngineCapacity → VIN jest niepoprawne, ponieważ może być wiele pojazdów o tej samej pojemności silnika.

Ta zależność funkcjonalna może sugerować umieszczenie atrybutu EngineCapacity w relacji z kluczem kandydującym VIN. Jednak nie zawsze może to być właściwe. Na przykład, jeśli ta zależność funkcjonalna występuje w wyniku przejściowych zależności funkcjonalnych VIN → VehicleModel i VehicleModel → EngineCapacity, to nie skutkowałoby to znormalizowaną relacją.

Wykłady

Ten przykład ilustruje koncepcję zależności funkcjonalnej. Modelowana sytuacja dotyczy studentów uczęszczających na jeden lub więcej wykładów, na każdym z których przydzielono im asystenta nauczyciela (AT). Załóżmy dalej, że każdy student jest w jakimś semestrze i jest identyfikowany przez unikalny identyfikator całkowity.

legitymacja studencka	Semestr	Wykład	TA
1234	6	Metody numeryczne	Jan
1221	4	Metody numeryczne	Kowal
1234	6	Obliczenia wizualne	Pion
1201	2	Metody numeryczne	Piotr
1201	2	Fizyka II	Szymon

Zauważamy, że ilekroć dwa wiersze w tej tabeli zawierają ten sam StudentID, muszą one również mieć te same wartości Semestru. Ten podstawowy fakt można wyrazić zależnością funkcjonalną:

Identyfikator studenta → Semestr.

Zauważmy, że gdyby dodano wiersz, w którym student miał inną wartość semestru, to zależność funkcjonalna FD przestałaby istnieć. Oznacza to, że FD wynika z danych, ponieważ możliwe jest posiadanie wartości, które unieważniłyby FD.

Można zidentyfikować inne nietrywialne zależności funkcjonalne, na przykład:

{Identyfikator studenta, wykład} → TA
{Identyfikator studenta, Wykład} → {Lt., Semestr}

Ten ostatni wyraża fakt, że zbiór {StudentID, Lecture} jest superkluczem relacji .

Model działu pracowniczego

Klasycznym przykładem zależności funkcjonalnej jest model działu pracowniczego.

dowód pracownika	Imię i nazwisko pracownika	Identyfikator działu	Nazwa oddziału
0001	nieznany z nazwiska	1	Zasoby ludzkie
0002	Jane Doe	2	Marketing
0003	John Smith	1	Zasoby ludzkie
0004	Jane Goodall	3	Obroty

Ten przypadek reprezentuje przykład, w którym wiele zależności funkcjonalnych jest osadzonych w pojedynczej reprezentacji danych. Należy pamiętać, że ponieważ pracownik może być członkiem tylko jednego działu, unikalny identyfikator tego pracownika określa dział.

Identyfikator pracownika → Nazwisko pracownika
Identyfikator pracownika → Identyfikator działu

Oprócz tej relacji tabela ma również zależność funkcjonalną poprzez atrybut inny niż klucz

Identyfikator wydziału → Nazwa działu

Ten przykład pokazuje, że nawet jeśli istnieje FD Identyfikator pracownika → Identyfikator działu — identyfikator pracownika nie byłby logicznym kluczem do określenia nazwy działu. Proces normalizacji danych rozpoznałby wszystkie FD i umożliwiłby projektantowi konstruowanie tabel i relacji, które są bardziej logiczne w oparciu o dane.

Własności i aksjomatyzacja zależności funkcyjnych

Biorąc pod uwagę, że X , Y i Z są zbiorami atrybutów w relacji R , można wyprowadzić kilka właściwości zależności funkcyjnych. Do najważniejszych należą następujące, zwykle nazywane aksjomatami Armstronga :

Refleksyjność : Jeśli Y jest podzbiorem X , to X → Y
Zwiększanie : Jeśli X → Y , to XZ → YZ
Przechodniość : jeśli X → Y i Y → Z , to X → Z

„Refleksyjność” można osłabić do zaledwie , tj. Jest to faktyczny aksjomat , w którym pozostałe dwa są właściwymi regułami wnioskowania , a dokładniej dają podstawę do następujących reguł konsekwencji składniowych: X → ∅ {\ Displaystyle X \ $rightarrow$

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

Te trzy reguły są solidną i kompletną aksjomatyzacją zależności funkcjonalnych. Ta aksjomatyzacja jest czasami opisywana jako skończona, ponieważ liczba reguł wnioskowania jest skończona, z zastrzeżeniem, że wszystkie aksjomat i reguły wnioskowania są schematami , co oznacza, że zakres X , Y i Z obejmuje wszystkie podstawowe terminy (zbiory atrybutów).

Stosując augmentację i przechodniość, można wyprowadzić dwie dodatkowe zasady:

Pseudoprzechodniość : Jeśli X → Y i YW → Z , to XW → Z
Skład : Jeśli X → Y i Z → W , to XZ → YW

unii i dekompozycji można również wyprowadzić z aksjomatów Armstronga:

X → Y i X → Z wtedy i tylko wtedy, gdy X → YZ

Zamknięcie zależności funkcjonalnej

Zamknięcie jest zasadniczo pełnym zestawem wartości, które można określić na podstawie zestawu znanych wartości dla danej relacji przy użyciu jej zależności funkcjonalnych. Do dowodu używa się aksjomatów Armstronga - tj. zwrotności, augmentacji, przechodniości.

Biorąc pod uwagę ${$ { \ $fa$ $F}$ } ( $\$ displaystyle $}$ $R}$ ${\ displaystyle$ ⁺ ) to zbiór wszystkich FD, które są logicznie implikowane przez ${\ displaystyle F}$ .

Zamknięcie zbioru atrybutów

Zamknięcie zestawu atrybutów X w odniesieniu do $fa$ zbiorem X ⁺ wszystkich atrybutów, które są funkcjonalnie określone przez X za pomocą $\ displaystyle F}$ ⁺ .

Przykład

Wyobraź sobie następującą listę FD. Obliczymy domknięcie A z tej zależności.

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

Zamknięcie wyglądałoby następująco:

a) A → A (według refleksyjności Armstronga) b) A → AB (według 1. i (a)) c) A → ABD (według (b), 3 i przechodniości Armstronga) d) A → ABCD (według (c ) i 2)

Zamknięcie to zatem A → ABCD. Obliczając zamknięcie A, potwierdziliśmy, że A jest również dobrym kandydatem na klucz, ponieważ jego zamknięciem jest każda pojedyncza wartość danych w relacji.

Pokrycia i równoważność

Okładki

Definicja : $obejmuje,$ jeśli każdy FD w $}$ wywnioskować z $F$ \ $displaystyle$ ${\ displaystyle F}$ obejmuje ${\ displaystyle G}$ , jeśli ${\ displaystyle G}$ ⁺ ⊆ ${\ displaystyle F}$ ⁺ Każdy zestaw zależności funkcjonalnych ma kanoniczną osłonę .

Równoważność dwóch zestawów FD

Dwa zestawy FD $\ displaystyle$ sol ${$ $}$ na schemacie są równoważne, zapisane $\ displaystyle F}$ ≡ ${\ displaystyle G}$ , jeśli ${\ displaystyle F}$ ⁺ = ${\ displaystyle G}$ ⁺ . Jeśli $\ displaystyle F$ okładka dla i odwrotnie. fa $}$ ≡ $displaystyle G$ $}$ Innymi słowy, równoważne zestawy zależności funkcjonalnych nazywane są wzajemnymi pokrywami .

Niezbędne osłony

Zbiór $fa$ $displaystyle$ , jeśli nie ma odpowiedniego podzbioru z $\ displaystyle F}$ z $F'}$ ≡ $displaystyle F}$ . Jeśli taki $_$ , $.$ $displaystyle F}$ ${\ displaystyle F$ $nie$ zbędną okładką dla $jeśli$ $},$ okładką dla i jest zbędna. Alternatywną charakterystyką braku redundancji jest to, że nie jest nadmiarowa, jeśli nie ma FD $w$ → Y takim , że $displaystyle F}$ $\$ - { X → Y } $\ displaystyle \ modele }$ X → Y . Wywołaj FD X → Y w zbędnym w $displaystyle$ \ $F}$ , jeśli ${\ displaystyle F}$ - { X → Y } ${\ displaystyle \ modele$ X → Y.

Zastosowania do normalizacji

Twierdzenie Heatha

Ważną właściwością (dającą natychmiastowe zastosowanie) zależności funkcyjnych jest to, że jeśli R jest relacją z kolumnami nazwanymi z jakiegoś zestawu atrybutów U i R spełnia pewną zależność funkcyjną X → Y , to ${\ Displaystyle R = \ Pi _ {XY} (R) \ muszka \ Pi _ {XZ} (R)}$ gdzie Z = U - XY . Intuicyjnie, jeśli zależność funkcjonalna X → Y zachodzi w R , to relację można bezpiecznie podzielić na dwie relacje wzdłuż kolumny X (która jest kluczem do ${\ Displaystyle \ Pi _{XY}(R)\bowtie \Pi _{XZ}(R)} )$ zapewniając, że po ponownym połączeniu obu części żadne dane nie zostaną utracone, tj . R w dwóch mniejszych relacjach. Fakt ten jest czasami nazywany twierdzeniem Heathsa ; jest to jeden z wczesnych wyników teorii baz danych.

$, że$ wyciągnąć wartości Y z dużej relacji R i zapisać je w jednym nie ma powtórzeń wiersz dla X i jest faktycznie tabelą przeglądową dla Y z kluczem X i w konsekwencji ma tylko jedno miejsce do aktualizacji Y odpowiadającego każdemu X w przeciwieństwie do „dużej” relacji R , w której istnieje potencjalnie wiele kopii każdego X , każda ze swoją kopią z Y , które muszą być synchronizowane podczas aktualizacji. (Ta eliminacja redundancji jest zaletą w OLTP , w których oczekuje się wielu zmian, ale nie tak bardzo w kontekstach OLAP , które obejmują głównie zapytania). Dekompozycja Heatha pozostawia tylko X , który działa jako klucz obcy w pozostałej części dużej tabeli ${\ Displaystyle \ Pi _ {XZ} (R)}$ .

Zależności funkcjonalnych nie należy jednak mylić z zależnościami włączenia , które są formalizmem dla kluczy obcych; mimo że są używane do normalizacji, zależności funkcjonalne wyrażają ograniczenia dotyczące jednej relacji (schematu), podczas gdy zależności inkluzyjne wyrażają ograniczenia między schematami relacji w schemacie bazy danych . Co więcej, te dwa pojęcia nawet nie przecinają się w klasyfikacji zależności: zależności funkcjonalne są zależnościami generującymi równość, podczas gdy zależności inkluzyjne są zależnościami generującymi krotki . Wymuszanie ograniczeń referencyjnych po dekompozycji (normalizacji) schematu relacji wymaga nowego formalizmu, czyli zależności inkluzyjnych. W rozkładzie wynikającym z twierdzenia Heatha nic nie stoi na przeszkodzie, aby wstawić krotki w mające pewną wartość X , ${\ Displaystyle \ Pi _ {XY} (R)}$ nie znaleziono w $}$ .

Formy normalne

Formy normalne to poziomy normalizacji bazy danych , które określają „dobroć” tabeli. Ogólnie rzecz biorąc, trzecia postać normalna jest uważana za „dobry” standard dla relacyjnej bazy danych. ^{[ potrzebne źródło ]}

Normalizacja ma na celu uwolnienie bazy danych od anomalii aktualizacji, wstawiania i usuwania. Zapewnia również, że wprowadzenie nowej wartości do relacji będzie miało minimalny wpływ na bazę danych, a tym samym minimalny wpływ na aplikacje korzystające z bazy danych. ^{[ potrzebne źródło ]}

Nieredukowalna funkcja zależna od zbioru

Zbiór S zależności funkcyjnych jest nieredukowalny, jeśli ma następujące trzy właściwości:

Każdy prawy zbiór zależności funkcjonalnej S zawiera tylko jeden atrybut.
Każdy lewy zbiór zależności funkcjonalnej S jest nieredukowalny. Oznacza to, że zmniejszenie dowolnego atrybutu z lewego zestawu zmieni zawartość S (S utraci część informacji).
Zmniejszenie jakiejkolwiek zależności funkcjonalnej zmieni zawartość S.

Zestawy zależności funkcjonalnych o tych właściwościach są również nazywane kanonicznymi lub minimalnymi . Znalezienie takiego zbioru S zależności funkcyjnych, który jest odpowiednikiem pewnego zbioru wejściowego S' podanego jako dane wejściowe, nazywamy znalezieniem minimalnego pokrycia S': problem ten można rozwiązać w czasie wielomianowym.

Zobacz też

Dalsza lektura

Codd, EF (1972). „Dalsza normalizacja modelu relacyjnego bazy danych” (PDF) . Transakcje ACM w systemach baz danych . San Jose, Kalifornia: Stowarzyszenie Maszyn Komputerowych .

Linki zewnętrzne

Gary Burt (lato 1999). „CS 461 (systemy zarządzania bazami danych) notatki z wykładów” . University of Maryland Baltimore County Wydział Informatyki i Elektrotechniki.
Jeffreya D. Ullmana. „Notatki z wykładu CS345” ( PostScript ) . Uniwersytet Stanford.
Osmar Zaiane (9 czerwca 1998). „Rozdział 6: Ograniczenia integralności” . Notatki z wykładów CMPT 354 (Systemy baz danych I) . Wydział Informatyki Uniwersytetu Simona Frasera .