Uploaded byBảo Ngọc Lê Show
0% found this document useful (0 votes) 101 views 24 pages Copyright© © All Rights Reserved Available FormatsPPT, PDF, TXT or read online from Scribd Share this documentDid you find this document useful?Is this content inappropriate?0% found this document useful (0 votes) 101 views24 pages 2.1.2 Tach Bao Toan PTHUploaded byBảo Ngọc Lê Jump to Page You are on page 1of 24 Search inside document Reward Your CuriosityEverything you want to read. Anytime. Anywhere. Any device. No Commitment. Cancel anytime. Việc quan trọng nhất khi thiết kế cơ sở dữ liệu quan hệ là ta phải chọn ra tập các lược đồ quan hệ tốt nhất dựa trên một số tiêu chí nào đó. Và để có được lựa chọn tốt, thì chúng ta cần đặc biệt quan tâm đến mối ràng buộc giữa các dữ liệu trong quan hệ, đó chính là các phụ thuộc hàm. Để hiểu hơn về câu hỏi tại sao phải thiết kế một cơ sở dữ liệu tốt, chúng ta hãy cùng tìm hiểu ví dụ sau RESULT(StNo, StName, SubNo,SubName, Credit, Mark) Quan hệ RESULT( Kết quả học tập) có các thuộc tính: StNo(Mã sinh viên), StName(Tên sinh viên), SubNo(Mã môn học), SubName(Tên môn học), Credit (Số đơn vị học trình) và Mark (điểm thi của sinh viên trong môn học). Sau đây là minh hoạ dữ liệu của quan hệ RESULT Minh họa dữ liệu của quan hệ RESULTQuan hệ trên thiết kế chưa tốt vì
Nhận xét: Qua phân tích trên, ta thấy chúng ta nên tìm cách tách quan hệ trên thành các quan hệ nhỏ hơn. Trong chương này chúng ta sẽ nghiên cứu về những khái niệm và các thuật toán để có thể thiết kế được những lược đồ quan hệ tốt. Phụ thuộc hàm(Functional Dependencies)
Định nghĩa phụ thuộc hàmCho r(U), với r là quan hệ và U là tập thuộc tính. Cho A,B ⊆ U, phụ thuộc hàm X → Y (đọc là X xác định Y) được định nghĩa là: ∀ t, t’ ∈ r nếu t.X = t’.X thì t.Y = t’.Y (Có nghĩa là: Nếu hai bộ có cùng trị X thì có cùng trị Y) Phụ thuộc hàm được suy ra từ những quy tắc dữ liệu khi ta khảo sát yêu cầu của bài toán. Từ mã số bảo hiểm xã hội, ta có thể suy ra được tên của nhân viên (Ssn→ Ename)Từ mã dự án, ta có thể suy ra tên và vị trí của dự án (PNumber→{PName, PLcation}) Biểu diễn FDs của 2 lược đồ quan hệ EMP_DEPT và EMP_PROJHệ tiên đề ArmstrongCho lược đồ quan hệ r(U), U là tập thuộc tính, F là tập các phụ thuộc hàm được định nghĩa trên quan hệ r. Ta có phụ thuộc hàm A → B được suy diễn logic từ F nếu quan hệ r trênU thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A → B. Tập phụ thuộc hàm: F = { A → B, B → C} Ta có phụ thuộc hàm A → C là phụ thuộc hàm được suy từ F. Hệ tiên đề Armstrong được sử dụng để tìm ra các phụ thuộc hàm suy diễn từ F. Hệ tiên đề Armstrong bao gồm:n 1. Phản xạ: Nếu Y → X thì X → Y 2. Tăng trưởng: Nếu Z → U và X → Y thì XZ → YZ (Ký hiệuXZ là X∪Z) 3. Bắc cầu: Nếu X → Y và Y → Z thì X → Z 4. Giả bắc cầu: Nếu X → Y và WY → Z thì XW → Z 5. Luật hợp: Nếu X → Y và X → Z thì X →YZ 6. Luật phân rã: Nếu X → Y và Z → Y thì X → Z Trong sáu luật trên thì a4, a5, a6 suy được từ a1, a2, a3. Bao đóng của tập phụ thuộc hàm
F + = { X →Y | F X →Y } Bao đóng của tập thuộc tính X trên FBao đóng của tập thuộc tính X xác định trên tập phụ thuộc hàm F ký hiệu là X+ là tập hợp tất cả các thuộc tính có thể suy ra từ X. Ký hiệu: X + = { Y | F ㅑ X →Y } X+ có thể được tính toán thông qua việc lặp đi lặp lại cá quy tắc 1, 2, 3 của hệ tiên đề Armstrong. Thuật toán xác định bao đóng của tập thuộc tính X+
Cho tập phụ thuộc hàm
Như vậy, tập thuộc tính {SSN, PNUMBER} là khoá của quan hệ. Khoá của quan hệCho quan hệ r(R), tập K ⊂ R được gọi là khóa của quan hệ r nếu: K+=R và nếu bớt một phần tử khỏi K thì bao đóng của nó sẽ khác R. Như thế tập K ⊂ R là khoá của quan hệ nếu K+=R và ( K \A )+ ≠R , ∀ A ⊂ R. ChoR = { A, B, C, D, E, G } và tập phụ thuộc hàm: F= { AB → C , D → EG , BE → C , BC → D , CG → BD, ACD → B, CE → AG} Ta sẽ thấy các tập thuộc tính K1 = { A, B } , K2 = {B,E} , K3={C,G} , K4={C,E} , K5 = {C,D}, K6={B,C} đều là khóa của quan hệ. Như vậy, một quan hệ có thể có nhiều khóa. Thuật toán tìm khoá Ý tưởng: Bắt đầu từ tập U vì Closure(U+,F) = U. Sau đó ta bớt dần các phần tử của U để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U. Thuật toán
Nhận xét
Cho lược đồ quan hệ R = { A,B,C,D,E,G,H,I} và tập phụ thuộc hàm: F= { AC → B, BI → ACD, ABC → D , H → I , ACE → BCG , CG → AE } Tìm khoá K? Ta có Left={A,B,C,H,E,G} Bước 1: K=Left={A,B,C,H,E,G} Bước 2 Bước 2 Tập thuộc tính A B C D E G H I Ghi chú ABCHEG x x x x x x x x BCHEG x x x x x x x x Loại A CHEG x x x x x x x x Loại B CHG x x x x x x x x Loại E Như vậy, {C,H,G} là một khoá của R. Nếu muốn tìm tất cả các khoá của R, ta cần thay đổi trật tự loại bỏ phần tử của khoá K. Tập phụ thuộc hàm tương đươngHai tập phụ thuộc hàm F và G là tương đương nếu
Vì thế, F và G là tương đương nếu F+ = G+ Nếu F và G là tương đương thì ta nói F phủ G hay G phủ F. Vì thế, thuật toán sau đây sẽ kiểm tra sự tương đương của hai tập phụ thuộc hàm:
Tập phụ thuộc hàm tối thiểuTập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các điều kiện sau:
Nhận xét:
Thuật toán: Tìm tập phụ thuộc hàm tối thiểu G của F
Các dạng chuẩn của quan hệĐịnh nghĩa các dạng chuẩnDạng chuẩn 1(First Normal Form)Định nghĩa Một quan hệ ở dạng chuẩn 1 nếu các giá trị của tất cả thuộc tính trong quan hệ là nguyên tử (tức là chỉ có 1 giá trị tại một thời điểm). Ví dụ
Nhận xét
Mô tả dữ liệu của 2 quan hệ này Minh họa dữ liệu của DEPARTMENT và DEPT_LOCATIONSDạng chuẩn 2(Second Normal Form_2NF)Định nghĩa Một quan hệ ở dạng chuẩn 2 nếu
Sơ đồ mô tả Sơ đồ mô tả NF2Ví dụ Quan hệ EMP_PROJ không phải ở dạng chuẩn 2 vì tồn tại 2 phụ thuộc hàm FD2, FD3 là phụ thuộc hàm bộ phận (trái với phụ thuộc hàm đầy đủ) Quan hệ Emp_projQuan hệ sau đây ở dạng chuẩn 2 Quan hệ EMP_DEPT ở dạng chuẩn 2 Minh hoạ dữ liệu của quan hệ EMP_DEPTQuan hệ sau đây ở dạng 2NF Minh hoạ dữ liệu của quan hệ THESISNhận xét
Dạng chuẩn 3 (Third Normal Form)Định nghĩa Một quan hệ ở dạng chuẩn 3 nếu
Biểu diễn bằng sơ đồ Dạng chuẩn 3NFVí dụ Quan hệ EMP_DEPT không phải ở dạng chuẩn 3 vì còn tồn tại phụ thuộc hàm DNumber→DName, DMgrSsn là phụ thuộc hàm phụ thuộc bắc cầu vào khoá. Quan hệ EMP_DEPT không phải ở dạng chuẩn 3Tách quan hệ trên thành 2 quan hệ: EMPLOYEE và DEPARTMENT. 2 quan hệ sau đều ở dạng chuẩn 3 Mô tả dữ liệu của quan hệ EMPLOYEE và DEPARTMETNhận xét
Dạng chuẩn Boyce _Codd(Boyce-Codd Normal Form)Định nghĩa Quan hệ R ở dạng chuẩn BCNF khi tất cả các phụ thuộc hàm X →A trong R đều phải có X là khoá của R. Ví dụ Quan hệ sau ở dạng 3NF nhưng không phải BCNF. Minh hoạ dữ liệu của quan hệ TEACH vi phạm chuẩn Boyce -CoddĐể nhận được quan hệ ở BCNF, ta có thể tách quan hệ trên: Cách 1: R1(Student, Instructor) và R2(Student, Course) Cách 2: R1(Couse, Instructor} và R2(Course, Student) Cách 3: R1(Instructor, Course} và R2(Instructor, Student) Việc tách quan hệ như trên sẽ làm mất đi phụ thuộc hàm FD1. Phép phân rã các lược đồ quan hệĐịnh nghĩaPhép phân rã các lược đồ quan hệ R={A1, A2, . . . , An}là việc thay thế lược đồ quan hệ R thành các lược đồ con {R1, . . . , Rk}, trong đó Ri⊆R và R=R1 ∪ R2…∪ Rk Cho quan hệ R với các phụ thuộc hàm như sau Lược đồ quan hệ RTa có thể phân rã thành 3 lược đồ R1(MaSV, TenSV, Lop) và Phép phân rã không mất mát thông tin Cho R là một lược đồ quan hệ, phép rã ρ=(R1,R2, . . .,Rn) và D là tập các phụ thuộc dữ liệu. Phép phân rã ρ không mất mát thông tin nếu khi thực hiện phép toán kết nối tự nhiên các quan hệ thành phần R1, R2,…,Rn ta vẫn nhận được kết quả của quan hệ ban đầu. Ví dụ về một phép phân rã có mất mát thông tin: Cho quan hệ Quan hệ mẫu MaSV MaMH Điem 1 A 3 2 A 5 3 A 6 4 B 6 5 C 9 Nếu ta phân rã quan hệ trên thành 2 quan hệ: R1(MaSV, MaMH) và R2(MaMH, Điem) như sau: R1 R2: R1 MaSV MaMH 1 A 2 A 3 A 4 B 5 C R2 MaMH Điem A 3 A 5 A 6 B 6 C 9 Thực hiện phép kết nối tự nhiên 2 quan hệ R1 và R2: R1*R2= R1*R2 MaSV MaMH Điem 1 A 3 1 A 5 1 A 6 2 A 3 2 A 5 2 A 6 3 A 3 3 A 5 3 A 6 4 B 6 5 C 9 Như vậy, khi nối tự nhiên 2 bảng, ta nhận được quan hệ không giống quan hệ ban đầu→ Phép phân rã trên là mất mát thông tin. Vấn đề đặt ra đối với người thiết kế là phải tìm ra những phép phân rã không làm mất mát thông tin (chi tiết sẽ được trình bày ở phần sau). Bây giờ chúng ta sẽ tìm hiểu một thuật toán để kiểm tra một phép phân rã có mất mát thông tin hay không. Thuật toán kiểm tra phép phân rã không mất mát thông tinInput
OutputKết luận phép tách ρ không mất mát thông tin. Các bước của thuật toán Bước 1
Bước 2
Bước 3 Xem xét bảng kết quả. Nếu xuất hiện một dòng chứa toàn giá trị a1, a2 ,…,an thì kết luận phép tách ρ không mất mát thông tin. Cho quan hệ Minh họa dữ liệu của quan hệ EMP_DEPTTách quan hệ trên thành 2 quan hệ Quan hệ EMPLOYEE được phân rã (tách) thành 2 quan hệTập phụ thuộc hàm F Tập phụ thuộc hàm FKiểm tra phép tách trên là không mất mát thông tin: Bước 1 Bước 1 EName SSN BDate Address DNumber DName DMgrSsn EMPLOYEE a1 a2 a3 a4 a5 b16 b17 DEPARTMENT b21 b22 b23 b24 a5 a6 a7 Bước 2: Xét phụ thuộc hàm DNumber→ DName, DMgrSsn. Ta nhận thấy có giá trị a5 ở dòng thứ 2, nên ta sẽ làm bằng giá trị a6, a7 cho dòng thứ 1. Bước 3: Tồn tại một dòng chứa giá trị a1, a2,..a7. Kết luận, phép phân rã trên không mất mát thông tin. Bước 3 EName SSN BDate Address DNumber DName DMgrSsn EMPLOYEE a1 a2 a3 a4 a5 a6 a7 DEPARTMENT b21 b22 b23 b24 a5 a6 a7 Sinh viên thực hiện phép nối tự nhiên 2 quan hệ EMPLOYEE và DEPARTMENT trên để kiểm tra có bằng quan hệ ban đầu EMP_DEPT Chuẩn hoá quan hệChuẩn hoá quan hệ là việc phân rã một lược đồ quan hệ thành các lược đồ con ở dạng chuẩn 3 hoặc ở BCNF sao cho vẫn bảo toàn phụ thuộc và không mất mát dữ liệu. Thuật toán phân rã lược đồ quan hệ thành các lược đồ quan hệ con ở BCNFInput
Output Phép phân rã của R không mất thông tin và mỗi lược đồ quan hệ trong phép tách đều ở dạng BCNF đối với phép chiếu của F trên lược đồ đó. Các bước của thuật toán
Ví dụ Cho lược đồ quan hệ R(CTHRSG). Trong đó:
Dựa vào thuật toán tìm khoá→Khóa của R là HS. Yêu cầu: Tách lược đồ R thành các lược đồ con ở dạng BCNF. Biểu diễn quá trình tách quan hệ R thành các quan hệ ở BCNFNhư vậy, quan hệ R được tách thành 4 quan hệ R1, R21, R221, R222 đều ở BCNF. Thuật toán phân rã một lược đồ quan hệ thành các lược đồ con ở 3NF.Input
Output Phép tách không mất mát thông tin trên R thành các lược đồ con ở dạng chuẩn 3 sao cho vẫn bảo toàn các phụ thuộc hàm. Các bước của thuật toán
Ví dụ Cho lược đồ quan hệ R(C,T,H,R,S,G) với tập phụ thuộc hàm tối thiểu F C→T, HR→C, HT→R, CS→G, HS→ R. Yêu cầu: Phân rã lược đồ quan hệ trên thành các quan hệ con đều ở dạng 3NF.
Như vậy, quan hệ R được tách thành các quan hệ sau: R1, R21, R221, R222
Bài tập Cho một quan hệ R ={A, B, C, D, E, F, G, H, I, J} và tập phụ thuộc hàm F = { A,B→ C A→ D, E B→ F F→ G, H D→ I, J } Yêu cầu: - Tìm {A}+ ={D, E, I ,J } - Tìm khóa của quan hệ R. - Tách quan hệ R thành BCNF. - Kiểm tra xem việc tách trên có mất mát thông tin không? Lặp lại yêu cầu ở bài 1 với tập phụ thuộc hàm sau G= {A,B → C B, D→ E, F A, D → G, H A→ I H→J} Cho một quan hệ R ={CourseNo, SecNo, OfferingDept, Credit_Hours, CourseLevel, InstructorSSN, Semester, Year, Days_Hours, RoomNo, NoOfStudents} và tập phụ thuộc hàm: |