Ph thuc hàm
Ph thuc hàm
và
Chun hóa c s d liu
Chng 7
Ni dung trình bày
̇ Nguyên tc thit k các lc đ quan h.
̇ Ph thuc hàm.
̇ Các dng chun.
̇ Mt s thut toán chun hóa.
Ph thuc hàm
Nguyên tc thit k
̇ Nhìn li vn đ thit k csdl
•Da trên trc quan ca ngi thit k.
•Thiu mt tiêu chun hình thc đ đánh giá.
̇ ánh giá cht lng thit k
•Ng ngha ca các thuc tính.
•Gim các giá tr tha trong các b.
•Gim các giá tr null trong các b.
• Không đ xut hin các b không có thc.
Ng ngha ca các thuc tính (1)
p.k.
MaPhongDChiNgSinhMaNVTen
f.k.NHANVIEN
p.k.
TrPhongMaPBTen
f.k.PHONGBAN
p.k.
TrusoMaPB
f.k.f.k.
TRUSO_PHONG

333445555Nghien cuu5…09/10/1965123456789Hung
Nghien cuu
TenPB
5
MaPB
333445555 08/12/1965333445555Nghia
TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
D liu b trùng lp
Ph thuc hàm
Thông tin tha trong các b (2)
̇ D thng khi thêm b
̇ D thng khi xóa b
999887777Nghien cuu5…09/10/1965123456789Hung
333445555Nghien cuu5…08/12/1965333445555Nghia
Hanh chinh
TenPB
4
MaPB
987654321nullnullnullnull
TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
333445555Nghien cuu5…09/10/1965123456789Hung
333445555Nghien cuu5…08/12/1965333445555Nghia
TenPBMaPB TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
Thông tin tha trong các b (3)
̇ D thng khi sa b
̇ Tránh xy ra các d thng cp nht d liu.
̇ Có th vi phm nguyên tc này đ tng hiu qu truy vn

Phát sinh các b không có thc (2)
Thu DucHung
Tan BinhHung
DiadiemTenNV
Thu DucNghia
NHANVIEN_DIADIEM
Thu DucSan pham Y7.52123456789
Tan BinhSan pham X32.51123456789
DiadiemTenDASoGioMaDAMaNV
102333445555
NHANVIEN_DUAN1
Thu DucSan pham Y
HungThu DucSan pham Y102333445555
NghiaThu DucSan pham Y7.52123456789
Thu Duc
Thu Duc
Tan Binh
Diadiem
Nghia
Hung
Hung
TenNV
San pham Y7.52123456789
San pham X32.51123456789
TenDAGioMaDAMaNV
San pham Y102333445555
Kt t nhiên
Phát sinh các b không có thc (3)
̇ Xây dng các lc đ quan h sao cho vic thc
hin phép kt bng gia chúng ch áp dng trên

BAr(R)
r không tha A → B, nhng tha B → A
Ph thuc hàm (2)
̇ r ∈ R tha các ràng buc PTH đc gi là trng thái hp l
ca R.
̇ Nhn xét
•Các PTH xut phát t các ràng buc trong th gii thc.
• ∀r ∈ R, ∀t ∈ r, t [X] là duy nht thì X là mt khóa ca R.
•Nu K là mt khóa ca R thì K xác đnh hàm tt c các tp thuc tính
ca R.
• PTH dùng đ đánh giá mt thit k CSDL.
TrPhongTenPBMaPBDiachiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
MaNV → MaPB MaPB → {TenPB, TrPhong}MaNV → TenNV
Ph thuc hàm
Bao đóng ca tp PTH
̇ F là tp PTH trên R
• F = {MaNV → TenNV, MaPB → {TenPB, TrPhong},
MaNV → MaPB}.
• ∀r ∈ R tha F và MaNV → {TenPB, TrPhong} cng đúng
vi r thì MaNV → {TenPB, TrPhong} gi là đc suy din
t F.
̇ Bao đóng ca F, ký hiu F
+
, gm
•F và
•Tt c các PTH đc suy din t F.
̇ F gi là đy đ nu F = F
+
.

⇔ Y ⊆ X
+
.
•Nu K là khóa ca R thì K
+
= U.
Thut toán tìm X
+
̇ Nhp: U, F và X ⊆ U
̇ Xut: X
+
̇ Thut toán 7.1
• B1: X
+
= X;
• B2: Nu tn ti Y → Z ∈ F và Y ⊆ X
+
thì
X
+
:= X
+
∪ Z;
và tip tc B2. Ngc li qua B3.
• B3: xut X
+
.
Ph thuc hàm
Ví d tìm X
+

DED
ABCDEAB
X
F
+
X
c suy din t F
Ph thuc hàm
Các tp PTH tng đng
̇ Tp PTH F đc nói là ph tp PTH G nu G ⊂ F
+
.
̇ Hai tp PTH F và G là tng đng nu
•F ph G và
•G ph F.
̇ Nhn xét
• ∀X → Y ∈ G, nu Y ⊆ X
F
+
thì F ph G.
• F và G tng đng nu và ch nu F
+
= G
+
.
Tp PTH ti thiu (1)
̇ Tha PTH
•{A → B, B → C,
A → C}, vì A → C đc suy din t {A → B, B → C}
A → B, B → C ⇒ A → C (lut bc cu).

1
, …, A
k
}, A
i
∈ U
F := F ∪ {X → {A
i
}}.
• B3: Vi mi X → {A} ∈ F, X = {B
1
, …, B
l
}, B
i
∈ U
Vi mi B
i
, nu A ∈ (X - {B
i
})
F
+
thì
F := (F - {X → {A}}) ∪ {(X - {B}) → {A}}.
• B4: Vi mi X → {A} ∈ F
G := F - {X → {A}}
Nu A ∈ X
G
+

[S].
•K ⊆ U là khóa nu K là siêu khóa nh nht.
-A ∈ K đc gi là thuc tính khóa.
̇ Nhn xét
•S xác đnh hàm tt c các thuc tính ca R.
• R có th có nhiu khóa.
Ph thuc hàm
Xác đnh khóa ca lc đ
̇ Nhp: tp PTH F xác đnh trên lc đ R(U).
̇ Xut: khóa K ca R.
̇ Thut toán 7.3.1
• B1:
K = U = {A
1
, …, A
n
};
i = 1;
• B2:
Nu U ⊆ (K - {A
i
})
F
+
thì K = K - {A
i
}.
i = i + 1;
Nu i > n thì sang B3. Ngc li, tip tc B2.
• B3:

+
= DGCBEA.
-Lp 7: (DF)
F
+
= DFCBEAG ⇒ K = DF.
•B3:
Khóa là K = DF.
Ph thuc hàm
Xác đnh tt c khóa ca lc đ
̇ Nhp: tp PTH F xác đnh trên lc đ R(U).
̇ Xut: tt c khóa ca R.
̇ Thut toán 7.3.2
• B1:
Xây dng 2
n
tp con ca U = {A
1
, …, A
n
};
S = {};
• B2:
Vi mi tp con X ⊆ U
Nu U ⊆ X
F
+
thì S = S ∪ {X}.
• B3:
∀X, Y ∈ S, nu X ⊂ Y thì S = S - {X}.

-BCNF).
Dng chun 1 (1)
̇ Lc đ quan h R đc gi là thuc dng chun 1 nu và
ch nu mi thuc tính ca R là thuc tính đn.
Go Vap9876543214Hanh chinh
Tan Binh,
Thu Duc
3334455555Nghien cuu
CacTrusoTrPhgMaPBTenPB
PHONGBAN
Thu Duc3334455555Nghien cuu
Go Vap9876543214Hanh chinh
Tan Binh3334455555Nghien cuu
TrusoTrPhgMaPBTenPB
PHONGBAN
Không thuc
dng chun 1
Thuc dng chun 1
Ph thuc hàm
Dng chun 1 (2)
̇ Nhn xét
•Mi lc đ quan h đu thuc dng chun 1.
•Dng chun 1 có th dn đn s trùng lp d liu. Do đó
gây ra các d thng v cp nht d liu.
Dng chun 2 theo khóa chính (1)
̇ Lc đ quan h R đc gi là thuc dng chun 2 nu mi thuc tính
không khóa ca R ph thuc đy đ vào khóa chính ca R.
̇ R(U), K ⊆ U là khóa chính ca R
•A ∈ U là thuc tính không khóa nu A ∉ K.
•X → Y là PTH đy đ nu ∀A ∈ X thì (X - {A}) → Y không đúng trên R.

•Mi lc đ quan h thuc dng chun 2 cng thuc
dng chun 1.
•Nu R ch có mt khóa K và card(K) = 1 thì R thuc dng
chun 2.
•Còn xut hin s trùng lp d liu. Do đó gây ra các d
thng v cp nht d liu.
FD2
FD1
TenPBMaPB TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
Thuc dng
chun 2
Ph thuc hàm
Dng chun 3 theo khóa chính (1)
̇ Lc đ quan h R đc gi là thuc dng chun 3 nu
• R thuc dng chun 2.
•Mi thuc tính không khóa ca R không ph thuc bt cu vào khóa chính
ca R.
̇ Cho R(U)
•X → Y là PTH bt cu nu ∃Z ⊆ U, Z không là khóa và cng không là tp
con ca khóa ca R mà X → Z và Z → Y đúng trên R.
̇ Ví d
FD2
FD3
FD1
TenPBMaPB TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
PTH bt cu
Dng chun 3 theo khóa chính (2)
̇ Nhn xét

̇ R1(ABCDE) có 2 khóa là A và BC.
̇ Nhn xét
• nh ngha tng quát cho phép kim tra dng chun 3 mà không cn
kim tra dng chun 2.
FD2
FD1
EDCBA
FD4
R1
Lc đ bên
thuc dng
chun 2,
nhng không
thuc dng
chun 3
FD5
Ph thuc hàm
Dng chun Boyce - Codd (1)
̇ Lc đ quan h R đc gi là thuc dng chun BC nu
PTH không hin nhiên X → Y đúng trên R thì X là siêu khóa
ca R.
̇ R11(ABCD)
FD2
FD5
FD1
DCBA
R11
Lc đ R11 thuc dng chun 3,nhng không thuc dng chun BC
Dng chun Boyce - Codd (2)
1ba2

2 lc đ trên thuc dng chun BC
Thit k Top-Down
̇ Các bc thc hin
•Thit k lc đ mc khái nim vi mô hình d liu cp
cao (EER).
•Chuyn lc đ khái nim thành tp hp các quan h.
•Vi mi quan h xác đnh tp PTH.
•Áp dng các quy tc chun hóa đ loi b các PTH b
phn và bt cu trong các quan h.
Ph thuc hàm
Phân rã lc đ quan h
̇ Lc đ quan h chung R(A
1
, …, A
n
)
•Tp hp tt c các thuc tính ca các thc th.
̇ Xác đnh tp PTH F trên R.
̇ Phân rã
•S dng các thut toán chun hóa đ tách R thành tp
các lc đ D = {R
1
, …, R
m
}.
̇ Yêu cu
•Bo toàn thuc tính.
•Các lc đ R
i
phi  dng chun 3 hoc Boyce-Codd.

R11
FD1
DCA
R111
FD5
DB
R112
Ph thuc hàm
Phân rã bo toàn PTH (2)
2
δα
3
3
γβ
2
2
βα
1
DCBAR11
2
δ
3
4
β
4
3
γ
2
2
β

, …, R
m
} ca
lc đ R đi vi tp PTH F sao cho các R
i
 dng
chun 3.
̇ Thut toán 7.4
•Nhp: R(U), U = {A
1
, …, A
n
} và tp PTH F.
•Xut: D = {R
1
, …, R
m
}, R
i
 dng chun 3.
• B1:
- Tìm ph ti thiu G ca F.
• B2:
-Vi mi X → A
j
∈ G, xây dng lc đ R
i
(U
i
), U

m+1
là U
m+1
.
• B4:
-Xut các lc đ R
i
.
Ví d phân rã bo toàn PTH (1)
̇ Cho
• R(ABCDEFG)
•F = {B → A, D → C, D → EB, DF → G}
̇ Tách v dng chun 3, bo toàn PTH
• B1:
-Ph ti thiu G = {B → A, D → C, D → B, D → E, DF → G}.
• B2:
• B3:
-Xut D = {R
1
, R
2
, R
3
}.
R(ABCD
EFG)
R
1
(BA) R(DC)
R