BÀI GIẢNG CSDL Chương 6: Lý Thuyết Thiết Kế Cơ Sở Dữ Liệu
I. 1.
Khái Niệm Phụ thuộc Hàm Định Nghĩa: là khái niệm quan trọng nhất trong việc thiết kế cơ sở dữ liệu - cho quan hệ R trên tập thuộc tính U R(U) + với U={A1,A2,A3…An}
x,y,z là tập con của U x y nếu mọi t & t’ t.y=t’.y t.x=t’.x
Ví dụ: x={masv} y={hoten,ngaysinh}
đ/n hệ tiên đề amstrong
=>x y 2. Hệ tiên đề Amstrong a. Gọi R(U) là lược đồ quan hệ với U = {A1,…,An} là tập các thuộc tính. X,
Y, Z, W U. Hệ tiên đề Armstrong bao gồm:
F1) Tính phản xạ: Y X X Y F2) Tính bắc cầu: X Y, Y Z X Z F3) Tính mở rộng hai vế(tăng trưởng) X Y (Z U) XZ YZ
b. bổ đề . Bổ đề 1: Hệ tiên đề Armstrong là đúng. Có nghĩa là F là tập các phụ thuộc hàm đúng trên quan hệ R. Nếu X Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì X Y là đúng trên quan hệ R.
Bổ đề 2: F4) Cộng tính ở vế phảI( luật hợp) X Y, X Z X YZ F5) Tính tựa bắc cầu(giả bắc cầu) X Y, YZ W XZ W F6) Luật tách: X Y Z X Z và x y
Ví dụ: Cho tập phụ thuộc hàm F = {A B, B CD} ta chứng minh phụ thuộc hàm AC CD được suy diễn logic từ F.
Thật vậy: F3: A B AC BC F3: B CD BC CD
F3: AC BC, BC CD AC CD
Ví dụ 2:cho R={A,B,C,D,E}
F={A BC,B D,C E} CMR:A E,A D Ví dụ 3:cho R={ABCDEF}
F={A BC,AB D,AC E,DE F,F AD) CMR:A E,F DE
Bao đóng của phụ thuộc hàm
3. Tính bao đóng a. a. Định nghĩa: Cho tập phụ thuộc hàm F trên tập thuộc tính U. Bao đóng của F, ký hiệu là F+, là
tập nhỏ nhất các phụ thuộc hàm trên U thoả:
F+ = {X Y | F |== X Y}
b. Định nghĩa khác cho bao đóng của tập phụ thuộc hàm: F+ là tập các phụ thuộc suy diễn từ F nhờ hệ tiên đề Armstrong. Tức nó phải thoả
hai tính chất sau:
F+ F Khi áp dụng các tính chất F1, F2, F3 cho F+ ta không thu được phụ thuộc hàm nào
nằm ngoài F+.
c. Tính chất: (1): Tính phản xạ: F+ F (2): Tính đơn điệu: F G F+ G+ (3): Tính lũy đẳng: (F+)+ = F+ (4): (FG)+ F+G+ (5): (F+G)+ = (FG+)+ = (FG)+
3. Bao đóng của tập thuộc tính a. Định nghĩa: Cho tập phụ thuộc hàm F trên tập thuộc tính U và X U. Bao đóng của tập
thuộc tính X (đối với F), ký hiệu X+, là tập sau:
X+ = {A | X A F+}
b. Định nghĩa khác cho bao đóng của tập thuộc tính: X+ là tập các thuộc tính A sao cho X A có thể suy diễn được từ F bằng hệ
tiên đề Armstrong.
c. Tính chất: (1): Tính phản xạ: X+ X (2): Tính đơn điệu: X Y X+ Y+ (3): Tính lũy đẳng: (X+)+ = X+ (4): (XY)+ X+Y+ (5): (X+Y)+ = (XY+)+ = (XY)+ (6): X Y Y X+ (7): X Y Y+ X+ (8): X X+ và X+ X (9): X+ = Y+ X Y, Y X
F phủ phụ thuộc hàm G nếu G+ F+
F tương đương phụ thuộc hàm G nếu G+ = F+
Để xác định phụ thuộc hàm Y Z G+ hay không ta sử dụng thuật toán tính bao đóng tập thuộc tính để tính Y+ đối với G và kiểm tra xem Z Y+ hay không.
4. phụ thuộc hàm tương đương - khái niệm Cho R={A1,A2….An} Cho lược đồ quan hệ R và các tập phụ thuộc hàm F và G trên R ta nói:
Mệnh đề: F G+ F+ G+
Mệnh đề: Mỗi tập phụ thuộc hàm F tương đương với tập phụ thuộc hàm G gồm
các phụ thuộc hàm mà vế phải chỉ có 1 thuộc tính.
b. Phủ tối tiêu:
Để tối ưu hơn nữa việc thiết kế lược đồ CSDL quan hệ ta yêu cầu mạnh hơn đối với tập phụ
thuộc hàm tương đương.
Định nghĩa: Tập phụ thuộc hàm F gọi là phụ thuộc hàm tối thiểu nếu nó thoả mãn các điều
kiện sau:
(1): Vế phải của mỗi phụ thuộc hàm trong F chỉ có 1 thuộc tính.
(2): Mọi phụ thuộc hàm X A F là quan trọng, tức là tập phụ thuộc hàm có từ F bằng sự
loại bỏ phụ thuộc hàm X A:
F \ {X A}
không tương đương với F.
(3): Với mỗi phụ thuộc hàm X A F, mọi thuộc tính B X đều quan trọng, tức là tập phụ thuộc hàm có từ F bằng việc thay phụ thuộc hàm X A bởi phụ thuộc hàm (X \{B}) A:
(F \ {X A}) {X \ {B} A}
không tương đương với F.
Nhận xét: Điều kiện (2) đảm bảo không có phụ thuộc hàm dư thừa, điều kiện (3) đảm bảo
không có thuộc tính ở vế trái dư thừa.
Thuật toán tìm phủ tối thiểu:
- Input: Tập phụ thuộc hàm F.
- Output: Tập phụ thuộc hàm tối thiểu G tương đương với F.
- Method:
(1): Phân rã vế phải tất cả phụ thuộc hàm của F và gọi G là tập tất cả các phụ thuộc hàm
thu được.
(2): Loại các phụ thuộc hàm dư thừa trong G: Không tồn tại X A nào trong F mà tập F
- {X A} tương đương với F.
(3): Loại các thuộc tính dư thừa ở vế trái của các phụ thuộc hàm trong G: Không tồn tại X
A trong F mà Z X để cho:
(F - {X A}) {Z A}
tương đương với F.
Ví dụ:
Cho lược đồ R = (A, B, C, D, E, G) và tập phụ thuộc hàm F gồm các phụ thuộc hàm sau:
AB C D EG
C A
BE C
BC D
CG BD
ACD B CE AG
Ta áp dụng thuật toán tính phủ tối thiểu để tính phủ tối thiểu của F.
(1): Phân rã vế phải các phụ thuộc hàm trong F
Tập G thu được gồm các phụ thuộc hàm:
AB C BE C
C A
CG B
BC D CG D
ACD B CE A
D E
CE G
D G
(2): Loại các phụ thuộc hàm dư thừa và thuộc tính dư thừa
* Loại các phụ thuộc hàm dư thừa:
- Loại CG B, vì nó suy ra từ C A, ACD B và CG D bằng các phép kéo
theo như sau:
C A CG AG
(qui tắc mở rộng hai vế)
CG A
(qui tắc phân rã)
CGA & CGD & CG C
CG ACD
(qui tắc hợp)
CG ACD & ACD B CG B
(qui tắc bắc cầu)
Như vậy ta loại ra khỏi G.
- Loại CE A, vì nó suy ra từ C A.
Kết thúc bước này các phụ thuộc hàm còn lại như sau:
AB C BE C
C A
BC D CG D
ACD B
D E CE G
D G
*Loại thuộc tính dư thừa:
Trong phụ thuộc hàm ACD B, thuộc tính A dư thừa vì C A. Như vậy ta thay
ACD B bởi CD B.
Cuối cùng ta nhận được phủ tối thiểu:
AB C BE C
C A
BC D CG D
CD B
D E CE G
D G
6.Khoá và giải thuật tìm khoá a. Khái niệm khoá khái niệm căn bản - Cho R={A1,A2,A3…An} Cho K là tập con của R Cho r là quan hệ trên R
t1,t2 là hai bộ bất kỳ
Khi đó K gọi là khoá nếu như t1 t2 thì t1[k] t2[k] Là siêu khoá khi: K’ K
-khái niệm theo phụ thuộc hàm cho Cho R={A1,A2,A3…An} cho k R cho F là f tập phụ thuộc hàm
Khi đó : k la khoá nếu
+ k R + K’ K
b. giải thuật tìm khoá *ứng dụng:cho phếp xác định được khoá của một quan hệ dựa trên tập phụ
thuộc hàm
*bài toán:
cho R là quan hệ
F là tập phụ thuộc hàm yêu cấu: tìm khoá của R dựa trên F
Các bước:
b1: liệt kê các phần tử vế trái của phụ thuộc hàm F: L
liệt kê các phần tử vế phải của phụ thuộc hàm F:R1
b2: lấy R\R1=thuộc tính x // trong khoá phả chứa x
L giao R1=y
b3:tính bao đóng x+:
x+=R thì kết luận x là khoá nếu x+ R
chuyển sang bước 4
b4: ghép x với từng phần tử y Sau đó thực hiên như bước 3 Ví dụ: Cho lược đồ R = (A, B, C, D, E, G) và tập phụ thuộc hàm F gồm
các phụ thuộc hàm sau:
AB C, D EG,C A,BE C,BC D,CG BD
ACD B,
Tìm khoá?
Vd2: cho Q=(A,B,C,D,E,G,H,I)
F=(A BC,D EG,AE H,BD I)
a.
kiểm tra A I
b.
Tính bao đóng AE
c.
Tìm khoá
Ví dụ 3: cho R=(MNPQSU) F={M NP,P NQ,MN S,NS UQ} a.kiểm tra M Q? b.tính bao đóng của P c. Tìm khoá Ví dụ 4: cho R=(ABCDEG) F={AB C,AC DE,C BG,D EG} a.kiểm tra AB E b.tính bao đóng của AC c.tìm khoá
Chương 7: Các dạng chuẩn của quan hệ
I. 1.
Giới thiệu dạng chuẩn là gì? đ/n :là những quy ước phụ thuộc những ràng buộc áp dụng cho một quan hệ Tránh do bộ phát sinh khi cập nhật dữ liệu Các thao tác cập nhập : thêm,sửa, xoá, tìm kiếm, sắp xếp, lọc
Vd: cho 1 quan hệ sinh viên sv{hoten,masv,diem,mamh}// dạng chuẩn hay không chuẩn? vì
sao?
2.các loại dạng chuẩn gồm 4 dạng: - 1NF: dạng chuẩn 1 - 2NF : dạng chuẩn 2 - 3NF: dạng chuẩn 3 - BCNF: dạng chuẩn 4
II. Quy ước dạng chuẩn 1.dạng chuẩn 1NF *quy ước: giá trị của các thuộc tính trong mỗI bộ phải đầy đủ *chú ý: hầu hết tất cả các bảng dl đều ở dạng 1NF Ví dụ
Hàng 1
mah m1 m1
m3
10 20 100 10 23 slban 10 35 25 12 14
(mah,ngayban,slban) 5 M1 9 M2 9 M3 4 M1 M2 8 dạng 1NF
Hàng 2 ngayban 5 8 5 5 20 ko phải ở dạng 1NF (thiếu thông tin)
2. Dạng 2NF Quy ước
một quan hệ ở dạng 2NF khi: - nó ở dạng 1NF -các thuộc tính không khoá phải phụ thuộc hàm đầy đủ vào thuộc tính khoá Chuẩn hoá
nếu một quan hệ ở dạng 1NF nhưng lại ở dạng 2 thì phải chuẩn hoá như sau -tách các thuộc tính phụ thuộc một phần vào khoá và thuộc tính khoá vào bảng - khoá của bảng tách là thuộc tính khoá
Ví dụ: Cho 1 quan hệ R={ABCD} F={AB C,B D}
- Hỏi R đã ở dạng chuẩn 2 NF hay chưa? - tách bảng đã chuyển về 2NF
trả lời: -Khoá: AB R chưa phải ở dạng 2( vì D phụ thuộc 1 phần khoá) - tách R(ABCD)
R1(ABC), F={AB C}
Khoá AB R2(BD),F={B D}
Khoá B
kết luận: từ R tách 2 quan hệ R1,R2 đều ở dạng 2 NF
3.Dạng chuẩn 3NF *quy ước: một quan hệ ở dạng 3NF khi:
- ở dạng 2 NF -không tồn tại các thuộc tính không khoá phụ thuộc hàm bắc cầu vào khoá chính
phụ thuộc hàm bắc cầu: `
-chặt: A B,B C Thì A C và C không thể xác định được
A
- không chặt: A B,B C ,C A
*chuẩn hoá thành dạng 3NF nếu 1 quan hệ ở dạng 2NF nhưng chưa ở dạng 3NF thì phải tách - tách các thuộc tính phụ thuộc hàm bắc cầu và thuộc tính xác định hàm thành 1 bảng - khoá của bảng tách là thuộc tính xác định hàm
Ví dụ: cho R=(ABCD) F={AB C,C D) Tách R(ABCD) R1(CD);F={C D}//
Khoá là C
R2(ABC); F={AB C}
Khoá AB
Chú ý: phụ thuộc hoàn toàn 1NF 2NF
Phụ thuộc trực tiếp(không bắc cầu): 2NF 3NF
BÀI TẬP Cho R=(ABCDEGH) F={B AC,AB DE,A G,C H} -hỏi R ở dạng nào? - chuyển về 2 NF - chuyển về 3NF Bài làm R =(ABCDEGH) R1=(AG); F={A G}
khoá là: A
R2=(CH);F={C H}
khoá là :C
R3=(ABCDE);F3=(B AC,AB DE}
Tách R3 thấy B AC
B A(luật tách) B AB(luật tăng trưởng) AB DE B DE(bắc cầu) R31=(BAC),F={B AC}
Khoá là: B R32=(BDE)
kiểm tra:
4. Cách kiểm tra việc tách hợp lệ R=R1 R2 ….Rn hỏi tách R đúng hay không đúng giả thiết: R={A1,A2,A3…AN}N: thuộc tính - giả sử R=R1 R2 ….Rn F={f1,f2…fn}
b1:lập bảng có: n cột tương đương n thuộc tính nhãn của mỗi cột là tên thuộc tính
xác định m dòng(các quan hệ được tách ra) đặt chỉ số: Stt cho cột và dòng ghi giá trị aij: j là chỉ số dòng
i là chỉ số cột tại các quan hệ các
quan hệ có thuộc tính được tách
B2 cập nhật
Từ F nếu có X Y
nếu X ở 2 ô có giá trị giống nhau thì Y cập nhật giá trị
bằng nhau
lặp lại nhiều lần cho đến khi nào 1 dòng xuất hiện toàn a
thì quá trình tách là đúng
Ví dụ 1
cho R(ABCD)
F={AB C,B D,BC A} Tách thành:ABC,DC,DBA Hỏi phép tách này có mất thông tin hay không? Ví dụ 2: Cho R=(ABCDE)
F={AB DE,E AD,D C}. Tách thánh BDC,AE,ABD
Phép tách có bảo toàn hay không?
5. chuẩn BCNF(boyed godd)
Quy định: mọi thuộc tính không khoá phải phụ thuộc hàm vào
chuẩn rất mạnh hoàn toàn dựa vào định nghĩa phụ thuộc hàm, trong thự tế sử dụng BCNF nhiều hơn 3NF
khoá
- không tồn tại 1 trường hợp ngược lại: khoá phụ thuộc
Khái niệm khoá theo quan điểm phụ thuộc hàm
hàm không khoá
cho R={A1,A2,A3…AN}
K R, K gọi là khoá nếu:
- k {A1,A2,A3…AN} - không tồn tại k’ k, k’ {A1,A2,A3…AN}
Ví dụ R={ABCD},F={AB C,C D}
AB là khoá, và AB {A,B,C,D}
Chú ý:tập thuộc tính xác định hàm tất cả các thuộc tính còn lại -khoá dự tuyển: giả sử R đều có K1,K2 là khoá, có tính chất của
khoá. gọi K1,K2 là khoá dự tuyển
Ví dụ R={ABCD},F={AB C,BC D,D AB} Tìm K=? K1={AB} K2={BC} K3={D} gọi K1 ,K2 ,K3 các khoá dự tuyển
Ví dụ 2:R={ABCD},F={AB CD,D B}
dạng chuẩn 3NF , không ở dạng chuẩn BCNF vì khoá AB
CD không là khoá
Quy tắc tách nếu quan hệ không ở dạng chuẩn BCNF thì chuyển về BCNF như
sau(trong quan hệ vẫn có thuộc tính khoá phụ thuộc hàm vào không khoá)
-tách thuộc tính không khoá và thuộc tính khoá thuộc phụ thuộc hàm
vào không khoá thành 1 bảng
- khoá của bảng tách là thuộc tính không khoá Ví dụ 2 tách R1:={B,D} R2:={A,B,C} R2={A,C,D}
BÀI TẬP Bài 1: cho R=(A,B,C,D,E,G) F={AB CD,BC E,D GB} Yêu cầu:- tìm khoá
-xác định dạng chuẩn R - tách R thanh BCNF
Bài 2:R=(A,B,C,D,E) F={AB ED,E A,A C} Yêu cầu:- tìm khoá
-xác định dạng chuẩn R - tách R thanh BCNF
6. Cách kiểm tra R được tách R1, R2 - cho R la tập thuộc tính,F là tập phụ thuộc hàm - nếu R tách ra R1,R2 thì trong F có 1 phụ thuộc hàm có
dạng R1
