Cho f là một phụ thuộc hàm trên U, nếu quan hệ R thoả mãn phụ thuộc hàm f thì ta ký hiệu R(f), nếu R không thoả mãn phụ thuộc hàm thì ta ký hiệu ⎤ R(f). Cho F là một tập các phụ thuộc hàm trên U, nói rằng quan hệ R thoả mãn tập<[r]
Bài giảng môn cơ sở dữ liệu nâng cao CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM VÀ PHỦ CỰC TIỂU. Phần I: Cơ sở lý thuyết phụ thuộc hàm 1. Qui ước về các ký hiệu 2. Phụ thuộc hàm 3. Hệ tiên đề Amstrong 4. Bao đóng của tập thuộc tính (X+) 5. Thuật toán (thuật toán tính bao đóng của X). Phần II: Phủ cực tiểu (Ph[r]
Trong 6 luật trên, chỉ cần 3 luật 1, 2 và 6 là đủ, nghĩa là các luật còn lại có thể suy dẫn từ ba luật này. i Hệ luật dẫn Armstrong là đúng Nói rằng X → Y là phụ thuộc hàm được suy diễn nhờ vào luật dẫn Armstrong nếu tồn tại các tập phụ thuộc hàm F 0[r]
Thuật toán tìm phủ tối thiểu của tập phụ thuộc hàm Bước 1: Phân rã các phụ thuộc hàm có vế phải nhiều thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính Bước 2: Loại các thuộc tính có vế trái dư thừa của mọi phụ thuộc hàm[r]
Ph ủ t ố i thi ể u c ủ a t ậ p ph ụ thu ộ c hàm (minimal cover) Ph ụ thu ộ c hàm d ư th ừ a : F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’ F sao cho F’ F. Ngược lại F là tập phụ thuộc hàm dư thừa.
+ Xác định vế Phải VP của phụ thuộc hàm Fi : đối với từng PTH đã xác định được ở trên, ta tìm Bao đóng VT+, sau đó giao với tập thuộc tính Qi khi đó ta có X->Y là PTH được bao trong quan[r]
2. Q là lược đồ quan hệ. F là tập phụ thuộc hàm, X là tập con của Q + và Y = { các thuộc tính xuất hiện ở vế phải của các phụ thuộc hàm trong F} thì X + ⊆ X ∪ Y. Chứng minh 1. Theo thuật toán tìm bao đóng thì bao đóng X + hay (X-A) + đượ[r]
12.4.4: Tập phụ thuộc hàm tối thiểu F được gọi là một phụ thuộc hàm tối thiểu (phủ tối thiểu) nếu F thỏa mãn đồng thời ba điều kiên sau: 1. F là tập phụ thuộc hàm có vế trái không dư thừa. 2. F là tập phụ thuộc hàm<[r]
Bước 4: Xây dựng tập chứa tất cả các khóa của Q từ tập S bằng cách xét mọi S i , S j con của S (i ≠ j), nếu S i ⊂ S j thì ta loại S j (i,j=1..n), kết quả còn lại của S chính là tập tất cả các khóa cần tìm. Ví dụ 8: Tìm tất cả các khóa của lược đồ quan hệ và tập ph[r]
Tài liệu slide bài giảng CSDL liên quan đến phần Phụ thuộc hàm, bao gồm các nội dung: Định nghĩa Biểu diễn PTH bằng đồ thị Suy diễn logic các PTH Hệ tiên đề Amstrong Bao đóng Bao đóng của tập thuộc tính Khóa Thuật toán tìm khóa Phủ tối thiểu
4.1. Khái niệm phụ thuộc hàm, các quy tắc suy diễn trên các phụ thuộc hàm 4.2. Bao đóng của một tập phụ thuộc hàm, Phủ tối thiểu của một tập phụ thuộc hàm, báo đóng của một tập thuộc tính, cách xác định khóa của một qua[r]
2 B Với kết quả của phép tách trên câu a, lược đồ R đã ở dạng bảo toàn phụ thuộc vì khi ta hợp các phép chiếu của các bảng thu được từ các phép tách trên vẫn thu được tập phụ thuộc hàm F[r]
PHẦN BẮT BUỘC 7 ĐIỂM TT NỘI DUNG ĐIỂM CÂU 1 2 ĐIỂM A _BAO ĐÓNG CỦA TẬP THUỘC TÍNH VÀ THUẬT TOÁN TÌM BAO ĐÓNG_ 1.5 _ĐỊNH NGHĨA BAO ĐÓNG_ - Cho tập phụ thuộc hàm F trên tập thuộc tính U và[r]
Vào: Lược đồ quan hệ Q, tập phụ thuộc hàm F Ra: Khẳng định Q cóa đạt dạng chuẩn 2NF hay không Bước 1: Tìm tất cả các khóa của Q Bước 2: Với tất cả các khóa K, tìm bao đóng của tất cả các tập con thật sự S của K.
Bước 3: loại khỏi F các phụ thuộc hàm dư thừa. Chú ý: Theo thuật toán trên, từ một tập phụ thuộc hàm F luôn tìm được ít nhất một phủ tối thiểu F tt để F ≡ F tt và nếu thứ tự loại các phụ thuộc hàm trong tập F là khác nhau thì có thể sẽ t[r]
- Không tồn tại phụ thuộc hàm trong F có thuộc tính vế trái dư thừa. Một vấn đề đặt ra là nếu F chưa tối thiểu thì hãy biến đổi F để thu được một tập phụ thuộc hàm tối thiểu từ F. Giải thuật tìm tập phụ thuộc hàm tối thiểu từ F gồm 3 bước[r]
2 TRANG 2 Ở DẠNG BẢO TOÀN PHỤ THUỘC VÌ KHI TA HỢP CÁC PHÉP CHIẾU CỦA CÁC BẢNG THU ĐỢC TỪ CÁC PHÉP TÁCH TRÊN VẪN THU ĐỢC TẬP PHỤ THUỘC HÀM F’ GIỐNG PHỤ THUỘC HÀM F ĐÃ CHO.. Viết chương tr[r]
Chúng ta không thể thay thế bất kỳ một phụ thuộc hàm X →A trong F bằng phụ thuộc hàm Y→A, trong đó Y là tập con đúng của X mà vẫn còn là một tập phụ thuộc hàm tương đương với F.. Chúng t[r]