Bài giảng Cơ sở dữ liệu - Bài 8: Thiết kế cơ sở dữ liệu mức quan niệm - Vũ Văn Định

Bài 8. THIẾT KẾ SCDL MỨC QUAN NIỆM
 Trên thực tế, một ứng dụng có thể đựơc phân tích. 
thiết kế thành nhiều lược đồ CSDL khác nhau. Để
đánh giá việc thiết kế một lược đồ CSDL, người ta
dựa trên các tiêu chuẩn về sự trùng lặp thông tin, chi 
phí kiểm tra và các ràng buộc toàn vẹn...
 Vậy để tránh sự dư thừa thông tin, ta cần chuẩn hoá
tất cả các lược đồ trong quá trình thiết kế.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
1. Phép tách các lược đồ quan hệ
- ĐN: 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 đồ
{ R1, R2, .., Rk}, trong đó
Ri  R, i= 1,..,k 
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
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ :
Cho lược đồ quan hệ người cung cấp :
S(MCTY, ĐC, MH, GIA)
với tập pth : MCTY ĐC
MCTY, MH GIA
Có thể được tách thành 2 lược đồ khác là :
S1(MCTY, ĐC) và S2 ( MCTY, MH, GIA)
như vậy sẽ không mất công lưu địa chỉ của
một công ty nhiều lần
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Kết nối không mất mát thông tin 
- Nếu R là một lược đồ quan hệ được
tách thành các lược đồ con R1, R2, .., Rk
và D là một tập các phụ thuộc dữ liệu. Nói
rằng phép tách là tách - kết nối không mất
mát thông tin đối với D nếu với mỗi quan hệ
r trên R thoả D:
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
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Kiểm tra phép kết nối không
mất mát thông tin 
Input: R ={ A1, A2, .., An} tập các phụ
thuộc hàm và phép tách p =(R1, R2, .., 
Rk)
Output: Phép tách có phải là không mất
mát thông tin hay không ?
Phương pháp : Thiết lập một bảng với n cột
k hàng.; cột thứ j tương ứng với thuộc tính
Aj; hàng thứ i tương ứng với lược đồ Ri. 
Tại ô (i,j) điền kí hiệu aj nếu Aj Ri, nếu
không điền kí hiệu bij
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
- Xét các pth:
+Xét ( X Y ) F , xét các hàng và nếu có
giá trị bằng nhau trên thuộc tính X thì làm bằng
các giá trị của chúng trên Y. Khi làm bằng trên
Y, nếu một trong hai giá trị là aj thì ưu tiên làm
bằng aj, nếu không làm bằng một trong các kí
hiệu bij.
+Tiếp tục với các pth khác ( kể cả việc lặp
lại các pth đã được áp dụng) cho đến khi không
còn áp dụng được nữa.
- Xem xét kq: Nếu xuất hiện một hàng gồm toàn
kí hiệu a1, a2, .. , an thì phép kết nối là không
mất mát thông tin, ngược lại là kết nối mất mát
thông tin.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
VD1: Quan hÖ ng­êi cung cÊp:
R(MCTY, ĐC, MH, GIA) ®­îc t¸ch thµnh 2 quan hÖ:
R1(MCTY, ĐC) vµ R2(MCTY, MH,GIA) 
víi c¸c phô thuéc hµm: MCTY ĐC 
MCTY,MH GIA
Kiểm tra xem phép tách trên có mất mát thông tin hay 
không ?
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
B¶ng ban ®Çu ®­îc thiÕt lËp nh­ sau: 
a1
a1
MCTY
a3a3b22R2
b14b13a2R1
GIAMH§C
1 2 3 4
1
2
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
¸p dông phô thuéc hµm MCTY ĐC cho 2 
hµng cña b¶ng. Ta nhËn thÊy 2 hµng b»ng nhau
trªn cét tªn (®Òu lµ a1) nªn ë cét §C chóng ®­îc
lµm b»ng vµ b»ng a2. Khi ®ã ta thÊy b¶ng kÕt
qu¶ lµ:
Cã hµng thø 2 cã c¸c gi¸ trÞ toµn lµ a, do ®ã phÐp
t¸ch lµ T¸ch - KÕt nèi kh«ng mÊt m¸t th«ng tin. 
a1
a1
Tªn
a3a3a2R2
b14b13a2R1
Gi¸S¶n phÈmĐÞa chØ
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Bµi tËp:
B1. Cho l­îc ®å quan hÖ R={A, B, C, D} vµ tËp phô
thuéc hµm F={A B, AC D}
PhÐp t¸ch quan hÖ R thµnh 2 quan hÖ R1={AB} vµ
R2={ACD} cã tæn thÊt th«ng tin kh«ng? V× sao?
B2. Cho lược đồ quan hệ với các thuộc tính A, B, C, D, E, F 
và tập phụ thuộc hàm
F= { AB C, C D, ABD E, F A}
Kiểm tra tính mất mát thông tin của phép tách R thành : 
(R) = ( BC, AC, ABDE, ABDF)
B3. Dùng kĩ thuật bảng kiểm tra tính tổn thất của các
phép tách sau :
R= , U = ABCDE ; 
F = { A C, B C , C D , DE C , CE A}
p = ( AD, AB, BE , CDE)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2. Một số khái niệm
* Thuộc tính khoá và không khoá
- Cho một lược đồ quan hệ R trên tập
thuộc tính U ={ A1, .., An}. Thuộc tính A U 
được gọi là thuộc tính khoá ( nguyên thuỷ
hay cơ bản) nếu A là một thành phần thuộc
một khoá nào đó của R, ngược lại A được gọi
là thuộc tính không khoá (phi nguyên thuỷ
hoặc thứ cấp).
-VD : Cho lược đồ R trên tập thuộc tính
u= { A, B, C, D } với các pth AB C , B D 
, BC A . Ta thấy AB và BC là khoá. Vậy A, 
B, C là thuộc tính khoá ( hay cơ bản) , còn D 
là thuộc tính không khoá hay thứ cấp.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
* Phụ thuộc hàm đầy đủ
Cho lược đồ quan hệ R(U) trên
tập thuộc tính U = { A1, ... ,Ak}. X 
và Y là hai tập thuộc tính khác nhau
X  U và Y  U.
Y là phụ thuộc hàm đầy đủ vào X 
nếu Y là pth vào X nhưng không pth
vào bất kì tập con thực sự nào của X
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Phụ thuộc bắc cầu
Cho một lược đồ quan hệ R(U); X là một
tập con các thuộc tính X U, A là một thuộc
tính thuộc U. A được gọi là phụ thuộc bắc cầu
vào X trên R nếu tồn tại một tập con Y của R 
sao cho X Y, Y A nhưng Y X với A 
XY.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3. Các dạng chuẩn của lược đồ quan hệ
- Quan hệ được chuẩn hoá là quan
hệ trong đó mỗi miền của một thuộc
tính chỉ chứa các giá trị nguyên tố ( 
tức là không phân nhỏ được nữa)
- Quan hệ có chứa các miền giá trị
là không nguyên tố gọi là quan hệ
không chuẩn hoá.
- Mét quan hÖ ®­îc chuÈn ho¸ cã thÓ thµnh mét
hoÆc nhiÒu quan hÖ chuÈn ho¸ kh¸c vµ kh«ng
lµm mÊt m¸t th«ng tin.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
C¸c d¹ng chuÈn:
- D¹ng kh«ng chuÈn
- D¹ng chuÈn thø nhÊt (1NF: First Normal Form)
- D¹ng chuÈn thø hai (2NF)
- D¹ng chuÈn thø ba (3NF)
- D¹ng chuÈn Boye – Codd (BCNF)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.1. D¹ng chuÈn thø nhÊt:
Mét l­îc ®å quan hÖ R ®­îc gäi lµ ë d¹ng chuÈn
mét (1NF) nÕu vµ chØ nÕu toµn bé c¸c miÒn cã
mÆt trong R ®Òu chØ chøa c¸c gi¸ trÞ nguyªn tè.
VD: Cho bảng quan hệ GD ( Ten_GV, MON_GD)
C, VISUAL BASIC, TK WEPHà
PASCAL, NM CSDNLan
Mon_GDTen_GV
Các giá trị ở thuộc tính Mon_GD chưa là giá trị
nguyên tố nên bảng trên chưa ở dạng chuẩn 1. 
Để đưa lược đồ trên về dạng chuẩn 1 ta tách
thuộc tính kép thành các thuộc tính đơn như sau : 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
TK WEPHà
VISUAL BASICHà
NM CSDNLan
CHà
PASCALLan
Mon_GDTen_GV
Bảng GD ở dạng chuẩn 1:
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.2. D¹ng chuÈn thø 2:
L­îc ®å quan hÖ R ë d¹ng chuÈn 2 (2NF) nÕu:
 R ë d¹ng chuÈn mét
 Mọi thuéc tÝnh kh«ng kho¸ cña R lµ phô thuéc hµm ®Çy
®ñ vµo kho¸ chÝnh.
VD:Cho quan hÖ:
SVTHI ( MONTHI, MSSV, TEN, TUOI, DIACHI, DIEM )
2HT22Tu135
7HN20Lan115
6HP21Ha124
7HN20Lan114
6HP21Ha123
8HN20Lan113
§iÓmĐÞa chØTuæiTªnMSSVM«n thi
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Khoá chính của quan hệ trên là (Monthi , 
MSSV).Ta thấy các thuộc tính không khoá: ten, 
tuoi , diachi không phụ thuộc đầy đủ vào khoá
chính (chỉ phụ thuộc vào MSSV). Do đó, vi phạm
2NF. Để lược đồ ở dạng chuẩn 2, ta tách thành 2 
quan hệ : 
SINHVIEN (MSSV, TEN, TUOI, DIACHI) vµ
THIXONG (MONTHI, MSSV, DIEM)
Hai quan hệ trên đã ở 2NF vì mọi thuộc tính
không khoá đều đã phụ thuộc hàm đầy đủ vào
khoá chính
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.3 Dạng chuẩn thứ 3 ( 3NF)
Lược đồ quan hệ R ở dạng chuẩn thứ 3 ( 3NF) nếu :
 R ở dạng chuẩn 2
Mỗi thuộc tính không khoá là không phụ thuộc hàm bắc
cầu vào khoá chính.
- VD1 : Cho lược đồ quan hệ R ( SAIP) với các phụ thuộc
hàm : SI P và S A.
R không ở 3NF. Vì có A là một thuộc tính không khoá, phụ
thuộc bắc cầu vào khoá chính: SI S , S A và S SI.
- VD2: Lược đồ quan hệ R ( CSZ) với các phụ thuộc hàm: 
CS Z, Z C. Trong lược đồ này, mọi thuộc tính đều là
thuộc tính khoá. Do vậy R ở 3 NF
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.4 Dạng chuẩn Boye-Codd ( BCNF)
Lược đồ quan hệ R ở dạng chuẩn Boye-Codd ( 
BCNF) nếu với mọi : X A thoả trên R , A X thì X là
một khoá của R.
- VD :Trong ví dụ R(CSZ) nêu trên, rõ ràng R không ở
BCNF mà là ở 3NF vì rằng Z C nhưng Z không phải là
một khoá của R.
- Định lý : Nếu một lược đồ quan hệ R với tập phụ thuộc
hàm F là ở BCNF thì nó là ở 3NF.
- Nhận xét : Trong CSDL, các lược đồ quan hệ ở dạng
chuẩn 1, 2, 3 vẫn tồn tại sự dư thừa thông tin. Để tối thiểu
sự dư thừa thông tin thì các bảng phải ở dạng chuẩn
BCNF
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4. Chuẩn hoá bảng
Chuẩn hoá bảng là cách đưa một bảng chưa chuẩn
hoá về dạng chuẩn 3NF hoặc BCNF mà không làm mất mát
thông tin.
Có hai phương pháp để chuẩn hoá lược đồ quan hệ :
 Phương pháp phân rã : Tách một lược đồ quan hệ
thành nhiều quan hệ khác thỏa mãn các dạng chuẩn.
 Phương pháp tổng hợp : Gom các thuộc tính thành
từng nhóm tạo thành quan hệ thoả mãn các dạng chuẩn.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4.1. Đưa một bảng chưa chuẩn hoá về dạng
chuẩn hoá
 Tách các nhóm thuộc tính lặp thành một bảng, khoá của
bảng là khoá của bảng ban đầu và thuộc tính định danh của
nhóm lặp.
 Những thuộc tính còn lại lập thành một bảng với khoá
của bảng là khoá của bảng ban đầu.
 Quá trình tách chỉ dừng lại khi ta đã nhận được các bảng
đã chuẩn hoá ( không còn thuộc tính lặp)
 VD : Quan hệ đơn hàng:
DONHANG ( SoĐ,MaH , TenH, SL, MAK, TenK,Tel)
DONHANG1 (SoĐ, MaH, TenH, SL)
DONHANG2 (SoĐ, MaK, TenK, Tel)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4.2. Đưa bảng ở 1NF về 2NF
 Tách các thuộc tính phụ thuộc vào một phần của khoá
thành một bảng, bảng này có khoá là thuộc tính gây ra sự
phụ thuộc.
 Các thuộc tính còn lại là một bảng với khoá của bảng
là khoá của bảng ban đầu.
 VD : Quan hệ ;
SVTHI ( MONTHI, MSSV, TEN, TUOI, DIACHI, DIEM )
ở 1NF nhưng chưa ở 2NF. Để quan hệ ở 2NF, ta
tách thành 2 quan hệ : 
SINHVIEN (MSSV, TEN, TUOI, DIACHI) vµ
THIXONG (MONTHI, MSSV, DIEM)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4.3. Phép tách một lược đồ quan hệ thành
3NF
Phép tách một lược đồ quan hệ R với tập pth F tối thiểu , 
không làm mất mát thông tin trên R, bảo toàn các pth sao cho mỗi
lược đồ con đều ở 3NF:
- B1 : Gom tất cả các thuộc tính của R không liên quan đên một pth
nào của F, hoặc vế trái, hoặc vế phải , cho vào một lược đồ.
- B2 : Nếu có một phụ thuộc hàm nào của F mà liên quan tới tất cả
các thuộc tính của R thì kết quả ra chính là R.
- B3 : Ngoài ra, phép tách đưa ra các lược đồ gồm các thuộc tính XA
cho pth X A; nếu X A1, X A2, ... , X An thì thay thế tập
thuộc tính XA1A2...An cho XAi ( 1<= i<= n). Quá trình tiếp tục đến
khi tất cả các lược đồ đều đã ở 3NF
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ : Cho lược đồ quan hệ R ( CTHRSG) với tập pth
tối thiểu : C T , HR C , HT R , CS G và HS 
 R.
Thuật toán trên cho ta kết quả của phép tách là tập
lược đồ gồm 5 lược đồ con ở 3NF là : 
R1 (CT) (ứng với pth C T)
R2 (HRC) (ứng với pth HR C)
R3 ( HTR) (ứng với pth HT R)
R4 ( CSG) (ứng với pth CS G)
R5 (HSR) (ứng với pth HS R)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4.3. Phép tách một lược đồ quan hệ thành
BCNF
Phép tách một lược đồ quan hệ R với tập pth F, không làm
mất mát thông tin sao cho mỗi lược đồ con đều ở BCNF.
Phương pháp : Lặp liên tiếp. Tại mỗi bước phép tách p là bảo đảm
không mất mát thông tin đối với F.
-Bước đầu : p chỉ bao gồm R
-Các bước tiếp : Nếu S là một lược đồ thuộc p, S chưa ở
BCNF, chọn X A là pth thoả trên S, trong đó X không chứa khoá
của S, A X. Thay thế S trong p bởi S1 và S2 với :
S1 = XA, S2 = S - A
Quá trình tiếp tục cho tới khi tất cả các lược đồ đều ở dạng
chuẩn BCNF.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
VD: Cho lược đồ R(CTHRSG) với tập pth :
C T, HR C, HT R, CS G, HS R
Khoá của R là HS. 
Ta lần lượt xét các pth vi phạm điều kiện BCNF.
- Xét C T : vi phạm BCNF vì C không chứa khoá, dùng
thuật toán trên để tách thành : R1 ( CT ) và R2( CHRSG). 
Sau đó cần tính F+ và chiếu xuống R1 và R2, kiểm tra ta
thấy R1 đã ở BCNF, R2 thì chưa. Ta tách tiếp R2. 
Phép tách cuối cùng được :
R1(CT), R2 ( CSG), R3 ( CHR), R4 ( HSR)
Quá trình tách có thể được biểu diến qua sơ đồ : 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
R(CTHRSG)
Khoá =HS
R1(CT)
Khoá =C
R2(CHRSG)
Khoá =HS
R21(CSG)
Khoá =CS
R22(CHRS)
Khoá =HS
R221(HRC)
Khoá =HR,HC
R222(HSR)
Khoá =HS
C T, HR C, HT R, 
CS G, HS R
HR C, HT R, 
CS G, HS R
HR C, 
HC R, 
HS R
HR C, HC R HS R
CS G
C T
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
BTVN:
B1. Cho lược đồ quan hệ R= với tập thuộc tính
U = ABCDEHG và tập phụ thuộc hàm F={DE G, E 
A, H C, CG H, DG EA, D B}
a. Xác định khoá của lược đồ quan hệ trên. 
b. Xác định dạng chuẩn cao nhất của lược đồ quan hệ
trên.
B2. Xác định dạng chuẩn cao nhất của lược đồ quan hệ
với các thuộc tính ABCDEF và tập phụ thuộc hàm
{AB C,C B,ABD E,F A} 
B3. Cho W= R = { A, B, C, D}
F= { B D, A C, C ABD}. Hỏi W có là 2NF, 3NF 
không ?
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
B4. Xác định dạng chuẩn cao nhất của lược đồ quan hệ
sau: H=(U,F); U=ABCD; 
F={CD B,A C,B ACD}
B5. Cho lược đồ R=(BOISQD) và
F={S D,I B, IS Q,B O}
a. Chứng tỏ rằng phép tách:
R=(SD,IB, ISQ,BO) Là phép tách không mất mát
thông tin.
b. Chứng tỏ phép tách trên là ở dạng 3NF.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí