CƠ SỞ DỮ LIỆU
Bài 4:
PHỤ THUỘC HÀM
13/08/2012 1 HVĐ – THQL
BÀI TOÁN THỰC TẾ
• Nghiên cứu hình thức các ràng buộc
– Xây dựng cấu trúc bảo đảm các ràng buộc tự động
thoả, do đó không cần lập trình
– Đánh giá một lược đồ cơ sở dữ liệu
13/08/2012 HVĐ – THQL 2
MỤC TIÊU
• Kiến thức:
– Phụ thuộc hàm
– Dạng chuẩn
– Kỹ thuật tableaux
• Kỹ năng:
– Tìm phủ tối tiểu
– Xác định dạng chuẩn
– Đánh giá lược đồ CSDL
• Yêu cầu: áp dụng thực tế
13/08/2012 HVĐ – THQL 3
NỘI DUNG
• Phụ thuộc hàm
• Phủ tối tiểu
• Dạng chuẩn
• Kỹ thuật tableaux
• Đánh giá lược đồ CSDL
• Khảo sát tình huống
13/08/2012 HVĐ – THQL 4
PHỤ THUỘC HÀM
• Phụ thuộc hàm

L2
L2
PHỤ THUỘC HÀM
• Phụ thuộc hàm là một
loại ràng buộc toàn vẹn
• Phụ thuộc hàm là luật
– PTH X  Y ngụ ý: biết
X sẽ xác định được Y
– Quan hệ r thỏa X  Y
• Các dòng có X giống
nhau thì Y cũng vậy
• r[X,Y] có X siêu khoá
– Luật nên lưu riêng để áp
dụng, ví dụ
• HDSo  NLap
• MaHG  Dgia
• HDSo,MaHG  SoL
13/08/2012 7 HVĐ – THQL
HDSo NLap MaHG DGia SoL
H01
H01
H02
H02
12
12
14
14
H01
H02
H01

QUY TẮC QUẢN LÝ
• Cho cơ sở dữ liệu lưu các dữ liệu liên quan đến
{Gviên, Sviên, Lớp , Môn, Khoa, Điểm, Tênsv}
• Các quy tắc sau đây, cái nào là phụ thuộc hàm
– Sinh viên thuộc về một lớp
– Sinh viên thuộc về một khoa
– Lớp thuộc về một khoa
– Sinh viên học một môn phải có điểm
– Sinh viên phải có tên
– Mỗi lớp có không quá 30 sinh viên
• Tổ chức lại các bảng
13/08/2012 9 HVĐ – THQL
BÀI TOÁN THÀNH VIÊN
• Ta nói f là hệ quả của F (hay được suy từ F)
nếu một quan hệ r bất kỳ thoả F thì thoả f
• Ký hiệu tập các phụ thuộc hàm hệ quả là F
+
và
được gọi là bao đóng của F
• Bài toán kiểm tra f  F được gọi là bài toán
thành viên

13/08/2012 HVĐ – THQL 10
LUẬT DẪN
• Bộ luật
– F1: XX
– F2: XY suy ra XZY
– F3: XY và XZ suy ra XYZ
– F4: XYZ suy ra XY và XZ
– F5: XY và YZ suy ra XZ

 X  Y (F
+
)
• Kiểm tra tính thành viên f = AE

DI đối với
F = {A

D,AB

E,BI

E,CD

I,E

C}
– Tính AE
+
= AEDCI
– Ta có DI  AE
+

– Suy ra f F
+

13/08/2012 12 HVĐ – THQL
THẢO LUẬN
• Bài tập 2, 3, 4, 5
13/08/2012 HVĐ – THQL 13

S  HN, M  H, LM  G
– Trong một học kỳ: S  L
• Với mỗi ngữ cảnh cho biết F có tối tiểu không
13/08/2012 16 HVĐ – THQL
TÌM PHỦ TỐI TIỂU
• Cơ sở: bài toán thành viên
• Các bước
– Phân rã
– Rút gọn vế trái
– Rút gọn phụ thuộc hàm

13/08/2012 17 HVĐ – THQL
VÍ DỤ
• Dùng thuật toán:
– Phân rã
– Rút gọn VT
– Rút gọn PTH
• Dùng bộ luật dẫn

13/08/2012 18 HVĐ – THQL
A->C
AB->C
C->DI
CD->I
EC->AB
EI->C
A->C
AB->C
C->D
C->I

{ S -> D,
I -> B,
IS -> Q,
B -> O }
{ A -> BC,
B -> AC,
C -> A }
{ AB -> C,
C -> A,
BC -> D,
ACD -> B,
D -> EG,
BE -> C,
CG -> BD,
CE -> AG }
DƯ THỪA PHẢI
• Tìm những thuộc tính xuất hiện
ở vế phải nhiều lần (ví dụ D)
• Chọn một PTH liên quan (ví dụ
H->KDN)
• Bỏ thuộc tính này, rồi tính bao
đóng (ví dụ H
+
=HKDN)
• Kết luận (ví dụ H->KDN dư
thừa D)

R(KDHNMLG)
F={ K -> D,
H -> KDN,

M -> G,
HNM -> L}
13/08/2012 22 HVĐ – THQL
THỬ SỨC
• Xét CD -> I
• Tính C
+
= CDI, chứa D
• Vậy CD -> I dư thừa trái
F =
{A->C
AB->C
C->DI
CD->I
EC->AB
EI->C}
13/08/2012 23 HVĐ – THQL
DẠNG CHUẨN
• Phụ thuộc hàm
• Phủ tối tiểu
• Dạng chuẩn
– Khái niệm
– Bài toán tìm tập khoá
– Bài toán xác định dạng chuẩn
– Bài toán tìm tập phụ thuộc hàm chiếu
• Kỹ thuật tableaux
• Đánh giá lược đồ CSDL
• Khảo sát tình huống
13/08/2012 HVĐ – THQL 24
VI PHẠM DẠNG CHUẨN