tailieunhanh - Giáo trình cơ sở dữ liệu part 6

Tham khảo tài liệu 'giáo trình cơ sở dữ liệu part 6', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Tính bao đóng của một tập thuộc tính Bài toán Cho u là một tập các thuộc tính và F là tập phụ thuộc hàm trên u X c u. Hãy tính X . Thuật toán Vào u F X. Ra X . Tính liên tiếp các xo X x2 .-. theo quy tắc Bước ỉ Tam ệ Bước 2 WHILE Tam X DO Tam X FOR Vf w- z eFDO IF w X THEN X X u z Bước 3 RETƯRN X Ví dụ Cho F A D AB - E BI E CD I E - C và X AE sau khi thực hiện thuật toáh trên ta thu được x ACDEI. . Bổ đề X Y có thể suy dẫn từ F nhờ hệ tiên đề Armstrong khi và chi khi Y CZ x . . Dùng bao đóng của tập thuộc tính để xác định khoá một lược đổ quan hệ Định lí Cho u là một tập các thuộc tính F là tập phụ thuộc hầm trẽn u và XcU. Xlà khóa của Ư dưới F khi và chỉ khi Xị Ư. Một ví dụ áp dụng Cho u ABCDEH và F C - È AH - B B - D A - D . Hãy chứng minh rằng AHC là khoá tối thiểu của ư. Thực vậy - Vì AHC p AHCBDE X u nên AHC là khoá của u. - Mặt khác ta lại có A p AD U H p H u C p CE u 66 AH AHBD u AC f ACDE u HC HCE Ư Điều này có nghĩa là bất kỳ tạp con nào của AHC đều không lằ khoá của u vậy AHC là khoá tối thiểu của ư. . Dùng đổ thị của tập phụ thuộc hàm để xác định khoá của một lược đồ quan hệ a Đồ thị của một tập phụ thuộc hàm Ta có thể biểu diễn một phụ thuộc hàm bằng một đồ thị như sau - Phụ thuộc hàm A - B X --V 7 - Phụ thuộc hàm AB - c - Phụ thuộc hàm ABC - D - Phụ thuộc hàm A BC B B B Đồ thị cùa một tập phụ thuộc hàm Cho một tập phụ thuộc hàm F ta có thể biểu diễn thành một đồ thị với quy tắc Mỗi thuộc tính là một đỉnh trong đồ thị. 67 Ví dụ Cho tập phụ thuộc hàm F A - B AB - c B- D CD - E ta biểu diễn thành một đổ thị sau Trong đồ thị ta định nghĩa Đỉnh gốc là đỉnh mà chỉ có điểm đi của mũi tên. Ví dụ Đỉnh A của đồ thị trên. Đỉnh ngọn là đỉnh chỉ có điểm đến của mũi tên. Ví dụ Đỉnh E của đồ thị trên. Đỉnh trung gian là đỉnh vừa có điểm đến vừa có điểm đi của mũi tên. Ví dụ Đỉnh B c D của đồ thị trên. b Dùng đồ thị của một tập phụ thỉiậc hàm để xác định khoá của lược đồ quan hệ. Cho lược đồ quan hệ T Ư và tập phụ thuộc hàm F trên u. Thuật giải dùng đồ