Giáo trình Cơ sở dữ liệu: Phần 2 - CĐCN 4

Giáo trình Cơ sở dữ liệu: Phần 2 - CĐCN4 thuộc bộ môn Cơ sở dữ liệu với nội dung gồm 3 chương, từ chương 4 đến chương 6 sẽ phần nào cung cấp kiến thức chuyên ngành về khái niệm phụ thuộc hàm, phủ của phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu giúp các bạn sinh viên có thể nắm vững hơn về bộ môn mà mình đang theo học.
Nội dung trích xuất từ tài liệu:
Giáo trình Cơ sở dữ liệu: Phần 2 - CĐCN 4 Giaùo trình CÔ SÔÛ DÖÕ LIEÄU Trang 37 Chöông 4 . PHUÏ THUOÄC HAØM (functional dependency) Phuï thuoäc haøm (functional dependency) laø moät coâng cuï duøng ñeå bieåu dieãn moät caùch hình thöùc caùc raøng buoäc toaøn veïn (vaén taét: raøng buoäc). Phöông phaùp bieåu dieãn naøy coù raát nhieàu öu ñieåm, vaø ñaây laø moät coâng cuï cöïc kyø quan troïng, gaén chaët vôùi lyù thuyeát thieát keá cô sôû döõ lieäu. Phuï thuoäc haøm ñöôïc öùng duïng trong vieäc giaûi quyeát caùc baøi toaùn tìm khoùa, tìm phuû toái thieåu vaø chuaån hoùa cô sôû döõ lieäu. I KHAÙI NIEÂM PHUÏ THUOÄC HAØM Cho quan heä phanCong sau: phanCong (PHICONG, MAYBAY, NGAYKH, GIOKH) Cushing 83 9/8 10:15a Cushing 116 10/8 1:25p Clark 281 8/8 5:50a Clark 301 12/8 6:35p Clark 83 11/8 10:15a Chin 83 13/8 10:15a Chin 116 12/8 1:25p Copely 281 9/8 5:50a Copely 281 13/8 5:50a Copely 412 15/8 1:25p Quan heä phanCong dieãn taû phi coâng naøo laùi maùy bay naøo vaø maùy bay khôûi haønh vaøo thôøi gian naøo. Khoâng phaûi söï phoái hôïp baát kyø naøo giöõa phi coâng, maùy bay vaø ngaøy giôø khôûi haønh cuõng ñeàu ñöôïc chaáp nhaän maø chuùng coù caùc ñieàu kieän raøng buoäc qui ñònh sau: + Moãi maùy bay coù moät giôø khôûi haønh duy nhaát. + Neáu bieát phi coâng, bieát ngaøy giôø khôûi haønh thì bieát ñöôïc maùy bay do phi coâng aáy laùi. + Neáu bieát maùy bay, bieát ngaøy khôûi haønh thì bieát phi coâng laùi chuyeán bay aáy. Caùc raøng buoäc naøy laø caùc ví duï veà phuï thuoäc haøm vaø ñöôïc phaùt bieåu laïi nhö sau: + MAYBAY xaùc ñònh GIOKH + {PHICONG,NGAYKH,GIOKH} xaùc ñònh MABAY + {MAYBAY,NGAYKH} xaùc ñònh PHICONG hay + GIOKH phuï thuoäc haøm vaøo MAYBAY + MABAY phuï thuoäc haøm vaøo {PHICONG,NGAYKH,GIOKH} + PHICONG phuï thuoäc haøm vaøo {MAYBAY,NGAYKH} vaø ñöôïc kyù hieäu nhö sau: + {MAYBAY}→ GIOKH + {PHICONG,NGAYKH,GIOKH}→ MABAY + {MAYBAY,NGAYKH}→ PHICONG Trong kyù hieäu treân ta ñaõ kyù hieäu MAYBAY thay cho {MAYBAY}. Moät caùch toång quaùt: Bộ môn CSDL Trường CĐCN 4 Giaùo trình CÔ SÔÛ DÖÕ LIEÄU Trang 38 1 Ñònh nghóa phuï thuoäc haøm Q(A1,A2,…,An) laø löôïc ñoà quan heä. X, Y laø hai taäp con cuûa Q+={A1,A2,…,An}. r laø quan heä treân Q. t1,t2 laø hai boä baát kyø cuûa r. X → Y ⇔ (t1.X = t2.X ⇒ t1.Y = t2.Y) (Ta noùi X xaùc ñònh Y hay Y phuï thuoäc haøm vaøo X (X functional determines Y,Y functional dependent on X ) Tính chaát: + phuï thuoäc haøm X → ∅ ñuùng vôùi moïi quan heä r + phuï thuoäc haøm ∅ → Y chæ ñuùng treân quan heä r coù cuøng giaù trò treân Y. Ví duï: Quan heä sau thoûa maõn phuï thuoäc haøm ∅ → GIOKH phanCong (PHICONG, MAYBAY, NGAYKH, GIOKH) Cushing 83 9/8 10:15a Cushing 116 10/8 10:15a Clark 281 8/8 10:15a Clark 301 12/8 10:15a Clark 83 11/8 10:15a Chin 83 13/8 10:15a Chin 116 12/8 10:15a Copely 281 9/8 10:15a Copely 281 13/8 10:15a Copely 412 15/8 10:15a treân thöïc teá khoâng coù quan heä r naøo thoûa tính chaát treân neân töø ñaây veà sau neáu khoâng noùi roõ thì vôùi moät quan heä r baát kyø ta luoân xem phuï thuoäc haøm ∅ → Y luoân luoân khoâng thoûa treân r. 2 Phuï thuoäc haøm hieån nhieân (Trivial Dependencies) Heä quaû: Neáu X ⊇ Y thì X → Y. Chöùng minh: Giaû söû t1.X = t2.X do X ⊇ Y neân t1.Y = t2.Y theo ñònh nghóa suy ra X → Y Trong tröôøng hôïp naøy X → Y ñöôïc goïi laø phuï thuoäc haøm hieån nhieân. Ví duï phuï thuoäc haøm X → X laø phuï thuoäc haøm hieån nhieân. Vaäy vôùi r laø quan heä baát kyø, F laø taäp phuï thuoäc haøm thoûa treân r, ta luoân coù F ⊇ {caùc phuï thuoäc haøm hieån nhieân} 3 Thuaät toaùn Satifies Cho quan heä r vaø X, Y laø hai taäp con cuûa Q+. Thuaät toaùn SATIFIES seõ traû veà trò true neáu X → Y ngöôïc laïi laø false SATIFIES Vaøo: quan heä r vaø hai taäp con X,Y ra: true neáu X → Y, ngöôïc laïi laø false SATIFIES(r,X,Y) 1. Saép caùc boä cuûa quan heä r theo X ñeå caùc giaù trò gioáng nhau treân X nhoùm laïi vôùi nhau Bộ môn CSDL Trường CĐCN 4 Giaùo trình CÔ SÔÛ DÖÕ LIEÄU ...