Cơ sở dữ liệu nâng cao - Buổi 4 - Chương 2: Giai đoạn thiết kế quan niệm (3)

 Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
10
II.3.3 DC3- Vấn ñề còn tồn tại 
Ví dụ 2.10: môi trường ứng dụng của ví dụ 2.9 có
thêm một ràng buộc mới: f4: M →P
 Quan hệ LICH_KT có hai khóa (N,G,P) và
(N,G,M), vẫn ñạt chuẩn 3. 
Xét thể hiện sau:
CSDL1058:00 – 10: 002
101
101
101
P
CSDL
CSDL
Giải thuật
M
8:00 – 10: 003
10:00 – 12: 002
8:00 – 10: 002
GN
T_LỊCH_KT
Thêm   Tạo thông tin trùng lắp
Thêm   vi phạm f4
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
11
II.3.4 Dạng chuẩn Boyce – Codd –
Kent (DC BCK)

 Định nghĩa:
Q ở DC BCK nếu và chỉ nếu ∀ X → A không 
hiển nhiên ñịnh nghĩa trên Q thì ∀B ∈ Q+, ta 
luôn có (X→B) là một PTH thuộc F+; 
hay nói cách khác, X chứa một khóa của Q

 Ví dụ 2.11: 
 Quan hệ LỊCH_KT với hai khóa ở ví dụ 2.10 
không ñạt dạng chuẩn BCK vì có M → P.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
12
III.3.4 DC BCK - Giới hạn 

 DC BCK quan tâm giải quyết vấn ñề trùng 
lắp thông tin, nhưng xem nhẹ một tiêu 
chuẩn khác: sự thuận lợi khi kiểm tra phụ
thuộc dữ liệu.

 Ví dụ 2.12:
Thay ñổi cấu trúc CSDL của ví dụ 2.10 ñể tất cả
quan hệ ñạt DC BCK:
COI_THI (GVCT, N,G,P) ; GD (M,GV)
LICH_KT_1 (M,P) ; LICH_KT_2 (M,N,G)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
13
III.3.4 DC BCK – Giới hạn (2)
 Minh họa thể hiện của các quan hệ:
Không còn trùng lắp thông tin, nhưng bất tiện khi kiểm 
tra N,G,P → M : phải kết LICH_KT_1 và LICH_KT_2
10110:00 – 12:002Trần Văn C
10110:00 – 12:002Nguyễn Thị B
1018:00 – 10:002Nguyễn Văn A
PGNGV_CT
T_COI_THI 
CSDL
Giải thuật
M
Y
X
GV
T_GD
101
101
P
CSDL
Giải thuật
M
T_LỊCH_KT_1
CSDL
Giải thuật
M
10:00 – 12: 002
8:00 – 10: 002
GN
T_LỊCH_KT_2
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
14
III.3.5 Tính chất lồng nhau của 
các dạng chuẩn
DC 1
DC 2
DC 3
DC BCK
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
15
III.3.6 Dạng chuẩn của cấu trúc CSDL

 Định nghĩa: 
 Cho một cấu trúc CSDL C = {}, i = 1..n
 Dạng chuẩn của C là dạng chuẩn thấp nhất 
trong các dạng chuẩn của các Qi

 Ví dụ 2.13:
 Cấu trúc CSDL ở ví dụ 2.9 ñạt DC BCK
 Cấu trúc CSDL ở ví dụ 2.10 ñạt DC3 (vì có một 
quan hệ con chỉ ñạt DC3)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
16
II.4 Cấu trúc CSDL tương ñương - 
Đặt vấn ñề
 Nguyên tắc tương ñương:
Nếu C ’= {} (i = 1..n) ñược dùng ñể 
lưu trữ dữ liệu thay cho C = , có nghĩa 
là:
 Thông tin và dữ liệu ñược xác ñịnh ở gñ 
phân tích & thu thập nhu cầu phải ñược tìm 
thấy ñầy ñủ trong C’
 Thông tin và dữ liệu ñược lưu trong C’ là
những TT&DL lẽ ra ñược lưu trong C .
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
17
II.4 Cấu trúc CSDL tương ñương 
 Khái niệm TT ñược lưu trữ trong CSDL:
 TT ñược lưu trữ trong Q: q, một bộ của Q, là TT 
ñược lưu trong Q. q là tường minh nếu không 
chứa giá trị Trống (Null).
 TT ñược lưu trữ trong C : TT lẽ ra ñược lưu 
trong U (hoặc trong C ) ñược lưu thực tế trong 
các thể hiện của Qi:

 Cho TU, một thể hiện bất kỳ của U, TQi = TU[Qi+]

 2 ñiều kiện sau phải ñược thỏa:
1.∀ u∈ TU, u ∈ TQi
2.∀q∈ TQi, q ∈ TU
i=1
n
i=1
n
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
18
II.4 Cấu trúc CSDL tương ñương (2)

 Hai ñiều kiện này không phải luôn luôn ñược thỏa

 …mà thông thường ta có: 
TU ⊆ TU[Qi+], ∀TU

 Ví dụ 2.14: với cấu trúc quan hệ phổ quát của Vd 2.4:
< LỊCH_COI_THI (GVCT, N,G,P,M,GV) ,
F = {f1: GVCT→N,G,P; f2: M → GV; f3: N,G,P→M} >
Cho cấu trúc CSDL sau:
C1={;
;
; F3’ ={f’3: N,G,P →M}> }
i=1
n
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
19
II.4 Cấu trúc CSDL tương ñương (3)
Giải thuật8:00–10:002Võ.T.D
CSDL10:00–12:002Tr.V.C
CSDL10:00–12:002Ng.T.B
Giải thuật8:00–10:002Ng.V.A
MGNGV_CT
T_COI_THI_1
Giải thuật1038:00–10:002
CSDL10110:00–12:002
Giải thuật1018:00–10:002
MPGN
T_LICH_KT
YCSDL
XGiải thuật
GVMT_GD
XGiải thuật1038:00–10:002Võ.T.D
XGiải thuật1018:00–10:002Võ.T.D
CSDL
CSDL
Giải thuật
Giải thuật
M
101
101
103
101
P
Y10:00–12:002Tr.V.C
Y10:00–12:002Ng.T.B
X8:00–10:002Ng.V.A
X8:00–10:002Ng.V.A
GVGNGV_CT
T_COI_THI_1 T_LICH_KT T_GD
Giống 
với TU?
(trang 15)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
20
II.4 Cấu trúc CSDL tương ñương (4)

 Ba quan niệm về tính tương ñương lược 
ñồ CSDL:
 Tính chất bảo toàn phụ thuộc
 Tính chất bảo toàn thông tin
 Biểu diễn trọn vẹn
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
21
II.4.1 Tính chất bảo toàn phụ thuộc (i)

 Ưu tiên việc kiểm tra các phụ thuộc dữ liệu

 Quan niệm: các thông tin của CSDL ñược 
thể hiện thông qua phụ thuộc dữ liệu
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
22
II.4.1 Tính chất bảo toàn phụ thuộc 
(i) (2)

 Đối với phụ thuộc hàm:
Cho C1= 
và C2 = {}, i=1..n, với Fi = F+[Qi+]
(Fi là nhng pth ca F ñược ñịnh nghĩa trên Qi)
C1 ≡ C2 nếu thỏa hai ñiều kiện sau:
(i.1) ∪iQi+ = Q+
(i.2) (∪iFi)+ = F+ (∪iFi ≡F)
Ví dụ 2.16: 
 Kiểm tra tính tương ñương (theo tiêu chuẩn btpth) 
của cấu trúc CSDL trong Vd 2.6 và 2.9 với cấu trúc 
ban ñầu trong Vd 2.4 
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
23
II.4.2 Tính chất bảo toàn thông tin (ii)

 C1 ≡ C2 nếu thoả hai ñiều kiện sau:
(ii.1) ∪iQi+ = Q+
(ii.2) Q[Qi+] = Q , nghĩa là: 
∀TQ ∈ Q, TQ = TQ[Qi+]i=1
n
i=1
n
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
24
II.4.2 Tính chất bảo toàn thông 
tin (ii) - Phương tiện kiểm tra

 Cho: C1= 
và C2 = {}, i=1..n, với Fi = F+[Qi+]

 Bảng Tableau và qui trình thay thế ñuổi, 
dựa vào lut pth, ñược sử dụng ñể kiểm 
tra tính bảo toàn thông tin của C2 .
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
25
II.4.2 Tính chất bảo toàn thông 
tin (ii) - Phương tiện kiểm tra (2)

 Bảng Tableau:
 Có m cột tương ứng với m thuộc tính của 
quan hệ Q
 n dòng tương tương ứng với n quan hệ con Qi
 Mỗi ô ở dòng i và cột j của bảng chứa một 
trong hai giá trị:

 aj nếu Qi+ có chứa thuộc tính tương ứng với cột j

 bk trong trường hợp ngược lại, với k bắt ñầu từ 1 
và tăng dần mỗi khi cần dùng ñến giá trị b
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
26
II.4.2 Tính chất bảo toàn thông tin (ii) - 
Phương tiện kiểm tra (3)

 Luật phụ thuộc hàm áp dụng vào Tableau:
Với X → A ∈F:
Chọn hai dòng w1 và w2 trong Tableau sc w1.X = w2.X:
Nếu w1.A ≠ w2.A thì:
Nếu w1.A = aj và w2.A = bk thì thay thế bk trong w2.A bằng 
aj
Nếu w1.A = bk và w2.A = aj thì thay thế bk trong w1.A bằng 
aj
Nếu w1.A = bk và w2.A = bk’ thì thay thế bk’ trong w1.A bằng 
bk
Cuối nếu
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
27
II.4.2 Tính chất bảo toàn thông tin (ii) - 
Phương tiện kiểm tra (4)

 Qui trình thay thế ñuổi:
1. ∀f ∈ F: 
Áp dụng luật pth cho f
Cuối ∀
2. Lặp lại bước 1 cho ñến khi nào không 
còn thay ñổi ñược giá trị nào trong bảng 
Tableau thì dừng.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
28
II.4.2 Tính chất bảo toàn thông tin (ii) - 
Phương tiện kiểm tra (5)

 Gọi T’ là bảng kết quả sau khi ñã áp dụng 
qui trình thay thế ñuổi trên bảng Tableau T
 Nếu T’ có một dòng chứa toàn các giá trị aj thì
C2 bảo toàn thông tin.
 Ngược lại thì C2 không bảo toàn thông tin.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
29
II.4.2 Tính chất bảo toàn thông tin (ii) - 
Phương tiện kiểm tra (6)

 Ví dụ 2.15: 
Xét cấu trúc sau có tương ñương với cấu trúc trong Vd 2.4:
C2 = { <COI_THI (GVCT, N, G, P), F1 = 
{f1:GVCT→N,G,P}>;
;
}
CT_MON
GD
COI_THI
a5a1
a6a5b6b5b4b3
b2b1a4a3a2a1
GVMPGNGV_CT
Áp dụng f1
Áp dụng f2a6a2 a3 a4b7 b8 b10b9
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
30
II.4.2 Tính chất bảo toàn thông tin (ii) 
(3)
Một thể hiện minh họa:
1038:00 – 10:002Vo.T.D
10110:00 – 12:002Tr.V.C
10110:00 – 12:002Ng.T.B
1018:00 – 10:002Ng.V.A
PGNGVCT
T_COI_THI
YCSDL
XGiải thuật
GVM
T_GD
Giải thuậtVo.T.D
CSDLTr.V.C
Ng.T.B
Ng.V.A
GVCT
CSDL
Giải thuật
M
T_CT_MON
XGiải thuật1018:00–10:002Võ.T.D
CSDL
CSDL
Giải thuật
M
101
101
101
P
Y10:00–12:002Tr.V.C
Y10:00–12:002Ng.T.B
X8:00–10:002Ng.V.A
GVGNGVCT
T_COI_THI T_CT_MON T_GD
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
31
II.4.2 Tính chất bảo toàn thông tin (ii) 
(4)

 Ví dụ 2.16 : 
 Dùng bảng Tableau và qui trình thay thế ñuổi ñể kiểm 
tra tính bảo toàn thông tin của cấu trúc trong ví dụ 3.15
 Không thay thế ñược nữa và không tìm ñược dòng nào 
chứa toàn aj C2 không bảo toàn thông tin.
GD
LICH_KT
COI_THI_1
a6a5b8b7b6b5
a5a4a3a2b3
a5b1a3a2a1
GVMPGNGV_CT
Áp dụng 
f2
(M→GV)a6
a6b2
b4
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
32
II.4.3 Biểu diễn trọn vẹn

 Cấu trúc CSDL C2 là một biểu diễn trọn 
vẹn của C1 nếu 3 ñiều kiện 
(i.1), (i.2) và (ii.2) ñều ñược thỏa. 

 C2 là biểu diễn trọn vẹn ≡ C1 vừa bảo toàn 
thông tin, vừa tạo thuận lợi cho việc kiểm 
tra PTH
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
33
Ví dụ 2.17:
 Cấu trúc trong Vd 2.6 và 2.9 ñạt tiêu 
chuẩn biểu diễn trọn vẹn
 Cấu trúc trong Vd 2.15 ñạt tiêu chuẩn 
bảo toàn thông tin, nhưng không bảo toàn 
pth 
(f3: N,G,P→ M không còn ñược ñịnh nghĩa 
trên quan hệ nào)
II.4.3 Biểu diễn trọn vẹn (2)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
34
Câu hỏi?