Bài giảng Cơ sở dữ liệu: Chương 3

CHƯƠNG 3 PHỤ THUỘC HÀM & CHUẨN HÓA DỮ LIỆU

GV Th.S. Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế đối ngoại

Nội dung

• Khái niệm phụ thuộc hàm • Hệ tiên đề Amstrong • Bao đóng của tập phụ thuộc hàm • Bao đóng của tập thuộc tính • Tìm khóa • Định nghĩa chuẩn hóa • Các dạng chuẩn hóa GV Thiều Quang Trung

Dư thừa dữ liệu (Data redundancy)

• Mục đích của thiết kế CSDL là gom các thuộc tính thành các quan hệ sao cho giảm thiểu dư thừa dữ liệu

• Hậu quả của dư thừa dữ liệu: – Lãng phí không gian đĩa – Các bất thường khi cập nhật

– Bất thường khi thêm vào – Bất thường khi xóa bỏ – Bất thường khi sửa đổi

GV Thiều Quang Trung

• Ba loại bất thường:

Phụ thuộc hàm là gì ? (Functional Dependency)

• Phụ thuộc hàm mô tả mối liên hệ giữa các

thuộc tính

• Dựa vào phụ thuộc hàm để thiết kế lại CSDL,

GV Thiều Quang Trung

loại bỏ các dư thừa dữ liệu

Phụ thuộc hàm (Functional Dependency)

trên R, X và Y là 2 tập thuộc tính con.

• Cho lược đồ quan hệ R(U), r là 1 quan hệ bất kỳ

GV Thiều Quang Trung

• Định nghĩa: Phụ thuộc hàm (FD) f: X  Y trên lược đồ quan hệ R nếu và chỉ nếu mỗi giá trị X trong r có quan hệ chính xác với 1 giá trị Y trong r. Nghĩa là bất kể khi nào 2 bộ của r có cùng giá trị X thì cũng có cùng giá trị Y

Phụ thuộc hàm (Functional Dependency)

• Xét lược đồ quan hệ gồm n thuộc tính

– R(U), U={A1, A2,…, An}

• Phụ thuộc hàm (FD) giữa hai tập thuộc tính X, Y U

– Ký hiệu: X  Y. r  R,  t1, t2  r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. – X là vế trái (determinant) và Y là vế phải (dependent) của

FD.

r(R)

r không thỏa A  B, nhưng thỏa B  A

GV Thiều Quang Trung

Phụ thuộc hàm (Functional Dependency -FD)

• Phụ thuộc hàm là 1 đặc điểm ngữ nghĩa của các thuộc tính, được xem là 1 ràng buộc giữa các thuộc tính.

GV Thiều Quang Trung

• Ví dụ: Một nhân viên chỉ có 1 tiền lương nhưng nhiều nhân viên có thể có cùng 1 mức lương Emp_ID  Salary Salary -/-> Emp_ID

Phụ thuộc hàm (Functional Dependency -FD)

• Nếu X là 1 khóa dự tuyển (candidate key) thì tất cả các thuộc tính Y của lược đồ R sẽ phải phụ thuộc hàm vào X

primary key nên:

• Ví dụ: trong lược đồ PROFESSOR có ProfId là

dữ liệu.

GV Thiều Quang Trung

ProfId  Name, Qualification • Có một số FD trong lược đồ sẽ gây ra dư thừa

Ví dụ FD và dư thừa dữ liệu

PERSON(SSN, Name, Address,Hobby) với quy tắc là 1 người có thể có nhiều sở thích – SSN,Hobby  SSN, Name, Address,Hobby

• Bất thường xảy ra khi một người có nhiều sở thích

• Xét lược đồ:

GV Thiều Quang Trung

thay đổi địa chỉ

Giải thuật kiểm tra phụ thuộc hàm

f:X Y. Kiểm tra xem r thỏa mãn f hay không?

• Bài toán: cho quan hệ r và 1 phụ thuộc hàm

– Sắp thứ tự các bộ trong r theo các thuộc tính của

– If mỗi tập các bộ có cùng giá trị X thì có cùng giá

trị Y then

• Satisfies = true

– Else

• Satisfies = false

GV Thiều Quang Trung

• Function Satisfies(r,f:X Y)

Tập phụ thuộc hàm

• Gọi F là 1 tập phụ thuộc hàm trên R nếu mọi phụ thuộc hàm trong F đều là phụ thuộc hàm trên R

GV Thiều Quang Trung

• Phụ thuộc hàm tầm thường ( trivial FD) hay phụ thuộc hàm hiển nhiên x Y nếu Y  X • Số tập con có thể có của R = {A1,A2,...,An} là 2n. Ứng với mỗi tập con sẽ có tối đa 2n. Số FD tối đa có thể có trong 1 lược đồ là 22n.

Tập phụ thuộc hàm

toàn (integrity constraint), vì vậy DBMS cần phải quản lý các FD.

• FD được dùng để thể hiện các ràng buộc bảo

GV Thiều Quang Trung

• Với 1 tập S chứa toàn bộ các FD của 1 lược đồ, có cách nào tìm ra 1 tập T  S sao cho mọi FD của S đều ngầm suy từ các FD của T. Khi đó, DBMS chỉ quản lý các FD của T, các FD trong S sẽ được quản lý một cách tự động.

Hệ tiên đề Amstrong

GV Thiều Quang Trung

• Phụ thuộc hàm XY được suy diễn luận lý từ F nếu mọi quan hệ thỏa mãn mọi phụ thuộc hàm trong F thì cũng thỏa mãn XY – Ký hiệu F|=XY – F bao hàm (implies) XY – XY được suy diễn theo quan hệ từ F

Hệ tiên đề Amstrong

GV Thiều Quang Trung

• Quy tắc suy diễn (inference rule): nếu 1 quan hệ thỏa mãn 1 số phụ thuộc hàm nào đó thì quan hệ này cũng thỏa mãn 1 số phụ thuộc hàm khác

Hệ tiên đề Amstrong

– F1. Phản xạ (reflexivity): YX  XY – F2. Gia tăng (augmentation): XY 

XZ YZ

– F3. Bắc cầu (transitivity): XY và YZ

 X Z

GV Thiều Quang Trung

• Các tiên đề suy diễn:

Hệ tiên đề Amstrong

• F4. Hợp (additivity): XY và XZ  X YZ • F5. Chiếu (projectivity): XYZ  X Y • F6. Bắc cầu giả (pseudotransitivity): XY và

GV Thiều Quang Trung

YZW  XZ W

Bao đóng của tập phụ thuộc hàm

– F và – Tất cả các phục thuộc hàm được suy diễn từ F.

• Bao đóng (closure) của tập phụ thuộc hàm F là 1 tập phụ thuộc hàm nhỏ nhất chứa F sao cho không thể áp dụng hệ tiên đề Amstrong trên tập này để tạo ra 1 phụ thuộc hàm khác không có trong tập hợp này • Ký hiệu F+, gồm:

GV Thiều Quang Trung

• F gọi là đầy đủ nếu F = F+.

Các tính chất của bao đóng của tập phụ thuộc hàm

1. Tính phản xạ: với mọi tập phụ thuộc hàm F+

ta luôn có F  F+

2. Tính đơn điệu: nếu F  G thì F+  G+ 3. Tính lũy đẳng: với mọi tập phụ thuộc hàm F ta

GV Thiều Quang Trung

luôn có (F+)+ = F+.

Hệ tiên đề Amstrong

• Hệ tiên đề Amstrong là đúng đắn (sound)  các phụ thuộc hàm suy diễn từ F (tập phụ thuộc hàm trên r) theo hệ tiên đề Amstrong cũng là một phụ thuộc hàm trên r • Hệ tiên đề Amstrong là toàn vẹn

GV Thiều Quang Trung

(completeness)  bảo đảm rằng f  F+ nếu và chỉ nếu f là 1 FD được suy diễn

Phụ thuộc hàm tương đương

• Nếu F và G là 2 tập FD. F suy diễn G ( F

entails G) nếu F suy diễn được tất cả các FD có trong G.

và G suy diễn F

GV Thiều Quang Trung

• F và G là tương đương nhau nếu F suy diễn G

Kiểm tra các tập FD tương đương

false nếu ngược lại

if G does not entail f then return false

GV Thiều Quang Trung

• Input: F,G – các tập FD • Output: true nếu F tương đương G, For each f F do For each g  G do Return true

Ví dụ kiểm tra tập F tương đương

• Hãy khảo sát 2 tập FD sau: – F={ ACB, AC, DA} – G={AB, AC, DA, DB}

GV Thiều Quang Trung

F và G có tương đương nhau không??? Từ AC + Tiên đề F2  AAC (1) Từ (1)+ ACB + tiên đề F3  AB Từ DA + AB + tiên đề F3  D B F suy diễn G Tương tự khi xét G suy diễn F

Bao đóng của tập thuộc tính

• Làm thế nào để biết một FD X  Y được suy diễn

từ tập F cho trước ?

• Bao đóng của tập thuộc tính X đối với F, ký hiệu X+,

là – Tập các thuộc tính phụ thuộc hàm vào X. – X+ = {A  U | X  A  F+}

– X  Y  F+  Y  X+. – Nếu K là khóa của R thì K+ = U.

GV Thiều Quang Trung

• Nhận xét

Thuật toán tìm X+

– Bước 1: X+ = X; – Bước 2: Nếu tồn tại Y  Z  F và Y  X+ thì

X+ := X+  Z;

và tiếp tục bước 2. Ngược lại qua bước 3.

– Bước 3: Xuất X+.

GV Thiều Quang Trung

• Nhập: U, F và X  U • Xuất: X+ • Thuật toán:

Ví dụ thuật toán tìm X+

– F = {AB  C, BC  D, D  EG}. – X = BD. • Tính X+:

– X+ = BD. – Lặp 1:

• Tìm các FD có vế trái là tập con của X+ = BD – D  EG, thêm EG vào X+ ta được X+ = BDEG.

– Lặp 2:

• Tìm các FD có vế trái là tập con của X+ = BDEG

– Không có FD nào.

GV Thiều Quang Trung

– Vậy X+ = BDEG.

• Ví dụ 1, cho:

Kiểm tra phụ thuộc hàm suy diễn

– Cho F = {AB  C, A  D, D  E, AC  B} – Hai phụ thuộc hàm AB  E và D  C có được suy

diễn từ F hay không?

+ XF

Được suy diễn từ F

ABCDE

GV Thiều Quang Trung

• Dựa vào tính chất: X  Y  F+  Y  X+. • Ví dụ:

Giải thuật tìm khóa của lược đồ quan hệ

TN=U- fF right(f)

GV Thiều Quang Trung

• Nhập: R(U) và tập phụ thuộc hàm F • Xuất: tập hợp K bao gồm tất cả khóa của R • Tập thuộc tính nguồn (TN) chứa tất cả các thuộc tính xuất hiện ở vế trái và không xuất hiện ở vế phải của các phụ thuộc hàm và các thuộc tính không xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm

Giải thuật tìm khóa của lược đồ quan hệ

• Tập thuộc tính đích (TD) chứa tất cả các thuộc

tính có xuất hiện ở vế phải và không xuất hiện ở vế trái của các phụ thuộc hàm

GV Thiều Quang Trung

TD= fF right(f) - fF left(f) • Tập thuộc tính trung gian (TG) chứa tất cả các thuộc tính xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm

Thuật toán tìm tất cả khóa

tính trung gian TG

• Bước 1: tạo tập thuộc tính nguồn TN. Tập thuộc

• Bước 2: if TG =  then lược đồ quan hệ chỉ có 1

• Bước 3: tìm tất cả các tập con Xi của tập trung

gian TG

GV Thiều Quang Trung

khóa K K=TN Kết thúc Ngược lại qua bước 3

Thuật toán tìm tất cả khóa (tt)

if (TN  Xi)+ = Q+ then Si = TN  Xi

• Bước 4: tìm các siêu khóa Si bằng cách  Xi • Bước 5: tìm khóa bằng cách loại bỏ các siêu khóa

if Si Sj then Loại Sj ra khỏi tập siêu khóa S S còn lại chính là tập khóa cần tìm

GV Thiều Quang Trung

không tối thiểu  Si, Sj  S

Ví dụ tìm khóa

• Cho R(A,B,C,D,E,F) và F={DB, AC,

ADE, CF}. Tìm tất cả các khóa của R

• B1: TN={AD}, TG={C} • Xi là các tập con của TG

Khóa Xi Xi  TN (Xi  TN)+

Siêu khóa

ADBCEF=R+ AD AD  AD

GV Thiều Quang Trung

C ADC ADBCEF=R+ ADC

Ví dụ tìm khóa

EC}. Tìm khóa của R?

• Cho R(A,B,C,D,E,F) và F={AD, CAF, AB

Khóa

Xi  TN

(Xi  TN)+

Siêu khóa

 B

C CB

ABCDEF=R+

A AB

ABCDEF=R+

AC ABC

ABCDEF=R+

ABC

GV Thiều Quang Trung

• TN={B} , TG={AC} • Khóa của R là {AB} và {BC}

Chuẩn hóa

• Mục đích: loại bỏ các bất thường của 1 quan

hệ để có được các quan hệ có cấu trúc tốt hơn, nhỏ hơn

relation): là quan hệ có sự dư thừa dữ liệu là tối thiểu và cho phép người dùng thêm, sửa, xóa mà không gây ra mâu thuẩn dữ liệu

GV Thiều Quang Trung

• Quan hệ có cấu trúc tốt (well-structured

Chuẩn hóa

• Quá trình chuẩn hóa được thực hiện qua nhiều bước. Mỗi bước tương ứng một dạng chuẩn

– Dạng chuẩn 1(1NF – first normal form) – Dạng chuẩn 2(2NF- second normal form) – Dạng chuẩn 3(3NF – third normal form) – Dạng chuẩn BCNF – Boyce Codd

GV Thiều Quang Trung

• Các dạng chuẩn:

Bảng chưa chuẩn hóa

• 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 lặp lại hoặc các giá trị phức hợp

nhiều hàng có thể có cùng chung một thuộc tính

GV Thiều Quang Trung

• Nhóm lặp lại (Repeating group): một nhóm

Ví dụ bảng chưa chuẩn hóa

Repeating group GV Thiều Quang Trung

Dạng chuẩn 1 (1NF – first normal form)

– Có khóa chính – Không có nhóm lặp lại

• Bảng ở dạng chuẩn 1 nếu

• Bảng ở 1NF nếu mọi thuộc tính của R đều

GV Thiều Quang Trung

chứa các giá trị nguyên tố (không có thuộc tính đa trị)

Biến đổi về dạng chuẩn 1

– Loại bỏ các nhóm lặp lại – Xác định khóa chính của bảng – Xác định tất cả các phụ thuộc (dependencies)

trong bảng

• Quá trình chuẩn hóa gồm 3 bước:

GV Thiều Quang Trung

• Lược đồ phụ thuộc (dependency diagram): để giúp mô tả tất cả các phụ thuộc trong bảng

Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes)

Quan hệ Employee_Course

Name

Dept_Name Salary

Emp_I D

Course_ Title

Date_ Completed

100 M.Simpson Marketing

48000 SPSS

Surveys

6/19/2001 12/12/2002

140

A.Beeton

Acounting

52000 Tax Acc

12/8/2003

110 C.Lureco

Info System

43000 SPSS

C++

1/12/2003 2/6/2004

190

L.Davis

Finance

55000

150

S.Martin

Marketing

42000 SPSS Java

6/16/2002 5/7/2004

GV Thiều Quang Trung

Ví dụ quan hệ có thuộc tính đa trị (multivalued attributes)

Name

Dept_Name Salary Course_

Emp_ ID

Title

Date_ Completed

100 M.Simpson Marketing

48000 SPSS

6/19/2001

100 M.Simpson Marketing

48000 Surveys

12/12/2002

140 A.Beeton

Acounting

52000 Tax Acc

12/8/2003

110 C.Lureco

Info System

43000 SPSS

1/12/2003

110 C.Lureco

Info System

43000 C++

2/6/2004

190

L.Davis

Finance

55000

150 S.Martin

Marketing

42000 SPSS

6/16/2002

150 S.Martin

Marketing

42000 Java

5/7/2004

GV Thiều Quang Trung

 Dạng chuẩn 1  Khóa là EmpID + CourseTitle

A Dependency Diagram: First Normal Form (1NF)

GV Thiều Quang Trung

Dạng chuẩn 1 (1NF – Normal First Form)

– Dạng chuẩn 1 vẫn có thể có các bất thường khi cập

nhật

• Nhận xét:

• Ví dụ: trong lược đồ Employee_Course, sẽ có

 vi phạm quy luật bảo toàn thực thể

– Thay đổi tên phòng phải thay đổi hàng loạt thông

tin này cho tất cả các nhân viên của phòng đó – Xóa 1 course mà chỉ có 1 nhân viên học, thông tin

course sẽ bị xóa theo

GV Thiều Quang Trung

các bất thường sau: – Thêm 1 nhân viên mới chưa tham gia khóa học nào

Phụ thuộc hàm đầy đủ (Full functional dependency)

Y  X để cho YA

• XA là phụ thuộc hàm đầy đủ nếu không tồn tại

– Khóa là Emp_ID,Course – Emp_ID, Course  Grade là phụ thuộc hàm đầy đủ – Emp_ID Name, Dept_Name là phụ thuộc hàm

không đầy đủ

Emp_ID, Course Name, Dept_Name Emp_ID Name, Dept_Name Emp_ID  {Emp_ID, Course }

• Ví dụ: quan hệ Employee_Course

• Phụ thuộc hàm bộ phận (partial FD) XA, tồn

GV Thiều Quang Trung

tại Y  X sao cho YA

Dạng chuẩn 2 (2NF – second Normal Form)

thuộc hàm F nếu: – R ở dạng chuẩn 1 – Mọi thuộc tính không khóa đều phụ thuộc đầy đủ

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

• Lược đồ quan hệ R ở dạng 2NF đối với tập phụ

• Nếu quan hệ R chỉ có các khóa đơn thì đương

GV Thiều Quang Trung

nhiên quan hệ này ở dạng chuẩn 2

Biến đổi thành 2NF

• Loại bỏ các phụ thuộc hàm bộ phận và tạo thêm các quan hệ mới tương ứng với các phụ thuộc hàm bộ phận

GV Thiều Quang Trung

Second Normal Form (2NF) Conversion Results

GV Thiều Quang Trung

Dạng chuẩn 2

cập nhật

• Quan hệ ở 2NF vẫn có thể có các bất thường khi

– Khi sửa đổi lương giờ (CHG_HOUR) của 1 loại công

việc mà có nhiều nhân viên đang cùng làm

– Khi xoá 1 nhân viên đang làm công việc mà chỉ có

nhân viên đó làm thì sẽ làm mất luôn thông tin về công việc đó

GV Thiều Quang Trung

• Ví dụ: xét quan hệ EMPLOYEE đã ở chuẩn 2NF – Khi thêm 1 loại công việc mới mà công việc này chưa có nhân viên nào làm sẽ vi phạm ràng buộc khoá chính

Phụ thuộc bắc cầu (Transitive dependency)

• XA được gọi là phụ thuộc bắc cầu nếu tồn tại

Y để cho

XY, YA, Y-/->X

GV Thiều Quang Trung

Và A  XY • Nguyên nhân gây ra các bất thường khi cập nhật bảng 2NF là do có các thuộc tính không khóa phụ thuộc bắc cầu vào khóa của quan hệ

Dạng chuẩn 3 (3NF – third normal form)

tập phụ thuộc hàm F nếu: – R ở dạng 2NF – 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 1: Lược đồ quan hệ R ở 3NF đối với

GV Thiều Quang Trung

• Đị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à mọi phụ thuộc hàm X->A với A X thì X là 1 siêu khoá của R hoặc A là 1 thuộc tính khoá

Biến đổi thành dạng chuẩn 3

GV Thiều Quang Trung

• Loại bỏ các phụ thuộc bắc cầu trong quan hệ và tạo ra các quan hệ mới tương ứng với các phụ thuộc bắc cầu

Third Normal Form (3NF) Conversion Results

GV Thiều Quang Trung

Dạng chuẩn 3

cập nhật

• Quan hệ ở 3NF vẫn có thể có các bất thường khi

• Ví dụ: xét lược đồ quan hệ

EMPLOYEE_TEACHER(EmpId,Course,Teacher)

EmpId, Course  Teacher Teacher Course

Có 2 phụ thuộc hàm:  Thuộc dạng 3NF, bất thường xảy ra teacher thay

GV Thiều Quang Trung

đổi môn dạy

Dạng chuẩn Boyce-Codd (BCNF)

• Một quan hệ ở dạng BCNF nếu mọi vế trái (xác định/determinant) của F đều là khóa dự tuyển (candidate key)

thuộc tính, F là tập phụ thuộc hàm. Lược đồ ở dạng chuẩn BCNF nếu với mọi phụ thuộc hàm X Y  F, nếu 1 trong 2 điều kiện sau là đúng: – Y  X ( phụ thuộc hàm tầm thường) – X là siêu khóa của R

GV Thiều Quang Trung

• Cho 1 lược đồ quan hệ R(U,F) với U là tập

Ví dụ một quan hệ thuộc dạng chuẩn 3NF nhưng chưa là dạng chuẩn BCNF

GV Thiều Quang Trung

Chuyển đổi thành BCNF

• Một quan hệ ở BCNF thì nó cũng ở dạng 3NF • Có thể biến đổi trực tiếp bảng từ 1NF thành

GV Thiều Quang Trung

BCNF, mà không cần phải qua các bước chuẩn hóa 2NF, 3NF – Loại bỏ các vế trái không phải là siêu khoá – Tạo các quan hệ mới tương ứng với các vế trái sao cho vế trái trở thành siêu khoá của quan hệ mới

Ví dụ chuyển đổi sang dạng chuẩn BCNF

• Xét U ={ABCD}, F ={AB CD, AC BD} có 2

khóa: AB và AC

nên lược đồ ở dạng BCNF

GV Thiều Quang Trung

• Vì 2 phụ thuộc hàm này đều có vế trái là khóa,

Ví dụ chuyển đổi sang dạng chuẩn BCNF

GV Thiều Quang Trung

Ví dụ chuyển đổi sang dạng chuẩn BCNF

GV Thiều Quang Trung

So sánh 3NF và BCNF

• BCNF được xem là trường hợp đặc biệt của

3NF

GV Thiều Quang Trung

• Với quan hệ có nhiều candidate key phức hợp thì BCNF sẽ tránh được hai bất thường có thể xảy ra ở 3NF – 1 phần của khóa xác định 1 phần của khóa khác – Cột không khóa xác định 1 phần của khóa

GV Thiều Quang Trung