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.x=t’.x
t.y=t’.y






Ví dụ:
x={masv}
y={hoten,ngaysinh}
=>x y
2. Hệ tiên đề Amstrong
a.
đ/n hệ tiên đề amstrong
Gọi R(U) là lược đồ quan hệ với U = {A­1,…,An} là tập các thuộc tính. X,


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


3. Tính bao đóng
a.
Bao đóng của phụ thuộc hàm
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+

đóng tập thuộc tính để tính Y+ đối với G và kiểm tra xem Z  Y+ hay không.
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.

DE
DG

CE  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

 CG  A

(qui tắc mở rộng hai vế)
(qui tắc phân rã)

CGA & CGD & CG  C
CG  ACD & ACD  B

 CG  ACD

 CG  B

Như vậy ta loại ra khỏi G.
- Loại CE  A, vì nó suy ra từ C  A.

(qui tắc hợp)

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

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ệ
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?
I.
1.



2.các loại dạng chuẩn

9
100
5
25
M1
4
10
m3
5
12
M2
8
23
20
14
dạng 1NF
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



*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