CÁC THUẬT TOÁN BIẾN ĐỔI LƯỢC
ĐỒ QUAN HỆ VÀ ỨNG DỤNG
Biên tập bởi:
CÁC THUẬT TOÁN BIẾN ĐỔI LƯỢC
ĐỒ QUAN HỆ VÀ ỨNG DỤNG
Biên tập bởi:
Phiên bản trực tuyến:
http://voer.edu.vn/c/f3d62f19
MỤC LỤC
1. CÁC KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU
2. PHÉP GIẢN LƯỢC CỦA LƯỢC ĐỒ QUAN HỆ
3. CÀI ĐẶT CHƯƠNG TRÌNH
Tham gia đóng góp
1/29
CÁC KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU
CHƯƠNG I: CÁC KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU
1.1. Quan hệ và bộ [2]
Cho tập hữu hạn U = {A
1
, A
2
, , A
n
} khác trống (n ≥ 1). Các phần tử của U được gọi là
thuộc tính, ứng với mỗi thuộc tính A
i
⊆ U, i = 1, 2, , n có một tập không rỗng dom(A
i
)
được gọi là miền trị của thuộc tính A
i

Cho quan hệ R(U) và một PTH f: X ↑ Y trên U. Ta nói quan hệ R thỏa PTH f (hay PTH
f đúng trong quan hệ R), ký hiệu R(f), nếu hai bộ tùy ý trong R giống nhau trên X thì
cũng giống nhau trên Y, tức là:
2/29
R(X ↑ Y) ⇔ u,v ⊆ R: u.X = v.X ⇒ u.Y = v.Y
1.2.2. Hệ tiên đề Armstrong [2, 3]
Cho quan hệ R(U). Giả sử X, Y, Z, W ⊂ U.
F1. Tính phản xạ:
Nếu X ⊃ Y thì X ↑ Y
F2. Tính gia tăng:
Nếu X ↑ Y thì XZ ↑ YZ
F3. Tính bắc cầu:
Nếu X ↑ Y và Y ↑ Z thì X ↑ Z
Chú ý: Các PTH có vế trái chứa vế phải như mô tả trong F1 được gọi là tầm thường.
Các PTH tầm thường thoả trong mọi quan hệ.
1.2.3 Lược đồ quan hệ [2]
Lược đồ quan hệ (LĐQH) là một cặp p = (U, F) trong đó U là tập hữu hạn các thuộc
tính, F là tập các PTH trên U.
Quy ước: Trong trường hợp không chỉ rõ tập PTH F, ta xem LĐQH chỉ là một tập hữu
hạn các thuộc tính U.
1.3. Bao đóng của tập thuộc tính [2]
- Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Bao
đóng của tập thuộc tính X, ký hiệu X
+
, là tập tất cả các thuộc tính A ⊆ U mà PTH X↑A
có thể được suy diễn logic từ F nhờ hệ tiên đề Armstrong:
X
+
= {A ⊆ U | X ↑ A ⊆ F
+

Giả sử n là số lượng các thuộc tính trong U, m là số lượng các PTH trong F thì thuật
toán trên có độ phức tạp đa thức bậc hai theo chiều dài dữ liệu O(mn2).
1.4. Phủ của tập phụ thuộc hàm [2, 3]
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn được ra G, ký
hiệu F╞ G nếu g⊆G: F╞ g.
Ta nói F tương đương với G, ký hiệu F ≠ G, nếu F╞ G và G╞ F.
4/29
Nếu F ≠ G ta nói G là một phủ của F.
Ký hiệu: F !╞ G: F không suy dẫn ra được G
F !≠ G có nghĩa là F và G không tương đương.
Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký hiệu X
F
+
trong
trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập PTH F.
ζ Phủ thu gọn tự nhiên
Cho hai tập PTH F và G trên cùng một thuộc tính U. G là phủ thu gọn tự nhiên của F
nếu:
1. G là phủ của F, và
2. G có dạng thu gọn tự nhiên theo nghĩa sau:
a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau)
f ⊆ G: LS(f)⊘RS(f) = ⊕
b. Các vế trái của mọi PTH trong G khác nhau đôi một.
f,g ⊆ G: f ≃ g ⇔ LS(f) ≃ LS(g)
• Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F
Algorithm Natural_Reduced
Function: Tính phủ thu gọn tự nhiên của tập PTH
Format: Natural_Reduced (F)
Input: Tập PTH F
Output: Một phủ thu gọn tự nhiên G của F

1.5. Cơ sở của lược đồ quan hệ. [2, 3]
Cho LĐQH p = (U, F). Tập thuộc tính B ⊂⊂ U được gọi là cơ sở của LĐQH p
nếu:
(i) B
+
= U
(ii) A⊆B: (B\{A})
+
≃ U
Hai điều kiện trên tương đương với
(i) B → size 12{ rightarrow } {} U
(ii) A⊆B: (B\{A}) ! → size 12{ rightarrow } {} U
Nếu B thỏa mãn điều kiện (i) thì B được gọi là một siêu cơ sở.
6/29
Thuộc tính A ⊆ U được gọi là thuộc tính cơ sở (nguyên thủy hoặc cơ sở) nếu A có mặt
trong một cơ sở nào đấy. A được gọi là thuộc tính không cơ sở (phi nguyên thủy hoặc
thứ cấp) nếu A không có mặt trong bất kỳ cơ sở nào. Ký hiệu U
B
là tập các thuộc tính
cơ sở của LĐQH p và U
0
là tập các thuộc tính không cơ sở của p.
Chú ý: Trong một số tài liệu, thuật ngữ cơ sở được dùng theo nghĩa siêu cơ sở và thuật
ngữ cơ sở tối tiểu được dùng theo nghĩa cơ sở .
• Thuật toán tìm một cơ sở của LĐQH
Tư tưởng: Xuất phát từ một siêu cơ sở B tuỳ ý của LĐQH, duyệt lần lượt các thuộc tính
A của B, nếu bất biến (B\{A})
+
= U được bảo toàn thì A loại khỏi B. Có thể thay kiểm
tra (B\{A})

O(n
3
m).
1.6. Cách tính giao các cơ sở [2]
Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi cơ sở, đó chính là giao
các cơ sở.
Vậy giao các cơ sở chính là những thuộc tính không xuất hiện ở vế phải.
Giả sử M là giao các cơ sở. Nếu M
+
= U thì lược đồ chỉ có đúng 1 cơ sở, nếu M
+
size
12{ <> } {} U thì lược đồ có trên 1 cơ sở.
Gọi M là giao các cơ sở khi và chỉ khi: M
+
= U.
Cho LĐQH p = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi M là giao các cơ
sở của p. Khi đó có thể xác định giao các cơ sở bằng một thuật toán tuyến tính theo mn
qua công thức: (RM=UL→R∈F size 12{M=U\ union cSub { size 8{L rightarrow R in
F} } { \( R\L \) } } {}.
• Thuật toán xác định giao các cơ sở trong LĐQH
Algorithm BaseIntersec
Input:- Tập thuộc tính U
- Tập PTH F
Output: Giao các cơ sở (RM=UL→R∈F size 12{M=U\ union cSub { size 8{L
rightarrow R in F} } { \( R\L \) } } {}
Method
M:=U;
For each FD L↑R in F do
M:=M\(R\L);

+
= U
ii) A⊆M : (M\{A})
+
≃ U
Nếu không có cơ sở thứ 2: {} ⊕
Method
9/29
M := U;
For each attribute A in K do
If A ⊆ (M\{A})
+
then
M := M \ {A}
Endif;
Endfor;
For each attribute A in U \ B do
If A ⊆ (M\{A})
+
then
M := M \ {A}
Endif;
Endfor;
If M = K then return ⊕
Else return M;
Endif
End Base 2.
10/29
PHÉP GIẢN LƯỢC CỦA LƯỢC ĐỒ
QUAN HỆ

khỏi G những PTH tầm thường (có vế trái chứa vế phải), chuyển đổi mỗi PTH có hai vế
trái phải rời nhau và gộp các PTH có cùng vế trái.
2.3. Định lý cơ bản của phép biến đổi LĐQH. [2]
Cho LĐQH a=(U, F) và hai tập con rời nhau X và Y trong U. Khi đó (XY)
+
F
= XY
+
F\X
.
2.4. Dạng biểu diễn thứ nhất của cơ sở [2, 3, 4]
Nếu dịch chuyển LĐQH p = (U,F) theo tập X⊂U để nhận được LĐQH
q = p\X thì:
1. Base (p) = Base (q) khi và chỉ khi X⊂U
o
2. Base (p) = X⊗Base (q) khi và chỉ khi X⊂U
I
2.5. Dạng biểu diễn thứ hai của cơ sở [2, 3, 4]
Cho LĐQH p = (U,F). Khi đó mọi cơ sở B của p đều biểu diễn được dưới dạng K = LM
trong đó L là vế trái cực tiểu, không chứa tập con khác rỗng (vô sinh) của F và M là cơ
sở của LĐQH p\L
+
.
12/29
CÀI ĐẶT CHƯƠNG TRÌNH
CHƯƠNG 3. CÀI ĐẶT CHƯƠNG TRÌNH
3.1. Giới thiệu.
Chương trình được được xây dựng trên nền DEV - C++ để mô phỏng phép giản lược
lược đồ quan hệ và các thuật toán tìm bao đóng theo tiếp cận giản lược, thuật toán tìm
cơ sở theo tiếp cận giản lược.

A của B, nếu bất biến (B\{A})
+
= U được bảo toàn thì A loại khỏi B. Có thể thay kiểm
tra (B\{A})
+
= U bằng kiểm tra A ⊆ (B\{A})
+
Algorithm Base
Function: Tìm một cơ sở của LĐQH
Input: - Tập thuộc tính U
- Tập PTH F
Output: Cơ sở B ⊂ U thoả
i) B
+
= U
ii) A⊆B : (B\{A})
+
≃ U
Method
B := U;
For each attribute A in U do
If A ⊆ (B\{A})
+
then
B := B \ {A}
14/29
Endif;
Endfor;
Return B;
End Base.

CD → size 12{ rightarrow } {} A
D → size 12{ rightarrow } {} E
A → size 12{ rightarrow } {} B}
a. Thu gọn p để được q=(V,G) theo thuộc tính X=BD
b. Tính (AC)
+
c. Tìm cơ sở 1 của p
16/29
d. p có còn cơ sở nào khác ngoài cơ sở 1 không ? Vì sao ?
Giải
a. Thu gọn p để được q=(V,G) theo thuộc tính X=BD
V = U\X = ABCDE\BD = ACE
G = F\X = {C → size 12{ rightarrow } {} ⊕ (loại), C → size 12{ rightarrow } {} A, ⊕
→ size 12{ rightarrow } {} E, A → size 12{ rightarrow } {} ⊕ (loại)}
q = (V, G), V = ACE
G = {C → size 12{ rightarrow } {} A,
⊕ → size 12{ rightarrow } {} E}
b. Tính (AC)
+
X
0
= AC
X
1
= ACB (vì A → size 12{ rightarrow } {} B)
X
2
= ACBD (vì CB → size 12{ rightarrow } {} D)
X
3

U
I
= U\vế phải của F = ABCDE – ABDE = C
M
+
= C
+
= C size 12{ <> } {} U nên lược đồ có hơn một cơ sở.
Vậy ngoài cơ sở B
1
, lược đồ còn có cơ sở B
2
= BC vì thoả 2 điều kiện sau:
(i) B
+
= (BC)
+
= ABCDE = U
(ii) BC tối tiểu ( theo nghĩa (B \ {BC})
+
size 12{ <> } {} U ).
ζ Dữ liệu đưa vào chương trình được mã hóa như sau:
File: luocdo1
Mô tả Chú thích
5 // có 5 thuộc tính
A A // 1
B B // 2
C C // 3
D D // 4
18/29

Chương trình yêu cầu người sử dụng nhập vào mã số các thuộc tính thu gọn. Ví dụ ta
nhập vào mã số 2 4 ( B D) như hình 3.5. Chương trình in ra kết quả:
+ Số thuộc tính 3 (1 3 5 tương đương A C E)
+ Số phụ thuộc hàm 2 {C↑A, ⊕↑E}
+ Tìm được cơ sở 1 là C
21/29
Hình 3.5 Thu gon lược đồ
- Chọn 0. Thoát khỏi chương trình.
Hình 3.6 Thoát khỏi chương trình
Test tệp luocdo2:Cho LĐQH p = (U,F)
U = ABCDEH
F={ AE ↑ D,
A ↑ DH,
BC ↑ E,
E ↑ BC}
a. Với M = ADH, xác định q = (V,G) = p\M?
Tính V = U\M = ABCDEH\ADH = BCE
Tính G = F\M = {E ↑ ⊕ (loại),
⊕ ↑ ⊕ (loại),
BC ↑ E,
E ↑ BC}
22/29
Lược đồ quan hệ q = (V,G) trong đó:
V = BCE
G = {BC ↑ E,
E ↑ BC}
b. Tính (CE)
+
X
0

+
= ADH size 12{ <> } {} U nên lược đồ có hơn một cơ sở.
23/29