CƠ SỞ DỮ LIỆU Chương 4 1 Chương 4 - Lý thuyết thiết kế cơ sở dữ liệu quan hệ NỘI DUNG: • Tổng quan về thiết kế CSDL quan hệ • Phụ thuộc hàm • Phép tách các sơ đồ quan hệ (SĐQH) • Các dạng chuẩn đối với các SĐQH 2 Tổng quan về thiết kế CSDLQH • Vấn đề của một sơ đồ quan hệ được thiết kế chưa tốt: Giả sử ta cần một cơ sở dữ liệu lưu trữ thông tin về các hãng cung ứng. Sơ đồ quan hệ được thiết kế trong đó tất cả các thuộc tính cần thiết được lưu trong đúng 1 quan hệ: Suppliers(sid, sname, city, numofemps, product, quantity) sid sname city NOE product quantity S1 Smith London 100 Screw 50 S1 Smith London 100 Nut 100 S2 J&J Paris 124 Screw 78 S3 Blake Tokyo 75 Bolt 100 3 • Dư thừa dữ liệu: Hãng nào cung ứng nhiều hơn một mặt hàng thì thông tin của hãng đó sẽ bị lặp lại trong bảng (VD S1), mặt hàng được cung ứng bởi nhiều hãng cũng bị lặp lại (VD Screw) • Dị thường dữ liệu khi thêm: Nếu có một hãng chưa cung cấp mặt hàng nào, vậy giá trị cho thuộc tính product và quantity trong bộ dữ liệu mới được thêm vào sẽ không được xác định • Dị thường dữ liệu khi xóa: Nếu một hãng chỉ cung cấp một mặt hàng, nếu ta muốn xóa thông tin về sự cung cấp này thì ta sẽ mất thông tin về hãng cung cấp • Dị thường dữ liệu khi sửa đổi: Do thông tin bị lặp lại nên việc sửa đổi một bộ dữ liệu có thể dẫn đến việc không nhất quán trong dữ liệu về một hãng nếu sơ sót không sửa đổi trên toàn bộ các bộ giá trị liên quan đến hãng đó 4 Đề xuất giải pháp • Nếu sơ đồ trên được thay thế bằng 2 sơ đồ quan hệ – Supp(sid, sname, city, numofemps) – Supply(sid, product, quantity) thì tất cả các vấn đề nêu ở trên sẽ được loại bỏ. Tuy nhiên, khi tìm kiếm dữ liệu thì phải kết nối 2 bảng chứ không chỉ là chọn và chiếu trên một bảng như ở cách thiết kế trước. 5 Mục đích của chuẩn hoá • Xác định được một tập các lược đồ quan hệ, cho phép tìm kiếm thông tin một cách dễ dàng, đồng thời tránh được dư thừa dữ liệu.
• Hướng tiếp cận: – Một trong những kỹ thuật được sử dụng là Tách các lược đồ quan hệ có vấn đề thành những lược đồ quan hệ chuẩn hơn. – Phụ thuộc hàm (functional dependencies) được sử dụng để nhận biết các lược đồ chưa chuẩn và đề xuất hướng cải tiến. 6 Phụ thuộc hàm • Định nghĩa: – Cho R(U) là một sơ đồ quan hệ với U là tập thuộc tính {A1, A2,…,An}. X, Y là tập con không rỗng của U.
– Nói X xác định hàm Y, hay Y là phụ thuộc hàm vào X (viết: X → Y) nếu với một quan hệ r xác định trên R(U) và với 2 bộ bất kỳ t1, t2 thuộc r mà t1[X] = t2[X] thì t1[Y] = t2[Y] • Bản chất, nếu 2 bộ giống nhau về giá trị của các thuộc tính X thì cũng giống nhau về giá trị của các thuộc tính Y. • Phụ thuộc hàm là một trường hợp của ràng buộc toàn vẹn, tổng quát hóa khái niệm khóa. 7 • Ví dụ 1: AB → C A B C D a1 b1 c1 d1 a1 b1 c1 d2 a1 b2 c2 d1 a2 b1 c3 d1 • Ví dụ 2: trong cơ sở dữ liệu mẫu dùng trong Chương 3, ta có bảng S, với mỗi giá trị của sid đều tồn tại một giá trị tương ứng cho sname, city và status. Do đó, có sid → sname, sid → city, sid → status 8 Hệ tiên đề Amstrong đối với phụ thuộc hàm Cho R(U) là 1 sơ đồ quan hệ, U là tập các thuộc tính.
X,Y,Z,W U , Ký hiệu: XY = X Y • Phản xạ (reflexivity) : Nếu Y X thì X→Y • Tăng trưởng (augmentation) : Nếu X→Y thì XZ→YZ • Bắc cầu (transitivity) : Nếu X→Y, Y→Z thì X→Z Hệ quả của hệ tiên đề Amstrong • Luật hợp (union): Nếu X→Y, X→Z thì X→YZ. • Luật tựa bắc cầu (pseudo-transitivity) Nếu X→Y, WY→Z thì XW→Z. • Luật tách (decomposition): Nếu X→Y, Z Y thì X→Z 9 • Ví dụ 1: Cho tập phụ thuộc hàm {AB→C, C→A} Chứng minh: BC → ABC C→A BC → AB AB → C AB → ABC BC → AB, AB → ABC BC → ABC • Ví dụ 2: Cho lược đồ quan hệ R(ABEIJGH) và tập phụ thuộc hàm F = {AB→E, AG→J, BE→I, E→G, GI→H} Chứng minh: AB → GH 10 Bao đóng của một tập phụ thuộc hàm • Định nghĩa: – Cho F là một tập phụ thuộc hàm. Bao đóng của F ký hiệu là F+ là tập lớn nhất chứa các phụ thuộc hàm có thể được suy ra từ các phụ thuộc hàm trong F.
• Đặc điểm của bao đóng của một tập phụ thuộc hàm: – Có thể rất lớn – Chi phí rất tốn kém cho việc tìm kiếm • Vấn đề đặt ra: Kiểm tra xem một phụ thuộc hàm có được suy diễn từ một tập phụ thuộc hàm có sẵn không => sử dụng bao đóng của một tập thuộc tính đối với tập phụ thuộc hàm. 11 Bao đóng của một tập các thuộc tính đối với một tập các phụ thuộc hàm • Định nghĩa: – Cho một sơ đồ quan hệ R(U), F là một tập phụ thuộc hàm trên U. X là tập con của U. Bao đóng của tập thuộc tính X đối với tập F, ký hiệu là X+F (X+), là tập tất cả các thuộc tính được xác định hàm bởi X thông qua tập F X+ = {A U| X → A F+} • Có thể thấy, định nghĩa về bao đóng của một tập thuộc tính dựa trên bao đóng của tập phụ thuộc hàm.
=>Thuật toán xác định bao đóng của một tập thuộc tính 12 Thuật toán 1: Tìm bao đóng của một tập thuộc tính đối với tập phụ thuộc hàm • Vào: Tập hữu hạn các thuộc tính U, tập các pth F trên U, X U • Ra: X+F • Thuật toán Bước 0: X0 = X Bước i: Tính Xi từ Xi-1 Nếu Y→Z F và Y Xi-1 và A Z và A Xi-1 thì Xi = Xi-1 A ngược lại, Xi = Xi-1 Nếu Xi Xi-1 thì lặp Bước i ngược lai, chuyển Bước i+1 Bước cuối cùng: khi Xi = Xi-1 (không tăng thêm): X+F= Xi 13 Ví dụ • Cho R(U) , U = {A, B, C, D, E, F} F = {AB→C, BC→AD, D→E, CF→B} Tính (AB)+ • Thực hiện: – Bước 0: X0 = AB – Bước 1: X1 = ABC (do AB→ C) – Bước 2: X2 = ABCD (do BC→AD) – Bước 3: X3 = ABCDE (do D→E) – Bước 4: X4 = ABCDE 14 Bổ đề • X→Y được suy diễn từ tập F dựa trên hệ tiên đề Amstrong khi và chỉ khi Y X+F • Chứng minh: – Giả sử Y=A1., An là các thuộc tính và YX+ – Từ Định nghĩa X+ ta có X→Ai. Áp dụng tiên đề Amstrong cho mọi i, suy ra X→Y nhờ luật hợp. – Ngược lại, giả sử có X→Y, áp dụng hệ tiên đề Amstrong cho mỗi i, ta có X→Ai, AiY nhờ luật tách. Từ đó suy ra YX+ 15 Khoá tối thiểu • Định nghĩa: Cho sơ đồ quan hệ R=<U,F>, U là tập thuộc tính, F là một tập các phụ thuộc hàm xác định trên U.
K được gọi là khoá tối thiểu của R nếu: – K⊆U – K→U ∈ F+ – Với mọi K’⊂K, thì K’→U ∉ F+ • Với những gì đã đề cập trong phần bao đóng ở trên, có thể nói, để thỏa mãn là một khoá tối thiểu thì K+ = U và K là tập thuộc tính nhỏ nhất có tính chất này. 16 Thuật toán 2: Tìm khoá tối thiểu • Vào: U = {A1, A2, …, An} , F • Ra: khoá tối thiểu K xác định được trên U và F • Thuật toán Bước 0: K0= U Bước i: Nếu (Ki-1\{Ai})→U thì Ki= Ki-1\ {Ai} ngược lại, Ki= Ki-1 Bước n+1: K = Kn 17 Ví dụ Cho U = {A, B, C, D, E}, F = {AB→C, AC→B, BC→DE}. Tìm một khoá tối thiểu của một quan hệ r xác định trên U và F Thực hiện B0: K0= U = ABCDE B1: Kiểm tra xem có tồn tại phụ thuộc hàm (K0\{A})→U (BCDE→U) hay không. Ta cần phải sử dụng Thuật toán 1 để kiểm tra điều kiện tương đương là (BCDE)+ có bằng U không.
Vậy K1 = K0 = ABCDE B2: Tương tự, thử loại bỏ B ra khỏi K1 ta có (ACDE)+ = ABCDE = U. Vậy K2 = K1 \ {B} = ACDE B3: K3 = ACDE B4: K4 = ACE B5: K5 = AC B6: Vậy AC là một khoá tối thiểu mà ta cần tìm 18 Thuật toán khác tìm tất cả các khóa trong lược đồ quan hệ Gọi: • U là tập tất cả các thuộc tính CSDL, F là tập phụ thuộc hàm • L(left): là các thuộc tính xuất hiện bên trái, R(right): là các thuộc tính xuất hiện ở vế phải • S(superkey): là tập các siêu khóa, K(key): là tập các khóa 19 Tập thuộc tính nguồn (TN): gồm các thuộc tính chỉ xuất hiện ở vế trái, không xuất hiện ở vế phải của F và các thuộc tính không xuất hiện ở cả vế trái và vế phải của F. Vậy TN = U \ R • Ví dụ: Cho sơ đồ U = {A, B, C, D, E}, F = {AB→C, AC→B, BC→DE} L = {A, B, C}, R = {B, C, D, E}, TN = U \ R = {A} Tập thuộc tính đích (TĐ): gồm các thuộc tính chỉ xuất hiện ở R, không xuất hiện ở L. Vậy TĐ = R \ L • Ví dụ: Cho L = {A, B, C}, R = {B, C, D, E} TĐ = {D, E} Tập thuộc tính trung gian (TG): chứa các thuộc tính xuất hiện ở cả L và R.
Vậy TG = L ∩ R • Ví dụ: Cho L = {A, B, C}, R = {B, C, D, E} TG = L ∩ R = {B, C} 20 Thuật toán khác tìm tất cả các khóa trong lược đồ quan hệ Thuật toán: Bước 1: Tìm tập thuộc tính nguồn TN và tập thuộc tính trung gian TG Bước 2: Nếu TG = ∅ thì K(Key) = TN, và kết thúc thuật toán, xuất ra K của sơ đồ quan hệ <U,F> Ngược lại, nếu TG ≠ ∅ thì qua Bước 3 Bước 3: Tìm tất cả các tập con Xi của TG Bước 4: Tìm Siêu khóa (Si) Với ∀Xi, nếu (TN Xi)+ = U thì khi đó Si = TN Xi Bước 5: Tìm Khóa (Ki) bằng cách loại bỏ các siêu khóa không tối thiểu • Với mọi Si Sj thuộc S, nếu Si chứa trong Sj thì loại bỏ Sj ra khỏi tập siêu khóa.