CHUẨN HÓA CƠ SỞ DỮ LIỆU
1
1. Đặt vấn đề 2. Dạng chuẩn 1 3. Dạng chuẩn 2 4. Dạng chuẩn 3 5. Dạng chuẩn Boyce-Codd 6. Chuẩn hóa lược đồ CSDL bằng phương pháp phân rã
1. ĐẶT VẤN ĐỀ
Xét quan hệ ĐẶT_HÀNG (SốĐH, NgàyĐH, MãKH,
SoáÑH DH01 DH02 DH02
NgaøyÑH 5/1/99 13/2/99 13/2/99
MaõKH KH01 KH05 KH05
MaõHH H01 H02 H03
SoáLöôïng 50 30 40
MãHH, SốLượng )
Với tập Pth F = { SốĐH NgàyĐH, MãKH ; SốĐH,
2
MãHH SốLượng } => Có Trùng lắp thông tin
1. ĐẶT VẤN ĐỀ
Tăng chí phí lưu trữ
Tăng chi phí kiểm tra RBTV
Thiếu nhất quán
Vi phạm tính toàn vẹn của dữ liệu
3
Sự trùng lắp thông tin dẫn đến:
1. ĐẶT VẤN ĐỀ
Tổ chức lại thành 2 quan hệ như sau:
ĐẶT_HÀNG ( SốĐH, NgàyĐH, MãKH )
Với F1 = { SốĐH NgàyĐH, MãKH }
CHITIẾT_ĐH (SốĐH, MãHH, SốLượng )
Với F2 = { SốĐH, MãHH SốLượng }
4
=> Không còn xảy ra tình trạng trùng lắp thông tin
1. ĐẶT VẤN ĐỀ
Để có thể đánh giá một cách cụ thể chất lượng thiết kế
của một lược đồ CSDL, lúc đầu E.F.Codd (tác giả của mô hình dữ liệu quan hệ) đưa ra 3 dạng chuẩn và sau đó R.F.Boyce và E.F.Codd cải tiến dạng chuẩn 3 gọi là dạng chuẩn Boyce-Codd (BC)
Các dạng chuẩn được định nghĩa dựa trên khái niệm phụ
5
thuộc hàm
1. ĐẶT VẤN ĐỀ
Để biểu diễn được mọi quan hệ trong CSDL
Tránh sai sót khi thêm, xóa, sửa dữ liệu
Tránh phải xây dựng lại cấu trúc của các quan hệ
khi cần đến các kiểu dữ liệu mới
6
Mục đích của quá trình chuẩn hóa
2. DẠNG CHUẨN 1
Thuộc tính đơn: Giả sử có lược đồ quan hệ Q. Một thuộc tính A của Q gọi là thuộc tính đơn nếu nó không phải là một sự tích hợp của nhiều thuộc tính khác
Ví dụ 1: Môn không là thuộc tính đơn
CHUYÊN_MÔN (MÃGV, MÔN )
MAGV MÔN
GV01 PASC, CTDL
7
GV02 CSDL, PTTKHT
2. DẠNG CHUẨN 1
Một lược đồ quan hệ Q được gọi là ở dạng chuẩn 1 nếu
Định nghĩa:
Một lược đồ CSDL được gọi là ở dạng chuẩn 1 nếu mọi
mọi thuộc tính của Q đều là thuộc tính đơn
8
lược đồ quan hệ con Qi của nó đều ở dạng chuẩn 1
2. DẠNG CHUẨN 1
Ví dụ:
Quan hệ CHUYÊN_MÔN không đạt dạng chuẩn 1
MAGV GV01 GV01 GV02
MOÂN PASC CTDL CSDL
GV02
PTTKHT
9
Khắc phục CHUYÊN_MÔN (MÃGV, MÔN )
3. DẠNG CHUẨN 2
Phụ thuộc đầy đủ:
Giả sử có 1 lược đồ quan hệ Q và tập phụ thuộc hàm F.
F
b) X A là phụ thuộc hàm nguyên tố
Thuộc tính A được gọi là phụ thuộc đầy đủ vào 1 tập thuộc tính X nếu: a) A X+
10
( không tồn tại X’ X, mà X’ A )
3. DẠNG CHUẨN 2
Một lược đồ quan hệ Q được gọi là ở dạng chuẩn 2 nếu
Q ở dạng chuẩn 1
Mọi thuộc tính không khóa của Q đều phụ
Định nghĩa:
thuộc đầy đủ vào các khóa của Q
Một lược đồ CSDL được gọi là ở dạng chuẩn 2 nếu mọi
11
lược đồ quan hệ con Qi của nó đều ở dạng chuẩn 2
3. DẠNG CHUẨN 2
Ví dụ: Quan hệ ĐẶT_HÀNG (SốĐH, MãHH, NgàyĐH,
MãKH, SốLượng )
Với tập Pth F = { SốĐH NgàyĐH, MãKH ; SốĐH,
MãHH SốLượng }
Không đạt dạng chuẩn 2
Khắc phục: Tách thành 2 quan hệ:
ĐẶT_HÀNG ( SốĐH, NgàyĐH, MãKH )
Với F1 = { SốĐH NgàyĐH, MãKH }
CHITIẾT_ĐH (SốĐH, MãHH, SốLượng )
Với F2 = { SốĐH, MãHH SốLượng }
12
3. DẠNG CHUẨN 2
Nếu lược đồ quan hệ Q chỉ có 1 khóa K và K chỉ có 1
Nhận xét
Một lược đồ quan hệ Q ở dạng chuẩn 2 vẫn có thể chứa
thuộc tính thì Q ở dạng chuẩn 2
13
đựng sự trùng lắp thông tin.
4. DẠNG CHUẨN 3
Phụ thuộc bắc cầu: Thuộc tính A Q+ được gọi là phụ thuộc bắc cầu vào tập
2) Y X F+
3) A (X Y)
thuộc tính X nếu YQ+ : 1) X Y F+ và Y A F+
14
Khi đó X A được gọi là phụ thuộc hàm bắc cầu
4. DẠNG CHUẨN 3
Một lược đồ quan hệ Q được gọi là ở dạng chuẩn 3
Định nghĩa:
Q ở dạng chuẩn 2
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 nào của Q
Một lược đồ CSDL được gọi là ở dạng chuẩn 3 nếu
nếu
15
mọi lược đồ quan hệ con Qi của nó đều ở dạng chuẩn 3
4. DẠNG CHUẨN 3
Ví dụ: Quan hệ GIẢNG_DẠY(MãLớp, MãsốGV, TênGV,
Địachỉ )
Với tập Pth F = { Mãlớp MãsốGV; MãSốGV
TênGV, Địachỉ }
Không đạt dạng chuẩn 3
Khắc phục: Tách thành 2 quan hệ:
GIẢNG_DẠY(MãLớp, MãsốGV)
Với tập Pth F1 = { Mãlớp MãsốGV}
GIÁO_VIÊN(MãsốGV, TênGV, Địachỉ )
Với tập Pth F2 = {MãSốGV TênGV, Địachỉ }
16
4. DẠNG CHUẨN 3
Chính phụ thuộc hàm bắc cầu là nguyên nhân dẫn đến
Nhận xét
Dạng chuẩn 3 là tiêu chuẩn tối thiểu trong thiết kế cơ
tình trạng trùng lắp thông tin
17
sở dữ liệu
5. DẠNG CHUẨN BOYCE-CODD
Một lược đồ quan hệ Q được gọi là ở dạng chuẩn
Định nghĩa:
Một lược đồ CSDL được gọi là ở dạng chuẩn BC nếu mọi lược đồ quan hệ con Qi của nó đều ở dạng chuẩn BC
18
Boyce-Codd (BC) nếu mọi phụ thuộc hàm không hiển nhiên của F đều có vế trái là khóa
5. DẠNG CHUẨN BOYCE-CODD
Nếu 1 lược đồ quan hệ Q ở dạng chuẩn BC thì cũng ở
Nhận xét:
Trong 1 lược đồ quan hệ Q ở dạng chuẩn BC, việc
dạng chuẩn 3
19
kiểm tra phụ thuộc hàm chủ yếu là kiểm tra khóa nội
Ví dụ PCGD(Malop, Mamon, MAGV) F={Malop, Mamon->MAGV; MAGV->Mamon}
20
Phân rã PCGD(Malop, MAGV) GV(MAGV, Mamon)
5. DẠNG CHUẨN BOYCE-CODD
Ví dụ:
ĐẶT_HÀNG ( SốĐH, NgàyĐH, MãKH )
Với F1 = { SốĐH NgàyĐH, MãKH }
CHITIẾT_ĐH (SốĐH, MãHH, SốLượng )
Với F2 = { SốĐH, MãHH SốLượng }
21
=> 2 quan hệ đều đạt dạng chuẩn Boyce-Codd.
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Quá trình chuẩn hóa 1 lược đồ CSDL nhằm mục đích nâng cao chất lượng thiết kế hay cụ thể hơn là đưa các lược đồ quan hệ con từ dạng chuẩn thấp lên dạng chuẩn cao hơn mà tối thiểu phải là dạng chuẩn 3.
Phương pháp phân rã là 1 phương pháp dùng để
22
chuẩn hóa 1 lược đồ CSDL
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Sự bảo toàn thông tin
Việc chuẩn hóa 1 lược đồ quan hệ hay 1 lược đồ CSDL
Phép phân rã Q thành Q1, Q2, … được gọi là bảo toàn
phải bảo đảm 1 yêu cầu: bảo toàn thông tin
thông tin nếu:
23
TQ: TQ = TQ [Q1] ►◄ TQ [Q2] … ►◄ …
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Định lý Delobel
24
Cho lược đồ quan hệ Q(XYZ) và tập phụ thuộc hàm F Nếu X Y F+ thì phép phân rã Q thành 2 lược đồ quan hệ con: Q1(XY) và Q2(XZ) là bảo toàn thông tin
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Phương pháp phân rã:
Begin F+ = F \ { f F+ / VT(f) VP(f) Q+ } IF (F+ ) Then
25
Begin B1.Chọn 1 f0: X Y F+ B2.Tạo các lược đồ quan hệ con Q1 và Q2:
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ
+ }
+ }
Q1 = X Y F1 ={ f F+ / VT(f) VP(f) Q1 Q2 = Q+ \ Y F2 = { f F+ / VT(f) VP(f) Q2 B3.Phân rã đệ quy Q1 và Q2 End;
26
End;
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Ví dụ:
Khóa của Q là {BDA}, {BDC}
BD G : không đạt dạng chuẩn 2
Cho lược đồ quan hệ Q(ABCDEG) và tập pth F = { AE C (f1), CG A (f2), BD G (f3), GA E (f4) }
27
=> Sử dụng phương pháp phân rã
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Ví dụ:
Q(ABCDEG)
f3
Q1(BDG) F1={BD G}
Q2(BDACE) F2 = {AE C}
Q22(BDAE)
Q21(AEC) F21={AE C}
F22={BDA E}
28
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Nhận xét:
Thuật toán phân rã như trên là bảo toàn thông tin (định
Các lược đồ quan hệ con cuối cùng (nút lá trong cây
lý Delobel)
Thuật toán phân rã có thể tạo ra những lược đồ quan hệ
phân rã) đều ít nhất là dạng chuẩn 3
29
con không có nhiều ngữ nghĩa trong thực tế
6. CHUẨN HÓA LƯỢC ĐỒ CSDL BẰNG PHƯƠNG PHÁP PHÂN RÃ Nhận xét:
Chất lượng của CSDL kết quả có phụ thuộc vào việc
Thông thường pth được chọn là pth gây ra chất lượng xấu của lược đồ quan hệ. (pth không đầy đủ, pth bắc cầu)
30
chọn pth f0 ở từng bước phân rã
