Bài giảng Cơ sở dữ liệu: Chương 6 - Nguyễn Việt Cường

Chương 66 Chương

ChuChuẩẩn hn hóóaa (Normalization) (Normalization)

1

1

Khái niệm “Chuẩn hóa”

• Chuẩn hóa ñược xem như là một công cụ

dùng trong các pp thiết kế CSDL – Chuẩn hóa ñược thực hiện sau khi thiết kế

CSDL dùng mô hình ER

• Là quá trình ñánh giá và chỉnh sửa cấu trúc

bảng ñể giảm thiểu dư thừa dữ liệu – Dư thừa dữ liệu có khả năng làm cho dữ liệu

không nhất quán (mâu thuẫn dữ liệu)

• Các dạng chuẩn 1NF, 2NF, 3NF, BCNF

2

BBảảngng chưa

chưa chuchuẩẩnn hhóóaa

• Bảng không ở dạng chuẩn 1 ( hay chưa chuẩn hóa) nếu nó chứa một hoặc nhiều nhóm giá trị lặp

• Nhóm giá trị lặp(Repeating group)

PROJ_NUM

PROJ_NAME

EMP_NUM

EMP_NAME

15

Evergreen

103, 101, 105

June E. Arbough, John G. News, Alice K. Johnson

18

Amber Wave

114, 118, 104

Annelise Jones, James J. Frommer, Anne K. Ramoras

Nhóm giá trị lặp

3

3

1 (1NF) DDạạngng chuchuẩẩnn 1 (1NF)

First • Lược ñồ quan hệ R ở dạng chuẩn 1 _ First

Form, nếu

Normal Form, Normal – Có khóa chính, và – Không có nhóm lặp lại

PROJ_NUM

EMP_NUM

PROJ_NAME

EMP_NAME

15

Evergreen

103

June E. Arbough

15

Evergreen

101

John G. News

15

Evergreen

105

Alice K. Johnson

18

Amber Wave

114

Annelise Jones

18

Amber Wave

118

James J. Frommer

4

4

18

Amber Wave

104

Anne K. Ramoras

Dạng chuẩn 2 (2NF)

• Lược ñồ quan hệ R(U,F) ở dạng chuẩn 2 khi :

– Bảng ở dạng chuẩn 1, và – Mọi thuộc tính không khóa ñều phụ thuộc

ñầy ñủ vào mọi khóa của R

• Nhận xét : Nếu R chỉ có các khóa gồm một thuộc tính

thì ñương nhiên R ở dạng chuẩn 2

Full functional dependency • Phụ thuộc hàm ñầy ñủ _ Full functional dependency – X(cid:1)A là phụ thuộc hàm ñầy ñủ ⇔ ∃ Y ⊂ X , Y(cid:1)A – Ngược lại : X(cid:1)A là phụ thuộc hàm không ñầy ñủ

5

Dạng chuẩn 2 (2NF)

• Lược ñồ sau không ñạt 2NF

Q(PROJ_NUM, EMP_NUM, PROJ_NAME, EMP_NAME) với tập F = { f1: PROJ_NUM, EMP_NUM (cid:1) PROJ_NAME, EMP_NAME f2: EMP_NUM (cid:1) EMP_NAME f3: PROJ_NUM (cid:1) PROJ_NAME }

Gọi : f1 là phụ thuộc hàm không ñầy ñủ

f2, f3 là phụ thuộc riêng phần_ partial FD

6

DDạạngng chuchuẩẩnn 3 3 (3NF

(3NF ))

• ðịnh nghĩa 1: Lược ñồ quan hệ R ở 3NF ñối với

tập phụ thuộc hàm F nếu: – R ở dạng 2NF, và – Mọi thuộc tính không khóa ñều không phụ thuộc

bắc cầu vào khóa chính của R

• ðịnh nghĩa 2: Lược ñồ quan hệ R ở 3NF ñối với

tập phụ thuộc hàm F nếu: – R ở dạng chuẩn 1, và – ∀ X->A với A ∉X thì X là 1 siêu khoá của R

7

7

hoặc A là 1 thuộc tính khoá

DDạạng chu

n 3 (3NF ) ng chuẩẩn 3 (3NF )

• Lược ñồ sau không ñạt 3NF Q( EMP_NUM, EMP_NAME, JOB_CLASS, CHG_HOUR )

với tập F = {

f1 : EMP_NUM (cid:1) EMP_NAME,JOB_CLASS,CHG_HOUR f2 : JOB_CLASS (cid:1) CHG_HOUR }

=> f2 là phụ thuộc hàm bắc cầu

(transitive dependency)

8

Dạng chuẩn BCNF

• BCNF ñược xem là trường hợp ñặc biệt của 3NF • Lược ñồ quan hệ R(U,F), ñược gọi là ñạt BCNF nếu mọi X →A ∈ F , A∉X thì X là một siêu khóa của R

• Lược ñồ quan hệ sau không ñạt BCNF R( Proj_name, Emp_name, Assign_hours )

với 2 phụ thuộc hàm f1: Proj_name, Emp_name (cid:1) Assign_hours f2: Assign_hours (cid:1) Emp_num

9

Dạng chuẩn _ nhận xét

• Các qui tắc xác ñịnh các dạng chuẩn ñều

dựa vào khóa

• Dạng chuẩn 2NF tốt hơn 1NF; 3NF tốt hơn

2NF, … – Mỗi dạng chuẩn ñưa ra các ñiều kiện bổ sung

cho dạng chuẩn thấp hơn nó

BCNF

3NF

2NF

1NF

10

Quá trình chuẩn hóa lược ñồ CSDL

• Thực hiện chuẩn hóa từng lược ñồ quan hệ

– Là quá trình biến ñổi dạng chuẩn của một lược ñồ quan hệ từ thấp nhất tới dạng chuẩn cao nhất

– Phân tách một LðQH dần dần thành nhiều LðQH mới dựa trên việc nhận diện các phụ thuộc hàm

• Dạng chuẩn của một lược ñồ CSDL bằng dạng

chuẩn của lược ñồ quan hệ cao nhất

11

Ví dụ về chuẩn hóa

Xét R(U,F) ñạt dạng chuẩn 1

R ( PROJ_NUM, EMP_NUM, PROJ_NAME, EMP_NAME, JOB_CLASS, CHG_HOUR, HOURS )

f1: PROJ_NUM, EMP_NUM (cid:1)(cid:1)(cid:1)(cid:1) PROJ_NAME, EMP_NAME,

JOB_CLASS, CHG_HOUR, HOURS

f2: PROJ_NUM (cid:1)(cid:1)(cid:1)(cid:1) PROJ_NAME f3: EMP_NUM (cid:1)(cid:1)(cid:1)(cid:1) EMP_NAME, JOB_CLASS, CHG_HOUR f4: JOB_CLASS (cid:1)(cid:1)(cid:1)(cid:1) CHG_HOUR

12

Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn 2

Loại bỏ các phụ thuộc hàm riêng phần và tạo thêm các Lược ñồ

quan hệ mới tương ứng

13

Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn 3 • Loại bỏ các phụ thuộc bắc cầu trong lñqh và tạo ra các

lñqh mới tương ứng

14

Lược ñồ CSDL kết quả

Sau quá trình chuẩn hóa Q, ta thu ñược một lược ñồ CSDL ñạt 3NF

15

Ví dụ về chuẩn hóa Chuyển ñổi sang dạng chuẩn BCNF

• Giả ñịnh, trong bảng ASSIGNMENT tồn tại 2 phụ thuộc

hàm f1: Proj_name, Emp_name (cid:1) Assign_hours f2: Assign_hours (cid:1) Emp_num

Hoặc

PROJ_NUM ASSIGN_HOURS EMP_NUM

PROJ_NUM

ASSIGN_HOURS

ASSIGN_HOURS EMP_NUM

16

16

ðạt BCNF

Chuẩn hóa và Thiết kế CSDL

• Chuẩn hóa ñược xem như một phương pháp thiết

kế CSDL ñộc lập – Có 2 cách tiếp cận : tổng hợp và phân rã

• Với phần lớn các mục tiêu thiết kế DB : 3NF là

dạng chuẩn cao cần ñạt tới trong quá trình chuẩn hóa – Dạng chuẩn cao nhất không phải luôn luôn là mục

tiêu cần ñạt tới – Giảm dạng chuẩn

17

Chuẩn hóa LDQH bằng Phân rã

• Quá trình chuẩn hóa LDQH là quá trình phân rã LDQH ban ñầu thành một số LDQH con – Các LDQH con ñạt dạng chuẩn cao hơn =>

giảm dư thừa dữ liệu

• Về mặt lý thuyết, quá trình phân rã phải ñảm

bảo 2 yêu cầu – Bảo toàn thông tin – Bảo toàn phụ thuộc hàm

• Thuật toán phân rã thành BC (hay 3NF) bảo toàn thông tin và bảo toàn phụ thuộc hàm

18

Phân rã bảo toàn thông tin

• Xét lược ñồ quan hệ Q và tập F, giả sử Q ñược phân

rã thành D= { Q1, Q2 } Nói rằng D là phép phân rã bảo toàn thông tin nếu với mọi r là quan hệ bất kỳ của Q ta có

r = r.Q1 |><| r.Q2

• Tính chất

Xét lược ñồ quan hệ Q và tập F, D= { Q1, Q2 } là phân rã bảo toàn thông tin nếu và chỉ nếu (Q1+ ∩Q2+ ) →Q2+ ∈ F+ hoặc (Q1+ ∩Q2+ ) →Q1+ ∈ F+

• Phép tách Q thành n lược ñồ quan hệ Q1, Q2,…Qn

bảo toàn thông tin , nếu ở các bước trung gian tách Q thành Qi và Qik bảo toàn thông tin

19

Phân rã bảo toàn thông tin

r

TENNCC DIACHI DONGIA SANPHAM

12 Nguyeãn Kieäm Gaïch oáng Hung 200

12 Nguyeãn Kieäm Gaïch theû Hung 250

+

+

40 Nguyeãn Oanh Gaïch oáng Hung 200

DIACHI r1 = r.Q1 TENNCC SANPHAM DONGIA r2 = r.Q2 TENNCC

12 Nguyeãn Kieäm Hung Gaïch oáng Hung 200

40 Nguyeãn Oanh Hung Gaïch theû Hung 250

SANPHAM DONGIA DIACHI r’ = r1|><|r2 TENNCC

12 Nguyeãn Kieäm Gaïch oáng Hung 200

12 Nguyeãn Kieäm Gaïch theû Hung 250

40 Nguyeãn Oanh Gaïch oáng Hung 200

20

Phân rã không bảo toàn thông tin

40 Nguyeãn Oanh Gaïch theû Hung 250

Phân rã bảo toàn phụ thuộc hàm

• Cho phân rã D = (Q1, Q2,…, Qk) của lược ñồ Q

và tập pth F, với hình chiếu của F trên Qi ký hiệu ΠQi(F) sao cho ΠQi(F)={ X→Y | X → Y ∈ F+ và XY ⊆ Qi} Ta nói phân rã D bảo toàn tập phụ thuộc hàm F nếu F ≡ ∪ ΠQi(F) ⇔ F+ = (∪ ΠQi(F))+ với i=1..k

21

Ý nghĩa của phân rã bảo toàn pth

• Ví dụ

22

Phân rã không bảo toàn phụ thuộc hàm

Thuật toán phân rã thành 3NF bảo toàn thông tin , bảo toàn phụ thuộc hàm

• B1 : Tìm phủ tối thiểu Ftt của F • B2 :

– Nếu có những thuộc tính của Q không nằm trong một phụ thuộc nào của Ftt - dù ở vế phải hay vế trái của F thì chúng tạo thành một lược ñồ.

– Nếu có một phụ thuộc hàm nào của Ftt mà liên quan ñến tất cả các thuộc tính của Q thì kết quả phân rã chính là Q ( Q không thể phân rã)

– Cứ mỗi phụ thuộc hàm X →A ∈Ftt thì XA là một lược

ñồ cần tìm

– Nếu có một lược ñồ con chứa khóa K của Q thì kết thúc thuật toán .Ngược lại tạo một lược ñồ con K

23

Thuật toán phân rã thành 3NF bảo toàn thông tin , bảo toàn phụ thuộc hàm

Ví dụ: cho lược ñồ

Q(CTHRSG),F={C→T,HR→C,TH→R,CS→G,HS→R}

Hãy phân rã Q thành các lược ñồ con ñạt dạng chuẩn 3 vừa bảo

toàn thông tin vừa bảo toàn phụ thuộc hàm?

Giải: • F = Ftt = {C→T,HR→C,TH→R,CS→G,HS→R} là phủ tối thiểu. • Áp dụng thuật toán trên Q ñược phân rã thành các lược ñồ con

Q1(CT) Q2(HRC) Q3(THR) Q4(CSG) Q5(HSR)

• Khóa của Q là HS • ⇒Q1,Q2,Q3,Q4,Q5 chính la ket qua phân rã

24

Tóm tắt

Tồn tại nhiều phụ thuộc hàm trong một LðQH

Dư thừa dữ liệu

Các dạng chuẩn 1NF, 2NF, 3NF, BCNF

Chuẩn hóa LðQH

Chuẩn hóa bằng Phân rã

25