Bài giảng Chương 6: Phụ thuộc hàm

Nội dung

 Dư thừa dữ liệu  Phụ thuộc hàm

 Giải thuật kiểm tra 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

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 giảm thiểu dư thừa dữ liệu

 Hậu quả của dư thừa dữ liệu:

 Lãng phí không gian đĩa

 Các bất thường (anomalies) khi cập nhật

Bất thường dữ liệu (Data redundancy)

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

 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

Ví dụ về bất thường dữ liệu

SSN

Name

Address

Hobby

111111111 111111111 555666777 555666777 987654321

John Doe John Doe Mary Doe Mary Doe Bart Simpson

123 Main St. 123 Main St. 7 Lake Dr. 7 Lake Dr. Fox 5 TV

Stamps Coins Hiking Skating Acting

 Khóa chính của bảng PERSON?

 SSN + Hobby

 Thông tin cá nhân bị trùng lặp

Ví dụ về bất thường dữ liệu

 Nếu John thay đổi chỗ ở  update anomaly  Nếu bổ sung thêm người mới nhưng chưa biết sở thích  không thể tạo bản ghi mới được  insertion anomaly

 Nếu Bart Simpson chỉ có 1 sở thích  xóa sở thích Acting như thế nào  Delete anomaly

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

 Phụ thuộc hàm mô tả mối liên hệ giữa các thuộc

tính trong 1 bảng

 Dựa vào phụ thuộc hàm để tinh chỉnh CSDL, loại

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

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

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

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

 Phụ thuộc hàm (FD) f: X  Y trên lược đồ quan hệ R nếu và chỉ nếu mỗi giá trị X trong r có quan hệ chính xác với 1 giá trị Y trong r.

t1, t2  r(R): t1[X] = t2[X]  t1[Y]= t2[Y]

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

 X là vế trái, ký hiệu left(f) hay còn gọi là

determinant

 Y là vế phải, ký hiệu right(f) hay còn gọi là

dependent

Ví dụ phụ thuộc hàm

 Cho quan hệ như hình vẽ, hãy xác định các FD?

 AB  C

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

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

Y. Kiểm tra xem r thỏa mãn f hay không?

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

 Sắp thứ tự các bộ trong r theo các thuộc tính của X  If mỗi tập các bộ có cùng giá trị X thì có cùng giá trị

Y then  Satisfies = true

 Else

 Satisfies = false

Functional Dependencies

 Các phụ thuộc hàm của quan hệ R là:

 A  B  A  D

B,C  E,F

 Các bộ của quan hệ r(R) có vi phạm các FD này không?

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.

 Phụ thuộc hàm được xác định dựa vào quy tắc

nghiệp vụ

Ví dụ: Phụ thuộc hàm

 Một nhân viên chỉ có 1 mức 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)

 Từ quy tắc bảo toàn thực thể  nếu X là 1

candidate key thì tất cả các thuộc tính Y của lược đồ R sẽ phải phụ thuộc hàm vào X

 PROFESSOR(ProfId, Name, Qualification)

ProfId  Name, Qualification

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

 Có 1 số FD trong lược đồ gây ra dư thừa dữ liệu.

 Vd: Xét lược đồ PERSON(SSN, Name, Address,Hobby)

 Từ khóa chính xác định được FD:

SSN,Hobby  SSN, Name, Address,Hobby

 Từ quy tắc nghiệp vụ, xác định được FD:

Emp_ID  Name, Dept_Name, Salary

 Bất thường xảy ra khi một người có nhiều sở thích thay

đổi địa chỉ

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

SSN

Name

Address

Hobby

111111111 111111111 555666777 555666777 987654321

John Doe John Doe Mary Doe Mary Doe Bart Simpson

123 Main St. 123 Main St. 7 Lake Dr. 7 Lake Dr. Fox 5 TV

Stamps Coins Hiking Skating Acting

Lược đồ phụ thuộc hàm

 Lược đồ phụ thuộc hàm để biểu diễn phụ thuộc

hàm

 Vd: Emp_ID  Name, Dept_Name, Salary

Lược đồ phụ thuộc hàm

 Emp_ID  Name, Dept_Name, Salary  Emp_ID, Course_Title  Date_Completed

Phụ thuộc hàm tầm thường

 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  Ví dụ: Name, Address Name

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  Số tập con có thể có của R = {A1,A2,...,An} là 2n.  Ứng với 2 tập con sẽ tạo thành 1 FD  Số FD có

thể có được là 1 chỉnh hợp lặp chập 2 của 2n phần tử. Số FD tối đa có thể có (2n)2=22n.

Tập phụ thuộc hàm

 FD được dùng để thể hiện các ràng buộc bảo

toàn (integrity constraint), vì vậy DBMS cần phải quản lý các FD.

 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 chỉ quản lý các FD của T, các FD trong S sẽ được quản lý một cách tự động.

Hệ tiên đề Amstrong

 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 thì 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

 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 đó thì quan hệ này cũng thỏa mãn 1 số phụ thuộc hàm khác

Hệ tiên đề Amstrong

 F1. Phả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  F4. Hợp (additivity): XY và XZ  X YZ  F5. Chiếu (projectivity): XYZ  X Y  F6. Bắc cầu giả (pseudotransitivity): XY và YZW  XZ W

Ví dụ

 Dùng hệ tiên đề Amstrong để chứng minh

Nếu X  YZ và Z  W, thì X  YZW

 Chứng minh:

 Từ Z  W  YZZ  YZW (luật gia tăng) hay YZ 

YZW

 Từ X YZ và YZ  YZW  X  YZW (luật bắc cầu)

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

 Bao đóng (closure) của tập phụ thuộc hàm F là 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+

F+ là 1 tập hợp các FD được suy diễn từ 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

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

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

Cho F={AB C, CB} trên r(ABC) F+={AA, ABA, ACA, ABCA,

BB, ABB, BCB, ABCB, CC, ACC, BCC, ABCC, ABAB, ABCAB, ACAC, ABCAC, BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC, CB,CBC, ACB, ACAB }

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 (completeness)  bảo đảm rằng f  F+ nếu và chỉ 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 cả các FD có trong G.

 F và G là tương đương nhau nếu F suy diễn G và G

suy diễn F

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

 Input: F,G – các tập FD  Output: true nếu F tương đương G,

false nếu ngược lại

For each f F do

if G does not entail f then return false

For each g  G do

if F does not entail g then return false

Return true

Ví dụ

 Hãy khảo sát 2 tập FD sau:  F={ ACB, AC, DA}  G={AB, AC, DA, DB}

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

+ = {A|XA  F+}

 Bao đóng của tập thuộc tính X dựa trên một tập phụ thuộc hàm F (closure of X under F) là 1 tập thuộc tính sao cho: 𝑋𝐹

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm

 Input: tập thuộc tính X và tập phụ thuộc hàm F  Output: bao đóng của X dựa trên F Procedure Closure(X,F,Closure_X) Begin

Closure_X:=X; repeat Old_X := Closure_X; for mỗi WZ trong F do if W  Closure_X then

Closure_X :=Closure_X  Z;

until Closure_X = Old_X;

End;

Ví dụ tìm bao đóng của X

 Cho R(A,B,C,D,E,F) và tập F={f1:DB, f2: AC, f3:

ADE, f4:CF} F: F ={A}

F = {AC}; Từ f4  A+

F = {ACF}

 Tìm A+  A+  Duyệt F lần 1: Từ f2  A+  Duyệt F lần 2: A+

F không thay đổi

F = {ACF}

A+  Tìm {AD}+

F ???

Kiểm tra thành viên trong F+  Để xác định F ⊨ XY, cần kiểm tra X Y  F+  Giải thuật:

 Input: phụ thuộc hàm XY và tập F  Output: true nếu F⊨ XY, ngược lại là false Function Member(X,Y,F)

Begin if Y  Closure(X,F) then Member = true else Member = false;

End

Ví dụ kiểm tra phụ thuộc hàm

 Cho F={DB, AC, ADE, CB}. Kiểm tra F có

bao hàm AB??

F?  A+

F = {ACB}

- Tìm A+ - Do B  A+

F nên F bao hàm AB

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

 Input: R(U) và tập phụ thuộc hàm F

 Output: tập hợp K bao gồm tất cả khóa của R

 Tập thuộc tính nguồn (TN) chứa tất cả các thuộc tính xuất hiện ở vế trái và không xuất hiện ở vế phải của các phụ thuộc hàm và các thuộc tính không xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm

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

 Tập thuộc tính đích (TD) chứa tất cả các thuộc tính có xuất hiện ở vế phải và không xuất hiện ở vế trái của các phụ thuộc hàm

TD= fF right(f) - fF left(f)

 Tập thuộc tính trung gian (TG) chứa tất cả các

thuộc tính xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm

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