Phụ thuộc hàm và các dạng chuẩn - dhcnttanhhuycan83
Ôn tập cơ sở dữ liệu tuyển sinh cao học ĐHCNTT. Giáo trình của thầy PGS.TS. Đỗ Phúc. Khoa Hệ thống thông tin
Phần 2: Phụ thuộc hàm và các dạng chuẩn
( Functional Dependency and Normal Forms) - 2009
Phụ thuộc hàm và các dạng chuẩn - dhcnttanhhuycan83
Ôn tập cơ sở dữ liệu tuyển sinh cao học ĐHCNTT. Giáo trình của thầy PGS.TS. Đỗ Phúc. Khoa Hệ thống thông tin
Phần 2: Phụ thuộc hàm và các dạng chuẩn
( Functional Dependency and Normal Forms) - 2009
Nhận viết luận văn Đại học , thạc sĩ - Zalo: 0917.193.864
Tham khảo bảng giá dịch vụ viết bài tại: vietbaocaothuctap.net
Download luận văn đồ án tốt nghiệp ngành công nghệ thông tin với đề tài: Xây dựng phần mềm quản lý quán cà phê, cho các bạn có thể tham khảo
Bài 2: Các khái niệm trong CSDL quan hệ - Giáo trình FPTMasterCode.vn
Tìm hiểu các bước thiết kế CSDL quan hệ
Tìm hiểu các khái niệm trong thiết kế CSDL quan hệ:
Các khái niệm trong thiết kế CSDL mức khái niệm
Các khái niệm trong thiết kế CSDL mức vật lý
Làm quen với hệ quản trị CSDL Microsoft Access
Tạo các bảng và truy vấn trong Microsoft Access.
Nhận viết luận văn Đại học , thạc sĩ - Zalo: 0917.193.864
Tham khảo bảng giá dịch vụ viết bài tại: vietbaocaothuctap.net
Download luận văn đồ án tốt nghiệp ngành công nghệ thông tin với đề tài: Xây dựng phần mềm quản lý quán cà phê, cho các bạn có thể tham khảo
Bài 2: Các khái niệm trong CSDL quan hệ - Giáo trình FPTMasterCode.vn
Tìm hiểu các bước thiết kế CSDL quan hệ
Tìm hiểu các khái niệm trong thiết kế CSDL quan hệ:
Các khái niệm trong thiết kế CSDL mức khái niệm
Các khái niệm trong thiết kế CSDL mức vật lý
Làm quen với hệ quản trị CSDL Microsoft Access
Tạo các bảng và truy vấn trong Microsoft Access.
Data Normalization - How to normalize database from 1nf to bcnfHiuLimPhm
Normalize Database from 1 NF to BCNF. Data Normalization - How to normalize database from 1nf to bcnf.Data Normalization - How to normalize database from 1nf to bcnf. Data Normalization - How to normalize database from 1nf to bcnf.Data Normalization - How to normalize database from 1nf to bcnf.Data Normalization - How to normalize database from 1nf to bcnf.Data Normalization - How to normalize database from 1nf to bcnf
Nhận viết luận văn Đại học , thạc sĩ - Zalo: 0917.193.864
Tham khảo bảng giá dịch vụ viết bài tại: vietbaocaothuctap.net
Download luận văn thạc sĩ ngành phương pháp toán sơ cấp với đề tài: Phép biến đổi phân tuyến tính và áp dụng giải một số bài toán phổ thông, cho các bạn làm đề tài nghiên cứu
Nhận viết luận văn Đại học , thạc sĩ - Zalo: 0917.193.864
Tham khảo bảng giá dịch vụ viết bài tại: vietbaocaothuctap.net
Download luận văn thạc sĩ ngành toán giải tích với đề tài: Một số kết quả về nghiệm của phương trình Cauchy-Riemann, cho các bạn có thể làm luận văn tham khảo
Luận văn Phương Trình Và Bất Phương Trình Hàm Trong Lớp Hàm Lượng Giác Ngược , các bạn tham khảo thêm tại tài liệu, bài mẫu điểm cao tại luanvantot.com
Nhận viết luận văn Đại học , thạc sĩ - Zalo: 0917.193.864
Tham khảo bảng giá dịch vụ viết bài tại: vietbaocaothuctap.net
Download luận văn thạc sĩ ngành toán học với đề tài: Phương trình tích phân kỳ dị với dịch chuyển và phản xạ trên trục thực, cho các bạn làm luận văn tham khảo
2. NỘI DUNG :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
2/45
3. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
3/45
4. 16.1. Một số khái niệm liên quan
Chuẩn hóa:
Là quá trình tách một lược đồ quan hệ thành một tập các
lược đồ con, sao cho quá trình tách là không mất thông tin
và các lược đồ con là tối ưu hơn lược đồ ban đầu theo nghĩa:
hạn chế dư thừa dữ liệu, thuận lợi cho các quá trình tạo lập,
cập nhật và các thao tác tìm kiếm khác.
Định nghĩa về thuộc tính khóa:
Cho lược đồ quan hệ α=(U, F), thuộc tính A∈U được gọi là
thuộc tính khóa nếu như A thuộc một trong các khóa nào
đó, ngược lại A được gọi là thuộc tính không khóa.
4/45
5. 16.1. Một số khái niệm liên quan
Định nghĩa phụ thuộc hàm đầy đủ:
Cho lược đồ quan hệ α=(U, F), X, Y, Y⊆U tập thuộc tính
Y được gọi là phụ thuộc hàm đầy đủ vào tập thuộc tính
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ỳ một tập con thực sự nào của x tức
là:
- X→ Y ( Y phụ thuộc hàm vào X)
- ∀ X’⊂ X thì X’→ Y (mọi tập con thực sự của X đều
không thể xác định hàm Y)
5/45
6. 16.1. Một số khái niệm liên quan
Định nghĩa 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
- Y → X
- A ∉ XY
Nêú X → Y và Y không phụ thuộc bắc cầu vào X thì Y
phụ thuộc hàm trực tiếp vào X
6/45
∃
7. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
7/45
8. 16.2. Các dạng chUẩn
Sự cần thiết chuẩn hóa dữ liệu:
• Mục tiêu: là triệt tiêu mức cao nhất khả năng xuất hiện các dị thường
thông tin khi thực hiện các phép lưu trữ.
• Chẩn hóa: khảo sát danh sách các thuộc tính và áp dụng các tập quy tắc
phân tích vào danh sách đó, biến đổi thành nhiều tập 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.
8/45
9. 16.2. Các dạng chUẩn
Quá trình chuẩn hóa:
Là quá trình tách lược đồ quan hệ về một nhóm tương
đương các lược đồ quan hệ chiếu sao cho khi kết nối tự nhiên
không làm tổn thất thông tin và bảo toàn được các phụ thuộc
hàm.
Cơ sở chuẩn hóa:
Dựa trên các khái niệm về phụ thuộc hàm, phụ thuộc hàm
đầy đủ, khóa, các thuộc tính không khóa…
9/45
10. 16.2. Các dạng chUẩn
Ví dụ:
Lược đồ quan hệ QLCAP( TC#, GTR, MC#, N#, NXS)
Trong đó: TC# : Mã tuyến cáp GTR : Giá trị của cáp
NSX : Nước sản xuất MC# : Mã cáp
N# : Mã nước sản xuất
Ngữ nghĩa dữ liệu như sau:
Trong một tuyến cáp, giá trị của một loại cáp được xác định
duy nhất.
Mỗi mã cáp xác định mã nước sản xuất cáp.
Mã nước xác định tên nước sản xuất.
10/45
11. 16.2. Các dạng chUẩn
Hình 16.1: Sơ đồ các phụ thuộc hàm trong lược đồ quan
hệ QLCAP
GTR
MC#
TC#
NSX
N#
Ví dụ:
11/45
12. 16.2. Các dạng chUẩn
TC# GTR MC# N# NSX
T01 200 C01 HAQ Hàn Qu cố
T01 250 C02 HAQ Hàn Qu cố
T01 220 C03 VTC Vi t Namệ
T02 500 C01 HAQ Hàn Qu cố
T02 400 C04 JAN Nh t B nậ ả
T03 100 C05 RUS Nga
T04 400 C06 CHN Trung Qu cố
T04 450 C03 VTN Vi t Namệ
Bảng 16.1: Một thể hiện của lược đồ quan hệ
QLCAP
12/45
13. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
13/45
14. 16.2.1. dạng chUẩn 1
(1NF-fist normal form)
Định nghĩa:
Một lược đồ quan hệ α=(U, F) được gọi là ở dạng chuẩn một ( 1NF)
nếu và chỉ nếu tất cả miền giá trị của các thuộc tính của R đều nguyên
tố (không thể phân chia được)
Ví dụ:
Xét quan hệ S(S#, PRO), thấy rằng thuộc tính PRO chứa các giá trị
không nguyên tố. Vì vậy quan hệ này không phải là quan hệ dạng
chuẩn 1NF.
14/45
15. 16.2.1. dạng chUẩn 1
(1NF-fist normal form)
Ví dụ:
Bảng 16.2: Một ví dụ quan hệ không 1NF.
S# PRO
P# QTY
S1 100 1
200 1
300 2
S2 100 2
200 2
S3 300 3
100 1
15/45
16. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
16/45
17. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Trước khi nghiên cứu dạng chuẩn thứ 2, ta xét ví dụ sau đây:
Xét CSDL gồm 2 lược đồ quan hệ THI (MONTHI,
GIAOVIEN) và SINHVIEN ( MONTHI, MSSV, TEN, TUOI,
DCHI, DIEM) phản ánh thông tin về kết quả thi của một đơn
vị nào đó. Trong
quan hệ THI thì MONTHI là khóa và trong quan hệ
SINHVIEN thì MONTHI và MSSV là khóa. Ở
quan hệ thứ hai dễ nhận thấy rằng MONTHI, MSSV, DIEM
xác định kết quả thi của sinh viên còn MSSV, TEN, TUOI,
DCHI xác định đối tượng dự thi.
17/45
18. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Xét các hiện hành của 2 lược đồ quan hệ THI và SINHVIEN
như sau:
THI
MONTHI GIAOVIEN
Toán T.Trợ
Lý T.Công
Hóa T.Giao
18/45
19. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
SINHVIEN
MONTHI MSSV TEN TUOI DCHI DIEM
Toán 11 Lan 20 HN 8.0
Toán 12 Hue 21 HY 7.5
Hóa 11 Lan 20 HN 7.0
Hóa 12 Hue 21 HY 6.0
Lý 11 Lan 20 HN 5.0
Lý 13 An 21 BN 4.0
19/45
20. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Trong quá trình cập nhật, truy suất dữ liệu xuất hiện các vấn
đề sau:
Dư thừa dữ liệu
Phép thay đổi
Phép chèn
Phép loại bỏ
20/45
21. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Định nghĩa:
Cho lược đồ quan hệ α=(U, F), lược đồ α được gọi là ở dạng
chuẩn 2( ký hiệu là 2 NF) nếu như lược đồ ở dạng chuẩn 1 NF
và các thuộc tình không khóa của α là phụ thuộc đầy đủ vào
khóa chính.
Thuật toán kiểm tra lược đồ có ở dạng chuẩn 2NF
hay không?
Input: Lược đồ quan hệ α =( U, F)
Output: Khẳng định α có đạt dạng chuẩn 2NF hay không
21/45
22. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Thuật toán 1:
Thuật toán kiểm tra dạng chuẩn 2NF
Vào: Lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: Khẳng định Q cóa đạt dạng chuẩn 2NF hay không
Bước 1: Tìm tất cả các khóa của Q
Bước 2: Với tất cả các khóa K, tìm bao đóng của tất cả cá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 chẩn 2NF ngược lại Q đạt được dạng chuẩn
2NF.
22/45
23. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Ví dụ:
Cho lược đồ quan hệ Q(A, B, C, D) và tập phụ thuộc hàm:
F={AB→C, B→D, BC→A } . Hỏi Q có đạt chuẩn 2NF hay không?
Giải:
Iα =Q ∪ ( Ri- -Li )=ABCD (C∪D∪A)=B. Iα ≠Q
N={∪ ( Ri- -Li ) sao cho Li ⊆Iα }=D
N’=(Iα N)+ Iα =(BD)+ B = D (N’⊆ Nα )
N’’=∪ Ri- - ∪ Li =ACD ABC=D
Nα=N∪N’∪N’’=D
B=Q Nα Iα=ABCD D B=AC
Vì B=2 => có hai khóa BA và BC
23/45
24. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Iα ={ B}, B={AC}
Khóa là K=AB và K=BC. Ta thấy B⊂ K, B→D, 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 2NF.
X (Iα ∪ X) (Iα ∪ X)
+
Siêu khóa Khóa
B BD
A AB ABCD AB AB
C BC ABCD ABCD BC
AC ABC ABCD ABC
24/45
25. 16.2.2. dạng chUẩn 2
(2NF-Second normal form)
Thuật Toán 2:
Bước 1: Tìm tất cả các khóa của lược đồ α, từ tất cả các khóa
này ta suy ra các thuộc tính không khóa của lược đồ α. Ký
hiệu tập thuộc tính không khóa này là NK.
Bước 2: Với mỗi khóa Ki, ký hiệu họ của các tập con thực sự
của Ki là { S1, S2, …, Ski }, ký hiệu Q={ Q1, Q2, …, Qn } là
họ tất cả các tập con thực sự của khóa Ki.
Bước 3: Tìm bao đóng Q+ ={ Q1+, Q2+, …, Qn+ }
Bước 4: Nếu Q+ ∩ NK=φ với mọi i=1…n thì lược đồ α ở
dạng chuẩn 2NF ngược lại tồn tại Q+ ∩ NK≠φ thì lược đồ α
không ở dạng chuẩn 2NF.
25/45
26. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
26/45
27. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Định nghĩa 1:
Cho lược đồ quan hệ α= ( U, F), lược đồ α được gọi là ở
dạng chuẩn 3 ( ký hiệu là 3 NF), nếu như lược đồ ở dạng
chuản 2NF và các thuộc tính không khóa của α là không phụ
thuộc hàm bắc cầu vào khóa chính.
Định nghĩa 2:
Cho lược đồ quan hệ α =( U, F), lược đồ α được gọi là ở
dạng chuẩn 3, ký hiệu là 3NF, nếu như mọi phụ thuộc hàm
X→ A ∈ F+ với A ∉ X thì:
- Hoặc X là siêu khóa.
- Hoặc A là thuộc tính khóa.
27/45
28. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Nhận xét:
Lược đồ quan hệ α =( U, F), với F là tập các phụ thuộc hàm
có vế phải chỉ gồm một thuộc tính. Khi đó lược đồ α ở dạng
chuẩn 3NF khi và chỉ khi 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.
28/45
29. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Thuật toán kiểm tra lược đồ có ở dạng chuẩn 3NF hay không?
Từ định nghĩa về dạng chuẩn 3NF trên ta có thuật toán
kiểm tra xem một lược đồ có ở dạng chuẩn 3NF hay không
như sau:
Input: Lược đồ quan hệ α =( U, F)
Output: Khẳng định α có đạt dạng chuẩn 3NF hay không
29/45
30. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Thuật toán 1:
Thuật toán kiểm tra dạng chuẩn BCNF
Vào: Lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: Khẳng định Q có đạt dạng chuẩn 3NF hay không
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 FItt có vế
phải một thuộc tính.
Bước 3: Nếu mọi phụ thuộc hàm X→ A∈ FItt với A ∉ X đều
có X là siêu khóa hoặc A là một thuộc tính khóa thì Q đạt
chẩn 3 ngược lại Q không đạt chuẩn 3.
30/45
31. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Ví dụ:
Cho lược đồ quan hệ Q(A, B, C, D) F={ AB→C;
D→B; C→ABD } Hỏi lược đồ có ở dạng
chuẩn 3NF?
Giải:
Iα =Q ∪ ( Ri- -Li )=ABCD ABCD= φ , Iα ≠Q
N={∪ ( Ri -Li ) sao cho Li ⊆Iα }= φ
N’=(Iα N)+ Iα = φ (N’⊆ Nα )
N’’=∪ Ri - ∪ Li =ABCD ABCD= φ
Nα=N∪N’∪N’’= φ
B=Q Nα Iα=ABCD φ =ABCD
Vì B=4>2
=> Iα ={φ}, B={ABCD}
31/45
32. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
K1= { AB };K2= { AD };
K3= { C } là khóa
=> mọi phụ thuộc hàm X→A∈F
đều có A là thuộc tính
khóa.
Vậy Q đạt chuẩn 3NF.
X (Iα ∪ X) (Iα ∪ X)
+
Siêu khóa Khóa
A A A
B B B
C C ABCD C C
D D BD
AB AB ABCD AB AB
AC AC ABCD AC
AD AD ABCD AD AD
BC BC ABCD BC
BD BD BD
CD CD ABCD CD
ABC ABC ABCD ABC
ABD ABD ABCD ABD
ACD ACD ABCD ACD
BCD BCD ABCD BCD
32/45
33. 16.2.3. dạng chUẩn 3
(3NF-THiRD normal form)
Thuật toán 2:
Bước 1: Tìm tất cả khóa của lược đồ α.
Bước 2: Từ F tìm tập phụ thuộc hàm tương đương F’, mà vế
phải của các phụ thuộc hàm trong F’ chỉ có một thuộc tính.
Bước 3: Nếu mọi phụ thuộc hàm X→A∈F’ với A∉X đều có X
là siêu khóa hoặc A là thuộc tính khóa thì α đạt chuẩn 3NF
ngược lại α không đạt chuẩn 3NF.
33/45
34. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
34/45
35. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
Định nghĩa 1:
Cho lược đồ quan hệ α= ( U, F), lược đồ α được gọi là ở dạng
chuẩn Boyce Codd, ký hiệu là BCNF, nếu như lược đồ ở dạng
chuẩn 1NF và nếu X→A∈F+ (A∉X) thì X phải là siêu khóa
của lược đồ.
Định ngĩa 2:
Cho lược đồ quan hệ α= ( U, F), lược đồ α được gọi là ở dạng
chuẩn Boyce Codd, ký hiệu là BCNF, nếu như lược đồ ở dạng
chuẩn 1NF và nếu X→A∈F là phụ thuộc hàm không tầm
thường (Y⊄ X) thì X phải là siêu khóa của lược đồ.
35/45
36. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
Thuật toán kiểm tra lược đồ ở dạng chuẩn BCNF hay không?
Từ định nghĩa về dạng chuẩn BCNF trên ta có thuật toán
kiểm tra xem một lược đồ có ở dạng chuẩn BCNF hay không
như sau:
Input: Lược đồ quan hệ α =( U, F)
Output: Khẳng định α có đạt dạng chuẩn BCNF hay không
36/45
37. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
Thuật toán 1:
Thuật toán kiểm tra dạng chuẩn BCNF
Vào: Lược đồ quan hệ Q, tập phụ thuộc hàm F
Ra: Khẳng định Q có đạt dạng chuẩn 3NF hay không
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 FItt có vế
phải một thuộc tính.
Bước 3: Nếu mọi phụ thuộc hàm X→ A∈ FItt với A ∉ X đều
có X là siêu khóa thì Q đạt chẩn BCNF ngược lại Q không đạt
chuẩn BCNF.
37/45
38. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
Ví dụ:
Q (A, B, C, D, E, I) F={ACD→EBI; CE→AD }.
Hỏi Q có đạt chuẩn BCNF hay không?
Giải:
Iα =Q ∪ ( Ri -Li )=ABCDEI (EBI∪AD)=C => Iα ≠Q
N={∪ ( Ri -Li ) sao cho Li ⊆Iα } = φ
N’=(Iα N)+ Iα = φ (N’⊆ Nα )
N’’=∪ Ri - ∪ Li =ABDEI ACDE=BI
Nα=N∪N’∪N’’=BI
B=Q N’ Iα=ABCDEI BI C=ADE
Vì B=3>2 => Iα ={ C}, B={ADE}
38/45
39. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
F =FItt={ ACD→E, ACD→B, ACD→I, CE→A, CE→D}
Mọi phụ thuộc hàm của FItt đều có vế trái là siêu khóa
=> Q đạt dạng chuẩn BCNF.
X (Iα ∪ X) (Iα ∪ X)+ Siêu khóa Khóa
C C
A AC AC
D CD CD
E CE ABCDEI CE CE
AD ACD ABCDEI ACD ACD
AE ACE ABCDEI ACE
DE CDE ABCDEI CDE
ADE ACDE ABCDEI ADE
39/45
40. 16.2.4. dạng chUẩn BCNF
(Boyce Codd normal form)
Thuật tán 2:
Bước 1: Từ F tìm tập phụ thuộc hàm tương đương F’, mà vế
phải của các phụ thuộc hàm trong F’ chỉ có một thuộc tính.
Bước 2: Nếu mọi phụ thuộc hàm X→A∈F+ với A∉X đều có
X là siêu khóa thì α đạt chẩn BCNF ngược lại α không đạt
chuẩn BCNF.
40/45
41. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
41/45
42. 16.2. Thuật toán tìm dạng chuẩn cao nhất
của lược đồ
Cho lược đồ quan hệ α =( U, F), hãy tìm dạng chuẩn cao nhất
của lược đồ α.
Input: Lược đồ quan hệ α =( U, F) ( ở đây ta giả thiết rằng
lược đồ α đã được chuẩn hóa, tức là đã ở dạng chuẩn 1).
Output: Dạng chuẩn cao nhất của lược đồ α.
Thuật toán:
Bước 1: Tìm tất cả các khóa của lược đồ α.
Bước 2: Sử dụng thuật toán kiểm tra lược đồ ở dạng chuẩn
BCNF, nếu lược đồ ở dạng BCNF thì dừng thuật toán và kết
luận dạng chuẩn cao nhất của lược đồ là BCNF, ngược lại thì
chuyển qua bước tiếp theo.
42/45
43. 16.2. Thuật toán tìm dạng chuẩn cao nhất
của lược đồ
Thuật toán:
Bước 3: Sử dụng thuật toán kiểm tra lược đồ ở dạng chuẩn
3NF, nếu lược đồ ở dạng 3NF thì dừng thuật toán và kết luận
dạng chuẩn cao nhất của lược đồ là 3NF, ngược lại thì chuyển
qua bước tiếp theo.
Bước 4: Sử dụng thuật toán kiểm tra lược đồ ở dạng chuẩn
2NF, nếu lược đồ ở dạng 2NF thì dừng thuật toán và kết luận
dạng chuẩn cao nhất của lược đồ là 3NF, ngược lại thì lược đồ
ở dạng chuẩn 1NF.
43/45
44. NỘI DUNG Chi tiết :
Một số khái niệm liên quan
Các dạng chuẩn
Dạng chuẩn 1 (1NF- Fist 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)
Thuật toán tìm dạng chuẩn cao nhất của lược đồ
Mối quan hệ giữa các dạng chuẩn
44/45
45. 16.4. Mối quan hệ giữa các dạng chuẩn
Định lý: Một lược đò ở dạng chuẩn cao khi thì cũng ở dạng
chuẩn thấp, tuy nhiên điều ngược lại có thể đúng, điều này
được môt tả trong hình sau:
1NF1NF
45/45