Bài Giảng Chương 8: Phủ Tối Thiểu

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Bài giảng Chương 8: Phủ tối thiểu pdf 8 736 KB 1 182 4.1 ( 14 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Phủ tối thiểu Giải thuật tìm phủ tối thiểu Lược đồ tổng hợp thành 3NF Minimal cover Tập phụ thuộc hàm

Nội dung

1 Phủ tối thiểu – Minimal cover 2  Phủ tối thiểu Fc của F là tập FD nhỏ nhất sao cho 𝐅 + = 𝑭+ 𝒄  Minimal Cover for a given set of FDs is not unique. Phủ tối thiểu – Minimal cover  3 Tập phụ thuộc hàm Fc được gọi là tối thiểu (minimal) nếu thỏa mãn các tính chất sau: Vế phải của mọi FD đều là thuộc tính đơn  Nếu giảm bất kỳ thuộc tính nào bên vế trái của mỗi FD, tập phụ thuộc mới sẽ không tương đương với phụ thuộc hàm ban đầu.  Không thể loại bỏ bất kỳ FD nào khỏi Fc vẫn được tập phụ thuộc hàm tương đương với tập Fc ban đầu.  Giải thuật tìm phủ tối thiểu 4 Input: tập phụ thuộc hàm F  Output: Fc là 1 phủ tối thiểu của F 1. Fc:=F 2. Biến đổi tất cả FD thành thuộc tính đơn bên phía phải 3. for each X A in Fc  For each attribute B that is an element of X  If { {Fc- {XA}} U { (X- {B}) A }}  Fc then replace X A with (X-{B})  A in Fc  4. For each X A in Fc if {Fc- {XA}}  Fc then remove X A from Fc Return Fc Ví dụ    5 Cho F={ BA, DA, AB D}. Tìm phủ tối thiểu của F Bước 2: tất cả FD đều có vế phải là thuộc tính đơn Bước 3:  Với ABD có thuộc tính dư thừa vế trái không? Có thể thay thế bởi AD hay BD F’= (F – {ABD})  {AD} = ={ BA, DA, B D}.  Cần chứng minh F  F’ B A ⟹ B AB  Từ F ta có ⟹ B  D  F  F’ AB  D  Từ F’ ta có B  D  AB  D  F’  F  Kết luận A là thuộc tính dư thừa của AB D  F’ ={ BA, DA, B  D}   F  F’ Ví dụ   Bước 4:  F’= { BA, DA, B  D}  Vì B  D và DA  BA. FD BA là dư thừa 𝐾ế𝑡 𝑙𝑢ậ𝑛 𝐹𝑐" = {𝐷 → 𝐴, 𝐵 → 𝐷} là phủ tối thiểu 6 Lược đồ tổng hợp thành 3NF  7 Input R(U,F) 1. Tìm phủ tối thiểu G 2. Đối với FD có vế trái X trong G, tạo 1 lược đồ quan hệ với thuộc tính {X {A1} {A2}…{Ak}, với XA1, X A2,…, XAk 3. Nếu không có lược đồ nào trong D chứa khóa của R, tạo thêm 1 lược đồ trong D chứa các thuộc tính của khóa 4. Loại bỏ quan hệ dư thừa khỏi D. Một quan hệ được gọi là dư thừa nếu nó là phép chiếu của 1 quan hệ khác trong D Ví dụ 8 Cho phủ tối thiểu G sau, hãy tổng hợp thành các lược đồ quan hệ : {Emp  Esal, Ephone, Dno; Pno  Pname, Plocation}. Khóa chính của lược đồ là Emp, Pno.  Áp dụng giải thuật, sau bước 2 có 2 lược đồ:  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  Bước 3: tạo thêm 1 quan hệ mới tương đương với khóa của R {Emp_ssn, Pno}  Kết quả là có 3 lược đồ  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  R3(Emp_ssn, Pno}   This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Atlat Địa lí Việt Nam Bài tiểu luận mẫu Thực hành Excel Trắc nghiệm Sinh 12 Lý thuyết Dow Hóa học 11 Đồ án tốt nghiệp Tài chính hành vi Giải phẫu sinh lý Đơn xin việc Mẫu sơ yếu lý lịch Đề thi mẫu TOEIC adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này