Cơ sở dữ liệu 1_Chương 4: Phụ thuộc hàm và dạng chuẩn

C s d li u 1 ơ ở ữ ệ

Ch

ươ

ụ

ng 4: Ph thu c hàm ộ và d ng chu n ạ

ẩ

ả

ễ Th

Gi ng viên: Nguy n Công ngươ

Ch

ươ

ụ

ng 4: Ph thu c hàm và d ng chu n

ộ ạ

ẩ

ụ

ị ệ

ủ ậ ộ

 Đ nh nghĩa ph thu c hàm. ộ  H tiên đ Armstrong ề  Bao đóng c a t p ph thu c hàm ụ  Gi ậ  Các d ng chu n. ạ

i thu t tìm khóa. ả

ẩ

Ví dụ

MSSV

Ngay sinh Lop GVC

Ho ten SV

Diem TB

05110123

Lan

7.8

05110032 Mai

7.2

05110045

Lan

N 1-1-1986 051 Đ oạ 5-2-1985 051 Đ oạ Vân 4-5-1986 052

7.5

05110056

Hùng

5-2-1985 052

Vân

7.4

06110012

Hoa

2-3-1986 061

Khôi

7.8

Ph thu c hàm ộ

ụ

 Đ nh nghĩa ph thu c hàm ộ  Các lu t suy di n cho ph thu c hàm (h ệ ụ

ị

ộ

 T p ph thu c hàm t  T p ph thu c hàm t

ng ươ

ng đ i ti u ụ ễ ậ lu t Armstrong) ụ ụ ậ ậ ậ ộ ộ ươ ố ể

Ph thu c hàm ộ

ụ

 M t ph thu c hàm (Functional Dependency)

ụ ộ ộ

ậ ộ ộ

là m t ràng bu c gi a hai t p thu c tính ữ ộ trong CSDL

Ph thu c hàm (2) ộ

ụ

 L

ồ ệ ượ ộ

c đ quan h có n thu c tính: R(A1, A2, …, An) X và Y là 2 t p con c a R ậ ủ

ằ

thu c hàm vào X, n u: ộ

 Ta nói r ng X xác đ nh hàm Y hay Y ph ụ ị ế r(R): t1[X] = t2[X] (cid:222)

f: left(f)

ụ

ộ

 X là v trái c a ph thu c hàm  Y là v ph i c a ph thu c hàm

f: right(f)

" t1[Y] = t2[Y]

ế ế

ụ

ộ

t1, t2 ˛  V i ớ f : X  Y: ủ ả ủ

Ph thu c hàm (3) ộ

ụ

 L u ý: ư

ự

ẳ

i X i X

 N u X là khóa d tuy n c a R, ta có th kh ng ể ồ ạ Y, v i m i t p con Y ớ ể

ủ ế ị ọ ậ ế ồ ạ Y trong R, không th kh ng đ nh

ể R ẳ

ị

đ nh t n t  N u t n t có t n t

i Y

ồ ạ X trong R hay không

Ph thu c hàm (4) ộ

ụ

 Ví d :ụ

MSSV

Ho ten SV Ngay sinh

Lop GVCN Diem TB

05110123 Lan

1-1-1986

051

7.8

05110032 Mai

5-2-1985

051

7.2

05110045 Lan

4-5-1986

052

Đ oạ Đ oạ Vân

7.5

05110056 Hùng

5-2-1985

052

Vân

7.4

06110012 Hoa

2-3-1986

061

Khôi

7.8

H tiên đ Armstrong

ệ

ề

 Còn g i là H lu t suy di n Armstrong

ễ ọ

ả

 IR1: Lu t ph n x (reflexive rule) Y, thì X  Y

 IR2: Lu t gia tăng (augmentation rule)

 {X  Y } |= XZ  YZ ậ ắ

 IR3: Lu t b c c u (transitive rule) ầ

 {X  Y, Y  Z} |= X  Z

ệ ậ (Inference Rules) ạ ậ  N u X ế ậ

H quệ

ả

 IR4: lu t phân rã – lu t chi u

ế ậ ậ

 IR5: lu t h p (union rule)  {X  Y, X  Z} |= X  YZ

(decomposition, projective rule)  {X  YZ} |= X  Y ậ ợ

 IR6: lu t b c c u gi ậ ắ

(pseudotransitive rule) ả

 Ch ng minh???

ầ  {X  Y, WY  Z } |= WX  Z

ứ

ụ

ộ

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

ụ ộ

ộ ậ ụ ộ

ụ ấ

 Bao đóng (closure) c a m t t p ph thu c ủ + là t p ph thu c hàm nh hàm F, ký hi u Fệ ỏ ậ nh t ch a F sao cho không th áp d ng h ệ ể ứ tiên đ Armstrong trên t p này đ t o ra m t ộ ph thu c hàm không có trong t p này

ề ậ

ể ạ ậ ụ ộ

Bao đóng c a t p thu c tính ủ ậ d a trên t p ph thu c hàm ụ

ộ ộ

ự

ậ

ủ ậ ự ậ

 Bao đóng c a t p thu c tính X d a trên t p ộ ph thu c hàm F (Closure of X under F), ký ộ ụ hi u Xệ F, là t p thu c tính Y sao cho:  $  "

X  Y ˛ X  Z ˛

F+ F+: Z ˝

ậ ộ

Bao đóng t p thu c tính (2)

ộ

ậ

 Ví d :ụ

 F = {SSN  ENAME,

PNUMBER  {PNAME, PLOCATION}, {SSN, PNUMBER}  HOURS}

 { SSN }+ = { SSN, ENAME }  { PNUMBER }+ = { PNUMBER, PNAME, PLOCATION }  { SSN, PNUMBER }+ = { SSN, PNUMBER, ENAME,

PNAME, PLOCATION, HOURS }

Gi

i thu t tìm bao đóng

ả

ậ

ộ

ậ

ự

Input: T p thu c tính X và t p PTH 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 each W  Z in F do

if W ˝ Closure_X then

Closure_X := Closure_X ¨ Z;

until Closure_X = Old_X;

End

Gi

i thu t tìm bao đóng

ả

ậ

ượ ệ

 Ví d : Cho l ụ v i t p PTH F={D ớ ậ

 {A}+

 Tìm bao đóng: F  {A, D}+ F

c đ quan h R(A,B,C,D, E,F) ồ B, AC, ADE, CF}

+

Ki m tra thành viên trong F

ể

 Làm th nào đ ki m tra xem PTH X ể ể ế + hay không? thu c Fộ

 Y có

i

ộ ố

ớ

M t s khái ni m liên quan t ệ khóa

 Siêu khóa  Khóa d tuy n  Thu c tính khóa là thu c tính thành ph n

ự ể

ầ ộ ộ

c a m t khóa d tuy n nào đó ự ủ ể ộ

Gi

i thu t tìm khóa

ả

ậ

ủ

ậ t c các khóa c a R

Input: T p thu c tính U và t p PTH F c a R Output: T p h p K ch a t ủ

ứ ấ ả

ộ ợ

ậ

Procedure Set_of_Keys(U, F, K); Begin

" f ˛ F right(f);

N := U - ¨ if N+

F = U then K := {N}

else begin

" f ˛ F right(f) - ¨

" f ˛ F left(f);

D := ¨ L := U – N ¨ D; K := ˘ ; for each Li ˝ L do if (N¨ Li)+

F = U then K := K ¨

{N¨ Li};

while $ Ki , Kj

˛ K and Ki (cid:204) Kj do

K := K – {Kj};

end

End;

Gi

i thu t tìm khóa

ả

ậ

 Ví d :ụ

 R(A, B, C, D, E, F, G)  F={ABCD, ADB, BEG, DFA} c đ quan h R  Hãy tìm khóa c a l ủ ượ

ệ

ồ

V n đ d th a d li u

ề ư ừ

ữ ệ

ấ

 Ví dụ

MSSV

Ho ten SV Ngay sinh

Lop GVCN Diem TB

05110123 Lan

1-1-1986

051

7.8

Đ oạ

05110032 Mai

5-2-1985

051

7.2

Đ oạ

05110045 Lan

4-5-1986

052

Vân

7.5

05110056 Hùng

5-2-1985

052

Vân

7.4

06110012 Hoa

2-3-1986

061

Khôi

7.8

Các b t th

ấ

ườ

ng khi c p nh t ậ ậ

 Ví d : Thêm sinh viên

 B t th ườ ấ ụ

ng khi thêm d li u ữ ệ

ấ

ườ

ng khi c p nh t ậ

ậ

Các b t th (2)

 B t th ấ

 Xóa Sinh viên Hoa???

ng khi xóa d li u ườ ữ ệ

ấ

ườ

ng khi c p nh t ậ

ậ

Các b t th (3)

 B t th ấ

ng khi thay đ i d li u ườ ổ ữ ệ

D ng chu n

ẩ

ạ

ứ

 Là khái ni m dùng đ phân lo i m c đ d ộ ư ể ng có th x y ể ả c đ ồ

ừ ệ ữ ệ ạ ườ

ấ ậ ủ ộ ượ

th a d li u và nh ng b t th ữ ra trong quá trình c p nh t c a m t l ậ CSDL

Ví dụ

MSSV

Ngay sinh Lop GVC

Ho ten SV

Diem TB

05110123

Lan

7.8

05110032 Mai

7.2

05110045

Lan

N 1-1-1986 051 Đ oạ 5-2-1985 051 Đ oạ Vân 4-5-1986 052

7.5

05110056

Hùng

5-2-1985 052

Vân

7.4

06110012

Hoa

2-3-1986 061

Khôi

7.8

D ng chu n 1

ẩ

ạ

 D ng chu n 1 (1NF): Không có thu c tính đa

ộ

tr và thu c tính ph c h p ợ

ạ ị  Cách gi ẩ ứ ộ i quy t??? ế ả

D ng chu n 2

ẩ

ạ

ầ ủ

 Ph thu c hàm đ y đ  Ph thu c hàm riêng ph n  D ng chu n 2 (2NF): ẩ

c đ đã đ t 1NF.

ượ

ộ ộ ầ

ạ i ph thu c hàm riêng ph n vào

ồ ồ ạ

ụ

ộ

ầ

khóa

 Cách gi

ụ ụ ạ  L  Không t n t

ả i quy t??? ế

D ng chu n 3

ạ

ẩ

 Ph thu c hàm b c c u (transitive

ụ ầ ắ ộ

ượ

ầ

 D ng chu n 3 (3NF): ạ ẩ  L c đ đ t 2NF ồ ạ  Không t n t i ph thu c hàm b c c u vào khóa. ụ ồ ạ  Đ c đi m: M i PTH đ u có đ c đi m ọ ể

ắ ặ

dependency)

ộ ề  V trái là siêu khóa, ho c ặ  V ph i là thu c tính khóa

ế ế

ả  Cách gi ả

ộ i quy t??? ế

ể ặ

D ng chu n Boyce-Codd

ạ

ẩ

ế

 BCNF: m i PTH trong l ọ  V trái là siêu khóa i quy t???  Cách gi ế ả  D ng chu n 4 (4NF) ẩ ạ

ượ c đ ph i th a ả ỏ ồ

T ng k t ế

ổ

ấ

ệ ả

ng ươ

 V n đ d th a d li u ữ ệ ề ư ừ ng khi c p nh t  Các b t th ậ ậ ườ ấ  Ph thu c hàm ộ ụ  H lu t suy di n Armstrong và h qu ễ ệ ậ  Bao đóng t p thu c tính ộ ậ  T p ph thu c hàm t ươ  T p ph thu c hàm t ố ể

ng đ i ti u ụ ụ ậ ậ ộ ộ