CSDL
CHƯƠNG III: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ
Mục đích của thiết kế khái niệm là cho ra lược đồ khái niệm ở mức cao, độc lập với
hệ quản trị CSDL thông qua việc xác định các yêu cầu mô tả thế giới thực. Người ta
đưa ra các khái niệm thiết kế CSDL bằng cách mô tả các cơ chế trừu tượng, các quá
trình tư duy rồi thông qua đó có thể tập trung vào các thuộc tính chung của dữ liệu và
không để ý đến các chi tiết thừa.
Tổng quan về vấn đề thiết kế CSDL:
Các CSDL là thành phần cơ bản trong hệ thống thông tin. Việc thiết kế CSDL
được coi là hoạt động thông dụng, có hiệu quả đối với cán bộ chuyên môn lẫn người
dùng không chuyên.
Nhiều bài toán đã hiểu không rõ ràng và không trong sáng về bản chất chính xác
của dữ liệu mức khái niệm và mức trừu tượng. Trong nhiều trường hợp, dữ liệu được
mô tả từ khi bắt đầu đề án trong cấu trúc dữ liệu lưu trữ, chứ không tập trung vào việc
hiểu thuộc tính có cấu trúc của dữ liệu. Các dữ liệu cần độc lập với việc cài đặt.
Nên tầm quan trọng là tiếp cận khái niệm, trong thiết kế CSDL điều này rất quan
trọng đối với cả những đề án CSDL loại nhỏ, lớn.
Khi thiết kế một CSDL quan hệ thường đòi hỏi phải chọn các lược đồ quan hệ.
Việc chọn tập các lược đồ này có thể tốt hơn hoặc xấu hơn tập các lược đồ khác dựa
trên một số tiêu chuẩn nào đó.
Vậy làm thế nào để thiết kế một CSDL tốt? Ta khảo sát ví dụ quan hệ THI như sau:
( MaSV, Hoten, Lop, Tenmon, Sotiet, Diem)
Với cách tổ chức dữ liệu như trên sẽ có các vấn đề nãy sinh như sau:
-
Dư thừa dữ liệu: là sự trùng lặp thông tin trong CSDL. Như ví dụ trên, nếu mỗi
sinh viên thi môn nào thì họ tên, lớp, số tiết bị lặp lại
-
Không nhất quán dữ liệu: là hệ quả của việc dư thừa dữ liệu. Khi sửa lại số tiết
của một môn học nào đó có thể xảy ra trường hợp cùng 1 môn nhưng số tiết không
giống nhau.
-
Dị thường khi thêm bộ: Không thể thêm bản ghi nếu như chưa đầy đủ dữ liệu.
Ví dụ: Một sinh viên chưa có điểm thi nào cả, khi đó không thể đưa Lớp, HoTen là
một bản ghi vào quan hệ.
-
Dị thường khi xoá bộ: Thể hiện khi xoá bản ghi là xoá luôn những thông tin cần
thiết. Ví dụ: Không thể xoá tất cả môn thi của một sinh viên nào đó, bởi môn thi đó có
thể được nhiều sinh viên thi.
Vậy quan hệ THI nêu trên có thể được phân chia thành những quan hệ khác nhau
nhằm tránh tất cả những điều đã nêu nhằm đạt được một lược đồ CSDL (tập các lược
đồ CSDL) sao cho tốt hơn. Vì vậy người ta đã xây dựng một cơ sở lý thuyết thiết kế cơ
sở dữ liệu quan hệ hay còn gọi là chuẩn hoá mô hình quan hệ.
Phụ thuộc hàm:
Là nền tảng cơ bản của việc chuẩn hoá cơ sở dữ liệu.
Khái niệm:
Cho lược đồ quan hệ R(U) (U={A
1
, A
2
, ..., A
n
} là tập hữu hạn các thuộc tính)và X,
Y là các tập con của U. Ta nói rằng X
xác định hàm
Y hay Y
phụ thuộc hàm
X, ký
hiệu X
→
Y, nếu mọi quan hệ bất kỳ r của lược đồ R thoả mãn:
∀
t1, t2
∈
r
: t1[X] = t2[X]
⇒
t1[Y] = t2[Y]
Cần nhấn mạnh rằng tính chất phụ thuộc hàm phải thoả với mọi quan hệ
r
của lược
đồ R. Ta không thể chỉ xét một quan hệ đặc biệt (quan hệ rỗng chẳng hạn) rồi quy nạp
cho toàn lược đồ. Nhưng ta có thể phủ nhận phụ thuộc hàm qua một quan hệ cụ thể
nào đó.
Ví dụ 1
: Trong quan hệ hãng cung ứng S ta có các phụ thuộc hàm:
S#
→
Sname
S#
→
Status
S#
→
City
Nhưng ngược lại không đúng có nghĩa là :
Sname
→
S #: không đúng
Status
→
S # : không đúng
City
→
S #: không đúng
Ví dụ 2:
Trong quan hệ THI, có các phụ thuộc hàm sau:
MaSV
→
Hoten, Lop
MaSV, Tenmon
→
Diem
Mon
→
Sotiet
a.
Ý nghĩa: Phụ thuộc hàm X
→
Y có nghĩa là khi biết giá trị của một bộ nào
đó tại X thì biết giá trị của bộ đó tại Y.
b.
Định nghĩa:
-
Phụ thuộc hàm X
→
Y gọi là phụ thuộc hàm tầm thường nếu Y
⊂
X (hiển nhiên
là nếu Y
⊂
X thì theo định nghĩa ta có X
→
Y).
-
Phụ thuộc hàm X
→
Y gọi là phụ thuộc hàm nguyên tố nếu không có tập con
thực sự Z
⊂
X thoả Z
→
Y.
-
Tập thuộc tính K
⊂
R gọi là khoá nếu nó xác định hàm tất cả các thuộc tính
và K
→
R là phụ thuộc hàm nguyên tố.
Suy dẫn logic phụ thuộc hàm:
Cho lược đồ quan hệ R(U) và F là tập tất cả các phụ thuộc hàm của lược đồ R(U),
phụ thuộc hàm X
→
Y là một phụ thuộc hàm nào đó (X, Y
⊆
U). Ta nói rằng phụ
thuộc hàm X
→
Y được suy dẫn logic từ F, hay F suy dẫn logic X
→
Y. Ký hiệu: F |->
X
→
Y nếu nó thoả mãn: Mỗi quan hệ r xác định trên lược đồ R(U) thoả F thì r cũng
thoả X
→
Y
-
Ví dụ: Cho F = { A
→
B, B
→
C }. CM F
|-> A
→
C.
Ta có:
∀
t1, t2
∈
r: t1[A] = t2[A]
⇒
t1[B] = t2[B] ( vì A
→
B)
⇒
t1[C] = t2[C]
( vì B
→
C)
⇒
A
→
C (đpcm).
Bao đóng của tập phụ thuộc hàm (FD):
Cho lược đồ quan hệ R(U), tập FD F của R, bao đóng của tập FD F. Ký hiệu: F
+
là
tập tất cả các phụ thuộc hàm X
→
Y sao cho phụ thuộc hàm X
→
Y được suy dẫn logic
từ F
F
+
= { X
→
Y | F |-> X
→
Y}
Chú ý
:
F
+
là tập phụ thuộc hàm lớn nhất thoả R và chứa F
Ví dụ
: Cho R=(A,B,C) và F = {A
→
B, B
→
C}. Khi đó bao đóng F+ gồm các
phụ thuộc hàm X
→
Y thoả
(i) X chứa A, Y bất kỳ:
A,B,C
→
A,B,C;
A,B,C
→
B,C;
A,B,C
→
B;
A,B
→
A,B;
A,B
→
A;
A,B
→
C;
A,C
→
A,C;
A,C
→
B;
A
→
A,B,C;
A
→
B,C;
A
→
B;
A,B,C
→
A,B;
A,B,C
→
A;
A,B,C
→
C;
A,B
→
A,C;
A,B
→
B;
A,C
→
A,B,C;
A,C
→
B,C;
A,C
→
B;
A
→
A,B;
A
→
A;
A
→
C;
A,B,C
→
A,C;
A,B,C
→
B;
A,B
→
A,B,C;
A,B
→
B,C;
A,B
→
B;
A,C
→
A,B;
A,C
→
A;
A,C
→
C;
A
→
A,C;
A
→
B;
(ii) X chứa B nhưng không chứa A, Y không chứa A:
BC
→
BC;
B
→
BC;
BC
→
B;
B
→
B;
BC
→
C
B
→
C
(iii) C
→
C
Bao đóng của tập phụ thuộc hàm (FD):
Cho lược đồ quan hệ R(U), tập FD F của R, bao đóng của tập FD F. Ký hiệu: F
+
là
tập tất cả các phụ thuộc hàm X
→
Y sao cho phụ thuộc hàm X
→
Y được suy dẫn logic
từ F
F
+
= { X
→
Y | F |-> X
→
Y}
-
-
Chú ý
:
F
+
là tập phụ thuộc hàm lớn nhất thoả R và chứa F
Ví dụ
: Cho R=(A,B,C) và F = {A
→
B, B
→
C}. Khi đó bao đóng F+ gồm các
phụ thuộc hàm X
→
Y thoả
(i) X chứa A, Y bất kỳ:
A,B,C
→
A,B,C;
A,B,C
→
B,C;
A,B,C
→
B;
A,B
→
A,B;
A,B
→
A;
A,B
→
C;
A,C
→
A,C;
A,C
→
B;
A
→
A,B,C;
A
→
B,C;
A
→
B;
A,B,C
→
A,B;
A,B,C
→
A;
A,B,C
→
C;
A,B
→
A,C;
A,B
→
B;
A,C
→
A,B,C;
A,C
→
B,C;
A,C
→
B;
A
→
A,B;
A
→
A;
A
→
C;
A,B,C
→
A,C;
A,B,C
→
B;
A,B
→
A,B,C;
A,B
→
B,C;
A,B
→
B;
A,C
→
A,B;
A,C
→
A;
A,C
→
C;
A
→
A,C;
A
→
B;
(ii) X chứa B nhưng không chứa A, Y không chứa A:
BC
→
BC;
B
→
BC;
BC
→
B;
B
→
B;
BC
→
C
B
→
C
(iii) C
→
C
Về mặt lý thuyết ta hoàn toàn có thể xây dựng thủ tục tính bao đóng F
+
của tập phụ
thuộc hàm F, nhưng trên thực tế bài toán xác định F
+
là không khả thi vì với số thuộc
tính và phụ thuộc hàm lớn sẽ dẫn đến bùng nổ tổ hợp.
ề mặt lý thuyết ta hoàn toàn có thể xây dựng thủ tục tính bao đóng F
+
của tập phụ
thuộc hàm F, nhưng trên thực tế bài toán xác định F
+
là không khả thi vì với số thuộc
tính và phụ thuộc hàm lớn sẽ dẫn đến bùng nổ tổ hợp.
Thay vào đó chúng ta sẽ xem xét một bài toán khác: "Kiểm tra xem một phụ thuộc
hàm có thuộc bao đóng F
+
hay không ?". Bài toán này gọi là bài toán thành viên. Bài
toán thành viên thiết thực hơn bài toán tính bao đóng vì trong thực tế rất hiếm khi phải
tìm tất cả các phụ thuộc hàm suy diễn lô-gic từ
F
.
Bài toán thành viên liên quan mật thiết với khái niệm bao đóng của tập thuộc tính.
Các qui tắc phụ thuộc hàm:
a. Hệ tiên đề Amstrong:
(A
1
) Quy tắc phản xạ:
Y
⊂
X
⊂
R
⇒
X
→
Y
(A
2
) Quy tắc tăng trưởng:
X
→
Y & Z
⊂
R
⇒
X
∪
Z
→
Y
∪
Z
(A
3
) Quy tắc bắc cầu:
X
→
Y & Y
→
Z
⇒
X
→
Z
Ví dụ:
Cho lược đồ R=(A,B,C) và F={AB
→
C; C
→
A}. Dùng các quy tắc Armstrong ta
chứng minh rằng (B,C)
→
(A,B,C).
Thật vậy, ta có:
C
→
A
C
∪
(B,C)
→
A
∪
(B,C)
theo giả thiết,
theo quy tắc tăng trưởng A
2
.
Từ đó suy ra
(B,C)
→
(A,B,C)
b. Tính đúng và tính đủ của các quy tắc suy diễn
Tập hợp các quy tắc suy diễn
A
gọi là
đúng
nếu mọi phụ thuộc hàm suy ra từ F
nhờ sử dụng
A
cũng được suy diễn lôgic từ F:
F
A
= {X
→
Y | X
→
Y suy ra từ F nhờ hệ tiên đề Amstrong}
Tức là nếu ký hiệu F
A
là tập các phụ thuộc hàm suy ra từ F nhờ các quy tắc của A,
thì A gọi là đúng nếu F
A
⊂
F
+
.
Tập hợp các quy tắc suy diễn
A
gọi là
đủ
nếu mọi phụ thuộc hàm suy diễn lôgic
từ F cũng suy ra từ F nhờ sử dụng A, tức làF
+
⊂
F
A
.
Định lý 1:
Hệ tiên đề Amstrong là đúng
Chứng minh:
(A1): Tiêu đề A1 rõ ràng là đúng vì không
thể có hai bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó.
(A2): Cho quan hệ r thoả mãn phụ thuộc hàm
X
→
Y. Tồn tại hai bộ t, u
∈
r sao cho t[XZ] = u[XZ] mà t[YZ]
≠
u[YZ]. Vì rằng t[Z]
= u[Z] nên để có t[YZ]
≠
u[YZ] thì t[Y]
≠
u[Y] là trái với giả thiết X
→
Y. Vậy t[YZ]
= u[YZ].
(A3): Cho quan hệ r thoả mãn phụ thuộc hàm
X
→
Y. Giả sử tồn tại hai bộ t và u
∈
r sao cho t[X] = u[X] và t[Z]
≠
u[Z]. Từ X
→
Y
suy ra t[X] = u[X] nên t[Y]=u[Y]. Nhưng lại có t[Y] = u[Y] và t[Z]
≠
u[Z] thì trái với
giả thiết Y
→
Z. Do vậy t[Z]=u[Z]. Suy ra X
→
Y đúng trên quan hệ r.
Từ hệ tiên đề Amstrong suy ra hệ quả:
(A
4
) Quy tắc hợp:
Nếu X
→
Y & X
→
Z thì X
→
Y
∪
Z
(A
5
) Quy tắc tựa bắc cầu:
Nếu X
→
Y, Y
∪
W
→
Z thì X
∪
W
→
Z
(A
6
) Quy tắc phân rã:
Nếu X
→
Y & Z
⊂
Y thì X
→
Z
Chứng minh:
(A4): Từ X
→
Y dùng quy tắc tăng trưởng,
thêm X có X
→
XY. Từ X
→
Z dùng quy tắc tăng trưởng thêm Y có XY
→
YZ. Và cuối c
ùng dùng quy tắc bắc cầu suy ra cho X
→
XY và XY
→
YZ có X
→
YZ.
(A5): Từ X
→
Y dùng quy tắc tăng trưởng,
thêm W có XW
→
YW. Dùng luật bắc cầu cho XW
→
YW và YW
→
Z suy ra XW
→
Z.
(A6): Vì Z
⊆
Y nên Y
→
Z (thêo quy tắc phản
xạ).
-
Ví dụ:
Cho lược đồ R (A, B, C, D, E, G). F gồm các phụ thuộc hàm sau:{AE
→
C, CG
→
A, BD
→
G, GA
→
E}. Chứng minh BCD
→
ABCDEG.
BDC
→
A (Qui tắc tựa bắc cầu)
Ta có BD
→
G, CG
→
A (giả thiết). Vậy
BDC
→
GC (tăng trưởng)
BDC
→
GA (quy tắc hợp)
GA
→
E (giả thiết)
BDC
→
E (Quy tắc bắc cầu)
BDC
→
ABCDGE (Quy tắc hợp)
ii
Định lý 2:
Hệ tiên đề Amstrong là đủ
Chứng minh
: Ta chứng minh nếu X
→
Y không thoả trên r thì X
→
Y không
thể suy dẫn lôgic từ F.
Gọi F là tập các phụ thuộc hàm trên tập thuộc
tính U. Giả sử X
→
Y là không thể suy dẫn được từ hệ tiên đề Amstrong. Xét quan hệ
r gồm 2 bộ như sau:
11...1
11...1
Các thuộc tính thuộc
X
+
11..1
00...0
Các thuộc tính còn lại
Trước hết cần chỉ ra rằng tất cả các phụ
thuộc hàm F đều thoả r. Thật vậy, giả sử (V
→
W)
∈
F nhưng không thoả trên r. Do
đó V
⊆
X
+
, hoặc hai bộ của r sẽ không bằng nhau ít nhất trên một thuộc tính của V.
Như vậy W không thể là tập con của
X
+
hoặc V
→
W thoả trên r.
Gọi A
∈
W nhưng A không thuộc
X
+
. Vì
XV
⊆
X
+
, X
→
V suy ra từ hệ quả. (V
→
W)
∈
F do vậy, nhờ quy tắc bắc cầu suy
ra X
→
A. Nhưng do A không thuộc
X
+
như giả thiết, do vậy là mâu thuẫn. Từ đó
đến kết luận rằng mỗi (V
→
W)
∈
F đều thoả mãn trên r.
Bây giờ cần chứng minh rằng X
→
Y không
thoả trên r. Như trên có X
⊆
X
+
và suy ra Y
⊆
X
+
, nếu không 2 bộ thuộc r là bằng
nhau trên X nhưng không bằng nhau trên Y. Do đó X
→
Y không thể đúng trên r.
Kết luận: Nếu X
→
Y không suy diễn từ hệ
tiên đề Amstrong thì X
→
Y không thể suy diễn logic từ F. Vậy hệ tiên đề là đủ.
Bao đóng của tập thuộc tính:
Đặt vấn đề:
Cho R(U) và tập phụ thuộc hàm F của R. Tập phụ thuộc hàm X
→
Y (X, Y
⊆
U) là
một phụ thuộc hàm nào đó. Kiểm tra xem tập phụ thuộc hàm X
→
Y có thuộc
F
+
không? (Mà bài toán tìm
F
+
có độ phức tạp hàm mũ.)
Ví dụ: Cho F = {A
→
B1, A
→
B2…, A
→
Bn} Tìm
F
+
?
Ta có:
F
+
có tất cả
2
n
phụ thuộc hàm dạng X
→
X với X thuộc {B1, B2,…Bn,
A}
Suy ra n nhỏ nhưng
F
+
có thể lớn. Vì vậy để tìm
F
+
ta đi tìm
X
+
là bao đóng
của tập thuộc tính X rồi sau đó kiểm tra xem Y có chứa trong
X
+
không? (Y
⊆
X
+
),
nếu có thì X
→
Y thuộc
F
+
.
Định nghĩa:
Cho lược đồ quan hệ R(U), tập FD F của R và X
⊆
U. Bao đóng của X. Ký hiệu là
X
+
là tập tất cả thuộc tính A sao cho FD X
→
A được suy dẫn logic từ F nhờ
Amstrong hay X
→
A thuộc
F
+
.
X
+
= {A | X
→
A
∈
F
+
} = {A | X
→
A
∈
F
A
}
Bổ đề 1:
Tập phụ thuộc hàm X
→
Y thuộc
F
+
khi và chỉ khi Y
⊆
X
+
.
a.
Chứng minh
: Giả sử Y = { A
1
, A
2
, ..., A
n
}
⊆
U, X
→
Y
∈
F
+
. Chứng
minh Y
⊆
X
+
(CM điều kiện cần), CM điều kiện đủ: Từ Y
⊆
X
+
suy ra X
→
Y
∈
F
+
Ta có: X
→
Y
∈
F
+
.
Theo luật tách (A6) ta có: X
→
A
1
∈
F
+
,..., X
→
A
n
∈
F
+
. Theo định nghĩa trên ta có: A
1
∈
X
+
, A
n
∈
X
+
. Từ đó suy ra { A
1
, A
2
, ..., A
n
}
⊆
X
+
. Suy ra Y
⊆
X
+
(điều kiện cần)
Ta có
Y
⊆
X
+
suy ra { A
1
, A
2
, ..., A
n
}
⊆
X
+
. Suy ra A
1
∈
X
+
, ..., A
n
∈
X
+
. Theo định nghĩa ta có: X
→
A
1
∈
X
+
,..., X
→
A
n
∈
X
+
. Theo luật hợp ta có:
X
→
Y
∈
F
+
(điều phải chứng minh).
b.
Nhận xét
:
X
+
là tập thuộc tính lớn nhất chứa trong U và thoả X
→
X
+
∈
F
+
Thuật toán tìm bao đóng của tập thuộc tính:
Đầu vào: Tập các thuộc tính của R, tập phụ thuộc hàm F trên R và tập X
⊂
R.
Đầu ra:
Bao đóng
X
+
của X đối với F.
Phương pháp: Ta tính lần lượt dãy các tập thuộc tính sau: X
(0)
, X
(1)
,..., X
(k)
,...
theo các bước sau:
(i) Đặt X
(0)
:= X, F
0
:= F, k := 1
(ii) Biết X
(k
−
1)
, tính X
(k)
như sau:
Đặt X(k) := X(k
−
1).
Lần lượt duyệt qua các phụ thuộc hàm
U
→
V
∈
F
0
.
Nếu V
⊂
X(k) thì đặt
F
0
:=
F
0
\
{U
→
V}
Nếu U
⊂
X(k) thì ta mở rộng X(k) :=
X(k)
∪
V và đặt
F
0
:=
F
0
\ {U
→
V}
Nếu X(k) = R hoặc
F
0
=
∅
, thì kết
thúc, và ta có
X
+
= X(k).
(iii) Nếu điều kiện kết thúc: X
(k)
= X
(k
−
1)
thoả mãn, thì thuật toán dừng, ta có X
+
= X
(k)
. Ngược lại, tăng k lên 1 và quay lại bước (ii).
Ví dụ
: Cho lược đồ R=(A,B,C,D,E,G) và tập phụ thuộc hàm F gồm các phụ thuộc
hàm sau
f
1
: AB
→
C
f
2
: C
→
A
f
3
: BC
→
D
f
4
: ACD
→
B
f
5
: D
→
EG
f
6
: BE
→
C
f
7
: CG
→
BD
f
8
: CE
→
AG
Đặt X = (B,D), ta áp dụng thuật toán trên để xác định bao đóng X
+
.
Đặt X(0) := X = (B,D),
F
0
:= F = { f1 , f2 , ... , f8 }
Tính X(1): Đặt X(1) := X(0) = (B,D). Duyệt qua các phụ thuộc hàm trong
F
0
ta
thấy
Phụ thuộc hàm f3: BC
→
D; f4: ACD
→
B có
vế phải thuộc X(1). Vậy ta loại f3 , f4 khỏi
F
0
và được
F
0
= { f
1
, f
2
, f
5
, f
6
, f
7
, f
8
}
Phụ thuộc hàm f5:D
→
EG có vế trái D
⊂
X(1)
, vì vậy
X
(2)
:= X
(1)
∪
{E,G} = {B,D,E,G} và F
0
= { f
1
, f
2
, f
6
, f
7
, f
8
}
Phụ thuộc hàm
f6: BE
→
C có vế trái
BE
⊂
X(1) , vì vậy
X
(3)
:= X
(2)
∪
{C} = {B,C,D,E,G} và F
0
= { f
1
, f
2
, f
7
, f
8
}
Phụ thuộc hàm f7: CG
→
BD có vế phải
thuộc X(1). Vậy ta loại f7 khỏi F0 và được
F
0
= { f
1
, f
2
, f
8
}
Phụ thuộc hàm
f8: CE
→
AG có vế trái
CE
⊂
X(1) , vì vậy
X
(4)
:= X
(3)
∪
{A,G} = {A,B,C,D,E,G} và F
0
= { f
1
, f
2
}
Vì đến đây X
(4)
= R, nên quá trình giải dừng và X
+
= R.
Phủ của tập phụ thuộc hàm:
Phủ tương đương:
Cho 2 tập phụ thuộc hàm F và G, F được gọi là phủ của tập G nếu G
⊂
F
+
. Hai tập
phụ thuộc hàm F và G được gọi là tương đương nếu F phủ G và G phủ F:
F
+
=
G
+
Để xác định phụ thuộc hàm Y
→
Z
∈
G
+
hay không ta sử dụng thuật toán tính bao
đóng tập thuộc tính để tính
Y
+
đối với G và kiểm tra xem Z
⊂
Y
+
hay không?
Bổ đề:
Nếu F
⊂
G
+
thì
F
+
⊂
G
+
Chứng minh:
Cần CM
F
+
⊂
G
+
⇒
∀
(X
→
Y)
∈
F
+
. CM: (X
→
Y)
∈
G
+
Không mất tính tổng quát. Giả sử xét một quan hệ bất kỳ thoả G, cần chứng minh:
r thoả X
→
Y
Thật vậy: r thoả G
⇒
r thoả
G
+
(theo ĐN:
G
+
=
{ X
→
Y|G
m
X
→
Y})
⇒
r thoả F (theo gt)
⇒
r thoả
F
+
(theo ĐN)
⇒
r thoả X
→
Y (đpcm)
Phủ cực tiểu:
a.
Tập phụ thuộc hàm có vế trái dư thừa:
F là tập phụ thuộc hàm trên lược đồ quan hệ Q, Z là tập các thuộc tính, Z
→
Y
∈
F.
Nói rằng phụ thuộc hàm Z
→
Y có vế trái dư thừa (phụ thuộc hàm không đầy đủ) nếu
có 1 A
∈
Z
sao cho:
F = F – { Z
→
Y }
∪
{(Z-A)
→
Y}
Ngược lại Z
→
Y là phụ thuộc hàm có vế trái không dư thừa hay là phụ thuộc hàm
đầy đủ vào Z hay phụ thuộc hàm đầy đủ.
Ví dụ
: Q(A, B, C), F = {AB
→
C, B
→
C}
F = F – {AB
→
C}
∪
{(AB – A)
→
C} = {B
→
C}
AB
→
C: là phụ thuộc hàm không đầy đủ.
B
→
C: là phụ thuộc hàm đầy đủ.
b.
Tập phụ thuộc hàm có vế phải có một thuộc tính:
Mỗi tập phụ thuộc hàm F đều tương đương với 1 tập phụ thuộc hàm G mà vế phải
của các phụ thuộc hàm trong G chỉ gồm 1 thuộc tính.
Ví dụ
: Cho F = {A
→
BC, B
→
C, AB
→
D}
Ta suy ra F = {A
→
B, A
→
C, B
→
C, AB
→
D} = G
G được gọi là tập phụ thuộc hàm có vế phải có một thuộc tính.
c.
Tập phụ thuộc hàm dư thừa:
Nói rằng F là tập phụ thuộc hàm dư thừa nếu tồn tại F’
⊂
F sao cho F’
≡
F. Ngược
lại F là phụ thuộc hàm không dư thừa.
Ví dụ
: Cho F = {A
→
BC, B
→
D, AB
→
D} thì F dư thừa vì:
F
≡
F’= { A
→
BC, B
→
D}
d.
Tập phụ thuộc hàm tối thiểu:
Cho tập phụ thuộc hàm F, F được gọi là phủ cực tiểu nếu nó thoả mãn đồng thời 3
tính chất sau:
F là tập phụ thuộc hàm có vế trái không dư thừa.
F là tập phụ thuộc hàm có vế phải là 1 thuộc tính.
F là tập phụ thuộc hàm không dư thừa.
e.
Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm:
Đầu vào
: Tập phụ thuộc hàm F.
Đầu ra
: Tập phụ thuộc hàm tối thiểu G tương đương với F.
Phương pháp
:
∀
A
∈
Y} ( G tương đương F)
Bước 1:
Đặt G = {X
→
A |
∃
X
→
Y
∈
F &
Bước 2
: Lần lượt xét các FD X
→
A
∈
G theo
thứ tự nào đó nếu G \ {X
→
A} còn tương đương với F thì loại X
→
A ra khỏi G và đặt
lại:
G = G \ {X
→
A}
Bước 3:
Lần lượt xét các FD X
→
A
∈
G, ứng
với mỗi FD X
→
A
∈
G ta lại xét từng thuộc tính B
∈
X nếu G \ {X
→
A}
∪
X \ {B}
→
A
mà còn tương đương với G thì loại B ra khỏi X và đặt lại:
G = G \ {X
→
A}
∪
X \ {B}
→
A
Ví dụ
: Cho tập FD F = {A
→
B, A
→
C, B
→
C
,
B
→
A, C
→
A}. Tìm phủ cực tiểu của F.
Ta có: G = F.
Lần lượt xét các FD của G theo thứ tự cột.
Xét A
→
B: Kiểm tra xem (G \
{A
→
B})
+
=
G
+
⇔
A
+
/ G \ {A
→
B}
→
B?
Ta có:
A
+
= AC
⊄
B. Vậy không loại A
→
B
Xét B
→
A: Kiểm tra xem (G \
{B
→
A})
+
=
G
+
⇔
B
+
/ G \ {B
→
A}
→
A?
Ta có:
B
+
= ABC
⊂
A. Vậy loại B
→
A
Xét A
→
C: Kiểm tra xem (G \
{A
→
C})
+
=
G
+
⇔
A
+
/ G \ {A
→
C}
→
C?
Ta có:
A
+
= ABC
⊂
C. Vậy loại A
→
C
Xét C
→
A: Kiểm tra xem (G \
{C
→
A})
+
=
G
+
⇔
C
+
/ G \ {C
→
A}
→
A?
Ta có:
C
+
= C
⊄
A. Vậy không loại C
→
A
Xét B
→
C: Kiểm tra xem (G \
{B
→
C})
+
=
G
+
⇔
B
+
/ G \ {B
→
C}
→
C?
Ta có:
B
+
= B
⊄
C. Vậy không loại B
→
C
Vậy phủ tối thiểu là: G = {A
→
B, C
→
A,
B
→
C}
Ví dụ: Cho lược đồ R(A,B,C,D,E,G) và tập phụ thuộc hàm F gồm các phụ thuộc hàm sau: f 1 : AB → C f 5 : D → EG f 2 : C → A f 6 : BE → C f 3 : BC → D f 7 : CG → BD f 4 : ACD → B f 8 : CE → AG Tính phủ tối thiểu của F? Phân rã vế phải các phụ thuộc hàm trong F. Tập G thu được gồm các phụ thuộc hàm: AB → C BE → C C → A CG → B BC → D CG → D ACD → B CE → A D → E CE → G D → G Ta có: G = F. Lần lượt xét các FD của G theo thứ tự cột. Xét AB → C: Kiểm tra xem (G \ {AB → C}) + = G + ⇔ ( AB) + / G \ {AB → C} → C? Ta có: ( AB) + = AB ⊄ C. Vậy không loại AB → C Xét C → A: Kiểm tra xem (G \ {C → A}) + = G + ⇔ C + / G \ {C → A} → A? Ta có: C + = C ⊄ A. Vậy không loại C → A Xét BC → D: Kiểm tra xem (G \ {BC → D}) + = G + ⇔ ( BC ) + / G \ {BC → D} → D? Ta có: ( BC ) + = ABC ⊄ D. Vậy không loại BC → D Xét ACD → B: Kiểm tra xem (G \ {ACD → B}) + = G + ⇔ ( ACD ) + / G \ {ACD → B} → B? Ta có: ( ACD ) + = ABCDEG ⊂ B. Vậy loại ACD → B ⇔ D + / G \ {D → E} → E? Xét D → E: Kiểm tra xem (G \ {D → E}) + = G + Ta có: D + = DG ⊄ E. Vậy không loại D → E Xét D → G: Kiểm tra xem (G \ {D → G}) + = G + ⇔ D + / G \ {D → G} → G? Ta có: D + = DE ⊄ G. Vậy không loại D → G Xét BE → C: Kiểm tra xem (G \ {BE → C}) + = G + ⇔ ( BE ) + / G \ {BE → C} → C? Ta có: ( BE ) + = ö ⊄ C. Vậy không loại BE → C Xét CG → B: Kiểm tra xem (G \ {CG → B}) + = G + ⇔ (CG) + / G \ {CG → B} → B? Ta có: (CG) + = ACDEG ⊄ B. Vậy không loại CG → B Xét CG → D: Kiểm tra xem (G \ {CG → D}) + = G + ⇔ (CG) + / G \ {CG → D} → D? Ta có: (CG) + = ABCDEG ⊂ D. Vậy loại CG → D Xét CE → A: Kiểm tra xem (G \ {CE → A}) + = G + ⇔ (CE ) + / G \ {CE → A} → A? Ta có: (CE ) + = ACG ⊂ A. Vậy loại CE → A Xét CE → G: Kiểm tra xem (G \ {CE → G}) + = G + ⇔ (CE ) + / G \ {CE → G} → G? Ta có: (CE ) + = AC ⊄ G. Vậy không loại CE → G Vậy phủ tối thiểu là: G = {AB → C, C → A, BC → D, D → E, D → G, BE → C, CG → B, CE → G} Khoá của lược đồ quan hệ: Định nghĩa: Cho lược đồ quan hệ R(U), tập FD F của R. Tập thuộc tính K ⊆ U được gọi là khoá của R nếu K thoả mãn đồng thời 2 tính chất sau: i K → U ∈ F + ⇔ K + = U và ii ∀ K ' ⊂ K : K’ không → U ⇔ (K’ ) + ≠ U Ví dụ: Cho LĐQH R(U), với U = ABCD, và F = {A → B, A → C, B → A, AB → D} a. Tìm X + với X = AB b. Kiểm tra xem X có phải là khoá của LĐQH R không? Giải: iii X thoả vì X + =U iv Tìm A + và B + nếu A + =U hoặc B + =U thì X không là khoá, ngược lại A + ≠ U và B + ≠ U thì X là khoá. Ta có A + = ABCD = U. Vậy X không là khoá mà A là khoá. Nhận xét: Trong 1 LĐQH có tồn tại nhiều tập thuộc tính khoá khác nhau. Với ví dụ trên ta có 2 tập thuộc tính khoá: K1 = A, K2 = B. Thuật toán tìm 1 khoá của LĐQH: Vào : LĐQH R(U) Tập FD F Ra : 1 khoá của LĐQH R Phương pháp : K:=U; For each A in U do If (K - {A} ) + =U then K:=K – {A}; Return K; Ví dụ : Cho R(A, B, C); F = {A → B, A → C, B → A} Đặt K = U = ABC Loại A vì ((K - {A} ) = BC = ABC = U). Vậy K = BC Không loại B vì ((K - {B} ) = C = C ≠ U) Loại C vì ((K - {C} ) + = B + = ABC = U). Vậy K = B Công thức tìm giao tất cả các khoá trong LĐQH (định lý) : Cho LĐQH R(U), tập FD F. Giao của tất cả các khoá trong LĐQH R là công thức sau: M=u- ∪ (R – L) ∀ (L → R) ∈ F Trong đó: R: Right, L: Left a. Ví dụ 1 : R (A, B, C), F = {A → B, A → C, B → A}. Suy ra M = ABC – BCA =khong chua b. Ví dụ 2 : R (C, S, Z), F = {CS → Z, Z → C}. Suy ra M = CSZ – ZC = S c. Định lý 1 : Nếu bao đóng giao của tất cả các khóa trong LĐQH R(U) mà bằng U thì lược đồ đó duy nhất tồn tại 1 khoá là M d. Thuật toán tìm tất cả các khoá của LĐQH : Vào : LĐQH R(U) Tập phụ thuộc hàm F. Ra : Tập tất cả các khoá {K1, K2,…, Km} của LĐQH R. Phương pháp: M=u- ∪ (R – L) ∀ (L → R) ∈ F If M + = U then Return K =M; // có duy nhất một khoá K = M Else { D:= ∪ R - ∪ L; ∀ (L → R) ∈ F ∀ (L → R) ∈ F j:=1; K:={}; T:=u-DM; //M: tập thuộc tính khoá, T:tập thuộc tính nghi ngờ là khóa For each T i in T do If ( T i M ) + =U then { K = T i M; // T i M nghi ngờ là khoá K = K + { K j }; j=j+1; } For each K i , Kj in K do If K i ⊂ Kj then // K j không phải là khoá K = K – { K j }; Return K; 1. Dạng chuẩn thứ nhất (1NF): Quan hệ gọi là ở dạng chuẩn thứ nhất hay quan hệ chuẩn hoá nếu miền giá trị của mỗi thuộc tính chỉ chứa những giá trị nguyên tử, tức là không phân chia được nữa. Như vậy mỗi giá trị trong quan hệ cũng là nguyên tử Dạng chuẩn 1 chỉ có ỹ nghĩa ở mức thể hiện của lược đồ quan hệ, vì chỉ liên quan đến giá trị các thuộc tính của các bộ trong một quan hệ được định nghĩa trên lược đồ quan hệ đó. Dạng chuẩn thứ 2 (2NF): Thuộc tính A gọi là phụ thuộc hàm đầy đủ vào thuộc tính X nếu X → A là phụ thuộc hàm nguyên tố. Giả sử K là khóa của lược đồ R. Khi đó mọi thuộc tính không khoá A của R đều phụ thuộc hàm vào khoá K: K → A. Nếu A không phụ thuộc hàm đầy đủ vào K thì tồn tại tập con thực sự H của K xác định hàm A, tức là H → A. Khi đó phụ thuộc hàm H → A gọi là phụ thuộc hàm bộ phận. Một lược đồ quan hệ gọi là ở dạng chuẩn 2 nếu nó ở dạng chuẩn 1 và không có phụ thuộc hàm bộ phận, tức là mọi thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào các khoá của lược đồ. a. Ví dụ 1: Cho LĐQH R (MaSV, Hoten, Mon, Diem), F= {MaSV → Hoten, MaSV, Mon → Diem} Để xác định dạng chuẩn 2: Khoá: K = {MaSV, Mon} Không khoá: {Hoten, Diem} Kiểm tra thuộc tính không khoá có phụ thuộc hàm đầy đủ vào K không? LĐQH trên không phải là 2NF vì tồn tại K’={MaSV} ⊂ K mà K’ → Hoten b. Ví dụ 2: Cho LĐQH R(A, B, C, D), F={AB → C, BC → D} Khoá K = AB Tập thuộc tính không khoá: {C, D} LĐQH trên là 2NF vì K’={B} hoặc {A} không xác định C, D c. Ví dụ 3: Cho LĐQH R(A, B, C) và F= {A → B, B → C Khoá: K = A Vậy R là 2NF Dạng chuẩn thứ 3 (3NF): Cho LĐQH R(U), tập FD F. LĐQH R được gọi là ở dạng 3NF nếu trong F không tồn tại 1 phụ thuộc hàm (FD): X → A, A ∉ X, X + ≠ U và A là thuộc tính không khoá. a. Ví dụ 1 : Cho LĐQH R(A, B, C, D) và F = {AB → C, BC → D} Khoá K= {AB} Thuộc tính không khoá: {C, D} LĐQH trên là 2NF nhưng không là 3NF vì tồn tại phụ thuộc hàm {BC → D} ∈ F mà ( BC ) + ≠ U b. Ví dụ 2: Cho LĐQH R(C, S, Z), F= {CS → Z, Z → C} Khoá K1 ={CS}, K2={SZ}. Không có thuộc tính không khoá LĐQH R là 3NF. c. Ví dụ 3: Cho LĐQH R(S, I, D, M) và F={SI → D, SD → M} Khoá K= {SI} Thuộc tính không khoá:{D,M} Lược đồ R trên là 2NF nhưng không là 3NF vì tồn tại SD → M mà (SD) + ≠ U và M ∉ SD d. Nhận xét: Để kiểm tra 1 LĐQH R(U), tập FD cho trước có ở dạng 3NF không thì ta lần lượt thực hiện các bước sau: Xác định tất cả các tập thuộc tính khoá của R. Suy ra tập thuộc tính không khoá. Lần lượt xét các phụ thuộc hàm X → A ∈ F trong đó A ∉ X, A là thuộc tính không khoá. Tính X + theo F rồi kiểm tra X + =U? Nếu không bằng thì kết thúc và kết luận R không là 3NF. Dạng chuẩn Boyce-Codd (BCNF): Cho LĐQH R(U) và FD F. LĐQH R ở dạng Boyce-Codd nếu mọi phụ thuộc hàm X → A ∈ F đều có X + =U. Ví dụ : Cho R (C, S, Z), F = {CS → Z, Z → C} LĐQH trên không là BCNF vì tồn tại {Z → C} mà Z + ≠ U Chú ý: Khi tiến hành chuẩn hoá 1 lược đồ R cho trước thì tập FD F xét ở đây được hiểu là ở dạng tối thiểu.
Bạn đang đọc truyện trên: TruyenTop.Vip