CƠ SỞ DỮ LIỆU NÂNG CAO - LÝ THUYẾT PHỤ THUỘC HÀM

Chia sẻ: Trinh Van Giang | Ngày: | Loại File: PPT | Số trang:23

Thêm vào BST

Báo xấu

255
lượt xem 77
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

TÀI LIỆU THAM KHẢO - CƠ SỞ DỮ LIỆU NÂNG CAO - LÝ THUYẾT PHỤ THUỘC HÀM

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CƠ SỞ DỮ LIỆU NÂNG CAO - LÝ THUYẾT PHỤ THUỘC HÀM

CƠ SỞ DỮ LIỆU NÂNG CAO LÝ THUYẾT PHỤ THUỘC HÀM Thầy giảng dạy: TS. Hoàng Quang 1
Tại sao phải nghiên cứu LTPTH? DỊ THƯỜNG DƯ THỪA DL 2
MỘT SỐ CÁC ĐỊNH NGHĨA TRONG LÝ THUYẾT PHỤ THUỘC HÀM 3
Phụ thuộc hàm X → Y ⇔ ∀ t1, t2 ∈ r : t1[X] = t2[X] ⇒ t1[Y] = t2[Y] A B C r= a b c b d c a e c r thỏa A C r thỏa B C 4
Lược đồ quan hệ thoả mãn phụ thuộc hàm X Y Stop ∃r ∈ R R= Or R= < U, F > KHÔNG THỎA MÃN 5
Bao đóng của tập phụ thuộc hàm R = . F+ là tập tất cả các phụ thuộc hàm hệ quả của F F+ = {X→Y | F╞ X→Y} F ⊆ F+ 6
Khoá của lược đồ quan hệ R = , X ⊆ U. X là khoá của R nếu: 1.X→U (siêu khoá) 2.Không ∃ X’ ⊂ X : X’ là siêu khoá của R Ví dụ: R = U = ABC; F = {A→B, B→C} {A} là khoá của R 7
Hệ tiên đề Amstrong Cho R = - (X, Y ⊆ U ) ∩ (X ⊆ Y) : Y→X ∈ F+ - (X, Y, Z ⊆ U) ∩ (X→Y) ∈ F+: XZ→YZ ∈ F+ (X, Y, Z ⊆ U) ∩ (X→Y ∈ F+, Y→Z ∈ F+): X→Z ∈ F+ - 8
Hệ tiên đề Amstrong (2) Ví dụ: R =, U =ABC, F = {A→B, A→C} Chứng minh: A → BC ∈ F+ A→B (1) A→C (2) Từ (1) ⇒ A → AB (3) (Luật gia tăng) Từ (2) ⇒ AB → BC (4) (Luật gia tăng) Từ (3) & (4) ⇒ A → BC (Luật bắc cầu) ⇒ đpcm 9
Bao đóng của tập thuộc tính (X+) X+ = {A | X→A ∈ F+}=X+F Ví dụ F = {A→B, B→C} A+F = ABC (AB)+ = ABC R = và X, Y ⊆ U. Khi đó: X → Y ∈ F + ⇔ Y ⊆ X +F 10
Hai tập phụ thuộc hàm tđương Cho F & G. F ⇔ G nếu và chỉ nếu F+ = G+ Ý tưởng đề kiểm chứng F ⇔ G +  F ⊆ G + (1) ⇒ ∀X(C / mY BT G ⇒ X F ⊇ Y → : ∈) F+ = G + ⇔  + ⇒ ∀X → Y ∈ F ⇒ XG ⊇ Y  G ⊆ F (2) + & G F+ F G+ 11
Hai tập phụ thuộc hàm tđương (2) Ví dụ: Kiểm tra F và G có tđương hay ko F={A→BC}, G={A→B, A→C {Kiểm tra F ⊆ G+} A→B :A+F = ABC B A→C: A+F = ABC C {Kiểm tra G ⊆ F+} A→BC: A+G = ABC BC Vậy F tđ với G 12
Phủ cực tiểu của một lược đồ quan hệ (1) Cho R = , F được gọi là phủ cực tiểu của R khi và chỉ khi:  Vế phải chỉ có 1 thuộc tính  Không có thuộc tính dư thừa ở vế trái  Không có phụ thuộc hàm dư thừa 13
Phủ cực tiểu của một lược đồ quan hệ (2) b) ⇔ ∀ X → A ∈ F, ∀ B ∈ X ⇔((F \ {X→A} ) ∪ (X \ {B} → A))+ ≠ F+ ⇔ ∀ X→A ∈F, ∀ B ∈ X: X\{B} →A ∉ F+ ⇔ ∀ X → A ∈ F, ∀ B ∈ X: (X \ {B})+ ⊇A c) ⇔ ∀ X → A ∈ F: X→A ∉ (F \ {X→A})+ ⇔ ∀ X → A ∈ F, X+F\{X→A} ⊇A 14
Phủ cực tiểu của tập phụ thuộc hàm R = . G đgl 1 phủ cực tiểu của F nếu thoả 2 điều kiện:  G ⇔F  G là phủ cực tiểu của R’ = Phủ cực tiểu của 1 phụ thuộc hàm là không duy nhất 15
Giải thuật tìm phủ cực tiểu  → A1 X Bước 1 X → A2  X → A1A 2 ...A n   → ˆ% Phan ra M  X → An  Bước 2 For (mỗi X → A ∈ F) do For (mỗi B ∈ X) do If ((X \ {B})+F ⊇ A) then X := X \ {B}; 16
Giải thuật (tt)  Bước 3 For (mỗi X → A ∈ F) do If (X+F\{X→A} ⊇ A) then F := F \ {X→A}; Kết luận: G := F; 17
PTH R = ,U = ABD, F ={B →A, D → A, A B→ D } B→D AB→D B+F\{B→D} = BA ⊇ D B+F = BAD ⊇ D ⇒ loại B→A bỏ A B+F\{B→A} = BDA ⊇ A ⇒ ⇒ F = {B→ A, B→D, loại bỏ B→A D→A} ⇒ F = {D→A, B→D} D→A ⊇ D F\{D→A} = D A + Kết luận: F = {D→A, B→D} 18
Khóa của lược đồ Định lý Hồ Thuần - Nguyễn Văn Bào (Điều kiện cần để X là khoá) (U \ P) ⊆ X ⊆ (U \ P) ∪ (T ∩ P) Function Key(R) Xđịnh T 1. Xác định P 2. X := (U \ P) ∪ (T ∩ P) 3. (X:= S) For do (A ∈ S ∩ T ∩ P ) 4. 5. If then X := X \ A; Return X. 19
Giải thuật xác định tất cả các khoá của 1 lược đồ quan hệ Định lý Lucchesi và Osborn: (Điều kiện cần và đủ để bổ sung khoá) R = . K là 1 tập khác rỗng các khoá của lược đồ quan hệ R. Điều kiện cần và đủ để bổ sung khoá mới vào K là: ∃ k∈K ∃ X→Y ∈ F sao cho T = X ∪ (K \ Y) không chứa phần tử nào của K. 20