Bài giảng Cơ sở dữ liệu (Database): Chương 4

CHƯƠNG 4: Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu quan hệ

Nội dung

 Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF)

Nội dung

 Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF)

Một số khái niệm

 Phụ thuộc hàm  Luật của phụ thuộc hàm  Bao đóng của tập phụ thuộc hàm  Các loại khóa  Thuộc tính thuộc khóa

Phụ thuộc hàm

 Phụ thuộc hàm (functional dependency) được sử dụng như 1 độ đo để đánh giá chất lượng của tập sơ đồ quan hệ được thiết kế

 Các phụ thuộc hàm và các khóa được dùng

để xác định các chuẩn của quan hệ

 Phụ thuộc hàm là các ràng buộc được xác

định từ ngữ nghĩa và mối quan hệ bên trong của các thuộc tính

Phụ thuộc hàm

 Một tập thuộc tính X xác định tập thuộc tính Y nếu giá trị trong X cho phép xác định một giá trị duy nhất trong Y

 Y phụ thuộc hàm vào X  X Y là đúng nếu bất cứ hai bộ nào có cùng giá trị X thì

phải có cùng giá trị Y Nếu t1[X]=t2[X], thì t1[Y]=t2[Y] với mọi bộ r(R)  X  Y trong R xác định một ràng buộc cho tất cả các thể

hiện r(R)

 Phụ thuộc hàm chính là các ràng buộc trên dữ liệu

Ví dụ về phụ thuộc hàm

 Mã số bảo hiểm cho phép xác định tên nhân viên

 Mã dự án cho phép xác định tên dự án và địa điểm

dự án PNUMBER  {PNAME, PLOCATION}

 Mã số bảo hiểm của nhân viên SSN và mã dự án

xác định số giờ mà nhân viên phải làm trong dự án {SSN, PNUMBER}  HOURS

SSN  ENAME

Phụ thuộc hàm

 Một phụ thuộc hàm là một tính chất của các

thuộc tính trong lược đồ quan hệ R

 Một ràng buộc phải đúng cho tất cả các thể

hiện của lược đồ quan hệ r(R)

Các luật cho phụ thuộc hàm

 Với một tập phụ thuộc hàm F, ta có thể suy ra các phụ

thuộc hàm mới  Luật Armstrong

A1. (Phản xạ - Reflexive) Nếu Y là tập con của X thì X  Y A2. (Tăng trưởng - Augmentation) Nếu X  Y, thì XZ 

YZ (Chú ý: XZ có nghĩa là X U Z)

 A1, A2, A3 tạo một tập các luật đúng và đầy đủ

A3. (Bắc cầu - Transitive) Nếu X  Y và Y  Z, thì X  Z

Các luật cho phụ thuộc hàm

 Luật tách - Decomposition

 If X  YZ, then X  Y and X  Z

 Luật hợp

 If X  Y and X  Z, then X  YZ  Luật tựa bắc cầu - Psuedotransitivity  If X  Y and WY  Z, then WX  Z

 Bao đóng của F cho tập phụ thuộc hàm là tập F+

của các phụ thuộc hàm suy diễn từ F

Phụ thuộc hàm đầy đủ

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

dependency): Y  Z là phụ thuộc hàm đầy đủ nếu bỏ đi bất cứ một thuộc tính nào trong Y thì phụ thuộc hàm này không còn đúng  {SSN, PNUMBER}  HOURS là một phụ thuộc hàm đầy đủ bởi vì SSN  HOURS hoặc PNUMBER  HOURS không còn đúng

 {SSN, PNUMBER}  ENAME không phải là phụ thuộc hàm đầy đủ (gọi là phụ thuộc hàm bộ phận) bởi vì SSN  ENAME

Một số khái niệm khác

 Phụ thuộc hàm tầm thường (Trivial

functional dependency)  {Employee ID, Employee Address} →

{Employee Address} là phụ thuộc hàm tầm thường vì {Employee Address} → {Employee Address}.

Khóa

• Siêu khóa (Superkey)

K  R

• Khóa (Candidate Key)

Khóa chính

K  R Không tồn tại K’  K, sao cho K’  R (tối thiểu)

Khóa

Siêu khóa

• Khóa chính (Primary Key)

• Thuộc tính thuộc khóa (Prime attribute) là 1 thuộc tính

trong khóa chính K

Khóa - ví dụ

 Bảng employee (employeeID, name, job, và

departmentID)  Siêu khóa: {employeeID }, {employeeID, Name}, {employeeID, Name, job}, và {employeeID, Name, job, departmentID}.

 employeeID là một khóa

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

Định nghĩa:

X, Y là các thuộc tính của R: X  Y nằm trong F+  Y  X+ Algorithm: •X(0) := X •Repeat

X(i+1) := X(i)  Z, where Z is the set of attributes such that there exists YZ in F, and Y  X(i)

•Until X(i+1) := X(i) •Return X(i+1)

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

R = (A, B, C, D, E) F = {ABC, CDE, BD, EA} Tính A+ và B+: A+ := {A}

ABC và {A}  A+

:= {A, B, C} := {A, B, C, D} BD và {B}  A+ := {A, B, C, D, E}CDE và {C, D} 

A+ không thay đổi

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

B+ := {B}

:= {B, D} BD và {B}  B+ dừng giải thuật vì B+ không thay đổi nữa

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

 A+ là bao đóng của tập thuộc tính  Nếu A+ = R, thì A là một siêu khóa của quan

hệ R

Tính khóa dựa trên bao đóng tập thuộc tính

R = (A, B, C, D, E) F = {ABC, CDE, BD, EA} Liệt kê tất cả các khóa của R • A+ = {A, B, C, D, E}do đó AABCDE, thì

A là khóa của quan hệ R.

• Vì EA, nên EABCDE. (bắc cầu) • Vì CDE, nên CDABCDE. (bắc cầu) • Vì BD, nên BCCD, BCABCDE. (tăng

trưởng, bắc cầu)

Thuộc tính khóa - Ví dụ

 Cho lược đồ quan hệ R trên tập thuộc tính U={A, B, C, D} với các phụ thuộc hàm AB->C và B->D và BC->A.  Xác định thuộc tính khóa và thuộc tính không khóa

Nội dung

 Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF)

Các quy tắc cho thiết kế cơ sở dữ liệu quan hệ

 Thiết kế cơ sở dữ liệu quan hệ: cách nhóm các thuộc tính đề tạo thành các lược đồ quan hệ

 Các chuẩn 1NF 2NF 3NF BCNF

Dư thừa dữ liệu và các dị thường khi cập nhật

 Dư thừa dữ liệu  Các dị thường:

 Dị thường khi thêm bộ  Dị thường khi xóa bộ  Dị thường khi thay đổi

Ví dụ về các dị thường

Ví dụ quan hệ:

EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)

 Dị thường khi cập nhật

 Chuyển tên của dự án từ P1 từ “Billing” thành “Customer-

Accounting” phải cập nhật nhiều lần do 100 nhân viên đang làm trong dự án P1

 Dị thường khi thêm bộ

 Không thể thêm một dự án không có nhân viên.  Không thể thêm một nhân viên nếu nhân viên đó chưa được chỉ

định vào 1 dự án cụ thể.

Ví dụ về các dị thường

 Dị thường xóa bộ

 Khi xóa 1 dự án thì toàn bộ nhân viên làm cho dự án bị xóa  Khi xóa một nhân viên của dự án chi bao gồm 1 nhân viên thì kết

quả là dự án bị xóa theo

 Dư thừa dữ liệu  Không nhất quán

 Đảm bảo cơ sở dữ liệu thiết kế không chứa các dị

thường thêm, xóa và cập nhật

Giá trị Null trong các bộ

 Các quan hệ phải được thiết kế sao cho các bộ của

nó có giá trị NULL ít nhất có thể  Các thuộc tính thường có giá trị NULL có thể được đặt



trong 1 quan hệ riêng  Giá trị NULL xảy ra do: thuộc tính không hợp lệ giá trị của thuộc tính không biết (có thể tồn tại) giá trị của thuộc tính tồn tại nhưng không chưa xác định được

Bộ giả

 Thiết kế không tốt có thể sinh ra lỗi khi thực hiện

các thao tác kết nối

 Các quan hệ phải được thiết kế để đảm bảo không có bộ giả nào được sinh ra khi thực hiện kết nối tự nhiên

Nội dung

 Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF)

Chuẩn hóa

 Chuẩn hóa: Là một quá trình chia nhỏ quan hệ thiết kế không tốt thành tập các quan hệ nhỏ hơn  Các chuẩn: dùng khóa và các phụ thuộc hàm để

xác định dạng chuẩn của quan hệ  Chuẩn 2, chuẩn 3, chuẩn Boyce-Codd dựa vào khóa và

 Chuẩn 4 dựa vào khóa và các ràng buộc đa trị

các phụ thuộc hàm

Chuẩn 1

 Không cho phép các thuộc tính đa trị, thuộc

tính không nguyên tố

Bài tập: xác định quan hệ nào là 1NF

Chuẩn 2

 Một quan hệ R ở dạng chuẩn 2 nếu tất cả thuộc tính không khóa A trong R là phụ thuộc đầy đủ vào khóa chính

 R có thể chia thành các quan hệ ở dạng chuẩn 2 thông qua

quá trình chuẩn hóa dạng chuẩn 2

Chuẩn 2: Ví dụ

 FIRST (supplier_no, status, city, part_no,

quantity)

 Phụ thuộc hàm:

 (supplier_no, part_no) -> quantity  (supplier_no) -> status  (supplier_no) -> city  city -> status

Chuẩn 2

 Hai thuộc tính city và status chỉ phụ thuộc một phần vào khóa chính (supplier_no và part_no)

 INSERT: Không thể thêm một nhà cung cấp (supplier) ở một thành phố

nào đó nếu nhà cung cấp đó chưa tham gia cung cấp.

 DELETE: Nếu xóa hàng cuối cùng của một nhà cung cấp thì thông tin

về địa chỉ của nhà cung cấp bị xóa.

 UPDATE: Thông tin về thành phố (city) xuất hiện nhiều lần cho cùng

một nhà cung cấp->không đồng nhất khi thay đổi thông tin.

 Phân rã quan hệ thành 2 quan hệ dạng

chuẩn 2NF:

 SECOND (supplier_no, status, city)  SUPPLIER_PART (supplier_no, part_no,

quantity)

Chuẩn 3

 Định nghĩa

 Phụ thuộc hàm bắc cầu (Transitive functional

 Ví dụ

 SSN  DMGRSSN là một phụ thuộc hàm bắc cầu vì SSN  DNUMBER và DNUMBER  DMGRSSN  SSN  ENAME không phải là phụ thuộc hàm bắc cầu

dependency): Tập thuộc tính Z không phải là khóa và tồn tại X  Y và Y  Z

vì không tồn tại tập thuộc tính X sao cho SSN  X và X  ENAME

Chuẩn 3

 Một quan hệ R ở dạng chuẩn 3 nếu nó :

 ở dạng chuẩn 2 và  không có thuộc tính không khóa A trong R phụ

thuộc bắc cầu vào khóa chính

Chuân 3NF

 SECOND (supplier_no, status, city)  supplier_no -> status  supplier_no ->city  city -> status

 SUPPLIER_CITY (supplier_no, city)  CITY_STATUS (city, status)

Chuẩn Boyce-Codd (Boyce-Codd Normal Form)

 Một quan hệ R là ở dạng chuẩn Boyce-Codd nếu có một phụ thuộc hàm X  A trong R thì X là một khóa của R  Chuẩn sau luôn luôn mạnh hơn chuẩn trước:

 Tất cả các quan hệ ở dạng chuẩn 2 đều ở dạng chuẩn 1  Tất cả các quan hệ ở dạng chuẩn 3 đều ở dạng chuẩn 2  Tất cả các quan hệ ở dạng chuẩn Boyce-Codd đều ở dạng chuẩn

 Tuy nhiên có một số quan hệ ở dạng chuẩn 3 nhưng

 Mục đích là chuẩn hóa để quan hệ ở dạng chuẩn 3 hoặc

không ở dạng chuẩn Boyce-Codd.

dạng chuẩn Boyce-Codd