Quan hệ này không đạt chuẩn 1 vì các thuộc tính TENMONHOC, DIEMTHI của bộ thứ nhất không mang giá trị đơn (chẳng hạn sinh viên NGUYEN THI THU có thuộc tính TENMONHOC là KY THUAT LAP TRINH, TOAN ROI RAC, CO SO DU LIEU).
Ta hoàn toàn có thể đưa quan hệ trên về dạng chuẩn 1 như sau:
Chú ý ràng khi xét các dạng chuẩn, nếu ta không nói gì thêm, ta hiểu dạng chuẩn đang xét ít nhất là đạt dạng chuẩn 1.
-
Dạng Chuẩn 2 (Second Normal Form)
Một lược đồ quan hệ Q ở dạng chuẩn 2 nếu Q đạt chuẩn 1 và mọi thuộc tính không khóa của Q đều phụ thuộc đầy đủ vào khóa.
Thuật toán kiểm tra dạng chuẩn 2
Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: khẳng định Q đạt chuẩn 2 hay không đạt chuẩn 2.
Bước 1: Tìm tất cả khóa của Q
Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả tập con thật sự S của K.
Bước 3: Nếu có bao đóng S+ chứa thuộc tính không khóa thì Q không đạt chuẩn 2
Ngược lại thì Q đạt chuẩn 2
Ví dụ 2: Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc hàm
F={ABC; BD; BCA}. Hỏi Q có đạt chuẩn 2 không?
Giải:
TN={B}, TG={AC}
-
Xi
|
(TN Xi)
|
(TN Xi)+
|
Siêu khóa
|
khóa
|
|
B
|
BD
|
|
|
A
|
AB
|
ABCD
|
AB
|
AB
|
C
|
BC
|
ABCD
|
BC
|
BC
|
AC
|
ABC
|
ABCD
|
ABC
|
|
Khóa là K1=AB và K2=BC. Ta thấy BK1, BD,D là thuộc tính không khóa thuộc tính không khóa không phụ thuộc đầy đủ vào khóa Q không đạt chuẩn 2.
Ví dụ 3: Quan hệ sau đạt chuẩn 2.
Q(G,M,V,N,H,P) F={GM; GN; GH; GP; MV; NHPM}
Giải:
TN={G} TG={M,N,H,P}
-
Xi
|
(TN Xi)
|
(TN Xi)+
|
Siêu khóa
|
khóa
|
|
G
|
Q+
|
G
|
G
|
M
|
GM
|
Q+
|
GM
|
|
N
|
GN
|
Q+
|
GN
|
|
MN
|
GMN
|
Q+
|
GMN
|
|
H
|
GH
|
Q+
|
GH
|
|
MH
|
GMH
|
Q+
|
GMH
|
|
NH
|
GNH
|
Q+
|
GNH
|
|
MNH
|
GMNH
|
Q+
|
GMNH
|
|
P
|
GP
|
Q+
|
GP
|
|
MP
|
GMP
|
Q+
|
GMP
|
|
NP
|
GNP
|
Q+
|
GNP
|
|
MNP
|
GMNP
|
Q+
|
GMNP
|
|
HP
|
GHP
|
Q+
|
GHP
|
|
MHP
|
GMHP
|
Q+
|
GMHP
|
|
NHP
|
GNHP
|
Q+
|
GNHP
|
|
MNHP
|
GMNHP
|
Q+
|
GMNHP
|
|
Lược đồ quan hệ Q chỉ có một khóa và khóa chỉ có một thuộc tính nên mọi thuộc tính đều phụ thuộc đầy đủ vào khóa Q đạt chuẩn 2
Hệ quả:
-
Nếu Q đạt chuẩn 1 và tập thuộc tính không khóa của Q bằng rỗng thì Q đạt chuẩn 2
-
Nếu tất cả khóa của quan hệ chỉ gồm một thuộc tính thì quan hệ đó ít nhất đạt chuẩn 2.
Ví dụ 4: Q(A,B,C,D,E,H) F={A E; C D; E DH}
Giải:
TN={ACB} TG={E}
-
Xi
|
(TN Xi)
|
(TN Xi)+
|
Siêu khóa
|
khóa
|
|
ACB
|
ABCDEH
|
ACB
|
ACB
|
E
|
ACBE
|
ABCDEH
|
ACBE
|
|
khóa của Q là K = {ABC}.CK, CD, D là thuộc tính không khóa D phụ thuộc không đầy đủ vào khóa nên Q không đạt chuẩn 2.
-
Dạng Chuẩn 3 (Third Normal Form)
Thuộc tính phụ thuộc bắc cầu
Q là lược đồ quan hệ, X,Y là hai tập con của Q+, A là một thuộc tính.
Nói rằng A phụ thuộc bắc cầu vào X nếu cả ba điều sau thỏa:
-
X Y,Y A
-
Y X
-
A XY
Định nghĩa 1:
Lược đồ quan hệ Q ở dạng chuẩn 3 nếu mọi phụ thuộc hàm X A F+ với A X đều có:
-
Hoặc X là siêu khóa
-
Hoặc A là thuộc tính khóa
Định nghĩa 2:
Lược đồ quan hệ Q ở dạng chuẩn 3 nếu mọi thuộc tính không khóa của Q đều không phụ thuộc bắc cầu vào một khóa bất kỳ của Q
Hai định nghĩa trên là tương đương, tuy nhiên việc cài đặt thuật toán kiểm tra dạng chuẩn 3 theo định nghĩa 1 thì hiệu quả hơn nhiều vì không phải kiểm tra tính phụ thuộc bắc cầu.
Ta chứng minh hai định nghĩa tương đương bằng cách:
Từ định nghĩa 1 không có phụ thuộc bắc cầu vào một khóa bất kỳ của Q. Thật vậy:
Giả sử có phụ thuộc bắc cầu vào khóa nghĩa là có K Y,Y A,Y K và A KY. Y A là một phụ thuộc hàm nên theo định nghĩa 1 có hai trường hợp xảy ra cho Y:
-
Y là siêu khóa YK điều này mâu thuẫn với Y K.
-
Y không là siêu khóa A là thuộc tính khóa điều này trái với giả thiết A KY
Từ định nghĩa 2 nếu XAF+ với AX thì X là siêu khóa hoặc A là thuộc tính khóa
Nếu XAF+ với AX có X không là siêu khóa và A không là thuộc tính khóa thì dẫn đến một số điều sau:
A không là thuộc tính khóa A K
X không là siêu khóa X K
Tóm lại ta có KX, XA,X K và A KX
A phụ thuộc bắc cầu vào K điều này mâu thuẫn với định nghĩa 2.
Hệ quả 1: Nếu Q đạt chuẩn 3 thì Q đạt chuẩn 2
Hệ quả 2: Nếu Q không có thuộc tính không khóa thì Q đạt chuẩn 3.
Chứng minh:
Hệ quả 1: Giả sử Q đạt dạng chuẩn 3 và có thuộc tính không khóa A không phụ thuộc hàm đầy đủ vào khóa K K’ K sao cho K’A như vậy ta có KK’,K’A,K’ K, A KK’ Q có phụ thuộc bắc cầu.
Hệ quả 2: mọi phụ thuộc hàm trong Q đều có vế phải là thuộc tính khóa Q đạt dạng chuẩn 3
Định lý:
Q là lược đồ quan hệ
F là tập các phụ thuộc hàm có vế phải một thuộc tính.
Q đạt chuẩn 3 nếu và chỉ nếu mọi phụ thuộc hàm XAF với AX đều có X là siêu khóa hay A là thuộc tính khóa
Chứng minh:
Q đạt dạng chuẩn 3 theo định nghĩa ta suy ra mọi phụ thuộc hàm XAF với AX có X là siêu khóa hoặc A là thuộc tính khóa.
Ngược lại ta phải chứng minh nếu mọi phụ thuộc hàm XAF với AX có X là siêu khóa hoặc A là thuộc tính khóa thì mọi phụ thuộc hàm XAF+ với AX cũng có X là siêu khóa hoặc A là thuộc tính khóa
Giả sử có phụ thuộc hàm XAF+ với AX sao cho X không là siêu khóa và A không là thuộc tính khóa sẽ dẫn đến A X+ X {các thuộc tính khóa} điều này mâu thuẫn với A K.Trước khi chứng minh A X+ X {các thuộc tính khóa} ta có nhận xét sau:
X không là siêu khóa X+ cũng không là siêu khóa. Theo thuật toán tìm bao đóng, X+ được hình thành từ các Xi ở mỗi bước Xi cũng không là siêu khóa.
Bước cơ sở: X0 = X X0 X {các thuộc tính khóa}
Bước qui nạp: giả sử có Xi-1 X {các thuộc tính khóa}. Bao đóng Xi được hình thành do có fj = Xj Yj để Xi-1 Xj và Xi = Xi-1 Yj fj = Xj Yj là phụ thuộc hàm có Xj không là siêu khóa fj = Xj Yj là phụ thuộc hàm có Yj là thuộc tính khóa Xi = Xi-1 Yj X {các thuộc tính khóa}
Qua chứng minh trên AX+ X {các thuộc tính khóa} A X{các thuộc tính khóa} A{các thuộc tính khóa} điều này nghịch lý với điều A K.
Thuật toán kiểm tra dạng chuẩn 3
Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: khẳng định Q đạt chuẩn 3 hay không đạt chuẩn 3.
Bước 1: Tìm tất cả khóa của Q
Bước 2: Từ F tạo tập phụ thuộc hàm tương đương F1tt có vế phải một thuộc tính.
Bước 3: Nếu mọi phụ thuộc hàm X A F1tt với AX đều có X là siêu khóa hoặc A là thuộc tính khoá thì Q đạt chuẩn 3 ngược lại Q không đạt chuẩn 3
Ví dụ 5: Cho lược đồ quan hệ Q(A,B,C,D) F={ABC; DB; CABD}.Hỏi Q có đạt chuẩn 3 không?
Giải:
TN= TG={ABCD}
-
Xi
|
(TN Xi)
|
(TN Xi)+
|
Siêu khóa
|
khóa
|
|
|
|
|
|
A
|
A
|
A
|
|
|
B
|
B
|
B
|
|
|
AB
|
AB
|
ABCD
|
AB
|
AB
|
C
|
C
|
ABCD
|
C
|
C
|
AC
|
AC
|
ABCD
|
AC
|
|
BC
|
BC
|
ABCD
|
BC
|
|
ABC
|
ABC
|
ABCD
|
ABC
|
|
D
|
D
|
BD
|
|
|
AD
|
AD
|
ABCD
|
AD
|
AD
|
BD
|
BD
|
BD
|
|
|
ABD
|
ABD
|
ABCD
|
ABD
|
|
CD
|
CD
|
ABCD
|
CD
|
|
ACD
|
ACD
|
ABCD
|
ACD
|
|
BCD
|
BCD
|
ABCD
|
BCD
|
|
ABCD
|
ABCD
|
ABCD
|
ABCD
|
|
K1 = {AB}; K2 = {AD}; K3={C} là các khóa mọi phụ thuộc hàm XAF đều có A là thuộc tính khóa. Vậy Q đạt chuẩn 3
Ví dụ 6: Quan hệ sau đạt chuẩn 3. Q(N,G,P,M) F = {NGPM,MP}
-
Dạng Chuẩn BC (Boyce-Codd Normal Form)
Một quan hệ Q ở dạng chuẩn BC nếu mọi phụ thuộc hàm XA F+ với AX đều có X là siêu khóa.
Hệ quả 1: Nếu Q đạt chuẩn BC thì Q đạt chuẩn 3 (hiển nhiên do định nghĩa)
Hệ quả 2: Mỗi lược đồ có hai thuộc tính đều đạt chuẩn BC (xét phụ thuộc hàm có thể có của Q )
Định lý:
Q là lược đồ quan hệ
F là tập các phụ thuộc hàm có vế phải một thuộc tính.
Q đạt chuẩn BC nếu và chỉ nếu mọi phụ thuộc hàm XAF với AX đều có X là siêu khóa
Chứng minh:
Q đạt dạng chuẩn BC theo định nghĩa ta suy ra mọi phụ thuộc hàm XAF với AX có X là siêu khóa.
Ngược lại ta phải chứng minh nếu mọi phụ thuộc hàm XAF với AX có X là siêu khóa thì mọi phụ thuộc hàm ZBF+ với BZ cũng có Z là siêu khóa. Thật vậy, do ZB không là phụ thuộc hàm hiển nhiên nên theo thuật toán tìm bao đóng phải có XAF sao cho ZX (X là siêu khóa) Z là siêu khóa.
Thuật toán kiểm tra dạng chuẩn BC
Vào: lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: khẳng định Q đạt chuẩn BC hay không đạt chuẩn BC.
Bước 1: Tìm tất cả khóa của Q
Bước 2: Từ F tạo tập phụ thuộc hàm tương đương F1tt có vế phải một thuộc tính
Bước 3: Nếu mọi phụ thuộc hàm X A F1tt với AX đều có X là siêu khóa thì Q đạt chuẩn BC ngược lại Q không đạt chuẩn BC
Ví dụ 7: Q(A,B,C,D,E,I) F={ACDEBI;CEAD}. Hỏi Q có đạt chuẩn BC không?
Giải: TN={C} TG={ADE}
-
Xi
|
(TN Xi)
|
(TN Xi)+
|
Siêu khóa
|
khóa
|
|
C
|
C
|
|
|
A
|
AC
|
AC
|
|
|
D
|
CD
|
CD
|
|
|
AD
|
ACD
|
ABCDEI
|
ACD
|
ACD
|
E
|
CE
|
ABCDEI
|
CE
|
CE
|
AE
|
ACE
|
ABCDEI
|
ACE
|
|
DE
|
CDE
|
ABCDEI
|
CDE
|
|
ADE
|
ACDE
|
ABCDEI
|
ACDE
|
|
Chia sẻ với bạn bè của bạn: |