I. Một số khái niệm cơ bản
! Định nghĩa: Phép tách các lược đồ quan hệ R=
{A1, A2, . An} là việc thay thế lược đồ quan hệ R
bằng tập các lược đồ con {R1, R2, ., Rk}, trong
đó
R
i ⊂ R, i = 1,.,k - Ri là các lược đồ con
và R = R1 ∪ R2 ∪ . ∪ Rk
Không đòi hỏi các Ri phải là phân biệt
Mục đích: Loại bỏ các dị thường dữ liệu
10 trang |
Chia sẻ: thuychi16 | Lượt xem: 1548 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Cơ sở dữ liệu - Chương VIII: Chuẩn hóa csdl data normalization, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
CHƯƠNG VIII:
CHUẨN HÓA CSDL
Data normalization
Cơ sở dữ liệu 3
I. Một số khái niệm cơ bản
! Định nghĩa: Phép tách các lược đồ quan hệ R=
{A1, A2, .. An} là việc thay thế lược đồ quan hệ R
bằng tập các lược đồ con {R1, R2, .., Rk}, trong
đó
Ri ⊂ R, i = 1,..,k - Ri là các lược đồ con
và R = R1 ∪ R2 ∪ ... ∪ Rk
Không đòi hỏi các Ri phải là phân biệt
Mục đích: Loại bỏ các dị thường dữ liệu
Cơ sở dữ liệu 4
Ví dụ
MaCTY ĐC MH GIA
1 Thanh Xuân 1 10000
1 Thanh Xuân 2 15000
2 Đống Đa 1 12000
2 Đống Đa 2 16000
MaCTY ĐC
1 Thanh Xuân
2 Đống Đa
MaCTY MH GIA
1 1 10000
1 2 15000
2 1 12000
2 2 16000
MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL
S1
S1
S1
S2
S2
S3
S4
An
An
An
Hòa
Hoà
Thanh
Trang
HCM
HCM
HCM
HN
HN
NT
NT
01
01
01
02
02
03
03
P1
P2
P3
P1
P3
P2
P2
Táo
Cam
Chanh
Táo
Chanh
Cam
Cam
650
500
450
650
450
500
500
300
200
400
100
300
200
210
Phép tách-Kết nối không mất mát thông tin
! Giả sử R tách thành các lược đồ con R1, R2, ..,
Rk và F là một tập pth.
! Nói rằng phép tách R thành các lược đồ con R1,
R2, , Rk là tách - kết nối không mất mát
thông tin đối với F nếu với mỗi quan hệ r trên R
thoả F thì
r = ΠR1(r) * Π R2 (r) * ... * Π Rk(r)
tức là r được tạo nên từ phép kết nối tự nhiên
của các hình chiếu của nó trên các Ri, i= 1..,k
Cơ sở dữ liệu 5
Phụ thuộc hàm đầy đủ
! Cho lược đồ quan hệ (U,F), X, Y⊆U.
! Khi đó Y được gọi là phụ thuộc hàm đầy đủ vào tập X nếu
như Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm
vào bất kỳ tập con thực sự nào của X, tức là:
- X → Y
- ∀Z ⊂ X thì Z /→ Y, mọi tập con thực sự của X đều không
thể xác định hàm Y
! VD: F = {AB ! C, A ! C}.
- Ta có pth AB ! C không phải là pth đầy đủ vì có pth A
! C
Cơ sở dữ liệu 6
Phụ thuộc hàm bắc cầu
! Cho lược đồ quan hệ α = (U,F), X ⊆ U, A ∈ U,
thuộc tính A được gọi là phụ thuộc hàm bắc cầu
vào tập thuộc tính X nếu như ∃ Y ⊆ X để:
- X → Y, Y → A
- Nhưng Y /! X với A ∉ XY
! VD: R(ABCDE), F = {AB ! CD, D ! E}, khoá: AB.
- Ta có: AB ! E là pth bắc cầu vì: ∃ D ⊂ R:
" AB ! D D ! E
" D /! AB E ∉ ABD
Cơ sở dữ liệu 7
II. Kiểm tra phép tách-kết nối không mất thông tin
! Input:
- R = {A1, A2, .., An} – n thuộc tính tập pth F và
- phép tách p = (R1, R2, .., Rk) – k lược đồ con
! Output: Kiểm tra phép tách có mất mát
thông tin hay không ?
Cơ sở dữ liệu 8 Cơ sở dữ liệu 9
Thuật toán
Bước 1: Lập bảng với n+1 cột và k+1 hàng
- Cột thứ j# thuộc tính thứ j của lược đồ (Aj)
- Hàng thứ i # lược đồ Ri.
- Tại ô (i,j) điền kí hiệu aj nếu Aj ∈ Ri, ngược lại điền kí hiệu bij
Bước 2: thay đổi giá trị cho bảng
! Lần lượt xét các pth (X→Y) ∈ F
! Nếu tồn tại hai hàng mà tất cả các cột ứng với thuộc tính X có giá trị bằng
nhau thì phải bằng nhau ở thuộc tính Y
" nếu có một giá trị aj trong các cột tương ứng với các thuộc tính của Y thì thay
thế hết thành aj, nếu không thay thế hết bằng ký hiệu bij
! Lặp lại bước 2 (kể cả lặp lại các phụ thuộc hàm đã áp dụng) cho tới khi
không làm thay đổi gì bảng nữa
Bước 3: Đánh giá kết quả
- Nếu xuất hiện một hàng gồm toàn kí hiệu a1, a2, .. , an thì phép tách-kết
nối là không mất mát thông tin,
- ngược lại là phép tách-kết nối mất mát thông tin.
Cơ sở dữ liệu 10
Ví dụ 1:
! Cho quan hệ:
CungCap( MaNCC, Sname, Add, Item, Price )
! Tập phụ thuộc hàm: MaNCC→Sname,Add,
Sname,Item→Price
! Kiểm tra phép tách thành hai sơ đồ con
C o n g T y { M a N C C , S n a m e , A d d } v à
MatHang{MaNCC, Item, Price} có mất mát thông
tin?
Cơ sở dữ liệu 11
! Lập bảng: 3 hàng – 6 cột
! Xét S# → Sname, Add:
- có cả hai hàng bằng
nhau tại thuộc tính S#
- làm bằng nhau các kí
hiệu đối với thuộc tính
Sname và Add
" làm b22 thành a2
" làm b23 thành a3
! Bảng có một hàng bao
gồm các ký hiệu a =>
phép tách không mất
mát thông tin
S# Sname Add Item Price
S#, Sname, Add a1 a2 a3 b14 b15
S#, Item, Price a1 b22 b23 a4 a5
a5 a4 b23
a3
b22
a2
a1
b15 b14 a3 a2 a1
Price Item Add Sname S#
Ví dụ:
! R={MSNV,TenNV,MaSoDA,TenDA, DiadiemDa, Sogio}
! F = { MSNV ! TenNV,
MasoDA ! {TenDA, DiadiemDA},
{MaSoDA, MSNV} ! Sogio }
! Kiểm tra phép tách thành
- R1 = { MSNV, TenNV}
- R2 = { MaSoDa, TenDA, DiadiemDA}
- R3 = { MSNV, MasoDA, Sogio}
! Có mất mát thông tin?
Cơ sở dữ liệu 12
Ví dụ
! R={MSNV, TenNV, MaSoDA, TenDA, DiadiemDa, Sogio}
! F = { MSNV ! TenNV,
MasoDA ! {TenDA, DiadiemDA},
{MaSoDA, MSNV} ! Sogio }
! Kiểm tra phép tách thành
- R1 = {TenNV, DiadiemDA}
- R2 = { MSNV, MasoDA, Sogio, TenDA, DiadiemDA}
! Có mất mát thông tin?
Cơ sở dữ liệu 13
Cơ sở dữ liệu 21
III. Chuẩn hóa lược đồ quan hệ
! Chuẩn hóa là quá trình khảo sát danh sách các
thuộc tính và áp dụng các quy tắc phân tích vào
danh sách đó, biến đổi thành nhiều tập nhỏ hơn
# Tách bảng thành nhiều bảng nhỏ hơn
! Sao cho:
- Tối thiểu việc lặp lại
- Tránh dị thường thông tin
- Xác định và giải quyết được sự không rõ ràng,
nhập nhằng trong suy diễn
Cơ sở dữ liệu 22
! Các loại dạng chuẩn gồm:
- Dạng chuẩn 1 (1NF – First Normal Form)
- Dạng chuẩn 2 (2NF – Second Normal Form)
- Dạng chuẩn 3 (3NF)
- Dạng chuẩn Boye Code (BCNF)
BCNF
3NF
2NF
1NF
Cơ sở dữ liệu 23
1. Dạng chuẩn 1NF
! Lược đồ quan hệ R được gọi là 1NF nếu và chỉ nếu tất
cả các thuộc tính của R thoả mãn cả 3 điều kiện sau:
- là kiểu nguyên tố,
- giá trị của các thuộc tính trên các bộ là đơn trị,
- không có một thuộc tính nào có giá trị tính toán từ
1 số thuộc tính khác
! Chú ý: khi xét dạng chuẩn nếu không nói gì thêm thì
dạng chuẩn đang xét ít nhất là đạt dạng chuẩn một
! Biểu diễn sơ đồ dạng 1NF:
R(A1,A2,A3, A4, A5)
1
2 3
4
Cơ sở dữ liệu 24
MSKH TenKH TP PVC MSMH TenMH ĐG SL
S1 An HCM 01 P1
P2
P3
Táo
Cam
Chanh
650
500
450
300
200
400
S2 Hòa HN 02 P1
P3
Táo
Chanh
650
450
100
300
S3 Thanh NT 03 P2 Cam 500 200
S4 Trang NT 03 P2 Cam 500 210
Cơ sở dữ liệu 25
! Kết luận: Để kiểm tra một lược đồ có là
dạng 1NF không thực hiện kiểm tra
nếu:
- Không có thuộc tính đa trị
- Không có thuộc tính phức hợp
Các bất thường của quan hệ ở 1NF
! Lược đồ ở dạng 1NF gặp khó khăn thêm-xóa-sửa
! Nguyên nhân: Tồn tại thuộc tính không khóa phụ
thuộc hàm riêng phần vào khóa
! Giải quyết: đưa về dạng chuẩn cao hơn 2NF
Chương 4. Cơ sở dữ liệu
MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL
S1
S1
S1
S2
S2
S3
S4
An
An
An
Hòa
Hoà
Thanh
Trang
HCM
HCM
HCM
HN
HN
NT
NT
01
01
01
02
02
03
03
P1
P2
P3
P1
P3
P2
P2
Táo
Cam
Chanh
Táo
Chanh
Cam
Cam
650
500
450
650
450
500
500
300
200
400
100
300
200
210
2. Dạng chuẩn 2NF
! LĐQH R được gọi là đạt dạng chuẩn 2 nếu R đã ở
dạng chuẩn 1 và tất cả các thuộc tính không khóa
(thuộc tính không tham gia vào khóa) đều phụ thuộc
hàm đầy đủ vào khóa.
! Mục đích:
- Giản ước sự dư thừa dữ liệu
- Tránh các dị thường cập nhật gây nên do sự dư thừa
dữ liệu này
! Biểu diễn sơ đồ dạng 2NF:
Cơ sở dữ liệu 30
R(A1,A2,A3, A4, A5)
1
4 3
Cơ sở dữ liệu 33
Thuật toán kiểm tra dạng chuẩn 2
! Bước 1: Tìm tất cả các khóa của quan hệ
! Bước 2: Với mỗi khóa K, tìm bao đóng của tất cả các tập
con thực sự S của K
- Chú ý: nếu khóa có một thuộc tính đơn thì không
cần phải kiểm tra và ở 2NF
! Bước 3:
- nếu có bao đóng S+ chứa thuộc tính không khóa thì
quan hệ không đạt chuẩn 2
- ngược lại thì quan hệ đạt chuẩn 2 (không tồn tại S mà
S+ chứa thuộc tính không khóa)
Ví dụ: kiểm tra dạng 2NF của quan hệ
! 1- QLSV (MaSV, Ten, NS, DC, TenLop, KhoaHoc, MaMH, TenMH,
Diem)
F = { f1: MaSV ! Ten, NS, DC, TenLop
f2: TenLop ! KhoaHoc;
f3: MaMH ! TenMH;
f4 : TenMH ! MaMH;
f5: MaSV, MaMH ! Diem }
! 2- KQHT (MaSV, MaMH, TenMH, Diem)
FKQHT = { f1: MaMH ! TenMH; f2 : TenMH ! MaMH;
f3: MaSV, MaMH ! Diem }
! 3- SV (MaSV, Ten, NS, DC, TenLop, KhoaHoc)
FSV = { f1:MaSV ! Ten, NS, DC, TenLop;
f2: TenLop ! KhoaHoc}
Cơ sở dữ liệu 34
Thuật toán đưa về dạng 2NF
! Nhóm các thuộc tính phụ thuộc vào một phần của
khoá và thuộc tính một phần tách thành quan hệ
mới, lấy phần đó làm khoá chính cho quan hệ.
! Giữ các thuộc tính phụ thuộc hoàn toàn vào khoá
và giữ lại khoá của quan hệ đó
Cơ sở dữ liệu 38
R(A1,A2,A3, A4, A5)
R1(A2, A4)
R(A1,A2,A3, A5)
Cơ sở dữ liệu 39
Ví dụ:
Kết quả là gì?
NV( MaNV, MaPhong,TenNV, Gioitinh, Diachi,TenPhong )
! Ví dụ 3:
- Cho R2 (Số hoá đơn, Số sản phẩm, Tên sản
phẩm, Lượng yêu cầu)
- F = { Số sản phẩm ! Tên sản phẩm }
- Hỏi quan hệ có ở dạng 2NF không? Nếu chưa
tách thành lược đồ ở dạng 2NF
Cơ sở dữ liệu 40
Các bất thường của quan hệ ở 2NF
! Khi tiến hành Thêm-Sửa-Xóa có thể không
thực hiện được hoặc tạo ra dị thường dữ liệu.
! Nguyên nhân: Tồn tại thuộc tính không
khóa phụ thuộc bắc cầu vào khóa
! Giải quyết: đưa về chuẩn cao hơn 3NF
Cơ sở dữ liệu 43 Cơ sở dữ liệu 44
3. Dạng chuẩn 3NF
! Lược đồ R ở 3NF nếu:
- Ở dạng 2NF
- Mọi thuộc tính không khóa đều không phụ thuộc bắc
cầu vào bất kỳ khóa chính của quan hệ
! Xét mọi pth X ! A thì
- Hoặc X là một siêu khóa của R
- Hoặc A là một thuộc tính khóa của R
! Sơ đồ:
R(A1,A2,A3, A4, A5)
1
4
Cơ sở dữ liệu 47
Thuật toán kiểm tra dạng chuẩn 3
! Output: kết luận Q đạt chuẩn 3 hay không đạt chuẩn 3
! Thuật toán:
- 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
F có vế phải một thuộc tính
- Bước 3: Kiểm tra
" Nếu mọi phụ thuộc hàm X!A ∈ F với A∉X đều
có X là khóa hoặc A là thuộc tính khóa thì Q đạt
chuẩn 3
" ngược lại Q không đạt chuẩn 3 (∃ X → A mà X
không là khóa và A không là thuộc tính khóa)
Cơ sở dữ liệu 48
! Ví dụ 1: Xét quan hệ CNHAN nhu sau:
- CNHAN(MACN, LOAINGHE, HESOTHUONG)
- các pth:
" MACN → LOAINGHE
" MACN → HESOTHUONG
" LOAINGHE → HESOTHUONG
" Hỏi lược đồ có đạt chuẩn 3 không?
Cơ sở dữ liệu 49
! Ví dụ 2: Cho lược đồ quan hệ
Q(A,B,C,D) và
F = { AB !C, D !B, C !ABD}. Hỏi Q
có đạt chuẩn 3 không?
Cơ sở dữ liệu
Đưa về dạng 3NF
! Tạo quan hệ mới gồm các thuộc tính phụ
thuộc bắc cầu vào thuộc tính khóa, lấy thuộc
tính bắc cầu làm khoá
! Giữ lại các thuộc tính phụ thuộc trực tiếp vào
khoá
! Thuộc tính bắc cầu nằm ở hai quan hệ
R(A1,A2, A3, A4, A5)
R1(A2, A4)
R(A1, A2, A3, A5)
Cơ sở dữ liệu 51
Ví dụ:
Kết quả 3NF là gì?
NV(MaNV,MaPhong,TenNV,Gioitinh,Diachi,TenPhong)
Cơ sở dữ liệu 52
! Ví dụ 4: Xét lược đồ quan hệ
! NHÂNVIÊN_ĐƠNVỊ( HọtênNV, MãsốNV, Ngàysinh,
Địachỉ, MãsốĐV, TênĐV, MãsốNQL)
! Với các phụ thuộc hàm:
- MãsốNV→HọtênNV, Ngàysinh,Địachỉ,MãsốĐV,TênĐV, MãsốNQL
- MãsốĐV→ TênĐV, Mã sốNQL
! Lược đồ có ở dạng 3NF không? Tách về 3NF
Ví dụ: Xây dựng chuẩn 3NF
! Ví dụ:Tập pth F được định nghĩa trên R như sau:
! F= { 1. MSKH ! TÊNKH,TP 2. MSMH ! TÊNMH,ĐG
3. MSKH, MSMH ! SL 4. TP ! PVC}
! Khoá: MSKH, MSMH $ đưa về 3NF
Cơ sở dữ liệu 55
MSKH TÊNKH TP PVC MSMH TÊNMH ĐG SL
S1
S1
S1
S2
S2
S3
S4
An
An
An
Hòa
Hoà
Thanh
Trang
HCM
HCM
HCM
HN
HN
NT
NT
01
01
01
02
02
03
03
P1
P2
P3
P1
P3
P2
P2
Táo
Cam
Chanh
Táo
Chanh
Cam
Cam
650
500
450
650
450
500
500
300
200
400
100
300
200
210
Kết quả ở 2NF
Cơ sở dữ liệu 56
MSKH MSMH SL
S1
S1
S1
S2
S2
S3
S4
P1
P2
P3
P1
P3
P2
P2
300
200
400
100
300
200
210
MSKH TÊNKH TP PVC
S1
S2
S3
S4
An
Hoà
Thanh
Trang
HCM
HN
NT
NT
01
02
03
03
MSMH TÊNMH ĐG
P1
P2
P3
Táo
Cam
Chanh
650
500
450
FR1 = {MSKH ! TÊNKH, TP
TP ! PVC}
FĐH = {MSKH, MSMH ! SL}
FMH = {MSMH! TÊNMH, ĐG}
Cơ sở dữ liệu 57
MSKH TÊNKH TP
S1
S2
S3
S4
An
Hoà
Bình
Trang
HCM
HN
NT
NT
TP PVC
HCM
HN
NT
01
02
03
FKH = {MSKH ! TÊNKH, TP}
FVC = {TP ! PVC}
MSMH TÊNMH ĐG
P1
P2
P3
Táo
Cam
Chanh
650
500
450
FMH = {MSMH! TÊNMH, ĐG}
MSKH MSMH SL
S1
S1
S1
S2
S2
S3
S4
P1
P2
P3
P1
P3
P2
P2
300
200
400
100
300
200
210
FĐH = {MSKH, MSMH ! SL}
Kết quả ở 3NF
Cơ sở dữ liệu 58
4. Dạng chuẩn BCNF (Boyce Codd)
! Định nghĩa: Lược đồ quan hệ R ở dạng
chuẩn BCNF nếu với mọi pth X→A của R,
A∉X thì X là một siêu khóa nhỏ nhất ! các
thuộc tính đều phụ thuộc trực tiếp vào khóa
! Sơ đồ:
R(A1,A2,A3, A4, A5)
1
Cơ sở dữ liệu 60
Thuật toán kiểm tra dạng chuẩn BCNF
! Bước 1: Tìm tất cả các khóa của quan hệ Q
! Bước 2: Từ tập pth F tạo tập pth tương đương với F
gọi là F có vế phải một thuộc tính
! Bước 3:
- nếu mọi pth X→A ∈F đều có X là khóa thì Q đạt chuẩn
BCNF
- ngược lại Q không đạt chuẩn BCNF (∃ X → A mà X không
là khóa)
# mọi pth đều có vế trái là khóa thì đạt chuẩn BCNF
ngược lại thì không
Cơ sở dữ liệu 61
! Ví dụ 1: Cho R = { C, S, Z}, Phụ thuộc
hàm: CS→Z, Z →C
! Xác định dạng chuẩn cao nhất
Cơ sở dữ liệu 63
Đưa về dạng BCNF
! Loại bỏ các thuộc tính khóa phụ thuộc hàm vào
thuộc tính không khóa ra khỏi quan hệ và tạo thành
một quan hệ riêng có khoá chính là thuộc tính
không khóa gây ra phụ thuộc.
R(A1, A2, A3, A4, A5)
R1(A4, A2)
R(A1, A4, A3, A5)
Cơ sở dữ liệu 64
Ví dụ:
Kết quả là gì?
Hoc(MaSV, MaMon, Diem, MaGV)
R(A1,A2,A3, A4, A5)
1
4 3
R(A1,A2,A3, A4, A5)
1
4
R(A1,A2,A3, A4, A5)
1
1NF
2NF
3NF
BCNF
R(A1,A2,A3, A4, A5)
1
2 3
4
Cơ sở dữ liệu 66
* Quá trình chuẩn hóa
IV. Chuẩn hóa quan hệ
! Chuẩn hóa quan hệ là việc phân rã một lược đồ
quan hệ thành các lược đồ con ở dạng chuẩn 3
hoặc ở dạng chuẩn BCNF sao cho vẫn bảo toàn
phụ thuộc và không mất mát dữ liệu
Cơ sở dữ liệu 67
1. Thuật toán phân rã thành các BCNF
! Input: Quan hệ R và tập PTH F
! Output: tách thành các lược đồ ở BCNF
! Các bước:
- Ban đầu phép tách S chỉ là R
- Chọn pth X!A trong đó X không chứa khóa của S và
A∉X ! PTH vi phạm BCNF
- Thay thế S bởi S1 và S2. Trong đó:
" S1 = XA
" S2 = S \ A (loại thuộc tính A khỏi S)
- Quá trình trên tiếp tục cho đến khi tất cả các lược đồ
quan hệ đều ở BCNF
Cơ sở dữ liệu 68
Ví dụ: Tách lược đồ về dạng BCNF
! Cho lược đồ R(CTHRSG), trong đó:
- C – Course; T – Teacher; H – Hour: Giờ học
- R – Room; S – Student; G – Group
! PTH F = { C!T; HR!C; HT!R; CS!G; HS!R }
! Khóa: HS
Cơ sở dữ liệu 74
C – Cource T – Teacher H – Hour R – Room S – Student G – Group
CSDL Tâm 7h 21 N.V Hà CSDL.1
CSDL Tâm 7h 21 T.V Huy CSDL.1
CSDL Tâm 7h 21 Đ.T Lan CSDL.1
CTDL Xuân 9h 22 N.V Hà CTDL.1
CTDL Xuân 9h 22 Đ.T Lan CTDL.1
CTDL Xuân 9h 22 L.T Linh CTDL.1
TRR Linh 7h 23 T.V An TRR.1
TRR Linh 7h 23 Đ.V Hưởng TRR.2
CT: Mỗi khoá học (course) có một thầy (teacher) duy nhất.
HRC: Tại một thời điểm (Hour) tại phòng học (room) chỉ có một khoá học duy nhất.
HTR: Tại một thời điểm và một giáo viên chỉ ở một phòng duy nhất
CSG: Một sinh viên học một course thì chỉ ở một lớp duy nhất.
HSR: Một SV, ở một thời điểm nhất định chỉ ở trong một phòng duy nhất.
! Xét CS!G
- Tách thành R1(CSG) và R2(CTHRS)
Cơ sở dữ liệu 75
R2(CTHRS)
C –
Cource
T –
Teacher
H –
Hour
R –
Room
S – Student
CSDL Tâm 7h 21 N.V Hà
CSDL Tâm 7h 21 T.V Huy
CSDL Tâm 7h 21 Đ.T Lan
CTDL Xuân 9h 22 N.V Hà
CTDL Xuân 9h 22 Đ.T Lan
CTDL Xuân 9h 22 L.T Linh
TRR Linh 7h 23 T.V An
TRR Linh 7h 23 Đ.V Hưởng
R1(CSG)
C –
Cource
S –
Student
G –
Group
CSDL N.V Hà CSDL.1
CSDL T.V Huy CSDL.1
CSDL Đ.T Lan CSDL.1
CTDL N.V Hà CTDL.1
CTDL Đ.T Lan CTDL.1
CTDL L.T Linh CTDL.1
TRR T.V An TRR.1
TRR Đ.V Hưởng TRR.2
! Xét C!T
- Tách thành R21(CT) và R22(CHRS)
Cơ sở dữ liệu 76
R21(CT)
C –
Cource
T –
Teacher
CSDL Tâm
CTDL Xuân
TRR Linh
R1(CSG)
C –
Cource
S – Student G – Group
CSDL N.V Hà CSDL.1
CSDL T.V Huy CSDL.1
CSDL Đ.T Lan CSDL.1
CTDL N.V Hà CTDL.1
CTDL Đ.T Lan CTDL.1
CTDL L.T Linh CTDL.1
TRR T.V An TRR.2
TRR Đ.V Hưởng TRR.2
R22(CHRS)
C –
Cource
H –
Hour
R –
Room
S – Student
CSDL 7h 21 N.V Hà
CSDL 7h 21 T.V Huy
CSDL 7h 21 Đ.T Lan
CTDL 9h 22 N.V Hà
CTDL 9h 22 Đ.T Lan
CTDL 9h 22 L.T Linh
TRR 7h 23 T.V An
TRR 7h 23 Đ.V Hưởng
! Xét CH!R
- Tách thành R221(CHR) và R222(CHS)
Cơ sở dữ liệu 77
R21(CT)
C –
Cource
T –
Teacher
CSDL Tâm
CTDL Xuân
TRR Linh
R1(CSG)
C –
Cource
S – Student G – Group
CSDL N.V Hà CSDL.1
CSDL T.V Huy CSDL.1
CSDL Đ.T Lan CSDL.1
CTDL N.V Hà CTDL.1
CTDL Đ.T Lan CTDL.1
CTDL L.T Linh CTDL.1
TRR T.V An TRR.2
TRR Đ.V Hưởng TRR.2
R221(CHR)
C –
Cource
H –
Hour
R –
Room
CSDL 7h 21
CTDL 9h 22
TRR 7h 23
R222(CHS)
C –
Cource
H –
Hour
S – Student
CSDL 7h N.V Hà
CSDL 7h T.V Huy
CSDL 7h Đ.T Lan
CTDL 9h N.V Hà
CTDL 9h Đ.T Lan
CTDL 9h L.T Linh
TRR 7h T.V An
TRR 7h Đ.V Hưởng
2. Thuật toán phân rã thành các 3NF
! Input: Lược đồ R và tập các phụ thuộc hàm F
! Output: Tách thành các lược đồ ở 3NF
! Thuật toán:
- Loại bỏ các thuộc tính R nếu thuộc tính đó không liên quan
đến PTH của F (không có mặt ở cả hai vế của PTH)
- Nếu có một PTH của F liên quan đến tất cả các thuộc tính
của R thì kết quả chính là R (không tách nữa)
- Xét các PTH X!A vi phạm 3NF (phụ thuộc bắc cầu vào
khóa) và tách thành một lược đồ XA
" Nếu tồn tại các PTH X!A1, X!A2, , X!An thì gộp thành
XA1A2..An
Cơ sở dữ liệu 79
Ví dụ: Tách về 3NF
! Cho lược đồ R(CTHRSG), trong đó:
- C – Course; T – Teacher; H – Hour: Giờ học
- R – Room; S – Student; G – Group
! PTH F={ C!T; HR!C; HT!R; CS!G; HS!R}
! Khóa: CHS
Cơ sở dữ liệu 80
R
C – Cource T – Teacher H – Hour R – Room S – Student G – Group
CSDL Tâm 7h 21 N.V Hà CSDL.1
CSDL Tâm 7h 21 T.V Huy CSDL.1
CSDL Tâm 7h 21 Đ.T Lan CSDL.1
CTDL Xuân 9h 22 N.V Hà CTDL.1
CTDL Xuân 9h 22 Đ.T Lan CTDL.1
CTDL Xuân 9h 22 L.T Linh CTDL.1
TRR Linh 7h 23 T.V An TRR.1
TRR Linh 7h 23 Đ.V Hưởng TRR.1
Cơ sở dữ liệu 81
R1
C –
Cource
T –
Teacher
CSDL Tâm
CTDL Xuân
TRR Linh
% Xét C!T vi phạm 3NF (phụ thuộc bắc cầu vào khoá),
% Tách R thành R1(C,T) và R2(C,H,R,S,G).
R2
C –
Cource
H –
Hour
R –
Room
S – Student G –
Group
CSDL 7h 21 N.V Hà CSDL.1
CSDL 7h 21 T.V Huy CSDL.1
CSDL 7h 21 Đ.T Lan CSDL.1
CTDL 9h 22 N.V Hà CTDL.1
CTDL 9h 22 Đ.T Lan CTDL.1
CTDL 9h 22 L.T Linh CTDL.1
TRR 7h 23 T.V An TRR.1
TRR 7h 23 Đ.V Hưởng TRR.1
Cơ sở dữ liệu 82
% Xét CS!G vi phạm 3NF(phụ thuộc bộ phận vào khoá),
% tách R2 thành R21(C,S,G) và R22(C,H,R,S).
R21
C –
Cource
S – Student G –
Group
CSDL N.V Hà CSDL.1
CSDL T.V Huy CSDL.1
CSDL Đ.T Lan CSDL.1
CTDL N.V Hà CTDL.1
CTDL Đ.T Lan CTDL.1
CTDL L.T Linh CTDL.1
TRR T.V An TRR.1
TRR Đ.V Hưởng TRR.1
R1
C –
Cource
T –
Teacher
CSDL Tâm
CTDL Xuân
TRR Linh
R22
C –
Cource
H –
Hour
R –
Room
S – Student
CSDL 7h 21 N.V Hà
CSDL 7h 21 T.V Huy
CSDL 7h 21 Đ.T Lan
CTDL 9h 22 N.V Hà
CTDL 9h 22 Đ.T Lan
CTDL 9h 22 L.T Linh
TRR 7h 23 T.V An
TRR 7h 23 Đ.V Hưởng
Cơ sở dữ liệu 83
% Xét HR!C vi phạm 3NF, tách R22 thành
R221(H,R,C) và R222(H,S,R)
R221
C –
Cource
H –
Hour
R –
Room
CSDL 7h 21
CTDL 9h 22
TRR 7h 23
R222
H –
Hour
R –
Room
S – Student
7h 21 N.V Hà
7h 21 T.V Huy
7h 21 Đ.T Lan
9h 22 N.V Hà
9h 22 Đ.T Lan
9h 22 L.T Linh
7h 23 T.V An
7h 23 Đ.V Hưởng
R1
C –
Cource
T –
Teacher
CSDL Tâm
CTDL Xuân
TRR Linh
R21
C –
Cource
S – Student G –
Group
CSDL N.V Hà CSDL.1
CSDL T.V Huy CSDL.1
CSDL Đ.T Lan CSDL.1
CTDL N.V Hà CTDL.1
CTDL Đ.T Lan CTDL.1
C