Thuật toán: Tìm bao đóng của một tập thuộc tính đối với tập phụ thuộc hàm  Đầu vào

123 
Nếu X
i
≠ X
i-1 
thì lặp B
i
ngược lại, chuyển B
n
Bn: X
+
F 
= X
i
Bảng 4.2: Thuật toán xác định bao đóng. 
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: X
0
= AB 
- Bước 1: X
1
= ABC (do AB→C) 
- Bước 2: X
2
= ABCD (do BC→AD) 
- Bước 3: X
3
= ABCDE (do D→E) 
- Bước 4: X
4
= ABCDE 
 4.2.3.3. 
Hai tập phụ thuộc hàm tương đương 
Định nghĩa: Tập phụ thuộc hàm F là phủ của tập phụ thuộc hàm G, hay G là phủ 
của F, hay F và G tương đương nếu F
+
= G
+
, kí hiệu là F 
≅ G 
Kiểm tra tính tương đương của 2 tập phụ thuộc hàm: 
Bước 1. Nếu với ∀ phụ thuộc hàm f
i
∈ F, f
i
có dạng Xf
i 
→ Yf
i
, mà f
i
∈ G
+
thì F
+
⊆ G
+
. Kiểm tra f
i
∈ G
+
bằng cách kiểm tra Yf
i
⊆ (Xf
i
)
+
G 
Bước 2. Tương tự, nếu ∀ phụ thuộc hàm g
j
∈ G, mà g
j 
∈ F
+
thì G
+
⊆ F
+
Bước 3. Nếu F
+
⊆ G
+
và G
+
⊆ F
+
thì F 
≅ G 
Ví dụ: Cho sơ đồ quan hệ R(U) với U = {A, B, C, D, E, F} 
F = {AB→C, D→EF, C→BD} 

124 
G = {AC→B, D→EF, B→CD} 
Hỏi F và G có phải là 2 tập phụ thuộc hàm tương đương hay không? 
Thực hiện: Đối với các phụ thuộc hàm trong F 
f
1
= AB→C. AB
+
G
= ABCDEF = U. Vậy f
1
∈ G
+
f
2
= D→EF ∈ G nên chắc chắn ∈ G
+
f
3
= C→BD. C
+
G
= C không chứa BD. Vậy f
3
∉ G
+
Kết luận F 
≇ G 
4.2.4. Khóa và các thuật toán tìm khóa 
 4.2.4.1. 
Khoá tối thiểu 
Định nghĩa: Cho lược đồ quan hệ R=, 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à khóa tối thiểu của R nếu: 
- K ⊆ U 
- K → U ∈ F
+
- Vớ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. 
Thuật toán: Tìm khóa tối thiểu 
Đầu vào: Tập hữu hạn các thuộc tính U = {A
1
, A
2
, …, A
n
}, tập các phụ 
thuộc hàm F trên U, X 
⊆ U 
Đầu ra: khoá tối thiểu K xác định được trên U và F 
Thuật toán 
B0: K
0
= U 
B1: Tính X
i
từ X
i-1
Nếu (K
i-1
\{A
i
})
→
U thì K
i
= K
i-1
\ {A
i
}, ngược lại, K
i
= K
i-1

125 
Bn: K = K
n
Bảng 4.3: Khóa tối thiểu. 
Ví dụ: Cho U = {A, B, C, D, E}, F = {AB→C, AC→B, BC→DE}.
Tìm một khóa tối thiểu của một quan hệ r xác định trên U và F 
Thực hiện 
- B
0
: K
0
= U = ABCDE 
- B
1
: Kiểm tra xem có tồn tại phụ thuộc hàm (K
0
\{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. (BCDE)
+ 
= BCDE , khác U. Vậy K
1
= K
0
= ABCDE 
- B2: Tương tự, thử loại bỏ B ra khỏi K
1
ta có (ACDE)
+
= ABCDE = U. Vậy K
2
= 
K
1
\ {B} = ACDE 
- B3: K
3
= ACDE 
- B4: K
4
= ACE 
- B5: K
5
= AC 
- Vậy AC là một khoá tối thiểu mà ta cần tìm 
 4.2.4.2. 
Thuật toán khác tìm tất cả các khóa trong lược đồ quan hệ 
Để xây dựng được thuật toán tìm khóa trong lược đồ quan hệ, chúng ta cần thống 
nhất một số kí hiệu như sau: 
- 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 (super key): là tập các siêu khóa 

126 
- K (key) : là tập các khóa 
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} 
L = {A, B} R = {B, C, E} 
TN = U \ R = {A, D} 
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, D, E} 
R = {E, F, G, H} 
TĐ = {F, G, H} 

tải về 4.98 Mb.

Chia sẻ với bạn bè của bạn: