Zależności funkcyjne. Aksjomaty Armstronga - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Zależności funkcyjne. Aksjomaty Armstronga, слайд №1

Zależności funkcyjne. Aksjomaty Armstronga, слайд №2

Zależności funkcyjne. Aksjomaty Armstronga, слайд №3

Zależności funkcyjne. Aksjomaty Armstronga, слайд №4

Zależności funkcyjne. Aksjomaty Armstronga, слайд №5

Zależności funkcyjne. Aksjomaty Armstronga, слайд №6

Zależności funkcyjne. Aksjomaty Armstronga, слайд №7

Zależności funkcyjne. Aksjomaty Armstronga, слайд №8

Zależności funkcyjne. Aksjomaty Armstronga, слайд №9

Zależności funkcyjne. Aksjomaty Armstronga, слайд №10

Zależności funkcyjne. Aksjomaty Armstronga, слайд №11

Zależności funkcyjne. Aksjomaty Armstronga, слайд №12

Zależności funkcyjne. Aksjomaty Armstronga, слайд №13

Zależności funkcyjne. Aksjomaty Armstronga, слайд №14

Zależności funkcyjne. Aksjomaty Armstronga, слайд №15

Zależności funkcyjne. Aksjomaty Armstronga, слайд №16

Zależności funkcyjne. Aksjomaty Armstronga, слайд №17

Zależności funkcyjne. Aksjomaty Armstronga, слайд №18

Zależności funkcyjne. Aksjomaty Armstronga, слайд №19

Zależności funkcyjne. Aksjomaty Armstronga, слайд №20

Zależności funkcyjne. Aksjomaty Armstronga, слайд №21

Zależności funkcyjne. Aksjomaty Armstronga, слайд №22

Zależności funkcyjne. Aksjomaty Armstronga, слайд №23

Zależności funkcyjne. Aksjomaty Armstronga, слайд №24

Zależności funkcyjne. Aksjomaty Armstronga, слайд №25

Zależności funkcyjne. Aksjomaty Armstronga, слайд №26

Zależności funkcyjne. Aksjomaty Armstronga, слайд №27

Zależności funkcyjne. Aksjomaty Armstronga, слайд №28

Zależności funkcyjne. Aksjomaty Armstronga, слайд №29

Zależności funkcyjne. Aksjomaty Armstronga, слайд №30

Zależności funkcyjne. Aksjomaty Armstronga, слайд №31

Zależności funkcyjne. Aksjomaty Armstronga, слайд №32

Zależności funkcyjne. Aksjomaty Armstronga, слайд №33

Zależności funkcyjne. Aksjomaty Armstronga, слайд №34

Zależności funkcyjne. Aksjomaty Armstronga, слайд №35

Zależności funkcyjne. Aksjomaty Armstronga, слайд №36

Zależności funkcyjne. Aksjomaty Armstronga, слайд №37

Zależności funkcyjne. Aksjomaty Armstronga, слайд №38

Zależności funkcyjne. Aksjomaty Armstronga, слайд №39

Zależności funkcyjne. Aksjomaty Armstronga, слайд №40

Zależności funkcyjne. Aksjomaty Armstronga, слайд №41

Zależności funkcyjne. Aksjomaty Armstronga, слайд №42

Zależności funkcyjne. Aksjomaty Armstronga, слайд №43

Zależności funkcyjne. Aksjomaty Armstronga, слайд №44

Zależności funkcyjne. Aksjomaty Armstronga, слайд №45

Zależności funkcyjne. Aksjomaty Armstronga, слайд №46

Zależności funkcyjne. Aksjomaty Armstronga, слайд №47

Zależności funkcyjne. Aksjomaty Armstronga, слайд №48

Zależności funkcyjne. Aksjomaty Armstronga, слайд №49

Zależności funkcyjne. Aksjomaty Armstronga, слайд №50

Zależności funkcyjne. Aksjomaty Armstronga, слайд №51

Zależności funkcyjne. Aksjomaty Armstronga, слайд №52

Zależności funkcyjne. Aksjomaty Armstronga, слайд №53

Zależności funkcyjne. Aksjomaty Armstronga, слайд №54

Zależności funkcyjne. Aksjomaty Armstronga, слайд №55

Zależności funkcyjne. Aksjomaty Armstronga, слайд №56

Zależności funkcyjne. Aksjomaty Armstronga, слайд №57

Zależności funkcyjne. Aksjomaty Armstronga, слайд №58

Zależności funkcyjne. Aksjomaty Armstronga, слайд №59

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Zależności funkcyjne. Aksjomaty Armstronga. Доклад-сообщение содержит 59 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Zależności funkcyjne

Слайд 2

Описание слайда:

Zależności funkcyjne Zależności funkcyjne między atrybutami są rodzajem warunków integralności. Definicja 3. Niech będzie dany zbiór atrybutów SCH oraz jego podzbiory X i Y. Mówimy, że Y jest funkcyjnie zależny od X, co zapisujemy X  Y, wtedy i tylko wtedy, gdy dla każdej relacji R rozpiętej na schemacie SCH i dla każdych dwóch krotek t1, t2  R jest spełniony warunek: t1(X) = t2(X)  t1(Y) = t2(Y).

Слайд 3

Описание слайда:

Zależności funkcyjne Dla zależności funkcyjnych sformułowano zbiór reguł wnioskowania, które pozwalają na wyprowadzenie nowych zależności na podstawie istniejących. Nazywamy je aksjomatami Armstronga.

Слайд 4

Описание слайда:

AKSJOMATY ARMSTRONGA A1. Y  X  X Y (zwrotność) A2. X  Y  Z  W  XW  YZ (powiększenie) A3. X  Y  Y  Z  X  Z (przechodniość)

Слайд 5

Описание слайда:

AKSJOMATY ARMSTRONGA Dowód A1. t1 (X) = t2 (X)  Y  X  t1 (Y) = t2 (Y) Zależności wynikające z aksjomatu zwrotności są często nazywane trywialnymi.

Слайд 6

Описание слайда:

AKSJOMATY ARMSTRONGA A2. Dowód przez zaprzeczenie. Załóżmy, że : t1 (XW) = t2 (XW)  t1 (YZ)  t2 (YZ). t1 (XW) = t2 (XW)  Z  W  t1 (XZ) = t2 (XZ)  t1 (X) = t2 (X)  t1 (Z) = t2 (Z) t1 (Z) = t2 (Z)  t1 (YZ)  t2 (YZ)  t1 (Y)  t2 (Y) Otrzymaliśmy: t1 (X) = t2 (X)  t1 (Y)  t2 (Y) , co jest sprzeczne z założeniem.

Слайд 7

Описание слайда:

AKSJOMATY ARMSTRONGA A3. ( t1 (X) = t2 (X)  t1 (Y) = t2 (Y))  (t1 (Y) = t2 (Y)  t1 (Z) = t2 (Z))  (t1 (X) = t2 (X)  t1 (Z) = t2 (Z))

Слайд 8

Описание слайда:

REGUŁY ARMSTRONGA Z aksjomatów Armstronga wynikają następujące reguły: D1. X  Y  X  Z  X  YZ (suma) D2. X  Y  WY  Z  XW  Z (pseudoprzechodniość) D3. X  Y  Z  Y  X  Z (rozkład)

Слайд 9

Описание слайда:

REGUŁY ARMSTRONGA Dowód D1. X  Y  X  Z  X  YZ X  Y  X  YX (aksjomat A2) X  Z  XY  ZY (aksjomat A2) X  YX  XY  ZY  X  YZ (aksjomat A3)

Слайд 10

Описание слайда:

REGUŁY ARMSTRONGA Dowód D2. X  Y  WY  Z  XW  Z X  Y  XW  YW (aksjomat A2) XW  YW  YW  Z  XW  Z (aksjomat A3)

Слайд 11

Описание слайда:

REGUŁY ARMSTRONGA Dowód D3. X  Y  Z  Y  X  Z Z  Y  Y Z (aksjomat A1) X  Y  Y  Z  X  Z (aksjomat A3)

Слайд 12

Описание слайда:

REGUŁY ARMSTRONGA Zbiór reguł wnioskowania jest zupełny (sound) i kompletny (complete). Oznacza to, że wszystkie wyprowadzone zależności są poprawne oraz że można wyprowadzić wszystkie zależności istniejące w danym schemacie relacji.

Слайд 13

Описание слайда:

Konsekwencja logiczna Oznaczmy przez F zbiór zależności funkcyjnych między atrybutami schematu SCH. Zależność funkcyjna f jest konsekwencją logiczną F, co zapisujemy F = f, jeśli f jest spełnione dla wszystkich relacji o schemacie SCH.

Слайд 14

Описание слайда:

Domknięcie zbioru zależności funkcyjnych F+ Jest to zbiór zależności funkcyjnych będących konsekwencjami logicznymi F

Слайд 15

Описание слайда:

Nasycenie atrybutu X+ Zbiór F+ zawiera zazwyczaj wiele elementów, nawet jeśli F nie jest zbiorem dużym. Za pomocą reguł wnioskowania można bowiem wyprowadzić wiele zależności. Wyznaczanie F+ jest więc procesem czasochłonnym. Znacznie łatwiej można wyznaczyć nasycenie atrybutu X+ .

Слайд 16

Описание слайда:

Nasycenie atrybutu X+ Jest to zbiór atrybutów prostych A takich, że zależność XA można wyprowadzić zgodnie z regułami wnioskowania.

Слайд 17

Описание слайда:

Twierdzenie 1 Zależność XY można otrzymać na podstawie reguł wnioskowania  Y X+

Слайд 18

Описание слайда:

Twierdzenie 1 Dowód Załóżmy, że Y = {A1, A2, …, An} 1. Y  X+. Zgodnie z definicją X+ jest zbiorem atrybutów Ai, takich, że prawdziwa jest zależność X  Ai. Na podstawie reguły sumy X  X+. Y  X+  X+  Y (aksjomat A1) X  X+  X+  Y  X  Y (aksjomat A3)

Слайд 19

Описание слайда:

Twierdzenie 1 2. X  Y X  Y  X  Ai. (D3) Oznacza to, że Ai  X+  Y  X+

Слайд 20

Описание слайда:

WYZNACZANIE NASYCENIA ATRYBUTU 1. Przyjmujemy X0 = X 2. W każdym następnym kroku powiększamy Xi , Xi+1 = Xi  S, o atrybuty należące do następującego zbioru S: S = {A:  Y  Z  Y  Xi  A  Z}. Ze względu na to, że Xi  Xi+1 …  U wnioskujemy, że metoda jest zbieżna. Proces wyznaczania X+ kończymy, gdy Xi = Xi+1 .

Слайд 21

Описание слайда:

REDUKT INFORMACYJNY A – zbiór atrybutów B  A jest reduktem informacyjnym w A wtedy i tylko wtedy gdy B identyfikuje A – B i nie istnieje podzbiór właściwy B’  B, taki że B’ identyfikuje A – B’.

Слайд 22

Описание слайда:

REDUKT ASOCJACYJNY A – zbiór atrybutów Bl, Br A, Bl  Br =  Bl jest reduktem asocjacyjnym w A wtedy i tylko wtedy gdy Bl identyfikuje Br i nie istnieje podzbiór właściwy Bl’  Bl , taki że Bl’ identyfikuje (Bl – Bl’)  Br .

Слайд 23

Описание слайда:

REDUKT ASOCJACYJNY A – zbiór atrybutów Bl, Br A, Bl  Br =  Redukt asocjacyjny Bl jest nierozszerzalny w A, wtedy i tylko wtedy nie istnieje zbiór Br’, taki że Br’ Br i Bl  Br’ =  i Bl identyfikuje Br’ .

Слайд 24

Описание слайда:

REDUKT ASOCJACYJNY A – zbiór atrybutów Bl, Br A, Bl  Br =  Redukt asocjacyjny Bl jest nieredukowalny w A, wtedy i tylko wtedy nie istnieje zbiór Bl’, taki że Bl’ Bl i Bl’ identyfikuje Br .

Слайд 25

Описание слайда:

Слайд 26

Описание слайда:

Jedynym reduktem informacyjnym jest Jedynym reduktem informacyjnym jest {Outlook, Temp, Humidity, Wind}  {Sport} Redukty asocjacyjne: {Outlook, Temp, Wind}  {Sport} {Outlook, Humidity, Wind}  {Sport} Są to redukty nierozszerzalne i nieredukowalne.

Слайд 27

Описание слайда:

POKRYCIA ZBIORÓW ZALEŻNOŚCI Zbiory zależności F i G są równoważne, jeśli F+ = G+. Mówimy, że F pokrywa G ( i G pokrywa F). Zbiory są równoważne  każda zależność z F należy do G+ i każda zależność z G należy do F+ . Twierdzenie 2 Każdy zbiór zależności funkcyjnych F jest pokryty zbiorem zależności G, w którym nie istnieje prawa strona o więcej niż jednym atrybucie.

Слайд 28

Описание слайда:

POKRYCIA ZBIORÓW ZALEŻNOŚCI Dowód: Niech X  Y  F, Y = {A1, A2 ,…, An}. Niech G będzie zbiorem zależności postaci X  Ai . Atrybuty Ai odpowiadają zależnościom X  Y  F. Na podstawie D3 X  Y  X  Ai  G  F+ . Na podstawie D1 X  A1  X  A2  … X  An  X  Y  F  G+

Слайд 29

Описание слайда:

ZBIÓR MINIMALNY Wyznaczenie F+ nie jest konieczne. Wystarczy wyznaczyć zbiór minimalny, czyli taki z którego wynikają wszystkie zależności należące do F+ .

Слайд 30

Описание слайда:

ZBIÓR MINIMALNY Zbiór zależności F jest minimalny jeśli: Prawa strona każdej zależności w F jest pojedyńczym atrybutem Zbiór F – {XA} nie jest równoważny F Zbiór F – {XA}  {ZA}, gdzie Z  X nie jest równoważny F.

Слайд 31

Описание слайда:

ZBIÓR MINIMALNY Warunek 2 oznacza, że zbiór F nie zawiera zależności redundantnych. Warunek 3 oznacza, że zbiór F nie zawiera zależności z atrybutami nadmiarowymi po lewej stronie.

Слайд 32

Описание слайда:

RÓWNOWAŻNOŚĆ ZBIORÓW Sprawdzanie równoważności zbiorów F i G. G  F+ F pokrywa G (każdą zależność ze zbioru G można wywnioskować na podstawie zbioru F) 2. F  G+ G pokrywa F (każdą zależność ze zbioru F można wywnioskować na podstawie zbioru G)

Слайд 33

Описание слайда:

RÓWNOWAŻNOŚĆ ZBIORÓW Przy sprawdzaniu równoważności można wykorzystać nasycenie atrybutu 1. Dla każdej zależności X  Y  F wyznaczyć X+ względem zbioru G. 2. Sprawdzić czy X+  Y. 3. Jeżeli warunek ten jest spełniony dla każdej zależności X  Y  F, to G pokrywa F, czyli F  G+.

Слайд 34

Описание слайда:

WYZNACZANIE KLUCZA Twierdzenie 3 Niech R oznacza relację o schemacie SCH. Niech F oznacza zbiór zależności funkcyjnych między atrybutami schematu SCH. X  A  F+  SCH – {A}  SCH  F+  Dowód: (SCH – {A})  X  (SCH – {A})  A  F+ (aksjomat A2)

Слайд 35

Описание слайда:

WYZNACZANIE KLUCZA Przy wyznaczaniu klucza wykorzystujemy twierdzenie 3. Jako pierwsze przybliżenie przyjmujemy zbiór wszystkich atrybutów: K = SCH. Następnie usuwamy poszczególne atrybuty sprawdzając czy K – {A}  SCH  F+. Algorytm kończy się, gdy nie istnieje możliwość usunięcia żadnego atrybutu. Otrzymany wynik zależy od kolejności w jakiej rozpatrujemy poszczególne atrybuty.

Слайд 36

Описание слайда:

WYZNACZANIE KLUCZA – UWAGI DODATKOWE Przy wyznaczaniu kluczy można wykorzystać następujące własności: 1. Każdy klucz kandydujący zawiera wszystkie atrybuty występujące tylko po lewej stronie zależności funkcyjnych 2. Nie istnieje klucz kandydujący zawierający atrybuty występujące tylko po prawej stronie zależności funkcyjnych 3. Jeżeli zbiór atrybutów występujących tylko po lewej stronie zależności funkcyjnych identyfikuje pozostałe atrybuty, to tworzy on jedyny klucz relacji.

Слайд 37

Описание слайда:

ROZKŁAD do 3NF Wyznaczyć zbiór minimalny Dla zależności postaci X  Ai utworzyć schemat {X, A1 , A2 , …, An } 3. Jeżeli żaden ze schematów nie zawiera klucza, utworzyć schemat, do którego należą atrybuty kluczowe

Слайд 38

Описание слайда:

ZWIĄZKI WIELOARGUMENTOWE

Слайд 39

Описание слайда:

Pracownik może brać udział w realizacji różnych projektów. Wymogiem formalnym jest podpisanie kontraktu z odpowiednim wydziałem. Pracownik może zawierać kontrakty z wieloma wydziałami. Między wydziałem i pracownikiem może istnieć tylko jeden kontrakt Pracownik może podpisać kontrakty z wieloma wydziałami na udział w realizacji tego samego projektu.

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Związki trójargumentowe 4. Każdy projekt jest realizowany na określonym wydziale i wydział może realizować wiele projektów

Слайд 42

Описание слайда:

Związki trójargumentowe 4. Każdy projekt jest realizowany na określonym wydziale i wydział może realizować wiele projektów P  W  EP  W

Слайд 43

Описание слайда:

Związki trójargumentowe 5. Każdy wydział może uczestniczyć w realizacji tylko jednego projektu oraz projekt może być realizowany przez wiele wydziałów

Слайд 44

Описание слайда:

Związki trójargumentowe 5. Każdy wydział może uczestniczyć w realizacji tylko jednego projektu oraz projekt może być realizowany przez wiele wydziałów W  P  WE  P

Слайд 45

Описание слайда:

Związki wieloargumentowe R(X1, X2, … , Xn) n – stopień związku, Xi – klucz i-tego zbioru Q(X1, X2, … , Xn) = M1: M2: … : Mn

Слайд 46

Описание слайда:

Слайд 47

Описание слайда:

Związki wieloargumentowe Związki trójargumentowe 1:1:1, a:1:1, a:b:1, a:b:c Kardynalności związków binarnych nie mogą mniejsze niż kardynalności związku trójargumentowego

Слайд 48

Описание слайда:

Слайд 49

Описание слайда:

Слайд 50

Описание слайда:

Слайд 51

Описание слайда:

Związki trójargumentowe XY  Z, XZ  Y, YZ  X 1:1:1 (x1, y1, z1), (x2, y2, z2), (x1, y2, z3), (x3, y3, z3) XZ  Y, YZ  X 1:1:c (x1, y1, z1) (x1, y1, z2), (x2, y1, z3), (x1, y2, z3) YZ  X 1:b:c (x1, y1, z1), (x1, y1, z2), (x1, y2, z1), (x2, y2, z2) Brak a:b:c (x1, y1, z1), (x1, y1, z2), (x1, y2, z1) , (x2, y1, z1)

Слайд 52

Описание слайда:

Związki trójargumentowe XY  Z, XZ  Y, YZ  X 1:1:1 K1=XY, K2 = XZ, K3 = YZ XZ  Y, YZ  X 1:1:c K1 = XZ, K2 = YZ YZ  X 1:b:c K=YZ Brak a:b:c K=XYZ

Слайд 53

Описание слайда:

Związki trójargumentowe Kardynalność Dopuszczalne zależności 1:1:1 każda M:1:1 X  Y, X  Z, Y  Z, Z  Y M:N:1 X  Z, Y  Z M:N:P brak

Слайд 54

Описание слайда:

Związki wieloargumentowe R(X1, X2, … , Xn) U = {X1, X2, … , Xn} U - {Xi}  Xi , i = 1, 2, …, n (2) U - {Xi, Xj }  Xi , i ≠j, i, j = 1, 2, …, n (3) F – zbiór zależności (2) L – zbiór atrybutów występujących tylko po lewej stronie zależności (2) P – zbiór pozostałych atrybutów

Слайд 55

Описание слайда:

Związki wieloargumentowe Twierdzenie W związku n-argumentowym R(X1, X2, … , Xn) ze zbiorem F zależności funkcyjnych między n atrybutami o postaci U – {Xi}  Xi , i = 1, 2, …, n (2) może istnieć zależność funkcyjna U – {Xi, Xj }  Xi , i ≠j, i, j = 1, 2, …, n (3) jeżeli atrybut Xi nie należy do zbioru L atrybutów występujących tylko po lewej stronie zależności (2).