Ôn thi cơ sở dữ liệu (GV: Tạ Thúc Nhu)

Chia sẻ: Vo Thanh Trung | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

279
lượt xem 59
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cơ sở dữ liệu (viết tắt CSDL; tiếng Anh là database) được hiểu theo cách định nghĩa kiểu kĩ thuật thì nó là một tập hợp thông tin có cấu trúc. Tuy nhiên, thuật ngữ này thường dùng trong công.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ôn thi cơ sở dữ liệu (GV: Tạ Thúc Nhu)

ÔN THI CƠ S D Li U CHU N HÓA CSDL Giáo viên: T Thúc Nhu Khoa CNTT trư ng H L c H ng I- Ph thu c hàm: CSDL@Khoa CNTT 2 1
1. Khái ni m ph thu c hàm: 1. Khái thu hàm: Kh • Cho m t lư c quan h Q • X ⊆ Q+, Y ⊆ Q+, X ≠ ∅, Y ≠ ∅ Y ph thu c hàm vào X, ký hi u X Y, n u ∀u, v ∈ Q: u.X = v.X thì u.Y = v.Y Quy ư c ký hi u: • N u Y không ph thu c hàm vào X ta ký hi u: X Y • f : ph thu c hàm • F : t p các ph thu c hàm CSDL@Khoa CNTT 3 Ví d : Tìm các ph thu c hàm trên quan h Ví Xét lư c quan h qu n lý k t qu h c t p c a sinh viên KQHT(MaSV, Ten, NS, TenLop, KhoaHoc, MaMH,TenMH,Diem) • Tân t : M i sinh viên có m t mã s phân bi t v i các sinh viên khác (MaSV); có tên (Ten), ngày sinh (NS) và h c m t l p (TenLop). M i l p có tên l p phân bi t và thu c m t khóa h c (KhoaHoc). M i môn h c có m t mã s phân bi t (MaMH), có tên môn h c (TenMH) cũng phân bi t. M i sinh viên h c nhi u môn, m i môn có i m thi (Diem) c a môn h c ó. CSDL@Khoa CNTT 4 2
2- Các Ph thu c hàm c bi t: 1. Ph thu c hàm hi n nhiên: X → X 2. Ph thu c hàm y (fully functional dependence): X −−>Y là ph thu c hàm y −/−> Khi và ch khi ∀X' ⊂ X, X' −/−> Y Ví d : Ph thu c hàm MaSV, MaMH −−> DiemMH là ph thu c hàm y vì : −/−> −/−> MaSV −/−> DiemMH và MsMH −/−> DiemMH CSDL@Khoa CNTT 5 3- Bao óng c a t p thu c tính: Cho L QH và X ⊆ Q+. Bao óng c a t p thu c tính X d a trên FQ, ký hi u X+FQ, là t p các thu c tính ph thu c hàm vào X d a trên FQ. −−> Ký hi u: X+FQ = { Y ∈ Q+ : X −−> Y ∈ F+Q} Nh n xét: 1. X ∈ X+FQ −−> 2. W −−> Z và W ⊆ X+FQ thì Z ⊆ X+FQ CSDL@Khoa CNTT 6 3
Ví d : Tìm bao óng c a t p thu c tính cho Q(ABCDEGH) và t p ph thu c hàm −−> −−> FQ ={f1:B −−>A; f2:DA−−>CE; f3:D −−>H; f4:GH−−>C; f5:AC−−>D} 1. Tìm bao óng c a t p thu c tính X1 = {BD} 2. Tìm bao óng c a t p thu c tính X2 = {BCG} CSDL@Khoa CNTT 7 4- Khóa c a quan h : nh nghiã: Cho lư c quan h < Q, FQ > −−> 1. S ⊆ Q+, S là siêu khóa c a Q n u S −−> Q+∈ FQ 2. K ⊆ Q+, K là khóa ch nh n u a) K là siêu khóa b) K−−>Q+ là ph thu c hàm y CSDL@Khoa CNTT 8 4
II- D ng Chu n Trên Quan H : II- ng • D ng chu n 1 • D ng chu n 2 • D ng chu n 3 • D ng chu n BCK CSDL@Khoa CNTT 9 1- D ng chu n 1: nh nghĩa DC1: 1.1 M t lư c quan h Q t d ng chu n 1 n u m i thu c tính c a Q u là thu c tính ơn. 1.2 Khái ni m Thu c tính ơn: M t thu c tính ư c g i là thu c tính ơn n u giá tr thu c tính ho c ch mang m t thông tin duy nh t; n u ư c ghép b i nhi u thông tin thì h th ng thư ng truy xu t trên toàn b giá tr c a nó. Ví d : – Thu c tính a_Ch – Thu c tính Ngày_Sinh CSDL@Khoa CNTT 10 5
2- D ng chu n 2: M t lư c quan h Q t d ng chu n 2 n u: a. Q có DC1 b. M i thu c tính không là thu c tính khóa u ph thu c hàm y vào các khóa c a Q. DC1 DC2 Nh n xét: N u m i khóa c a quan h Q ch có 1 thu c tính thì Q t d ng chu n 2. CSDL@Khoa CNTT 11 Ví d ki m tra d ng chu n 2 c a quan h : 1- QLSV(MaSV, Ten, NS, DC, TenLop, KhoaHoc, MaMH, TenMH, Diem) F = {f1:MaSV Ten, NS, DC, TenLop f2: TenLop KhoaHoc; f3: MaMH TenMH; f4 : TenMH MaMH; f5: MaSV, MaMH Diem } 2- KQHT(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 3- SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} CSDL@Khoa CNTT 12 6
3- D ng chu n 3: 3.1 Khái ni m Ph thu c b c c u: Cho lư c • quan h ; A ⊂ Q+, X ⊂ Q+ và t n t i X • A X A là ph thu c hàm b c c u n u t n t i nhóm thu c tính Y ⊂ Q+ th a m n 4 i u ki n sau: Y ∈ F+Q 1. X A ∈ F+Q 2. Y 3. Y −/−> X 4. A ⊄ {X ∪ Y} CSDL@Khoa CNTT 13 Ví d : SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} a) Ki m tra t n t i : MaSV KhoaHoc b) Ch ng minh {KhoaHoc} ph thu c b c c u vào {MaSV} CSDL@Khoa CNTT 14 7
3.2 nh nghiã DC3: Lư c quan h Q t d ng chu n 3 n u: 1. Q t d ng chu n 2 2. M i thu c tính không là thu c tính khóa u không ph thu c b c c u vào m t khóa nào c a Q. DC1 DC2 DC3 CSDL@Khoa CNTT 15 Ví d ki m tra d ng chu n 3 c a quan h : 1- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 2- SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} CSDL@Khoa CNTT 16 8
4. D ng chu n BCK (Boyee-Codd-Kent): Lư c quan h Q d ng chu n BCK n u 1. Q t d ng chu n 3 2. M i ph thu c hàm không hi n nhiên u ch a 1 khóa c a Q v trái. ∀X A ∈ F+Q : A ∉ X và X ch a 1 khóa c a Q DC1 DC2 DC3 DC BCK CSDL@Khoa CNTT 17 Ví d ki m tra d ng chu n BCK c a quan h : 1- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 2- SV(MaSV, Ten, NS, DC, TenLop) FSV = { f: MaSV Ten, NS, DC, TenLop} 3- LOP(TenLop, KhoaHoc) FLOP = { f: TenLop KhoaHoc} CSDL@Khoa CNTT 18 9
III- D ng chu n c a CSDL: Là d ng chu n th p nh t trong các lư c quan h có trên CSDL. Ví d : Xét d ng chu n c a CSDL g m 2 quan h sau: 1- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 2- SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} CSDL@Khoa CNTT 19 Ví d : Xét d ng chu n c a CSDL g m 3 quan h sau: 1- SV(MaSV, Ten, NS, DC, TenLop) FSV = { f: MaSV Ten, NS, DC, TenLop} 2- LOP(TenLop, KhoaHoc) FLOP = { f: TenLop KhoaHoc} 3- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} CSDL@Khoa CNTT 20 10
Ví d : Xét d ng chu n c a CSDL g m 4 quan h sau: 1- SV(MaSV, Ten, NS, DC, TenLop) FSV = { f: MaSV Ten, NS, DC, TenLop} 2- LOP(TenLop, KhoaHoc) FLOP = { f: TenLop KhoaHoc} 3- MONHOC(MaMH, TenMH) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH} 4- KQHT(MaSV, MaMH, Diem) FKQHT ={ f1: MaSV, MaMH Diem} CSDL@Khoa CNTT 21 IV- Chu n hóa Lư c Quan H : CSDL@Khoa CNTT 22 11
1- M c tiêu chu n hóa: Bi n i lư c • quan h có d ng chu n th p trong CSDL thành các lư c quan h t d ng chu n cao nh t Ví d : Xét CSDL g m 2 quan h sau: 1- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 2- SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} CSDL@Khoa CNTT 23 2- nh lý Delobel: (1973) • Xét quan h Q(X, Y, Z) có t p ph thu c hàm FQ • X, Y, Z là các t p con thu c tính khác r ng. N u t n t i X Y thì phép phân rã Q thành 2 quan h con Q1(X, Y) và Q2(X, Z) là b o toàn thông tin. - Q+ = Q1+ ∪ Q2+ . Nghĩa là: - Q = Q1 Q2 Ý tư ng: Chu n hóa quan h Q 1. Phân rã Q thành 2 quan h Q1 và Q2 b ng 1 m t ph thu c hàm f có VT(f) ∪ VP(f) ⊂ Q+. 2. L p l i phương pháp phân rã cho Q1 và Q2 cho n khi không còn ph thu c hàm như v y n a. CSDL@Khoa CNTT 24 12
3- Thu t toán phân rã: Thu t toán: Phân rã Input: Output: C = { QI }nI=1 {t p các l qh ư c phân rã} Begin b1. F* = FQ \ { f ∈ FQ : [VT(f)]+ = Q+ } b2. N u F* = ∅ thì C = {QI} là nghi m c a bài toán (k t thuc) Ngư c l i thì chuy n sang bư c b3 Y ∈ F* b3. Ch n ph thu c hàm f: X b4. Phân rã lư c quan h Q thành 2 lư c quan h con: < Q1(X, Y), F1={f ∈ FQ : VT(f) ∪ VP(f) ⊂ Q1+} > < Q2(Q+ \ Y), F2={ f ∈ FQ : VT(f) ∪ VP(f) ⊂ Q2+} > b5. N u F1 ∪ F2 FQ thì quay l i b3 ch n m t ph thu c hàm khác. ngư c l i thì sang b6 b6. Phân rã(Q1, F1); b7. Phân rã (Q2, F2); end; CSDL@Khoa CNTT 25 Ví d : Ví 1- KQMH(MaSV, MaMH, TenMH, Diem) FKQHT ={ f1: MaMH TenMH; f2 : TenMH MaMH; f3: MaSV, MaMH Diem} 2- SV(MaSV, Ten, NS, DC, TenLop, KhoaHoc) FSV = { f1:MaSV Ten, NS, DC, TenLop; f2: TenLop KhoaHoc} CSDL@Khoa CNTT 26 13
Ví d : VanChuyen(MsKH, TP, CTyVC, MsHH, SL) F = { f1: MsKH TP; f2: TP CtyVC; f3: MsKH, MsHH SL } – MsKH: Mã s Khách hàng. – TP: Thành ph khách . – CtyVC: công ty v n chuy n hàng. – MsHH: mã hàng hóa. – SL: s lư ng. 1. Xét d ng chu n 2. Phân rã thành các quan h có d ng chu n cao nh t CSDL@Khoa CNTT 27 Nh n xét: 1. T t c các quan h k t qu u t d ng chu n BCK 2. B o toàn thông tin. 3. Tùy theo th t các pth ư c xét mà k t qu và s lư ng quan h con có th khác nhau 4. Nên ưu tiên ch n ph thu c hàm gây ch t lư ng x u cho quan h . CSDL@Khoa CNTT 28 14