Phân rã thành BCNF
Các phân rã 1 và 3 không phải là BCNF vì P Sem → C nằm trong phân rã 2
Phân rã 1 được tách thành 2 lược đồ mới
– (P Sem C; {P Sem → C})
– (St Sem P; {})
→ Phân rã tuy không mất mát thông tin nhưng không
bảo toàn PTH St C Sem → P
29 trang |
Chia sẻ: vutrong32 | Lượt xem: 1187 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Cơ sở dữ liệu (Databases) - Chương 5: Dạng chuẩn và Chuẩn hóa, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
bangtqh@utc2.edu.vn
CƠ SỞ DỮ LIỆU
( Databases )
Chương 5: Dạng chuẩn và Chuẩn hóa
bangtqh@utc2.edu.vn
Nội dung
1. Dạng chuẩn
2. Chuẩn hóa lược đồ CSDL
3. Bài tập
Chương 5 - Dạng chuẩn và chuẩn hóa 2
bangtqh@utc2.edu.vn
5.1. Dạng chuẩn
Chuẩn hóa là gì?
– Chuẩn hóa là kỹ thuật dùng để tạo ra một tập các quan
hệ có các đặc điểm mong muốn dựa vào các yêu cầu
về dữ liệu của 1 enterprise
– Chuẩn hóa là 1 cách tiếp cận từ dưới lên (bottom-up
approach) để thiết kế CSDL, bắt đầu từ các mối liên hệ
giữa các thuộc tính
Mục đích của chuẩn hóa
– Loại bỏ các bất thường của 1 quan hệ để có được các
quan hệ có cấu trúc tốt hơn, nhỏ hơn
Quan hệ có cấu trúc tốt (well-structured relation):
– Là quan hệ có sự dư thừa dữ liệu là tối thiểu và cho
phép người dùng thêm, sửa, xóa mà không gây ra mâu
thuẫn dữ liệu
Chương 5 - Dạng chuẩn và chuẩn hóa 3
bangtqh@utc2.edu.vn
5.1.1.Sự dư thừa dữ liệu
Sự phụ thuộc giữa các thuộc tính gây ra sự dư thừa
– Ví dụ:
• Điểm các môn học Điểm trung bình xếp loại
• Địa chỉ zip code
4
TENPHG MAPHG TRPHG NG_NHANCHUC
Nghien cuu 5 333445555 05/22/1988
Dieu hanh 4 987987987 01/01/1995
Quan ly 1 888665555 06/19/1981
TENNV HONV
Tung Nguyen
Hung Nguyen
333445555
987987987
888665555
MANV
Vinh Pham
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
5.1.1.Sự dư thừa dữ liệu (tt)
Thuộc tính đa trị trong lược đồ ER nhiều bộ số liệu
trong lược đồ quan hệ
Ví dụ:
NHANVIEN(TENNV, HONV, NS,DCHI,GT,LUONG, BANGCAP)
5
TENNV HONV NS DCHI GT LUONG BANGCAP
Tung Nguyen 12/08/1955 638 NVC Q5 Nam 40000
Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Đại học
Hung Nguyen 09/15/1962 Ba Ria VT Nam 38000 Thạc sỹ
Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Trung học
Trung học
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
5.1.1.Sự dư thừa dữ liệu (tt)
Sự dư thừa sự dị thường
– Thao tác sửa đổi: cập nhật tất cả các giá trị liên quan
– Thao tác xóa: người cuối cùng của đơn vị mất thông
tin về đơn vị
– Thao tác thêm:
6
TENPHG MAPHG TRPHG NG_NHANCHUC
Nghien cuu 5 333445555 05/22/1988
Dieu hanh 4 987987987 01/01/1995
Quan ly 1 888665555 06/19/1981
TENNV HONV
Tung Nguyen
Hung Nguyen
333445555
987987987
888665555
MANV
Vinh Pham
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
5.1.1.Sự dư thừa dữ liệu (tt)
Các giá trị không xác định
– Đặt thuộc tính Trưởng phòng vào quan hệ NHANVIEN
thay vì vào quan hệ PHONGBAN
Các bộ giả
– Khi sử dụng các phép nối
7Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
5.1.1.Sự dư thừa dữ liệu (tt)
Một số quy tắc khi thiết kế CSDL quan hệ
– NT1: Rõ ràng về mặt ngữ nghĩa, tránh các sự phụ
thuộc giữa các thuộc tính với nhau
– NT2: Tránh sự trùng lặp về nội dung đảm bảo tránh
được các dị thường khi thao tác cập nhật dữ liệu
• Phải có một số thao tác khi thêm mới và cập nhật vào lược đồ quan
hệ, cũng như có thể gây sai hỏng trong trường hợp xóa bỏ các bộ
– NT3: Tránh sử dụng các thuộc tính có nhiều giá trị Null
• Khó thực hiện các phép nối và kết hợp
– NT4: Thiết kế các lược đồ quan hệ sao cho chúng có
thể được nối với điều kiện bằng trên các thuộc tính là
khoá chính hoặc khoá ngoài theo cách đảm bảo không
sinh ra các bộ “giả”
8Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
5.1.2. Các dạng chuẩn
Mỗi một dạng chuẩn là một tập các điều kiện trên
lược đồ nhằm đảm bảo các tính chất của nó (liên
quan tới dư thừa và bất thường trong cập nhật)
Chuẩn hóa dữ liệu: quá trình phân tích lược đồ quan
hệ dựa trên các FD và các khóa chính để đạt được
– Cực tiểu sự dư thừa
– Cực tiểu các phép cập nhật bất thường
Chương 5 - Dạng chuẩn và chuẩn hóa 9
bangtqh@utc2.edu.vn
5.1.2. Các dạng chuẩn (tt)
Phân loại
– Dạng chuẩn 1 (1NF – first normal form)
– Dạng chuẩn 2 (2NF – second normal form)
– Dạng chuẩn 3 (3NF – third normal form)
– Dạng chuẩn BCNF (Boyce-Codd normal form)
– Dạng chuẩn 4NF
10Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 1
Định nghĩa: quan hệ R được gọi là ở dạng 1NF nếu
miền giá trị của một thuộc tính chỉ chứa giá trị nguyên
tố đơn, ko phân chia được) và giá trị của mỗi thuộc
tính cũng là một giá trị đơn lấy từ miền giá trị của nó
Ví dụ
PHONGBAN( MaPHG, TenPHG, DDIEM)
PHONGBAN(MaPHG, TenPHG)
DDIEM_PHG(MaPHG, DDIEM)
11
Thuộc
tính đa trị
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 1 (tt)
Lược đồ gốc:
Table (Key1, aaa. . . (Key2, bbb. . . (Key3, ccc. . .) ) )
Để thỏa mãn 1NF chúng ta thực hiện
– Table1(Key1, aaa . . .)
– Table2(Key1, Key2, bbb . .)
– Table3(Key1, Key2, Key3, ccc. . .)
12
Table (Key1, . . . (Key2, . . . (Key3, . . .) ) )
Table1(Key1, . . .) TableA (Key1,Key2 . . .(Key3, . . .) )
Table2 (Key1, Key2 . . .) Table3 (Key1, Key2, Key3, . . .)
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 1 (tt)
Vấn đề còn tồn tại trong 1NF
Xét lược đồ
DDIEM_PHG(MaPHG, DDIEM)
– Vẫn bị lặp lại
– Ẩn chứa các phụ thuộc hàm
bộ phận
13
DIADIEMMAPHG
1
4
5
5
TP HCM
VUNGTAU
NHATRANG
HA NOI
5 TP HCM
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 2
Phụ thuộc hàm đầy đủ: Một phụ thuộc hàm X → Y
là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc
tính A nào ra khỏi X thì phụ thuộc hàm không còn
đúng nữa.
∀ A, A ∈ X, (X – {A}) → Y : là sai.
Phụ thuộc hàm bộ phận: Một phụ thuộc hàm X → Y
là phụ thuộc bộ phận nếu có thể bỏ một thuộc tính A∈
X, ra khỏi X phụ thuộc hàm vẫn đúng, điều đó có
nghĩa là với
∃A∈ X, (X – {A}) → Y
14Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 2 (tt)
2NF:
– Thỏa mãn 1NF
– Phụ thuộc hàm đầy đủ vào khóa chính
Với các quan hệ có thuộc tính khóa đơn thì ko phải
xét
Chỉ kiểm tra các lược đồ có chứa phụ thuộc hàm bộ
phận
15Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 2 (tt)
Ví dụ
NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA)
16
Phụ thuộc vào cả 2 MaNV, MaDA
Chỉ phụ thuộc vào MaDA
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 2 (tt)
Ví dụ
NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA)
17
Phụ thuộc vào cả 2 MaNV, MaDA
Chỉ phụ thuộc vào MaDA
NV_DA(MaNV, MaDA, Sogio)
DUAN(MaDA, TenDA) DUAN(MaDA, DDiemDA)
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 3
3NF dựa trên khái niệm phụ thuộc bắc cầu.
Định nghĩa: Một lược đồ quan hệ R là ở 3NF nếu nó:
– Thỏa mãn 2NF
– Không có thuộc tính không khoá nào của R là phụ
thuộc bắc cầu vào khoá chính.
18Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 3 (tt)
NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG)
19
Phụ thuộc vào MaNV
Phụ thuộc vào MaDV
Tất cả các thuộc tính phải phụ thuộc vào thuộc tính
khóa
- Một vài thuộc tính phụ thuộc vào thuộc tính ko phải là
khóa
- Chuẩn hóa Tách nhóm các thuộc tính đó thành quan
hệ mới
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn 3 (tt)
DONVI(MaDV, TenDV, TruongPHG)
20
Phụ thuộc vào MaNV
Phụ thuộc vào MaDV
NHANVIEN(MaNV, TenNV, NS, DCHI, MaDV)
NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG)
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Tóm tắt 3 dạng chuẩn 1-3
NF Nhận biết Cách chuẩn hóa
1 Quan hệ ko có thuộc tính đa
trị và quan hệ lặp
Chuyển tất cả quan hệ lặp
hoặc đa trị thành 1 quan hệ
mới
2 Phụ thuộc 1 phần vào thuộc
tính khóa
Tách thuộc tính phụ thuộc 1
phần thành lược đồ mới, đảm
bảo quan hệ với lược đồ liên
quan
3 Phụ thuộc ẩn, tồn tại phụ
thuộc hàm giữa các thuộc
tính ko phải là khóa
Tách các thuộc tính đó thành
lược đồ mới
21Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn Boyce-Codd
Một lược đồ quan hệ R được gọi là ở dạng chuẩn
Boyce-Codd (BCNF) nếu nó
– Thỏa mãn dạng chuẩn 3NF
– Không có thuộc tính phụ thuộc hàm vào thuộc tính
không khóa.
Ví dụ
22Chương 5 - Dạng chuẩn và chuẩn hóa
FD2
FD5
FD1
DCBA
R
bangtqh@utc2.edu.vn
Dạng chuẩn Boyce-Codd(tt)
Ví dụ:
R (A1,A2,A3,A4,A5)
Với các phụ thuộc hàm:
A1,A2 → A3,A4,A5
A4 → A2
23Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn Boyce-Codd(tt)
Nếu một lược đồ quan hệ không thoả mãn điều kiện BCNF,
thủ tục chuẩn hóa bao gồm:
– 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ệ
– tách chúng 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.
Ví dụ trên: R (A1,A2,A3,A4,A5)
Với các phụ thuộc hàm:
– A1,A2 → A3,A4,A5
– A4 → A2
lược đồ được tách ra như sau:
– R1( A4, A2)
– R2(A1, A4, A3, A5)
24Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn Boyce-Codd(tt)
25
SV_MH_GV(MaSV, MONHOC, GIANGVIEN)
Phụ thuộc vào MONHOC
Ví dụ
Phụ thuộc vào cả 2 MaSV, MaMH
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Dạng chuẩn Boyce-Codd(tt)
26
Phụ thuộc vào MONHOC
SV_MH_GV(MaSV, MaMH, MaGV)
Ví dụ
Phụ thuộc vào cả 2 MaSV, MaMH
SV_MH(MaSV, MaMH)
Chương 5 - Dạng chuẩn và chuẩn hóa
MH_GV(MaGV, MaMH)
bangtqh@utc2.edu.vn
5.1.3. Phân rã lược đồ quan hệ
Lược đồ quan hệ chung R(A1, , An)
– Tập hợp tất cả các thuộc tính của các thực thể.
Xác định tập phụ thuộc hàm F trên R.
Phân rã
– Sử dụng các thuật toán chuẩn hóa để tách R thành tập
các lược đồ D = {R1, , Rm}.
Yêu cầu
– Bảo toàn thông tin
– Các lược đồ Ri phải ở dạng chuẩn 3 hoặc BCNF.
Chương 5 - Dạng chuẩn và chuẩn hóa 27
bangtqh@utc2.edu.vn
Phân rã bảo toàn thông tin
Sau phân rã, CSDL không còn lưu trữ quan hệ R
nữa mà chỉ lưu lại các quan hệ chiếu của nó R1,
R2,..,Rn. CSDL phải có khả năng khôi phục lại
quan hệ gốc R từ các quan hệ chiếu này.
Nếu không khôi phục lại được quan hệ R thì việc
phân rã không biểu diễn cùng 1 thông tin với
CSDL gốc → Phân rã mất mát (lossy
decomposition)
28Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn thông tin (tt)
Phân rã lược đồ R = (U,F) thành 1 tập hợp các lược
đồ: R1 = (U1,F1) R2= (U2, F2). Rn = (Un,Fn)
Phân rã không mất mát thông tin nếu với mỗi thể hiện
r hợp lệ của R thì:
r = r1 r2 .. rn
Với r1 = piU1(r) r2 = piU2(r),. rn = piUn(r)
29Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn thông tin (tt)
Thực tế sẽ nhận được nhiều bộ (tuple) từ phép kết
các r1, r2,,rn hơn là các bộ gốc ban đầu Vậy tại
sao lại gọi là mất mát (lossy) ??
Tuy nhiều bộ hơn nhưng lại thiếu thông tin và không
có cách nào biết được bộ nào là đúng, bộ nào là
không đúng với bộ gốc.
Nhiều bộ hơn nhưng không đúng ≡ mất mát thông tin
30Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn thông tin (tt)
Định lý 5.1
– Phân rã D = {R1(U1), R2(U2)} của R(U) không mất
thông tin đối với tập PTH F nếu và chỉ nếu:
• (U1 ∩ U2) → (U1) ∈ F+, hoặc
• (U1 ∩ U2) → (U2) ∈ F+.
Định lý 5.3
– Nếu phân rã D = {R1, , Rm} của R không mất thông
tin đối với F và phân rã Di = {Q1, , Qk} của Ri không
mất thông tin đối với piRi(F) thì D’ = {R1, , Ri-1, Q1, ,
Qk, Ri+1, , Rm} của R cũng không mất thông tin.
Chương 5 - Dạng chuẩn và chuẩn hóa 31
bangtqh@utc2.edu.vn
Ví dụ
SSN Name Address Hobby
1111111 John 123 Main St. Stamps
1111111 John 123 Main St. Coins
5556667 Mary 7 Lake Dr. Hiking
5556667 Mary 7 Lake Dr. Skating
9876543 Simpson Fox 5 TV Acting
32
Xét lược đồ quan hệ
PERSON(SSN, Name, Address,Hobby)
Nếu phân rã lược đồ trên thành 2 lược đồ:
PERSON1(SSN, Name, Address)
HOBBY(SSN, Hobby)
Việc phân rã này có mất thông tin không?
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
33
Ví dụ
Ta có:
PERSON1 ∩ HOBBY = {SSN}
mà SSN là khóa chính của PERSON1, do đó
PERSON1 ∩ HOBBY PERSON1
Vậy: Phân rã này không mất thông tin
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn phụ thuộc hàm
Xét lược đồ quan hệ sau:
HASACCOUNT(ClientId, OfficeId, AccountNumber)
Với các PTH sau:
ClientId, OfficeId AcountNumber
AccountNumber OfficeId
Nếu phân rã lược đồ trên thành 2 lược đồ sau:
ACCTOFFICE (AccountNumber, OfficeId)
ACCTCLIENT (AccountNumber, ClientId)
Phân rã trên có mất mát thông tin không???
34Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn PTH (tt)
Phân rã trên không mất mát thông tin vì:
ACCTOFFICE ∩ ACCTCLIENT ={AccountNumber}
Do AccountNumber là Primary Key của
CCTOFFICE nên:
ACCTOFFICE ∩ ACCTCLIENT ACCTOFFICE
Nhưng phân rã này không bảo toàn
phụ thuộc hàm
35Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn PTH (tt)
Phụ thuộc hàm gốc:
ClientId, OfficeId AcountNumber
không tồn tại trong các phụ thuộc hàm của các
lược đồ phân rã vì:
– Cả hai phụ thuộc hàm phân rã đều không chứa đủ các
thuộc tính của phụ thuộc hàm gốc (1) nên không thể
suy diễn lại được phụ thuộc hàm này
36Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã bảo toàn PTH (tt)
Cho lược đồ R = (U,F)
D = {R1(U1,F1) , R2(U2, F2),.., R (Un, Fn) } là phân
rã của R. Phân rã này được gọi là bảo toàn phụ
thuộc hàm nếu và chỉ nếu F và ∪ Fi là tương
đương nhau.
Nếu 1 phụ thuộc hàm f ∈ F nhưng không thuộc
bất kỳ Fi nào không có nghĩa là phân rã không
bảo toàn phụ thuộc hàm nếu f có thể được suy
diễn từ ∪ Fi
– Chỉ khi nào f không thể suy diễn từ ∪ Fi thì phân rã đó
mới không bảo toàn PTH
Chương 5 - Dạng chuẩn và chuẩn hóa 37
bangtqh@utc2.edu.vn
Ví dụ
Phân rã quan hệ HASACCOUNT
38
AccountNumber ClientId OfficeId
B123 111111 SB01
A908 123456 MN08
AccountNumber OfficeId
B123 SB01
A908 MN08
Account Number ClientId
B123 111111
A908 123456
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Ví dụ
HASACCOUNT và phân rã của nó sau khi chèn
thêm 1 hàng
39
AccountNumber ClientId OfficeId
B123 111111 SB01
B567 111111 SB01
A908 123456 MN08
AccountNumber OfficeId
B123 SB01
B567 SB01
A908 MN08
Account Number ClientId
B123 111111
B567 111111
A908 123456
Sau khi join 2 lược đồ phân rã lại, phụ thuộc hàm
ClientId, OfficeId AcountNumber bị vi phạm
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phép chiếu của tập phụ thuộc hàm
Xét lược đồ quan hệ R =(U,F) và tập S ⊆ U
Phép chiếu của F lên tập các thuộc tính S được định
nghĩa như sau:
piS(F) = {XY|XY ∈F+ và X ∪ Y⊆ S}
40Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Giải thuật phân rã thành BCNF
R=(U,F) là 1 lược đồ quan hệ không ở chuẩn BCNF.
Giải thuật:
Thực hiện lặp lại việc phân chia R thành những lược đồ
nhỏ hơn sao cho các lược đồ mới có ít PTH vi phạm
BCNF hơn. Giải thuật kết thúc khi tất cả lược đồ kết quả
đều ở dạng BCNF
41Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Giải thuật phân rã thành BCNF
Input R = (U,F)
Decom = R
While có lược đồ S=(V, F’) trong Decom không phải BCNF
/*Nếu có XY ∈F sao cho X ∪ Y ⊆ S và vi phạm BCNF,
dùng FD này để phân rã*/
– Thay S trong Decom với S1 = (XY, F1)
– S2=( (S-Y) ∪ X, F2) với F1,F2 là tất cả các FD của F’
End
Return Decom
42Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Ví dụ
Cho R= (U,F)
U={ABCDEFGH},
F= {ABH C, ADE, BGH F, F ADH, BH GE}
Tìm FD vi phạm BCNF
– (ABH)+ = U , ABH là siêu khóa, ABH C không vi phạm BCNF
– A+ ≠ U, ADE vi phạm BCNF
Chia R thành
– R1 =(ADE, {ADE})
– R2 = (ABCFGH, {ABHC, BGHF, F AH, BHG})
43Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Ví dụ (tt)
Sau khi phân rã, chú ý đến 2 phụ thuộc hàm gốc F
ADH, BH GE
– Chia FADH thành {FAH, FD}
– Chia BHGE thành {BHG, BHE}
FD, BHE không có chỗ trong các phân rã mới (vì
không có ràng buộc nào có đủ thuộc tính cho các FD này)
Nhưng
– FD có thể suy diễn từ FAH ∈ R2 và ADE ∈ R1
– BH E có thể suy diễn được dựa vào (BH)+ từ R1,R2
Phân rã R1,R2 bảo toàn phụ thuộc hàm
44Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Ví dụ (tt)
R1 là BCNF
Với R2 (ABCFGH, {ABHC, BGHF, F AH, BHG})
– ABH C, BGH F không vi phạm BCNF (ABH, BGH đều là siêu khóa)
– F AH vi phạm BCNF
Vậy Phân rã R2 thành
– R21=(FAH, {FAH})
– R22= (FBCG, {} )
R21, R22 đều là BCNF nhưng khi đó các Phụ thuộc hàm ABH C, BGH
F và BHG không có mặt nữa và cùng không thể suy dẫn được từ
các PTH của R21, R22 và R1
Phân rã R2 không bảo toàn phụ thuộc hàm
45Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Nhận xét
Việc phân rã R thành R1, R21, R22 không phải là duy
nhất.
Nếu bắt đầu từ FD F ADH thì sẽ có
R1= (FADH; {F ADH})
R2 = (FBCEG,{})
R1,R2 cũng ở chuẩn BCNF và 1 số FD gốc cũng bị mất,
không thể suy diễn được
46Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
47
Tính chất của giải thuật phân rã BCNF
Không mất mát thông tin
Nhưng có thể không bảo toàn phụ thuộc hàm
Là giải thuật không xác định (nondeterministic), phụ
thuộc vào thứ tự các PTH được chọn để xét phân rã
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Giải thuật phân rã thành 3NF
Cho lược đồ R(U,F)
Bước 1: Tìm phủ tối thiểu G của F
Bước 2: Phân hoạch G thành các tập phụ thuộc hàm
G1,..,Gn sao cho mỗi Gi chứa các PTH có cùng vế trái
Bước 3: với mỗi Gi, tạo 1 lược đồ (Ri, Gi) với Ri chứa
tất cả thuộc tính có trong Gi
Bước 4: Nếu một trong các Ri thỏa (Ri)+F = R thì kết
thúc, ngược lại đặt Ro=(R, {}) là 1 lược đồ mới. Khi đó
R0, R1,, Rn là kết quả phân rã.
48Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Tính chất của giải thuật phân rã thành 3NF
Bảo toàn phụ thuộc hàm
Không mất thông tin
49Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
50
Ví dụ
Cho R= (U,F) với U={ABCDEFGH}, F= {ABH C, ADE, BGH F,
F ADH, BH GE}
Phủ tối thiểu của F là: G={BHC,AD,CE,FA,EF}
Phân rã thành 5 lược đồ:
– R1 (BHC; {BHC})
– R2 (AD; {AD})
– R3 (CE; {CE})
– R4 (FA; {FA})
– R5 (EF; {EF})
Không có lược đồ phân rã nào có (Ri)+F = siêu khóa BCGH của R, nên
bổ sung thêm lược đồ thứ 6
– R6 (BCGH;{})
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
51
Phân rã BCNF thông qua phân rã 3NF
Vì giải thuật phân rã BCNF có thể không bảo toàn
phụ thuộc hàm nên phân rã BCNF thông qua phân
rã 3NF. Nếu lược đồ sau phân rã là BCNF thì dừng,
nếu không thì dùng lúc đó mới dùng giải thuật BCNF
để phân rã tiếp
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
52
Ví dụ
Xét tập thuộc tính sau: St (Student), C (course), Sem
(semester), P (Professor), T (time) và R(room) và tập PTH
như sau:
St C Sem P
P Sem C
C Sem T P
P Sem T C R
P Sem C T R
P Sem T C
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
53
Phân rã 3NF bảo toàn FD
Phân rã thành 4 lược đồ như sau:
R1 (St C Sem P; {St C Sem P})
R2 (P Sem C; {P Sem C})
R3 (C Sem T P; {C Sem T P})
R4 (P Sem T R; {P Sem T R})
Vì không có phân rã nào hình thành siêu khóa cho
lược đồ gốc, nên bổ sung thêm lược đồ mới (bước 4)
R5 ( St T Sem P; {})
Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã thành BCNF
Các phân rã 1 và 3 không phải là BCNF vì P Sem
C nằm trong phân rã 2
Phân rã 1 được tách thành 2 lược đồ mới
– (P Sem C; {P Sem C})
– (St Sem P; {})
Phân rã tuy không mất mát thông tin nhưng không
bảo toàn PTH St C Sem P
54Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã thành BCNF
Phân rã lược đồ 3 thành
– (P Sem C; {P Sem C})
– (P Sem T; {})
Không mất mát thông tin nhưng cũng không bảo
toàn PTH C Sem T P
55Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Phân rã thành BCNF
Kết quả cuối cùng:
(P Sem C; {P Sem C})
(P Sem St)
(P Sem T)
(P Sem T R; {P Sem T R})
(St T Sem P)
56Chương 5 - Dạng chuẩn và chuẩn hóa
bangtqh@utc2.edu.vn
Bài tập
Chương 5 - Dạng chuẩn và chuẩn hóa 57
Các file đính kèm theo tài liệu này:
- co_so_du_lieu_ch5_dang_chuan_va_chuan_hoa_3991.pdf