Giải bài tập phụ thuộc hàm và dạng chuẩn

Ở bài viết này mình sẽ hướng dẫn các bạn làm một số bài tập cơ sở dữ liệu như là tìm bao đóng, khóa tối thiểu, các tập phụ thuộc hàm tối thiểu và chuẩn hóa quan hệ 3NF. Những bài tập này lúc đi học thi thầy giảng hơi mông lung một tí nhưng thực ra nó rất dễ. Mình xin được bắt đầu bài viết.

Hướng dẫn giải bài tập cơ sở dữ liệu

Đề bài: Cho quan hệ R trên tập thuộc tính U = (ABCDEGHIJ) và tập phụ thuộc hàm F = { A -> BC, E -> GC, B -> EH, AC -> I, GD -> AH, D->JG}
a, tìm bao đóng của tập thuộc tính {AD}
b, tìm tất cả khóa tối thiểu của R
c, tìm tập phụ thuộc hàm tối thiểu F* của F
d, chuẩn hóa quan hệ về 3NF

Hướng dẫn giải:

a,TÌM BAO ĐÓNG CỦA AD

Xét từng phụ thuộc hàm, tìm bao đóng của AD Xét A -> BC trong AD có A nên ta sẽ đưa BC vào bao đóng AD+ = {ADBC} Xét E -> GC bao đóng hiện tại không có E bỏ qua sau đó xét tiếp lần lượt các phụ thuộc hàm còn lại và quay lại xét những phụ thuộc hàm đã bỏ qua. Cuối cùng ta được kết quả:

AD+ = {ADBCEHIJGI}

b, Tìm khóa

U = {ABCDEGHIJG} Giao của khóa: X = U – tập tất cả thuộc tính bên phải phụ thuộc hàm X = ABCDEGHIJ – BCGEHIAJ = D Tìm bao đóng của D D+ = {DJGAHBCEI} So sánh bao đóng với U D+ = U vậy khóa tối thiểu của R là D

Nếu giao của khóa bằng rỗng thì đi tìm bao đóng của từng thuộc tính có trong U, phần tử nào bằng U thì nó là khóa.

c,Loại bỏ phụ thuộc hàm dư thừa F*

b1:Tách vế phải của phụ thuộc hàm ví dụ A -> BC tách thành A -> B và A -> C Tương tự ta được: A -> B , A -> C, E -> G , E -> C, B -> E , B -> H, AC -> I , GD -> A, GD -> H , D -> J, D -> G

b2: Kiểm tra từng phụ thuộc hàm có dư thừa không bằng cách: Tìm bao đóng của từng phần tử bên trái bỏ qua phần tử bên phải, nếu kết quả bao đóng có phần tử thuộc vế phải thì dư thừa ngược lại là không

Ví dụ:

A -> B => A+ = {ACI} không có B vậy A -> B không thừa. A -> C => A+ = {ABEHGCI} có C vậy A -> C thừa Tương tự với các phụ thuộc hàm còn lại b3: Đưa ra F * loại bỏ đi những phụ thuộc hàm thừa b4: Loại bỏ phụ thuộc hàm dư thừa vế trái. Chỉ xét những phụ thuộc hàm vế trái có lớn hơn 1 phần tử AC -> I Kiểm tra A thừa : tính C+ C+ = {C}, không có I vậy A không thừa Kiểm tra C thừa : tính A+ A+ = {ABEHGCI}, có I vậy C thừa kết quả: A -> I Tương tự với các phụ thuộc hàm còn lại

b5: Đưa ra kết quả F*

d, Chuẩn hóa quan hệ về chuẩn 3 NF

b1: Kiểm tra tất cả các thuộc tính trong U có tồn lại trong VT và VP của PTH F* hay không ? b2: Gộp các PTH có cùng vế trái. A -> BI , E -> GC, B -> EH, D -> AJG b3: Tách về dạng chuẩn 3: R1(ABI) R2(EGC) R3(BEH) R4(DAJG) Ta thấy khóa của quan hệ nằm trong R4 b4: Kết Luận

Vậy để quan hệ R thành dạng chuẩn 3NF ta cần tách thành các quan hệ sau: R1(ABI) R2(EGC) R3(BEH) R4(DAJG)

Okê vậy là mình đã xử lý xong những bài tập cơ sở dữ liệu này, nguồn của bài tập này mình lấy từ anh Son Nguyen. Nếu vẫn không hiểu các bạn có thể tìm từ khóa bài tập cơ sở dữ liệu trên youtube sẽ dễ hiểu hơn, mình xin được kết thúc bài viết tại đây.

Xem những bài tập sql server khác tại đây

CHƯƠNG 6: PHỤ THUỘC HÀM VÀ CÁC DẠNG CHUẨN

Giảng viên: ThS. Thái Bảo Trân

Nội dung

• Phụ thuộc hàm
– Hệ luật dẫn Amstrong
– Bao đóng
– Khóa
– Thuật toán tìm khóa
• Các dạng chuẩn
– Dạng chuẩn 1
– Dạng chuẩn 2
– Dạng chuẩn 3
– Dạng chuẩn Boyce Cod

1. Phụ thuộc hàm (PTH)

 PTH (Functional dependencies) là một loại RBTV rất quan trọng để phát hiện các thiết ế CSDL tốt. Có thể biểu diễn RBTV bằng PTH

 PTH biểu diễn mối liên hệ giữa các thuộc tính trong cùng một quan hệ.

 X, Y là hai tập thuộc tính trên quan hệ R r1, r2 à 2 bộ bất kỳ trên R Ta nói X xác định Y, ký hiệu X → Y, nếu và chỉ nếu 1[X] = r2[X] thì r1[Y] = r2[Y] X → Y là một phụ thuộc hàm, hay Y phụ thuộc X. X là vế trái của phụ thuộc hàm, Y là vế phải của phụ huộc hàm. Ví dụ:Cho quan hệ sinh viên như sau:

SINHVIEN(Tên, Mônhọc, SốĐT, ChuyênNgành, GiảngViên, Điểm)

Tên SốĐT ChuyênNgành?Mônhọc GiảngViên?

Tên Mônhọc Điểm?

Một số tính chất sau:Với mỗi Tên có duy nhất một SốĐT và ChuyênNgànhVới mỗi Tên, Mônhọc có duy nhất một ĐiểmVới mỗi Mônhọc có duy nhất một GiảngViên

Ký hiệu:

Các phụ thuộc hàm kéo theo:{Tên} → {ChuyênNgành}

{Mônhọc, Điểm} → {GiảngViên, Điểm}

2. Hệ luật dẫn Amstrong

Gọi F là tập các phụ thuộc hàm.Định nghĩa: X → Y được suy ra từ F, hay F suy ra X → Y,Ký hiệu: F ╞ X → Y nếu bất kỳ bộ của quan hệ thỏa F thì ũng thỏa X → YHệ luật dẫn Amstrong:Với X, Y, Z, W ⊆ U. Phụ thuộc hàm có các tính chất sau:F1) Tính phản xạ: Nếu Y ⊆ X thì X → YF2) Tính tăng trưởng: {X → Y} ╞ XZ → YZ

F3) Tính bắc cầu: {X → Y, Y → Z} ╞ X → Z

Từ hệ luật dẫn Amstrong ta suy ra một số tính chất sau:F4) Tính kết hợp: {X → Y, X → Z} ╞ X → YZF5) Tính phân rã: {X → YZ, X → Y} ╞ X → Z

F6) Tính tựa bắt cầu: {X → Y, YZ → W} ╞ XZ → W

Ví dụ: F = {A → B, A → C, BC → D}, chứng minh A → D?1) A → B2) A → C3) A → BC (tính kết hợp F4)4) BC → D

5) A → D (tính bắc cầu F3)

3. Bao đóng

 Bao đóng của tập phụ thuộc hàmBao đóng của tập phụ thuộc hàm F, ký hiệu F+ à ập tất cả các phụ thuộc hàm được suy ra từ F.Nếu F = F+ hì F là họ đầy đủ của các phụ thuộc àm. Thuật toán tìm bao đóng của tập thuộc tínhBao đóng của tập thuộc tính X đối với tập phụ thuộc àm F, ký hiệu là X+F à tập tất cả các thuộc tính Y ó thể suy dẫn từ X nhờ tập bao đóng của các phụ huộc hàm F+ X+

Thuật toán tìm bao đóng của tập thuộc tính

Ví dụ:Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập hụ thuộc hàmF={ f1: B → A , f2: DA → CE, f3: D → H, f4: GH →C, f5: AC → D}

Bài toán thành viênCho tập thuộc tính Q, tập phụ thuộc hàm F trên Q à một phụ thuộc hàm X → Y trên Q. Câu hỏi đặt ra ằng X → Y ∈ F+ hay không?

X → Y ∈ F+ ⇔ Y ⊆ X+

4. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

 Định Nghĩa: Cho lược đồ quan hệ Q(A1, A2, …, An)• Q+ là tập thuộc tính của Q.• F là tập phụ thuộc hàm trên Q.• K là tập con của Q+K là một khóa của Q nếu:• K+ = Q+

• Không tồn tại K'  K sao cho K’+= Q+ 

Tập thuộc tính S được gọi là siêu khóa nếu S K Thuộc tính A được gọi là thuộc tính khóa nếu AK ới K là khóa bất kỳ của Q. Ngược lại A được gọi là huộc tính không khóa.

 Một lược đồ quan hệ có thể có nhiều khóa và tập huộc tính không khóa cũng có thể bằng rỗng.

Thuật toán tìm một khóa của một lược ồ quan hệ Q– Bước 1: gán K = Q+– Bước 2: A là một thuộc tính của K,Đặt K’ = K - A. Nếu K’+= Q+ thì gán K = K' hực hiện lại bước 2

• 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ần tử của K.

Ví dụ: Cho lược đồ quan hệ Q và tập phụ huộc hàm F như sau:‒Q(A,B,C,D,E)‒F={AB→C, AC→ B, BC → DE} . Tìm 1 khóa K

Ví dụ:Cho R(U) với U= { A,B,C,D,E,G,H,I}F= { AC→B, BI→ACD, ABC→D , H→I, ACE→BCG,CG→AE }

Tìm 1 Khóa K ?

Giải:Bước 1: Gán K = U = {A,B,C,D,E,G,H,I}Bước 2: Lần lượt loại bớt các thuộc tính của K (bài tập)

Đáp án: K={C,G,H}

Từ thuật toán tìm khóa ta có các nhận xét sau: Các thuộc tính không xuất hiện trong cả vế trái lẫn vế hải của F phải có trong khóa. Các thuộc tính chỉ xuất hiện trong vế trái của tất cả các PTH trong F cũng phải có mặt trong Khóa.

 Trong quá trình tìm khóa ta có thể bỏ bớt tất cả các huộc tính đơn nằm bên phải của các PTH của F. Tuy hiên cần kiểm tra lại vì không phải lúc nào cũng có thể bỏ được các thuộc tính đó.

Thuật toán tìm tất cả khóa của lược đồ quan hệ: