Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 10 - ThS. Hoàng Mạnh Hà

Chia sẻ: Zcsdf Zcsdf | Ngày: | Loại File: PPTX | Số trang:59

Thêm vào BST

Báo xấu

84
lượt xem 3
download

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

Trong Bài giảng Phân tích thiết kế hệ thống thông tin Chương 10 Phụ thuộc hàm và dạng chuẩn nhằm trình bày về phụ thuộc hàm và dạng chuẩn. Bài giảng được trình bày khoa học, súc tích giúp các bạn sinh viên tiếp thu bài học nhanh.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 10 - ThS. Hoàng Mạnh Hà

Phân tích thiết kế HTTT Phụ thuộc hàm & Dạng chuẩn ThS. Hoàng Mạnh Hà hoangha84@gmail.com https://sites.google.com/site/
Nội dung • Phụ thuộc hàm • Dạng chuẩn SGU - CNTT - Cơ sở dữ 2
Phụ thuộc hàm SGU - CNTT - Cơ sở dữ 3
Định nghĩa • Là một khái niệm quan trọng trong lý thuyết thiết kế lược đồ quan hệ. • Một phụ thuộc hàm là một ràng buộc giữa 2 tập thuộc tính. • Giả sử có lược đồ quan hệ R(A1,A2,…,An) và X, Y là tập con của {A1,A2,…,An} • Ta nói: Y phụ thuộc hàm vào X (hay X xác định Y), ký hiệu XY nếu mỗi giá trị X trong R xác định duy nhất một giá trị Y trong R. SGU - CNTT - Cơ sở dữ 4
Định nghĩa • Nếu có X Y thì ta có: o ∀r1, r2 ∈ R sao cho r1.X=r2.X thì r1.Y=r2.Y • Xét lược đồ quan hệ: PHIM (TENPHIM, NAMSX, THOILUONG, LOAIPHIM, XUONGSX, DIENVIEN) SGU - CNTT - Cơ sở dữ 5
TEN NAMSX THOI Ví dụ LOAI XUONG DIENVIEN PHIM LUONG PHIM SX Star Wars 1977 124 Color Fox Carrie Fisher Star Wars 1977 124 Color Fox Mark Hamill Star Wars 1977 124 Color Fox Harrison Ford Mighty 1991 104 Color Disney Emilio Esteves Ducks Wayne’s 1992 95 Color Paramount Dana Carvey World Wayne’s 1992 95 Color Paramount Mike Meyers World • TENPHIM  LOAIPHIM SGU - CNTT - Cơ sở dữ 6
Hệ luật Armstrong SGU - CNTT - Cơ sở dữ 7
Hệ luật Armstrong SGU - CNTT - Cơ sở dữ 8
Hệ quả từ tập phụ thuộc Cho F là tập các phụ thuộc hàm định nghĩa hàm ộc hàm f cũng • trên R. Nếu có một phụ thu thỏa với mọi thể hiện của R thì ta gọi f là phụ thuộc hàm hệ quả của F. • VD: R(A, B, C, G, H, I) và tập phụ thuộc hàm F định nghĩa trên R: F={f1: A→B; f2: A→C; f3: CG→H; f4: CG→I; f5: B→H} Ta có f6: A→H là phụ thuộc hàm hệ quả từ F SGU - CNTT - Cơ sở dữ 9
Bao đóng của tập phụ thuộc Cho F là một tập các phụ thuộc hàm được hàmp các phụ thuộc • định nghĩa trên R. Tập hợ hàm hệ quả từ F được gọi là bao đóng của F. • Bao đóng của F ký hiệu là F+ • Ta có F⊆F+ SGU - CNTT - Cơ sở dữ 10
Thuật toán tìm bao đóng của Bước 1: F+=F F • • Bước 2: o Áp dụng các luật dẫn Armstrong để tìm phụ thuộc hàm hệ quả f từ F+ o Bổ sung f vào F+ • Bước 3: Lặp lại bước 2 cho đến khi không thể tìm được f khác từ F+ SGU - CNTT - Cơ sở dữ 11
Thuật toán tìm bao đóng của Ví dụ: R(A, B, C) và F={f1: A → B; f2: B → F • C} • F+={f1: A → B; f2: B → C; f3: A → C} SGU - CNTT - Cơ sở dữ 12
Bao đóng của tập thuộc tính • Cho F là tập các phụ thuộc hàm được định nghĩa trên R và tập thuộc tính X (X ⊆ R+) • Bao đóng của tập thuộc tính X dựa trên F được ký hiệu là X+F • X+F={Y | X → Y được suy dẫn từ F} SGU - CNTT - Cơ sở dữ 13
Thuật toán tìm bao đóng của X SGU - CNTT - Cơ sở dữ 14
Thuật toán tìm bao đóng của Ví dụ: X Cho lược đồ R(A, B, C, D, E, G) và tập phụ thuộc hàm F={ f1:AB→C; f2: BC→AD; f3: D→E; f4: CG→B} Tìm (AB)+F ? (AB)+F=- {A, dB, C, D, E} SGU - CNTT Cơ sở ữ 15
Phụ thuộc hàm suy dẫn • Cho phụ thuộc hàm f: X→Y, f suy dẫn từ F (ký hiệu F ⊢ f) nếu và chỉ nếu Y ⊆ (X)+F • VD: f: AB→E suy dẫn từ F do E ∈ (AB)+F SGU - CNTT - Cơ sở dữ 16
Tập phụ thuộc hàm tương đương SGU - CNTT - Cơ sở dữ 17
Phủ • Một tập phụ thuộc hàm G được gọi là phủ của F nếu G tương đương với F (G ≡ F) • Ví dụ: F = {A→BC; A→ D; CD → E} G= {A → BCE; A → ABD; CD → E} SGU - CNTT - Cơ sở dữ 18
Phủ tối tiểu • Phủ tối tiểu là một tập hợp các phụ thuộc hàm sao cho nếu ta loại bớt một phụ thuộc hàm trong đó thì tập phụ thuộc hàm còn lại không còn là một phủ của F. • Phủ tối tiểu được định nghĩa thông qua 2 khái niệm phụ thuộc hàm đầy đủ và phụ thuộc hàm dư thừa. SGU - CNTT - Cơ sở dữ 19
Phụ thuộc hàm đầy đủ • Xét phụ thuộc hàm X → Y • Nếu không có X’ ⊂ X sao cho F ≡ F – {X → Y} ∪ {X’ → Y} thì Y phụ thuộc đầy đủ vào X • Nghĩa là: Y phụ thuộc hàm vào X và không phụ thuộc hàm vào tập con nào của X. • Ví dụ: R(A, B, C, D, E, I) và F={A → BCD; BCD → E; CD → EI} F: BCD →ơEở là phụ thuộc hàm không đầy đủ vì 20 SGU - CNTT - C s dữ