KHÓA CỦA LƯỢC ĐỒ QUAN HỆ … - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Trang chủ >
Công Nghệ Thông Tin >
Cơ sở dữ liệu >

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (179.68 KB, 28 trang )

5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …Thuật toán tìm một khóa của một lược đồ quan hệ QK=Q+;Với mỗi A ∈ K doif (K-A)+ = Q thenK=K-ANếu muốn tìm các khóa khác (nếu có) của lược đồquan hệ, ta có thể thay đổi thứ tự loại bỏ các phầntử của K.195. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ (Thuậttoán cơ bản)Bước 1:Xác định tất cả các tập con của QĐể xác định tất cả các tập con của một lược đồ quan hệ Q(A1,A2,…,An) ta lần lượt duyệt tất cả 2n-1 tập hợp con khác rỗng của Q+ (n làsố thuộc tính của lược đồ quan hệ Q),kết quả tìm được giả sử là cáctập thuộc tính: S={X1, X2, …,X2n-1 }Bước 2: Chọn trong S ra tập siêu khóa của QNếu một tập con Xi (i=1..,2n-1) của Q+ có bao đóng đúng bằng Q+ thìtập con dó (theo định nghĩa trên) là một siêu khóa của Q.Giả sử ta đã có các siêu khóa là S = {S1,S2,…,Sm}Bước 3:Xây dựng tập chứa tất cả các khóa của Q từ tập SXét mọi Si,Sj con của S (i ≠ j), nếu Si ⊂ Sj thì ta loại Sj (i,j=1..n), kết205. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ QuanHệ (Thuật toán cải tiến)Một số khái niệm:xxxTập thuộc tính nguồn(TN) chứa tất cả các thuộc tính có xuất hiệnở vế trái và không xuất hiện ở vế phải của tập phụ thuộc hàm.Tập thuộc tính đích chứa tất cả các thuộc tính có xuất hiện ở vếphải và không xuất hiện ở vế trái của tập phụ thuộc hàm.Tập thuộc tính trung gian(TG) chứa tất cả các thuộc tính thuộcQ+ và không thuộc tập thuộc tính nguồn và cũng không thuộc tậpthuộc tính đích.Dữ liệu vào: Lược đồ quan hệ phổ quát Q và tập phụ thuộcdữ liệu F215. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …Thuật Toán Tìm Tất Cả Các Khóa Của Một LượcĐồ Quan Hệ (Thuật toán cải tiến)Bước 1: Tìm tập thuộc tính nguồn(TN), tập thuộctính trung gian(TG)Bước 2: Tìm tất cả các tập con của tập trung giangọi là Xi (bằng phương pháp duyệt nhị phân)Bước 3: If tập trung gian= ∅ thenTập Khóa = Tập thuộc tính nguồn ;Kết thúcNgược lại Qua bước 4225. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …Thuật Toán Tìm Tất Cả Các Khóa Của Một LượcĐồ Quan Hệ (Thuật toán cải tiến)Bước 4: S= ∅Xi tập trung gianif (Tập nguồn Xi)+ = Q+ thenS = S ∪ { Tập nguồn ∪ Xi}{S là tập các siêu khóa cần tìm}Bước 5: Loại bỏ các siêu khóa không tối tiểu∀ SI, Sj ∈ S if Si ⊂ Sj then Loại Sj ra khỏi Tập siêukhóa SS còn lại chính là tập khóa cần tìm.236. DẠNG CHUẨN CỦA LƯỢC ĐỒ Q.HỆChất lượng thiết kế của một lược đồ CSDL có thể đượcđánh giá dựa trên nhiều tiêu chuẩn trong đó sự trùng lắpthông tin và chi phí kiểm tra các ràng buộc toàn vẹn là haitiêu chuẩn quan trọng.Thuộc tính khóa/không khóa: A là một thuộc tính khóa nếuA có tham gia vào bất kỳ một khóa nào của quan hệ, ngượclại A gọi là thuộc tính không khóa.Thuộc tính phụ thuộc đầy đủ: A là một thuộc tính phụ thuộcđầy đủ vào tập thuộc tính X nếu X → A là một phụ thuộchàm đầy đủ (tức la không tồn tai X' ⊂ X sao cho X' → A ∈F)246. DẠNG CHUẨN CỦA LĐ QH (tt)Định Nghĩa Dạng Chuẩn Một (First Normal Form)Cho lược đồ quan hệ Q, Q được gọi là đạt dạngchuẩn 1 (1NF) nếu và chỉ nếu toàn bộ các thuộc tínhcủa Q đều mang giá trị đơn.x Lượcx Đưađồ quan hệ này không đạt dạng chuẩn 1quan hệ trên về dạng chuẩn 1:256. DẠNG CHUẨN CỦA LĐ QH (tt)Định Nghĩa Dạng Chuẩn HaiMột lược đồ quan hệ Q đạt dạng chuẩn 2 nếu Q đạt dạngchuẩn 1 và tất cả các thuộc tính không khóa của Q đều phụthuộc đầy đủ vào khóa.VD: Lược đồ quan hệ sau đạt chuẩn 2: Q(G,M,V,N,H,P)F={G → N; G → H; G → P; M → V; N,H,P → M}Hệ quả:xxQ đạt 2NF nếu Q là 1NF và tập thuộc tính không khóa của Q bằngrỗng.Nếu khóa của quan hệ chỉ có một thuộc tính thì quan hệ đó ít nhấtđạt chuẩn 2.26

Xem Thêm