Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 2)

92 trang hapham 2120

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_thiet_ke_co_so_du_lieu_2_phan_2.pdf

Nội dung text: Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 2)

Chương III: THIẾT KẾ CSDL MỨC QUAN NIỆM I. DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ Như đã đề cập trong phần I và II của chương II, trong một số quan hệ có thể chứa các thông tin trùng lắp ( dư thừa ), nên việc cập nhật dữ liệu (qua các phép tính thêm,sửa và hủy) gây ra những dị thường. Vì vậy các quan hệ trên cần thiết phải được biến đổi thành các dạng phù hợp hơn. Quá trình đó được gọi là chuẩn hóa. Quan hệ được chuẩn hóa là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa những giá trị nguyên tố tức là không phân nhỏ được nữa và do đó mỗi giá trị trong quan hệ cũng là nguyên tố. Quan hệ có chứa các miền giá trị là không nguyên tố gọi là quan hệ không chuẩn hóa. Mỗi quan hệ thuộc một trong các dạng sau: dạng không chuẩn hóa  dạng chuẩn 1  dạng chuẩn 2  dạng chuẩn 3  dạng chuẩn BOYCE-CODD Khi một lược đồ quan hệ được thiết kế ở dạng chuẩn càng cao ( như 3NF, BCNF ) thì khả năng dư thừa thông tin Trang 60
trong quan hệ sẽ giảm. Đặt biệt, nếu lược đồ quan hệ đạt BCNF thì quan hệ đó sẽ không có thông tin dư thừa. Các dạng chuẩn có vai trò quan trọng nhất là dạng chuẩn 3 (3NF) và dạng chuẩn Boyce Codd (BCNF) . Mục đích của chúng là tránh được các dư thừa và các bất thường. Chúng ta cần lưu ý: để xác định dạng chuẩn của một lược đồ quan hệ ta chỉ dựa vào tập các phụ thuộc hàm được định nghĩa trên lược đồ quan hệ đó. Trong dạng chuẩn 4 (4NF) thì ngoài tập các phụ thuộc hàm ta phải xét đến tập các phụ thuộc đa trị. I.1. Dạng chuẩn 1 (First Normal Form : 1NF) Định nghĩa: Một lược đồ quan hệ R được gọi là ở dạng chuẩn 1 (1NF) nếu và chỉ nếu toàn bộ các miền có mặt trong R đều chỉ chứa các giá trị nguyên tố. Định nghĩa nầy cho ta thấy rằng bất kỳ quan hệ chuẩn hóa nào cũng ở 1NF. Chúng ta cần lưu ý: trong định nghĩa các dạng chuẩn còn lại luôn kèm điều kiện trước tiên là phải đạt 1NF. Cho lược đồ quan hệ: CHUYEN_MON (MAGV, MON_GD), trong đó: MAGV là mã số của giáo viên và MON_GD là chuỗi gồm các môn học mà giáo viên có khả năng giảng dạy. Trang 61
Xét thể hiện sau : CHUYEN_MON (MAGV, MON_GD ) GV1 , CTDL,C,PASCAL GV2 , CSDL,TKCSDL Khi đó MON_GD không phải là thuộc tính nguên tố. Một trường hợp đặc biệt liên quan đến các thuộc tính có kiểu là ngày dương lịch (Datetime). Các thuộc tính nầy thực chất là thuộc tính kép (tích của các thuộc tính: ngày, tháng, năm). Tuy nhiên, chúng có thể được xem là thuộc tính đơn (thuộc tính nguyên tố) nếu như không có hoặc hiếm khi có nhu cầu truy xuất đến từng thành phần riêng lẻ: ngày, tháng hay năm. Nếu không có chú thích gì thêm, ta qui ước rằng những thuộc tính có miền giá trị là ngày dương lịch đều là thuộc tính nguyên tố. Trang 62
I.2. Dạng chuẩn 2 ( 2NF ) Trước khi nghiên cứu dạng chuẩn 2, xét ví dụ sau đây: Thí dụ III.1: Cho lược đồ CSDL gồm 2 quan hệ: THI và SINHVIEN THI (MONTHI GIAOVIEN) 3 A 4 B 5 C SINHVIEN(MONTHI MASV TENSV DIACHI DIEM) 3 11 Lan X 8 3 12 Ha Y 6 4 11 Lan X 7 4 12 Ha Y 6 5 11 Lan X 7 5 13 Tu Z 2 - Hình III.1 – Cơ sở dữ liệu vi phạm 2NF – Ta thấy MONTHI là khóa của quan hệ THI và MONTHI+MASV là khóa của quan hệ SINHVIEN. Trong quan hệ thứ hai các thuộc tính MONTHI, MASV, DIEM nói đến thông tin về kết quả thi của sinh viên. Khi đó MASV, TENSV, DIACHI nói về thông tin của đối tượng sinh viên. Trong quá trình cập nhật và lưu trữ dữ liệu xuất hiện những vấn đề sau đây: - Trong quan hệ SINHVIEN, việc lưu trữ thông tin 1 sinh viên ví dụ như “Lan” phải lặp lại 3 lần tên, 3 lần địa chỉ. Rõ ràng là thông tin bị dư thừa (trùng lắp). - Quá trình cập nhật dữ liệu gây nên những bất thường như sau: Trang 63
Phép cập nhật Do lý do nêu trên, khi cần sửa địa chỉ của “Lan” chẳng hạn, cần phải sửa 3 lần. Nếu việc sửa đổi bị sót sẽ xãy ra tình trạng dữ liệu không nhất quán: một sinh viên có thể có các địa chỉ khác nhau. Hơn nữa khi sửa đổi thông tin về một sinh viên lại không liên quan gì đến thông tin về kết quả thi. Thật ra để xác định các thông tin đặc trưng về một sinh viên, chỉ cần mã số sinh viên là xác định được duy nhất thông tin về họ. Phép thêm mới Trong quan hệ sinh viên chỉ chứa thông tin về những sinh viên đã thi (có điểm). Nếu muốn chèn thêm một sinh viên mới (chưa thi) thì không được vì khóa MONTHI, MASV là không đầy đủ. Bất thường nầy chỉ được khắc phục nếu loại bỏ những thông tin về kết quả thi ra khỏi quan hệ. Phép hủy bỏ Giả sử rằng với lý do nào đó cần loại bỏ môn thi thứ 5 mà danh sách sinh viên vẫn giữ nguyên. Khi đó ở quan hệ THI xóa bộ (5,C) còn ở quan hệ SINHVIEN nếu xóa môn thi thứ 5 (xóa 2 bộ cuối cùng) thì thông tin về sinh viên “Tu” sẽ mất. Nhận xét: Thật ra quan hệ SINHVIEN chưa đạt dạng chuẩn 2 nên mới xảy ra các bất thường trên. Để khắc phục những bất lợi trên, quan hệ SINHVIEN có thể tách thành hai quan hệ SVIEN(MASV, TENSV, DIACHI) và quan hệ KETQUA(MONTHI, MASV, DIEM). Lúc nầy cơ sở dữ liệu thành ba quan hệ và các quan hệ nầy đều ở dạng chuẩn 2. Trang 64
Cơ sở dữ liệu mới được trình như sau: THI (MONTHI GIAOVIEN) 3 A 4 B 5 C SVIEN(MASV TENSV DIACHI) 11 Lan X 12 Ha Y 13 Tu Z KETQUA(MONTHI MASV DIEM) 3 11 8 3 12 6 4 11 7 4 12 6 5 11 7 5 13 2 - Hình III.2 – Cơ sở dữ liệu đạt 2NF – Định nghĩa: Một lược đồ quan hệ R với tập các phụ thuộc hàm F, được gọi là ở dạng chuẩn 2 (2NF) nếu nó ở dạng chuẩn 1 và nếu mỗi thuộc tính không khóa của R đều phụ thuộc đầy đủ vào khóa. Nhắc lại: Trong một lược đồ quan hệ có ít nhất 1 khóa nhưng có thể có nhiều khóa. Mỗi khóa gồm 1 hay nhiều thuộc tính. Các thuộc tính tham gia vào 1 khóa nào đó được gọi là thuộc tính khóa. Các thuộc tính còn lại (không tham gia vào bất kỳ 1 khóa nào) được gọi là thuộc tính không khóa. Trang 65
Định nghĩa: Cho lược đồ quan hệ R = {A1,A2, , An} và F là tập các phụ thuộc hàm. Cho X và Y là hai tập thuộc tính khác nhau của R. Ta nói Y phụ thuộc hàm đầy đủ vào X nếu Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X. Nghĩa là muốn Y phụ thuộc hàm đầy đủ vào X thì phải thỏa cả 2 điều kiện sau: 1. X Y F+ 2.  X’  R: nếu (X’  X và X’ X ) thì X’ Y F+ Bây giờ chúng ta hãy xem lại quan hệ SINHVIEN đã trình bày ở Hình III.1 Với tập các thuộc tính R = {MONTHI, MASV, TENSV, DIACHI, DIEM}. Và tập các phụ thuộc hàm F = {f1, f2} như sau: f1 : MASV TENSV, DIACHI f2 : MONTHI, MASV DIEM Ta thấy khóa của lược đồ quan hệ trên là K = {MONTHI, MASV} vì: (i) K+ = { MONTHI, MASV } = { MONTHI, MASV, DIEM} do f1 = {MONTHI,MASV,DIEM,TENSV,DIACHI} do f2 = R (ii) MONTHI DIEM F+ và MASV DIEM F+ Vậy các thuộc tính không khóa là: TENSV, DIACHI và DIEM. Xét thuộc tính không khóa TENSV. Nhận xét rằng một thuộc tính bất kỳ của lược đồ đều phụ thuộc hàm vào khóa của lược đồ đó. Nghĩa là MONTHI, MASV TENSV F+ Trang 66
Do MASV TENSV F+ và {MASV}  K và {MASV} K nên MASV không phụ thuộc hàm đầy đủ vào khóa. Kết luận: lược đồ quan hệ trên vi phạm dạng chuẩn 2. Bạn hãy kiểm chứng: DIACHI cũng không phụ thuộc hàm đầy đủ vào khóa, nhưng DIEM thì phụ thuộc hàm đầy đủ vào khóa. Cả ba lược đồ quan hệ: THI, SVIEN và KETQUA ở Hình III.2 đều đạt dạng chuẩn 2. I.3. Dạng chuẩn 3 ( 3NF ) Để trình bày dạng chuẩn 3, ta đưa ra khái niệm về phụ thuộc bắc cầu như sau: Định nghĩa: Cho lược đồ quan hệ R = {A1,A2, , An} và F là tập các phụ thuộc hàm. Cho X là tập con của R và A là một thuộc tính thuộc R. Thuộc tính A được gọi là phụ thuộc bắc cầu vào tập thuộc tính X nếu tồn tại một tập con Y của R sao cho X Y F+,Y A F+, nhưng Y X F+, và A XY. Nghĩa là: để A phụ thuộc bắc cầu vào X, ta phải tìm được tập Y thỏa các điều kiện sau: (i) A XY; thuộc tính A không thuộc X và A không thuộc Y. (ii) phụ thuộc hàm X Y F+ (iii) phụ thuộc hàm Y A F+ (iv) phụ thuộc hàm Y X F+ Trang 67
Tính bắc cầu thể hiện qua sơ đồ sau: X Y A Cũng như ở 2NF việc loại bỏ phụ thuộc bắc cầu để đi đến 3NF nhằm lọai bỏ những dị thường gây ra trong trong quá trình cập nhật dữ liệu. Ta có định nghĩa về dạng chuẩn 3 sau: Định nghĩa: Một lược đồ quan hệ R với tập các phụ thuộc hàm F, được gọi là ở dạng chuẩn 3 (3NF) nếu nó ở dạng chuẩn thứ hai và nếu mỗi thuộc tính không khóa của R đều không được phụ thuộc bắc cầu vào khóa. Thí dụ III.2: Cho lược đồ quan hệ R (SAIP) với các phụ thuộc hàm SI P và S A. Ta thấy SI là khóa của R vì {S,I}+ = R và {S}+ = {S,A} R và {I}+ = {I} R. Xét thuộc tính không khóa A, chọn tập trung gian Y là S. Ta có: (i) A {S,I}  {S}. (ii) SI S F+ ,do tính phản xạ (tiên đề A1) (iii) S A F+ ,do giả thiết (iv) S SI F+ vì {S}+ = {S,A} Trang 68
Vậy thuộc tính không khóa A phụ thuộc bắc cầu vào khóa SI, nên lược đồ quan hệ trên vi phạm 3NF. Hơn nữa, lược đồ trên cũng không ở 2 NF vì thuộc tính không khóa A không phụ thuộc đầy đủ vào khóa SI do phụ thuộc hàm S A. Thí dụ III.3: Cho lược đồ quan hệ R (CSZ) với các phụ thuộc hàm CS Z và Z C. Ta thấy R có 2 khóa là SC và SZ. Bạn hãy kiểm chứng. Vì vậy tất cả các thuộc tính đều là thuộc tính khóa, do đó lược đồ trên đạt 3NF. Thí dụ III.4: Cho lược đồ quan hệ R (SIDM) và các phụ thuộc hàm SI D và SD M. Bạn hãy kiểm chứng: lược đồ nầy chỉ có 1 khóa là SI. Các thuộc tính không khóa là M và D. Lược đồ nầy vi phạm 3NF vì thuộc tính không khóa M phụ thuộc bắc cầu vào khóa SI khi chọn tập trung gian Y = {S,D}. Ta có SI SD F+ và SD M F+ và SD SI F+ và M {S,D}  {S,I}. Trang 69
I.4. Dạng chuẩn BOYCE-CODD ( BCNF ) Dạng chuẩn có điều kiện khắt khe hơn là dạng chuẩn Boyce Codd với định nghĩa sau: Định nghĩa : Lược đồ quan hệ R với tập các phụ thuộc hàm F được gọi được gọi là ở dạng chuẩn Boyce-Codd nếu X A đúng trên R, với A là thuộc tính không thuộc X thì X là một khóa bao hàm. Nhận xét: (1) Theo định nghĩa trên ta phải xét mọi phụ thuộc hàm không tầm thường X A của F+. (2) X là một khóa bao hàm (siêu khóa) nghĩa là X phải chứa một khóa nào đó của R. Nói cách khác, những phụ thuộc không tầm thường duy nhất là những phụ thuộc trong đó một khoá xác định hàm một hoặc nhiều thuộc tính khác. Như thế chúng ta phải tìm các phụ thuộc X A có vi phạm không chỉ trong những phụ thuộc đã cho mà còn trong những phụ thuộc được suy ra từ những phụ thuộc này. Tuy nhiên là nếu trong tập phụ thuộc F đã cho không có các vi phạm, và F chỉ chứa những phụ thuộc mà vế phải chỉ có một thuộc tính duy nhất thì không có vi phạm trong các phụ thuộc của F+. Thí dụ III.5: Xét lược đồ quan hệ R (CSZ) với các phụ thuộc hàm CS Z và Z C. Ta thấy R có 2 khóa là SC và SZ. Bạn hãy kiểm chứng. Vì vậy tất cả các thuộc tính đều là thuộc tính khóa, do đó lược đồ trên đạt 3NF. Trang 70
Lược đồ quan hệ CSZ với những phụ thuộc này không có dạng BCNF vì Z C đúng trong CSZ nhưng Z không phải là khoá của CSZ và cũng không chứa một khoá. Như vậy lược đồ trên đạt 3NF nhưng lại vi phạm BCNF. Định lý III.1: Nếu một lược đồ quan hệ R với tập các phụ thuộc hàm F là ở BCNF thì nó cũng ở 3NF. Chứng minh: Giả sử lược đồ quan hệ R là ở BCNF nhưng không ở 3NF. Như vậy tồn tại một thuộc tính không khóa A phụ thuộc bắc cầu vào khóa X, nghĩa là có tập Y sao cho: (i) A XY; thuộc tính A không thuộc X và A không thuộc Y. (ii) phụ thuộc hàm X Y F+ (iii) phụ thuộc hàm Y A F+ (iv) phụ thuộc hàm Y X F+ Do (i) nên Y A không phải là phụ thuộc hàm tầm thường. Và do (iv) ta có Y không phải là khóa bao hàm vì nếu ngược lại thì Y phải xác định hàm mọi tập thuộc tính của R tức là Y X F+. Theo định nghĩa về dạng chuẩn ta có (R,F) vi phạm BCNF. Điều nầy mâu thuẫn với giả thiết. I.5. Một định nghĩa khác cho dạng chuẩn 3 Trong một số tình huống, dạng chuẩn BCNF đòi hỏi một điều kiện quá khắt khe, theo nghĩa là không thể chuyển lược đồ quan hệ thành dạng đó bằng cách phân rã mà không làm mất đi đặc tính bảo toàn các phụ thuộc. Dạng chuẩn 3 cung cấp phần lớn các ưu điểm của BCNF như loại bỏ được các bất thường có liên đới, và điều kiện của nó có thể đạt được với Trang 71
một lược đồ CSDL tuỳ ý mà không phải bỏ đặc tính bảo toàn phụ thuộc hoặc đặc tính nối không mất. Do đó ta đưa thêm một định nghĩa khác (tương đương với định nghĩa cũ ở mục I.3 chương III) cho dạng chuẩn 3 như sau: Định nghĩa : Lược đồ quan hệ R với tập các phụ thuộc hàm F được gọi được gọi là ở dạng chuẩn 3 nếu X A đúng trên R, với A là thuộc tính không thuộc X thì hoặc X là một khóa bao hàm hoặc A là thuộc tính khóa. Chú ý rằng các định nghĩa của dạng chuẩn Boyce Codd và dạng chuẩn 3 đều giống nhau trừ mệnh đề “ hoặc A là thuộc tính khóa”, chính nó làm cho dạng chuẩn 3 bớt khắt khe hơn dạng chuẩn Boyce Codd. Giống như BCNF, về nguyên tắc, chúng ta không chỉ xét tập phụ thuộc F đã cho mà còn phải xét tất cả các phụ thuộc trong F+ để kiểm tra một vi phạm dạng chuẩn 3. Tuy nhiên chúng ta có thể chứng minh rằng nếu F chỉ chứa các phụ thuộc được phân rã sao cho các vế phải chỉ có một thuộc tính duy nhất thì chỉ cần kiểm tra những phụ thuộc của F. Nhận xét: Với mọi X A F+ mà A là thuộc tính X. Xét các điều kiện sau: (i) X  K; với K là một khóa của (R,F). (ii) A K; với K là một khóa của (R,F). Nếu thỏa (i) thì (R,F) đạt BCNF, đương nhiên nó cũng đạt 3NF. Nếu không thỏa (i) thì (R,F) vi phạm BCNF. Trang 72
Nếu thỏa (ii) thì (R,F) đạt 3NF. Nếu không thỏa cả 2 điều kiện trên thì (R,F) mới vi phạm 3NF, đương nhiên nó cũng vi phạm BCNF. Thí dụ III.6: Cho lược đồ quan hệ SAIP với các phụ thuộc SI P và S A. Ta thấy lược đồ nầy chỉ có một khóa duy nhất là SI. Xét phụ thuộc hàm S A. Ta có: - S không phải là khoá bao hàm (không thỏa i). - A là thuộc tính không khóa (không thỏa ii) Kết luận: lược đồ nầy vi phạm điều kiện 3NF. Thí dụ III.7: Xét lược đồ quan hệ R (CSZ) với các phụ thuộc hàm CS Z và Z C. Ta thấy R có 2 khóa là SC và SZ. Lược đồ nầy có dạng 3NF bởi vì tất cả các thuộc tính của nó đều là thuộc tính khóa. Do đó với phụ thuộc hàm X A F+ bất kỳ, đương nhiên thỏa điều kiện (ii). Phụ thuộc hàm Z C làm cho lược đồ vi phạm BCNF do Z không chứa một khóa nào của lược đồ. Như vậy ta có 2 định nghĩa về 3NF. Thật ra 2 định nghĩa nầy là tương đương do định lý sau: Định lý III.2: Các định nghĩa về dạng chuẩn 3 ở mục I.3 và I.5 trong chương III là tương đương. Trang 73
I.6. Ý nghĩa của dạng chuẩn Mục đích của dạng chuẩn BCNF là loại bỏ dư thừa mà các phụ thuộc hàm có thể gây ra. Giả sử rằng chúng ta có một lược đồ quan hệ R ở dạng BCNF, thế thì liệu có một dư thừa cho phép chúng ta tiên đoán giá trị của một thuộc tính bằng cách so sánh hai bộ rồi áp dụng một phụ thuộc hàm. Nghĩa là, chúng ta có hai bộ giống nhau ở một tập thuộc tính X và không giống nhau ở tập thuộc tính Y, trong khi đó ở thuộc tính A còn lại, giá trị ở một trong hai bộ này cho phép chúng ta tiên đoán giá trị trong bộ còn lại. Hai bộ này trông giống như sau: XYA x y1 a x y2 ? Ở đây, x, y1, y2 biểu diễn cho các danh sách giá trị ở các tập thuộc tính X và Y. Lưu ý phải có y1 y2 , nếu không 2 bộ trên trở thành 1 bộ. Nếu chúng ta có thể dùng phụ thuộc hàm để suy ra giá trị được chỉ ra bởi dấu chấm hỏi thì giá trị đó phải là a, và phụ thuộc được dùng phải là Z A, với Z  X. Tuy nhiên, Z không thể là một khoá bao hàm, bởi vì nếu như thế thì hai bộ ở trên sẽ là cùng một bộ, bởi vì chúng giống nhau ở Z và do phụ thuộc hàm Z Y nên y1 = y2. Vì thế, R không có dạng BCNF như đã giả thiết. Chúng ta kết luận rằng trong quan hệ có dạng BCNF, không giá trị nào có thể được tiên đoán từ những giá trị khác bằng cách chỉ dùng các phụ thuộc hàm. Dĩ nhiên, dạng chuẩn 3NF, ít khắt khe hơn BCNF, không thể loại bỏ được tất cả dư thừa. Trang 74
Một thí dụ kinh điển là lược đồ CSZ. Lược đồ này có dạng 3NF, nhưng cho phép các cặp bộ như: CZZ c s1 z ? s2 z và nhờ phụ thuộc Z C, chúng ta có thể suy ra giá trị chưa biết là c. Chú ý rằng những bộ này không vi phạm phụ thuộc CS Z. Trang 75
II. THIẾT KẾ CƠ SỞ DỮ LIỆU II.1. Phân rã một lược đồ quan hệ Thí dụ III.8: Chúng ta hãy xét lược đồ cơ sở dữ liệu chỉ gồm một quan hệ sau: SINHVIEN(MASV TENSV DIACHI MALP TENLP ) 11 Lan X CNA1 Cu nhan A1 12 Hai Y CNA1 Cu nhan A1 13 Tu Z CNA2 Cu nhan A2 - Hình III.3 – Cơ sở dữ liệu chưa phân rã – Trong lược đồ nầy có các ràng buộc (phụ thuộc hàm) sau: - Khi biết mã sinh viên ta có thể xác định duy nhất một tên, địa chỉ và mã lớp của sinh viên đó, nghĩa là có phụ thuộc hàm MASV TENSV, DIACHI, MALP. - Khi biết mã lớp có thể xác định duy nhất một tên lớp, nghĩa là có phụ thuộc hàm MALP TENLP. Khóa của lược đồ trên là MASV. Bởi vì bao đóng của {MASV} đối với hai phụ thuộc hàm trên là tập chứa tất cả các thuộc tính của lược đồ. Hơn nữa {MASV} chỉ gồm một thuộc tính nên thỏa tính “nhỏ nhất”. Ta thấy lược đồ nầy đạt 2NF do khóa chỉ có một thuộc tính nên luôn thỏa điều kiện “phụ thuộc đầy đủ vào khóa”. Nhưng lược đồ trên lại vi phạm 3NF do phụ thuộc bắc cầu MASV MALP TENLP. Vậy dạng chuẩn cao nhất mà lược đồ trên có thể đạt là 2NF. Do đó quan hệ trên có chứa các thông tin trùng lắp. Giả sử lớp “CNA1” có 100 sinh viên thì tên lớp “Cu nhan A1” sẽ lặp lại 100 lần. Trang 76
Để giải quyết vấn đề trên ta dùng phép “phân rã”, tức là tách lược đồ quan hệ trên thành các lược đồ quan hệ con với mong muốn các lược đồ quan hệ con mới nầy sẽ đạt dạng chuẩn cao hơn lược đồ quan hệ ban đầu. Như vậy sẽ giảm (hay không còn) các thông tin bị dư thừa trong các quan hệ mới. Bây giờ ta phân rã (tách) lược đồ quan hệ SINHVIEN ban đầu thành hai lược đồ quan hệ con SVIEN và LOP như sau: SVIEN(MASV TENSV DIACHI MALP) 11 Lan X CNA1 12 Hai Y CNA1 13 Tu Z CNA2 LOP(MALP TENLP ) CNA1 Cu nhan A1 CNA1 Cu nhan A1 CNA2 Cu nhan A2 - Hình III.4 – Cơ sở dữ liệu sau khi phân rã – Lược đồ quan hệ SVIEN có chứa phụ thuộc hàm MASV TENSV, DIACHI, MALP. Lược đồ nầy có khóa là MASV và đạt BCNF. Với lược đồ quan hệ LOP có chứa phụ thuộc hàm MALP TENLP. Lược đồ nầy có khóa là MALP và cũng đạt BCNF. Như vậy các lược đồ quan hệ mới đều đạt dạng chuẩn cao nhất (BCNF), cao hơn dạng chuẩn của lược đồ ban đầu (2NF). Do đó các quan hệ mới không còn chứa các thông tin trùng lắp. Trang 77
Tóm lại: Mục đích của phép phân rã là tạo ra một lược đồ cơ sở dữ liệu mới có dạng chuẩn cao hơn lược đồ cơ sở dữ liệu ban đầu. Ngoài mục đích đã nêu, ta còn mong muốn phép phân rã đạt hai yêu cầu là: - có nối không mất ( bảo toàn thông tin ) - bảo tòan phụ thuộc ( bảo toàn phụ thuộc hàm ) Hai yêu cầu nầy sẽ được nói rõ trong các phần sau. Bây giờ ta đưa ra một định nghĩa cho phép phân rã. Định nghĩa: Phân rã lược đồ quan hệ R = {A1,A2, , An} là thay nó bằng một tập ={R1,R2, , Rk} trong đó Ri là tập con của R sao cho R = R1  R2   Rk Các tập R không nhất thiết phải tách biệt. Theo thí dụ trên ta có R={MASV, TENSV, DIACHI, MALP, TENLP}. Và phép phân rã ={R1,R2} với R1= {MASV, TENSV, DIACHI, MALP } và R2= {MALP, TENLP}. Trang 78
II.2. Phân rã có nối không mất Tính nối không mất (bảo toàn thông tin) là yêu cầu quan trọng của phép phân rã. Ta xem lại thí dụ đã nêu như sau: Quan hệ cũ: R (MASV TENSV DIACHI MALP TENLP ) t1 11 Lan X CNA1 Cu nhan A1 r t2 12 Hai Y CNA1 Cu nhan A1 t3 13 Tu Z CNA2 Cu nhan A2 - Hình III.5a – Cơ sở dữ liệu chưa phân rã – Các quan hệ mới: R1 (MASV TENSV DIACHI MALP) t11 11 Lan X CNA1 r1 t12 12 Hai Y CNA1 t13 13 Tu Z CNA2 R2 ( MALP TENLP ) t21 CNA1 Cu nhan A1 r2 t22 CNA2 Cu nhan A2 - Hình III.5b – Cơ sở dữ liệu sau khi phân rã – Như vậy ta thay lược đồ R={MASV,TENSV,DIACHI, MALP,TENLP} bằng R1= {MASV,TENSV,DIACHI,MALP} và R2 = {MALP, MALP}. Giả sử r là quan hệ (thể hiện) hiện tại của lược đồ R, ta có r là tập gồm các bộ t1, t2 và t3 .Nếu CSDL sử dụng các lược đồ R1 và R2 thay cho R, vậy để chứa các thông tin hiện tại thì các quan hệ r1 của R1 và r2 của R2 sẽ gồm những bộ như Trang 79
thế nào ? Thật ra quan hệ của hai lược đồ mới này chính là hình chiếu của r trên tập các thuộc tính R1 và R2. Nghĩa là r1 = R1 (r) và r2 = R2 (r) Bạn hãy thực hiện lại phép chiếu một quan hệ lên một tập các thuộc tính như đã trình bày trong phần các phép toán đại số ở chương I. Lưu ý loại bỏ các bộ giống nhau khi chiếu r lên tập các thuộc tính của R2.Kết quả là: r1 = { t11 , t12 , t13 } và r2 = { t21 , t22 } Làm thế nào chúng ta biết được r1 và r2 chứa các thông tin giống như r ? Một cách biết được điều đó là kiểm tra xem có thể tính được r khi chỉ biết r1 và r2 hay không ? Chúng ta biết rằng cách duy nhất để hồi phục lại r là lấy nối tự nhiên của r1 và r2 .Bạn hãy tính để cho ra kết quả phép nối tự nhiên của r1 và r2 như đã trình bày trong phần các phép toán đại số ở chương I. Lưu ý trong quá trình nối phải so khớp các thuộc tính cùng tên gọi. Gọi s là kết quả của phép nối tự nhiên, tức là s = r1 * r2. Có 2 trường hợp xảy ra: (1) Nếu s r thì khi biết r1 và r2 chúng ta không có cách nào để khẳng định quan hệ gốc của lược đồ R là r hay s. Nghĩa là nếu nối tự nhiên không khôi phục được quan hệ gốc thì không có cách nào khôi phục để thu được một quan hệ duy nhất. (2) Nếu s = r tức là các lược đồ mới R1 và R2 có thể thay thế cho lược đồ R ban đầu vì khi cần thiết ta có thể khôi phục được quan hệ gốc từ các quan hệ của các lược đồ mới. Với phép phân rã luôn có được trường hợp thứ 2 với mọi quan hệ r bất kỳ của lược đồ gốc R (thỏa các phụ thuộc hàm), được gọi là phép phân rã bảo toàn thông tin hay còn gọi là phép phân rã có nối không mất. Trang 80
Bạn hãy kiểm chứng phép phân rã ở ví dụ trên đạt yêu cầu có nối không mất. II.2.1. Các nối không mất Ta xem định nghĩa sau về tính chất nối không mất của một phép phân rã. Định nghĩa: Nếu R là một lược đồ quan hệ được phân rã thành các lược đồ R1,R2, Rk và F là tập phụ thuộc hàm, ta gọi đây là phân rã không mất (ứng với F) nếu với mỗi quan hệ r của R thoả F, chúng ta có: r = R1 (r) * R2 (r) * * Rk(r) Nghĩa là mỗi quan hệ r là nối tự nhiên của các hình chiếu của nó trên các Ri. Như chúng ta đã thấy, đặc tính nối không mất là cần thiết vì quan hệ bị phân rã cần phải được khôi phục lại từ phân rã của chính nó. Lưu ý: Ta chỉ xét các quan hệ r của lược đồ R mà r thỏa F. Một số khẳng định về ánh xạ chiếu nối được trình bày trong Bổ đề III.1. Trước tiên chúng ta đưa ra một số ký hiệu. Nếu ={ R1,R2, .Rk} là một phân rã thì m là một ánh xạ được định nghĩa là m (r)= R1 (r) * R2 (r) * * Rk(r). Nghĩa là m (r) là nối tự nhiên các hình chiếu của r trên các lược đồ quan hệ trong . Vì vậy điều kiện nối không mất ứng với tập phụ thuộc F có thể diễn tả là: với mọi r thoả F, chúng ta có r = m (r). Trang 81
Bổ đề III.1: Gọi R là một lược đồ quan hệ, ={ R1,R2, .Rk} là một phân rã của R và r là một quan hệ của R, Gọi ri = ri (r) . Thế thì: a) r  m (r). b) Nếu s = m (r) thì ri (s) =ri c) m (m (r) ) = m (r). Chứng minh: a) Gọi  là một bộ thuộc r, và với mỗi i, gọi i= [Ri]. Thế thì i thuộc ri với mọi i. Theo định nghĩa của nối tự nhiên,  thuộc m (r) vì  giống i ở các thuộc tính của Ri với mọi i. b) Nếu s = m (r) thì r  s, suy ra rằng ri (r)  ri (s). Nghĩa là ri ri (s). Để chứng minh ri (s)  ri, gỉa sử rằng i thuộc ri (s) với một trị số I nào đó. Thế thì có một bộ  thuộc s sao cho [Ri]=i .Bởi vì  thuộc s, nên có bộ vj thuộc rj sao cho [Ri]= vj với mỗi j. Do vậy ở trường hợp cụ thể bên trên, [Ri] thuộc ri. Nhưng [Ri]= i nên i cũng thuộc ri. và do đó Ri (s) ri . Chúng ta kết luận rằng ri Ri (s). (c) Nếu s = m (r) thì do (b) , Ri (s) = ri. do đó m (s) = r1* r2* rk = m (r) Chúng ta nhận xét rằng nếu với mỗi i, ri là một quan hệ nào đó của Ri và s = r1* r2* rk thì ri (s) không nhất thiết phải bằng ri. Lý do là ri có thể chứa các bộ khiếm khuyết, là các bộ không khớp với bất kỳ bộ nào khi chúng ta lấy nối. Trang 82
Chẳng hạn nếu cho R1= AB, R2 = BC , r1 = {a1b1}, r2 = {b1c1, b2c2} thì s = {a1b1c1} và BC (s) = {b1c1} r2 . Nhưng nói chung Ri (s)  ri và nếu mỗi ri là chiếu của quan hệ r thì Ri(s) = ri . Khả năng lưu trữ các bộ khiếm khuyết là một ưu điểm của phân rã. Như chúng ta đã đề cập trước đây, bù lại, chúng ta phải tính toán nhiều nối hơn khi trả lời các câu vấn tin nếu có phân rã lược đồ quan hệ. Khi xem xét trên mọi phương diện, nhìn chung phân rã chỉ được sử dụng nhằm giải quyết các vấn đề đã được mô tả trong Phần II. II.2.2. Kiểm tra tính chất nối không mất Theo ví dụ trên, có thể kiểm tra một quan hệ cụ thể r của lược đồ R ( r thỏa F ) có được khôi phục bằng các quan hệ ri mới hay không. Bằng cách chiếu r lên tập các thuộc tính Ri , sau đó nối tự nhiên các hình chiếu nầy lại, cuối cùng so sánh kết quả với r ban đầu. Tuy nhiên, ta chưa thể khẳng định phép phân rã nầy là có nối không mất vì không thể kiểm tra được mọi quan hệ của R. Thuật toán sau giúp ta kiểm tra tính chất “nối không mất” của một phân rã. Thuật toán III.1: Kiểm tra tính chất nối không mất của một phân rã. NHẬP: - lược đồ quan hệ R = A1 .An - một tập phụ thuộc hàm F - một phân rã ={ R1, Rk} XUẤT: - một khẳng định có phải là một phân rã có nối không mất hay không. Trang 83
PHƯƠNG PHÁP: Bước 1: Chúng ta có n thuộc tính và k lược đồ con, nên ta xây dựng một bảng gồm n cột và k hàng: - Cột thứ j tương ứng với thuộc tính Aj - Hàng thứ i tương ứng với lược đồ quan hệ Ri. Ở vị trí hàng i và cột j, chúng ta đặt ký hiệu: - aj nếu Aj thuộc Ri - bij nếu Aj không thuộc Ri Bước 2: Xét lặp đi lặp lại mỗi phụ thuộc X Y trong F cho đến khi không còn thay đổi nào nữa trong bảng. Mỗi lần xét X Y, chúng ta tìm những hàng giống nhau ở tất cả các cột cho các thuộc tính trong X. Nếu thấy hai hàng như thế, hãy làm cho các ký hiệu của hai hàng này bằng nhau ở các thuộc tính của Y. Khi làm cho hai ký hiệu bằng nhau, nếu một trong hai ký hiệu là aj thì cho ký hiệu kia trở thành aj.Nếu hai ký hiệu là bij và bli thì có thể cho chúng trở thành bij hoặc bli một cách tuỳ ý. Điều quan trọng cần phải nhớ là khi cho hai ký hiệu bằng nhau, tất cả các xuất hiện của chúng trong bảng cũng phải cho bằng như thế; chúng ta thực hiện không đầy đủ nếu chỉ cho bằng nhau những ký hiệu nằm trong vi phạm của phụ thuộc X Y. Nếu sau khi sửa đổi các hàng của bảng như trên, chúng ta thu được một hàng a1 an (hàng chứa toàn a) thì phân rã này có nối không mất. Ngược lại đây không phải là phân rã có nối không mất . Trang 84
Thí dụ III.9: Xét lại thí dụ Hình III.5 với: Lược đồ R ={MASV,TENSV,DIACHI, MALP,TENLP} và F = { f1, f2 ) trong đó: f1 : MASV TENSV,DIACHI, MALP f2 : MALP TENLP và phân rã = { R1,R2 } trong đó: R1 = {MASV,TENSV,DIACHI,MALP} R2 = {MALP, MALP}. Để kiểm tra xem phân rã nầy có đặc tính có nối không mất hay không ? Áp dụng thuật giải trên ta thực hiện các bước sau: Bước 1: lập bảng khởi đầu - điền các giá trị ai và bij như sau: R MASV TENSV DIACHI MALP TENLP R1 a1 a2 a3 a4 b15 R2 b21 b22 b23 a4 a5 Vì MASV có trong R1 nên tại hàng 1 cột 1 ta có giá trị a1 Ngược lại MASV không có trong R2 nên tại hàng 2 cột 1 ta có giá trị b21 Bước 2: sửa lại dữ liệu sao cho thỏa các phụ thuộc hàm trong F. Bạn hãy xem bảng trên là một quan hệ (thể hiện) r nào đó của lược đồ quan hệ R. Quan hệ nầy gồm có các bộ sau: t1 = ( a1, a2, a3 , a4 , b15 ) và t2 = ( b21, b22, b23, a4 , a5 ) Bộ t1 cho thông tin sau: sinh viên có mã số là “a1” có tên là “a2”, Trang 85
Vấn đề đặt ra là quan hệ r với giá trị của các bộ như trên có thỏa các phụ thuộc hàm trong F hay không ? Nếu không, ta phải sửa lại các giá trị để r thỏa F. Ta hãy xét lần lược các phụ thuộc hàm trong F. - Xét f1 : MASV TENSV,DIACHI, MALP X Y Ta có: t1.MASV = (a1 ) (b21 ) = t2.MASV Vậy hai bộ là khác nhau ở vế X nên r thỏa f1. - Xét f2 : MALP TENLP X Y Ta có: t1.MALP = (a4 ) = (a4 ) = t2.MALP (giống X) nhưng: t1.TENLP = (b15 ) (a5 ) = t2.TENLP (khác Y) Quan hệ trên có hai bộ có giá trị giống nhau ở các thuộc tính thuộc vế X, nhưng khác nhau ở các thuộc tính thuộc vế Y nên r vi phạm f2. Vậy ta phải sửa lại các giá trị sao cho quan hệ trên không còn vi phạm f2. Sửa lại giá trị thuộc tính TENLP của bộ t1 từ “b15 ” thành “a5 ”. Lưu ý: chỉ sửa giá trị các thuộc tính trong vế Y và ưu tiên chọn aj .Bảng mới như sau: R MASV TENSV DIACHI MALP TENLP R1 a1 a2 a3 a4 a5 R2 b21 b22 b23 a4 a5 Sau khi sửa ta thấy quan hệ nầy thỏa f2. Ta dừng thuật toán ở đây và kết luận đây là một phân rã có nối không mất vì ta phát hiện được một dòng (dòng thứ 1 ) có các giá trị gồm toàn a là (a1, a2, a3, a4, a5 ). Trang 86
Thí dụ III.10: Xét lại phân rã R = SAIP thành R1 = SA và R2 = SIP. Các phụ thuộc là S A và SI P, và bảng khởi đầu là: R S A I P R1 a1 a2 b13 b14 R2 a1 b22 a3 a4 Bởi vì S A là hai hàng giống nhau ở cột S, chúng ta có thể làm cho các gía trị của cột A bằng nhau, cho b22 thành a2 . Bảng kết quả là: R S A I P R1 a1 a2 b13 b14 R2 a1 a2 a3 a4 Bởi vì hàng thứ hai đều là a, đây là nối không mất. Thí dụ III.11: Xét phân rã R = SAIP thành R1 = SAP và R2 = SI. Các phụ thuộc là S A và SI P, và bảng khởi đầu là: R S A I P R1 a1 a2 b13 a4 R2 a1 b22 a3 b24 Bởi vì S A là hai hàng giống nhau ở cột S, chúng ta có thể làm cho các gía trị của cột A bằng nhau, cho b22 thành a2 . Trang 87
Bảng kết quả là: R S A I P R1 a1 a2 b13 a4 R2 a1 a2 a3 b24 - Hình III.7 – Quan hệ nầy cũng thỏa SI P bởi vì giá trị các thuộc tính ở vế trái phụ thuộc hàm (SI) của hai bộ là khác nhau. Ta thấy quan hệ nầy thỏa tất cả các phụ thuộc hàm, nhưng không có dòng nào gồm toàn a, nên đây không phải là phân rã có nối không mất. Nhận xét: Bạn hãy xem bảng kết quả cuối cùng Hình III.7 là một quan hệ r nào đó của lược đồ R. Quan hệ nầy gồm các bộ sau: t1 = ( a1, a2, b13 , a4 ) và t2 = ( a1, a2, a3, b24 ) Ta có: - r thỏa tất cả các phụ thuộc hàm - bộ ( a1, a2, a3 , a4 ) r (*) Ta cũng có ( a1, a2, a4 ) SAP (r) và ( a1, a3) SI (r) do bảng ban đầu đã xuất hiện các giá trị “a” tại cột ứng với các thuộc tính của dòng đại diện cho lược đồ con tương ứng, và giá trị “a” không thay đổi trong quá trình chạy thuật toán (chỉ sửa “b” thành “a”). Nên theo kết quả của phép nối tự nhiên ta có ( a1, a2, a3, a4 ) SAP (r) * SI (r) ( ). Tóm lại: do (*) và ( ) ta có SAP (r) * SI (r) r, nên theo định nghĩa đây không phải là phân rã có nối không mất. Trang 88
Thí dụ III.12: Một thí dụ khác phức tạp hơn, gọi R = ABCDE và R1 = AD, R2 = AB, R3 = BE, R4 = CDE và R5 = AE. Giả sử có các phụ thuộc hàm: A C DE C B C CE A C D Bảng khởi đầu được trình bày trong Hình III.8a. Chúng ta có thể áp dụng A C để cho các ký hiệu b13, b23 và b53 bằng nhau. Sau đó chúng ta dùng B C để cho các ký hiệu này bằng bới b33 : kết quả được trình bày trong Hình III.8b, trong đó b13 được chọn làm ký hiệu đại diện. Bây giờ chúng ta dùng C D để cho các ký hiệu a4 , b24, b34 và b54 bằng nhau; ký hiệu kết quả phải là a4. Thế rồi DE C cho phép chúng ta cho b13 bằng với a3, và CE A cho b31 và b41 bằng với a4. Kết quả được trình bày trong Hình III.8c. Bởi vì hàng giữa đều là a nên phân rã này có tính chất nối không mất. Bạn đọc có thể tưởng lầm rằng chúng ta có thể đơn giản hoá Thuật toán III.1 bằng cách chỉ cho bằng nhau khi một trong các ký hiệu là ai. Thí dụ trên cho thấy rằng nhận định như thế là không đúng; nếu chúng ta không cho b13 ,b23 và b53 bằng nhau, chúng ta không bao giờ thu được một hàng chỉ chứa toàn a. a) R A B C D E R1 a1 b12 b13 a4 b15 R2 a1 a2 b23 b24 b25 R3 b31 a2 b33 b34 a5 R4 b41 b42 a3 a4 a5 R5 a1 b52 b53 b54 a5 Trang 89
b) R A B C D E R1 a1 b12 b13 a4 b15 R2 a1 a2 b13 b24 b25 R3 b31 a2 b13 b34 a5 R4 b41 b42 a3 a4 a5 R5 a1 b52 b13 b54 a5 c) R A B C D E R1 a1 b12 a3 a4 b15 R2 a1 a2 a3 a4 b25 R3 a1 a2 a3 a4 a5 R4 a1 b42 a3 a4 a5 R5 a1 b52 a3 a4 a5 - Hình III.8 – Định lý III.3 : Thuật toán III.1 xác định chính xác một phân rã có hay không có tính chất nối không mất. Chứng minh: Giả sử bảng cuối cùng sinh ra từ Thuật toán III.1 không có các hàng có toàn a. Chúng ta có thể xem bảng này như một quan hệ r của lược đồ R; các hàng là các bộ, và aj , bij là các giá trị riêng biệt, mỗi giá trị được lấy từ miền của thuộc tính Aj. Quan hệ r thoả phụ thuộc F bởi vì Thuật toán III.1 sửa đổi bảng mỗi khi tìm thấy một vi phạm. Chúng ta khẳng định rằng r m (r). Rõ ràng r không chứa bộ a1 ,a2 an. Nhưng đối với mỗi lược đồ Ri có một bộ  trong r, đó chính là bộ ở hàng i, sao cho i{Ri} chứa toàn a.Vì vậy nối của các Ri (r )chứa bộ có toàn a, vì ràng bộ này giống I với mọi i. Chúng ta kết luận rằng nếu bảng cuối cùng của Thuật toán III.1 không có một Trang 90
hàng nào chứa toàn a thì phân rã không có tính chất nối không mất; chúng ta đã tìm ra một quan hệ r của R thỏa F mà m (r) r. Ngược lại, giả sử rằng bảng cuối cùng có một hàng toàn a. Nói chung chúng ta có thể xem một bảng T bất kỳ như là một dạng biểu diễn hình ảnh của biểu thức phép tính quan hệ miền: {a1 ,a2 an (b11) (bkn)(R(wi)  R(wk))} (III.1) trong đó wi là hàng thứ i của T. Khi T là bảng khởi đầu, công thức (III.1) định nghĩa hàm m . Thật vậy, chú ý rằng m (r) chứa bộ a1 ,a2 an nếu và chỉ nếu với mỗi i, r chứa một bộ có aj ở thành phần thứ j nếu Aj là một thuộc tính của Ri và trong mỗi thuộc tính khác là một giá trị nào đó được biểu thị bằng bij . Bởi vì chúng ta giả sử rằng mọi quan hệ r của lược đồ R đều thoả các phụ thuộc F, chúng ta có thể suy ra rằng mỗi phép biến đổi do Thuật toán III.1 thực hiện trên bảng (bằng cách đồng nhất các ký hiệu) đều được tiến hành mà không ảnh hưởng đến tập các bộ được tạo ra bởi (công thức III.1), miễn là biểu thức đó thay đổi để phản ảnh các thay đổi của bảng. Phép chúng minh khẳng định này rất phức tạp, nhưng ý tưởng thì rõ ràng; chúng ta chỉ làm đồng nhất những ký hiệu nếu trong công thức III.1, chúng được áp dụng cho một quan hệ r thoả F, những ký hiệu này chỉ được gán cùng một giá trị bằng một cách nào đó. Bởi vì cuối cùng có một hàng chứa toàn a, biểu thức phép tính miền cho bảng này có dạng: {a1 an (b11) (bkn) (R(a1 an )  )} (III.2) Rõ ràng giá trị của (công thức III.2), khi được áp dụng cho quan hệ r của R, là một tập con của r. Tuy nhiên, nếu thoả F thì giá trị của (III.2) là m (r) và theo Bổ đề III.1a, r  m (r) . Vì thế khi r thoả F, (III.2) tính được chính r, vì thế r = m (r) . Điều đó nói lên rằng phân rã có nối không mất ứng với F. Trang 91
Thuật toán III.1 có thể áp dụng cho các phân rã với số lượng lược đồ bất kỳ. Tuy nhiên, đối với các phân rã thành hai lược đồ, chúng ta có một phép kiểm tra đơn giản hơn, đó là nội dung của định lý sau đây. Định lý III.4: Nếu = (R1,R2) là một phân rã của R, và F là tập các phụ thuộc hàm, thì có nối không mất ứng với F nếu và chỉ nếu (R1 R2) (R1- R2) hoặc (R1 R2) (R2-R1). Chú ý rằng những phụ thuộc này không nhất thiết thuộc tập F; chỉ cần chúng thuộc F+. R1 R2 R1- R2 R2-R1 hàng cho R1 aa .a aa .a bb .b hàng cho R2 aa .a bb .b aa .a - Hình III.9 – Một bảng hai hàng tổng quát – Chứng minh: Bảng khởi đầu, được sử dụng trong Thuật toán III.1, được trình bày trong Hình III.9, chúng ta đã lược bỏ những chỉ số trên a và b vì không quan trọng. Bằng phép qui nạp trên số lượng ký hiệu được xác định bằng thuật toán III.1 chúng ta có thể chứng minh rằng nếu ký hiệu b trên cột của thuộc tính A bị đổi thành a, thì A thuộc + (R1R2) . Đồng thời cũng bằng phép qui nạp trên số các bước cần để chứng minh biểu thức (R1 R2) Y nhờ các tiên đề Armstrong, chúng ta cũng có thể chứng minh rằng mọi ký hiệu b trong các cột của Y được đổi thành a. Vì vậy toàn bộ hàng cho R1 trở thành a nếu và chỉ nếu + R2-R1 (R1 R2) nghĩa là (R1 R2) (R2-R1) , và tương tự, toàn bộ hàng cho R2 trở thành a nếu và chỉ nếu (R1 R2) (R1- R2). Trang 92
Thí dụ III.13: Giả sử R = ABC và F = {A B}. Thế thì phân rã thành R1 = AB và R2 = AC có nối không mất bởi vì: R1  R2 = AB  AC = A R1 – R2 = AB – AC = B, và A B đúng nghĩa là phụ + thuộc hàm (R1 R2) (R1 – R2) thuộc F . Tuy nhiên nếu chúng ta phân rã R thành R1 = AB và R2 = BC không phải là có nối không mất bởi vì: R1  R2 = AB  BC = B R1 – R2 = AB – AC = A, và B A không đúng nghĩa là + phụ thuộc hàm (R1 R2) (R1– R2) không thuộc F . R2 – R1 = AC – AB = C, và B C không đúng nghĩa là + phụ thuộc hàm (R1 R2) (R2– R1) cũng không thuộc F . Chúng ta có thể thấy được bằng cách xét quan hệ r = {a1b1c1, a2b1c2} của R. Thế thì AB (r) * BC (r) = {a1b1c1, a1b1c2, a2b1c1, a2b1c2} Đó là một tập bao hàm thật sự của r. Trang 93
II.3. Phân rã bảo toàn phụ thuộc Chúng ta đã hiểu được rằng một phân rã cần phải có đặc tính nối không mất vì nó cho phép khôi phục lại một quan hệ ban đầu từ các hình chiếu của nó. Một đặc tính quan trọng khác của phân rã = (R1, , Rk) của lược đồ quan hệ R là có thể suy ra được tập phụ thuộc F của R từ các hình chỉếu của F trên các Ri. Cho lược đồ quan hệ R và F là tập các phụ thuộc hàm. Cho phân rã = (R1, Rk). Ta có các định nghĩa sau. Định nghĩa: Hình chiếu của F trên một tập các thuộc tính Z ký hiệu + là Z(F) là tập các phụ thuộc X Y thuộc F sao cho XY  Z ( chú ý rằng X Y không nhất thiết thuộc F; chỉ cần thuộc F+). Định nghĩa: Ta nói phân rã có bảo toàn tập phụ thuộc hàm F nếu hợp của tất cả các phụ thuộc trong các hình chiếu của F trên các lược đồ con tương đương với F. Gọi Fi = Ri (F), với i = 1, 2, , k k Đặt G = F1  F2   Fk = 1 Fk Theo định nghĩa thì: có bảo toàn phụ thuộc G ≡ F Nhắc lại G ≡ F (G tương đương F) nghĩa là G+ = F+ . Lý do cần bảo toàn tập F đó là vì các phụ thuộc trong F có thể được xem là các ràng buộc toàn vẹn (intergrity constraint) cho lược đồ quan hệ R. Nếu các phụ thuộc hình chiếu không suy ra được F thì khi biểu diễn R bằng =(R1 Rk ) chúng ta có thể thấy rằng giá trị hiện hành của các Ri có thể biểu diễn một quan hệ R không thoả F, ngay cả nếu có nối không mất ứng với F. Trang 94
Khi đó mỗi thao tác cập nhật trên một Ri, sẽ cần phải thực hiện một phép nối để kiểm tra lại rằng các ràng buộc không bị vi phạm. Thí dụ III.14: Chúng ta hãy xét Thí dụ “Sắp thời khóa biểu” trong đó chúng ta có các thuộc tính Phòng học (P), Giờ học (G), và Môn học (M). Theo qui định thì mỗi môn học chỉ được bố trí học vào 1 phòng học duy nhất, do đó có phụ thuộc hàm M P. Lưu ý mỗi môn học có thể học ở những giờ khác nhau. Đương nhiên với 1 phòng và 1 giờ cụ thể ta chỉ có thể sắp cho 1 môn học duy nhất, do đó có phụ thuộc hàm PG M. Phân rã của lược đồ quan hệ PGM thành GM và PM có nối không mất, bởi vì (GM  PM ) (PM – GM ) nghĩa là M P. Tuy nhiên, chiếu của F = {PG M,M P} trên GM chỉ cho những phụ thuộc tầm thường (suy ra từ tính phản xạ), còn chiếu trên PM cho ra M P và những phụ thuộc tầm thường khác. Chúng ta có thể thấy rằng M P và các phụ thuộc tầm thường không suy ra PG M được, vì thế phân rã này không bảo toàn các phụ thuộc. Chẳng hạn nối hai quan hệ trong Hình III.10(a) và (b) là quan hệ của Hình III.10 (c). Hình III.10(a) thỏa các phụ thuộc tầm thường như mọi quan hệ khác. Hình III.10(b) thỏa các phụ thuộc tầm thường và phụ thuộc M P.Tuy nhiên nối của chúng trong Hình III.10(c) vi phạm PG M. GMPM T.hai.7.00-9.30 CSDL P.101 CSDL T.hai.7.00-9.30 TKCSDL P.101 TKCSDL (a) (b) Trang 95
PGM P.101 T.hai.7.00-9.30 CSDL P.101 T.hai.7.00-9.30 TKCSDL (c) - Hình III.10 – Một nốI vi phạm phụ thuộc hàm – Nhận xét: Giả sử chúng ta sử dụng hai lược đồ con PG và PM để lưu trữ thông tin thay vì sử dụng lược đồ ban đầu PGM. Vì phân rã nầy là không bảo toàn phụ thuộc (bị mất phụ thuộc hàm) nên các lược đồ con sẽ không chứa một phụ thuộc hàm nào đó, ở đây là PG M bị mất. Khi nhập dữ liệu vào các lược đồ con ta không thể kiểm tra được phụ thuộc hàm PG M mà chỉ kiểm tra được phụ thuộc hàm M P. Do đó khi ta khôi phục lại quan hệ ban đầu bằng cách lấy nối tự nhiên của hai quan hệ con, ta thấy quan hệ nầy có thể vi phạm phụ thuộc PG M. Để có thể kiểm tra được phụ thuộc PG M, mỗi khi có thao tác nhập liệu trên các quan hệ con, ta phải lấy nối tự nhiên để tạo ra quan hệ ban đầu có đầy đủ các thuộc tính. Quan hệ có đủ các thuộc tính nầy chắc chắn chứa phụ thuộc PG M, nên ta có thể kiểm tra dữ liệu có thỏa phụ thuộc nầy hay không. Với một phép phân rã có bảo toàn phụ thuộc thì ta không cần thực hiện phép nối để kiểm tra các phụ thuộc trong F khi có thao tác nhập liệu trên các quan hệ con. Bởi vì các phụ thuộc hàm được chứa trên các lược đồ con thì tương đương với tập phụ thuộc hàm ban đầu F. Trang 96
Do đó khi có thao tác nhập liệu vào một quan hệ con của lược đồ Ri nào đó ta chỉ cần kiểm tra các phụ thuộc trong hình chiếu của F trên Ri là đủ, đó là Fi . Khi đó kết quả nối tự nhiên của các quan hệ con đương nhiên sẽ thỏa tất cá các phụ thuộc hàm trong F vì hợp các Fi sẽ tương đương với F. Thí dụ III.15: Chúng ta nên nhớ rằng một phân rã có thể có nối không mất ứng với một tập các phụ thuộc F nhưng không bảo toàn tập phụ thuộc hàm F như ví dụ trên. Sau đây ta xét một phân rã bảo toàn phụ thuộc nhưng lại không có tính chất nối không mất. Chẳng hạn như trường hợp F = {A B, C D}, R = ABCD, và ={AB,CD}. Phép phân rã nầy có hai lược đồ con, để kiểm tra tính nối không mất ta áp dụng định lý III.4. Vì R1  R2 = AB  CD =  nên không có phụ thuộc hàm dạng R1  R2 R1 – R2 hay R1  R2 R2 – R1 . Do đó phân rã nầy không có đặc tính nối không mất. Để kiểm tra tính bảo toàn phụ thuộc ta có: F1 = R1 (F) = AB (F) = { A B } và F2 = R2 (F) = CD (F) = { C D} Nên G = F1  F2 = { A B, C D} Theo định nghĩa thì phép phân rã trên có bảo toàn phụ thuộc vì G ≡ F II.3.1. Kiểm tra tính bảo toàn phụ thuộc Về nguyên tắc chúng ta có thể kiểm tra xem một phân rã = ( R1, ,Rk) có bảo toàn tập phụ thuộc F hay không. Chúng + ta chỉ cần tính F rồi chiếu nó trên tất cả các thành phần Ri. Sau đó lấy hợp của các tập phụ thuộc kết quả rồi kiểm tra xem tập này có tương đương với F hay không. Trang 97
Tuy nhiên trong thực tế, tính F+ là một công việc hết sức khó khăn vì số lượng các phụ thuộc chứa trong nó thường là hàm mũ theo kích thước của F. Nhưng có một cách để kiểm tra tính bảo toàn này mà không cần phải tính F+ ; phương pháp này có chi phí thời gian tỷ lệ với hàm đa thức theo kích thước của F. Thuật toán III.2: Kiểm tra tính bảo toàn các phụ thuộc. NHẬP: Một phân rã = ( R1, ,Rk) và tập các phụ thuộc F. XUẤT: Một khẳng định là có bảo toàn F hay không. PHƯƠNG PHÁP: k Chúng ta gọi G là  i=1 Ri (F). Chú ý rằng chúng ta không tính G; đơn giản chúng ta muốn xem nó có tương đương F hay không. Nhắc lại: do bổ đề II.4 ta có G ≡ F  (i) G  F+ và (ii) F  G+ Điều kiện (i) là hiển nhiên là do định nghĩa của phép chiếu F trên các Ri . Do đó để kiểm tra xem G có tương đương F hay không, ta chỉ cần kiểm tra điều kiện (ii). Để kiểm tra (ii), ta phải xét mỗi phụ thuộc X Y trong F và xác định xem X Y có thuộc G+ hay không. Tương đương với việc tính X+ (bao đóng của X) đối với các phụ thuộc hàm trong G, sau đó xét X+ có chứa Y hay không. Thủ thuật để tính X+ mà không cần có G là xét lặp đi lặp lại kết quả tính bao đóng X+ ứng với các hình chiếu của F trên các Ri. Trang 98
Chúng ta định nghĩa phép toán R trên các thuộc tính Z ứng với một tập phụ thuộc F là phép thế Z = Z  (Z  R)+  R), bao đóng được lấy ứng với F. Phép toán này nối Z với những thuộc tính A sao cho (Z  R) A thuộc R(F). Do đó chúng ta tính X+ ứng với G bằng cách khởi đầu với X, qua danh sách các Ri, ta lần lượt thực hiện các phép toán Ri với mỗi i. Nếu tại một vòng nào đó không có phép toán Ri nào làm thay đổi các tập thuộc tính hiện có thì chúng ta đã thực hiện xong: tập kết quả là X+. Về hình thức, thuật toán được viết là: Z := X While “ vẫn còn thay đổi với Z ” do For i := 1 to k do + Z := Z  (( Z  Ri)  Ri ) /* bao đóng được lấy ứng với F */ Nếu Y là một tập con của Z, là kết quả thực hiện các bước trên, thì X Y thuộc G+.Nếu mỗi X Y thuộc F đều thuộc G+, thuật toán trả lời “yes”, ngược lại thuật toán trả lời “no”. Thí dụ III.16: Xét tập các thuộc tính ABCD với phân rã {AB, BC, CD} và tập các phụ thuộc F= {A B, B C, C D ,D A}. Nghĩa là trong F+, mỗi thuộc tính đều xác định tất cả các thuộc tính còn lại. Lúc đầu chúng ta không nhận được phụ thuộc D A, nhưng điều đó không đúng. Khi chiếu F, thực sự chúng ta đã chiếu F+ trên các lược đồ quan hệ, vì thế chiếu trên AB chúng ta không chỉ thu được A B mà còn thu được B A. Tương tự, chúng ta có được C B thuộc BC(F) và D C thuộc CD(F), và ba phụ thuộc này suy ra được D A. Trang 99
Vì thế chúng ta có thể hy vọng rằng thuật toán 7.3 sẽ cho phép khẳng định rằng D A được suy ra từ: G = B(F)  BC(F)  CD(F) Chúng ta khởi đầu với Z = {D}. Áp dụng phép toán AB không thêm được thuộc tính nào bởi vì {D} (({D}  {A,B}+  {A,B}) cũng chỉ là {D}. Tương tự, phép toán BC cũng không làm thay đổi Z. Tuy nhiên khi chúng ta áp dụng phép toán CD thì thu được Z = {D} (({D}  {CD}+  {C,D}) = {D} ({D}+  {C,D}) = {D} ({A,B,C,D}  {C,D}) = {C,D} Tương tự ở vòng kế phép toán BC được áp dụng cho Z = {C,D} cho ra Z = {B,C,D}, và ở dòng thứ ba, phép toán AB đặt Z thành {A,B,C,D},sau đó không thay đổi Z được nữa. Vì thế ứng với G, {D}+ = {A,B,C,D}có chứa A nên chúng ta kết luận rằng D A thuộc G+. Bạn hãy kiểm tra rằng các phần tử khác của F cũng thuộc G+ ( thực sự chúng thuộc G). Do đó chúng ta kết luận rằng phân rã này bảo toàn được tập phụ thuộc F. Định lý III.5 : Thuật toán III.2 xác định chính xác X Y có thuộc G+ hay không. Trang 100
Chứng minh: Mỗi lần chúng ta thêm một thuộc tính vào Z, chúng ta đều sử dụng một phụ thuộc trong G, vì thế khi thuật toán trả lời “yes”, nó phải đúng nghĩa là X Y là hệ quả của G. Ngược lại, giả sử X Y thuộc G+. Thế thì có một chuỗi các bước mà qua đó, bằng cách dùng Thuật toán tính bao đóng để lấy bao đóng của X ứng với G, cuối cùng chúng ta sẽ gom tụ được tất cả các thuộc tính của Y. Mỗi bước này đều có sử dụng một phụ thuộc trong G, và phụ thuộc đó phải thuộc Ri (F) với một trị số i nào đó. Bởi vì G là hợp của chúng. Gọi một phụ thuộc như thế là U V. Dùng phép quy nạp trên số các phụ thuộc được áp dụng trong Thuật toán bao đóng để chứng minh rằng cuối cùng thi U trở thành một tập con của Z, và trong vòng kế tiếp, phép toán R, chắc chắn sẽ thêm vào Z tất cả các thuộc tính của V nếu chúng chưa có trong đó. II.4. Phân rã có nối không mất thành dạng BCNF Cho đến giờ chúng ta đã giới thiệu qua những đặc tính cần có đối với các lược đồ quan hệ: BCNF hoặc yếu hơn là 3NF. Trong phần II.2 và II.3 chúng ta thấy hai đặc tính tổng quát quan trọng nhất của các lược đồ cơ sở dữ liệu, đặc tính nối không mất và đặc tính bảo toàn phụ thuộc. Bây giờ sẽ kết hợp những ý tưởng này lại với nhau, nghĩa là xây dựng những lược đồ cơ sở dữ liệu có những đặc tính mong muốn cho lược đồ cơ sở dữ liệu và đối với mỗi lược đồ quan hệ cũng có những đặc tính mong muốn cho lược đồ quan hệ. Trang 101
Chúng ta sẽ nhận thấy rằng mọi lược đồ quan hệ đều có một phân rã không mất thành dạng chuẩn Boyce-Codd và nó cũng có thể phân rã thành dạng 3NF có nối không mất và vẫn bảo toàn phụ thuộc. Tuy nhiên có lẽ không có một phân rã nào cho một lược đồ quan hệ thành dạng Boyce-Codd mà vẫn bảo toàn được phụ thuộc. Lược đồ quan hệ CSZ là một thí dụ điển hình. Nó không có dạng Boyce-Codd bởi vì phụ thuộc Z C đúng, nhưng nếu chúng ta phân rã CSZ theo một cách sao cho CSZ không phải là một trong những lược đồ trong phân rã này thì phụ thuộc CS Z không suy ra được từ các phụ thuộc hình chiếu. Trước khi đưa ra thuật toán phân rã, chúng ta cần đến đặc tính của các phân rã nối không mất như dưới đây: Bổ đề III.2: Giả sử R là một lược đồ quan hệ với các phụ thuộc hàm F. Gọi = (R1, ,Rn) là một phân rã của R có nối không mất ứng với F, và gọi = (S1,S2) là một phân rã có nối không mất của R1 ứng với R1 (F). Thế thì phân rã của R thành (S1,S2,R2, ,Rn) cũng có nối không mất ứng với F. Chứng minh: Giả sử chúng ta lấy quan hệ r của R rồi chiếu nó trên R1, ,Rn để thu được các quan hệ tương ứng là r1, rn . Sau đó lại chiếu r1 trên S1và S2 để có s1,s2. Đặc tính nối không mất cho phép nối s1,và s2 để khôi phục chính xác r1 rồi chúng ta có thể nối r1, r2, , rn để khôi phục lại r. Bởi vì nối tự nhiên có tính kết hợp và thứ tự trong đó chúng ta thực hiện phép nối không là vấn đề quan trọng , vì thế chúng ta có thể khôi phục lại r mà không phụ thuộc vào thứ tự chúng ta lấy các nối của s1,s2,r1, rn . Chúng ta có thể sử dụng Bổ đề III.2 để xây dựng Thuật toán phân rã một lược đồ quan hệ R thành BCNF, tuy đơn giản nhưng tốn khá nhiều thời gian. Trang 102
Nếu chúng ta tìm thấy một vi phạm BCNF trong F, gọi là X A, chúng ta phân rã R thành các lược đồ R – A và XA. Cả hai đều nhỏ hơn R, bởi vì XA không thể là tất cả các thuộc tính của R (nếu thế thì X chắc chắn là khoá bao hàm, nên X A sẽ không vi phạm BCNF). Theo định lý III.4, phân rã R – A và XA có nối không mất, bởi vì giao của hai lược đồ là X, và X XA. Chúng ta tính chiếu của các phụ thuộc của R trên R – A và XA rồi lại áp dụng bước phân rã trên cho các lược đồ. Bổ đề III.2 khẳng định rằng tập lược đồ thu được bằng cách phân rã cho đến khi tất cả các lược đồ đều có dạng BCNF sẽ là một phân rã không mất. Vấn đề là phép chiếu các phụ thuộc có thể có chi phí thời gian tỷ lệ hàm mà theo kích thước của lược đồ R và tập phụ thuộc ban đầu. Tuy nhiên, chúng ta cũng có một cách để tìm một phân rã nối không mất thành những lược đồ có dạng BCNF với chi phí thời gian tỷ lệ hàm đa thức theo kích thước của tập phụ thuộc và lược đồ quan hệ. Có điều kỹ thuật này đôi khi lại phân rã một quan hệ đã có dạng BCNF. Bổ đề tiếp theo đưa ra một số đặc tính khác của các lược đồ BCNF. Bổ đề III.3: a) Mỗi lược đồ có hai thuộc tính đều có dạng BCNF. b) Nếu R không có dạng BCNF thì chúng ta có thể tìm được các thuộc tính A và B trong R sao cho (R – AB) A. Phụ thuộc (R – AB) B có thể cũng đúng trong trường hợp này. Trang 103
Chứng minh: Đối với trường hợp (a), gọi AB là một lược đồ. Ở lược đồ này chỉ có hai phụ thuộc không tầm thường có thể đúng : A B và B A. Nếu không có phụ thuộc nào đúng thì chắc chắn không có vi phạm BCNF. Nếu chỉ A B đúng thì A là một khoá, vì thế chúng ta không có vi phạm nào. Nếu chỉ B A đúng thì B là khoá, vì nếu cả hai đúng, cả A và B đều là khoá, vì thế không bao giờ có vi phạm BCNF. Đối với trường hợp (b), giả sử có một vi phạm X A trong R. Thế thì R phải có một thuộc tính B không thuộc XA, nếu không thì X là một khoá bao hàm, và X A không phải là vi phạm. Do đó (R – AB) A chính là điều phải chứng minh. Bổ đề III.3 cho chúng ta tìm các vi phạm BCNF trong một lược đồ quan hệ R có n thuộc tính bằng cách chỉ xét n(n1)/2 cặp thuộc tính {A,B} và tính bao đóng của R – AB ứng với tập phụ thuộc F đã cho. Như đã khẳng định, thuật toán đó thực hiện với thời gian O(n2), nhưng một dữ liệu được thiết kế cẩn thận có thể làm cho nó chạy nhanh hơn, với thời gian là O(n); dù sao, chi phí thời gian cũng là hàm da thức theo kích thước của R. Nếu không tồn tại A hoặc B sao cho (R- AB)+ chứa A hoặc B thì theo Bổ đề III.3(b), chúng ta biết rằng R có dạng BCNF. Điều quan trọng cần phải biết rằng đảo lại sẽ không đúng. Có thể R có dạng BCNF nhưng vẫn có một cặp {A,B} như trên. Chẳng hạn nếu R = ABC, và F = {C A, C B} thì R có dạng BCNF, nhưng R – AB = C, và xác định được A ( và cả B). Trước khi phân tích thuật toán phân rã BCNF, chúng ta cần có một ghi nhận nữa về hình chiếu của các phụ thuộc, cụ thể là: Trang 104
Bổ đề III.4: Nếu chúng ta có một tập phụ thuộc F trên R và chúng ta chiếu các phụ thuộc trên R1  R để được F1 rồi lại chiếu F1 trên R2  R1 để được F2 thì F2 = R2 (F) Nghĩa là chúng ta có thể giả sử rằng F là tập phụ thuộc của R1, dù rằng F có thể có những thuộc tính không có trong R1. Chứng minh: + Nếu XY R2 thì X Y thuộc F nếu và chỉ nếu nó + thuộc F1 . Bổ đề III.4 có môt hệ quả hết sức quan trọng. Đó là , nếu chúng ta phân rã các lược đồ quan hệ như trong Bổ đề III.2 thì thật sự chúng ta không bao giờ phải tính những phụ thuộc hình chiếu trong quá trình phân rã. Nghĩa là chúng ta chỉ sử dụng các phụ thuộc đã cho, lấy các bao đóng của tập thuộc tính khi cần thiết chứ không phải tính tất cả các hình chiếu của các phụ thuộc, là thuật toán có chi phí hàm mũ theo số lượng thuộc tính trong lược đồ. Chính nhận xét này và bổ đề III.3(b) cho phép chúng ta thực hiện , với chi phí thời gian là hàm đa thức theo kích thước của lược đồ và các phụ thuộc đã cho, nhằm tìm ra được một phân rã thành dạng BCNF có nối không mất cho lược đồ. Trang 105
Thuật toán III.3: Phân rã nối không mất thành dạng chuẩn Boyce-Codd. NHẬP: Lược đồ quan hệ R và các phụ thuộc hàm F. XUẤT: Một phân rã của R có nối không mất, sao cho mỗi lược đồ quan hệ trong phân rã có dạng Boyce-Codd ứng với hình chiếu của F trên lược đồ đó. PHƯƠNG PHÁP: Trọng tâm của thuật toán là lấy lược đồ quan hệ R rồi phân rã nó thành hai lược đồ. Một lược đồ có tập các thuộc tính XA; nó có dạng BCNF và phụ thuộc X A đúng. Lược đồ thứ hai sẽ là R – A, do đó nối của R – A với XA là nối không mất. Thực hiện đệ qui thủ tục phân rã, với R – A ở vị trí của R cho đến khi chúng ta đạt được một lược đồ đáp ứng được các điều kiện của Bổ đề III.3(b); chúng ta biết rằng lược đồ này có dạng BCNF. Thế thì bổ đề III.2 bảo đảm rằng lược đồ này cộng với các lược đồ BCNF được tạo ra từ mỗi bước đệ qui có nối không mất. Z:= Ri /* bất kỳ lúc nào Z cũng là một lược đồ của phân rã mà có thể không có dạng BCNF */ Repeat Phân rã Z thành Z – A và XA, trong đó XA có dạng BCNF và X A; /* sử dụng thủ tục con của Hình 7,6(b) */ thêm XA vào phân rã; Z := Z - Ai Until không thể phân rã Z bằng Bổ đề 7.7(b); Thêm Z vào trong phân rã Trang 106
(a) Chương trình chính. If không chứa A và B sao cho A thuộc (Z – AB)+ then cần nhớ rằng tất cả các bao đóng được lấy ứng với F */ return thông báo rằng Z có dạng BCNF và không phân rã được. else begin tìm một cặp A và B Y := Z; While Y chứa A và B sao cho (Y- AB) A do Y := Y – B; Return phân rã Z – A và Y; /* ở đây Y là XA trong chương trình chính */ end (b) Thủ tục phân rã - Hình III.11 – Chi tiết của thuật toán III.3 – Chi tiết Thuật toán được trình bày trong Hình III.11. Hình III.11 (a) là thủ tục chính, nó phân rã lặp đi lặp lại lược đồ quan hệ Z chưa biết là có dạng BCNF hay không; khởi đầu Z là R. Hình III.11 (b) là thủ tục phân rã, nó xác định không thể phân rã được Z hoặc phân rã Z thành Z – A và XA trong đó X A. Tập thuộc tính được chọn bằng cách khởi đầu với Y = Z, loại bỏ B lặp đi lặp lại, là thuộc tính trong cặp AB sao cho X A, trong đó X = Y – AB. Cần nhớ rằng X B đúng hay sai là điều không quan trọng. Trang 107
Thí dụ III.17: Chúng ta hãy xét lược đồ quan hệ CTHRSG, với: C = course (lớp, khoá học) T = teacher (giảng viên) H = hour (giờ học) R = room (phòng học) S = student (sinh viên) G = grade (điểm số). Các phụ thuộc hàm F chúng ta giả sử tồn tại là: C TMỗi khoá có một giảng viên HR C Tại một giờ học, một phòng chỉ có một lớp HT R Tại một giờ học, một giảng viên chỉ có mặt tại trong một phòng học CS G Mỗi sinh viên có một điểm số cho mỗi khoá. HS R Tại một giờ học, một sinh viên chỉ có mặt tại một phòng học. Bởi vì thuật toán III.3 không xác định thứ tự xét cặp AB, chúng ta sẽ đưa ra một chiến lược thống nhất theo thứ tự CTHRSG cho các thuộc tính và sử dụng lần lượt thuộc tính đầu tiên, rồi đến thuộc tính thứ hai, rồi thứ ba, v.v Chúng ta bắt đầu với toàn bộ lược đồ CTHRSG, và cặp đầu tiên được xét đến là CT. Chúng ta thấy rằng (HRSG)+ chứa C; nó cũng chứa T, nhưng không quan trọng. Do đó chúng ta bắt đầu vòng lặp while của Hình III.11 (b) với A = C, B = T, và Y = CHRSG. Bây giờ chúng ta thử cặp CH vào vai trò {A,B} nhưng (RSG)+ không chứa C lẫn H. chúng ta gặp may nhờ cặp kế tiếp là CR, bởi vì (HSG)+ chứa R. Vì vậy chúng ta có A = R, B = C, và chúng ta đặt Y là HRSG, bằng cách bỏ đi B như thường lệ. Với Y = HRSG chúng ta không gặp may cho đến khi chúng ta thử cặp RG, khi đó chúng ta tìm thấy (HS)+ chứa R. Vì vậy chúng ta có A = R và B = G, và Y được gán cho HRS. Trang 108
Tại điểm này, chúng ta không loại được thuộc tính nào khác ra khỏi Y, bởi vì phép kiểm tra của Bổ đề III.3(b) không thành công trên mỗi cặp trong HRS. Do vậy chúng ta có thể phân rã CTHRSG thành 1. HRS, có vai trò của XA, với X = HS và A = R 2. Z = CTHRSG – R, đó là CTHSG Bây giờ chúng ta thực hiện trên Z = CTHSG trong chương trình chính. Danh sách các cặp AB và các tập thuộc tính còn lại sau khi đã loại bỏ B là: 1. Trong CTHSG: A = T, B = H, để lại Y = CTSG 2. Trong CTSG: A = T, B = S, để lại Y = CTG 3. Trong CTG: A = T, B = G, để lại Y = CT Chắc chắn rằng CT có dạng BCNF do Bổ đề III.3 (a). Vì thế chúng ta thêm CT vào phân rã. Thuộc tính T đóng vai trò của A, vì thế trong chương trình chính chúng ta loại T đi và chuyển sang lược đồ Z = CHSG, là một lược đồ không có dạng Boyce-Codd. Trong CHSG, cặp thành công đầu tiên là A = G và B = H, để lại Y = CSG. Chúng ta không tìm được cặp nào cho phép phân rã lược đồ này theo Bổ đề III.3 (b), vì thế chúng ta thêm CSG vào trong phân rã, rồi áp dụng chương trình chính cho lược đồ đã loại bỏ A, nghĩa là Z = CHS. Chúng ta thấy rằng lược đồ này không thể phân rã được nhờ Bổ đề III.3 (b), do vậy nó cũng thuộc dạng BCNF, và chúng ta kết thúc. Chú ý rằng chúng ta thu được các nối không mất tại mỗi bước nếu chúng ta tổ hợp các lược đồ theo thứ tự ngược lại với thứ tự tìm thấy chúng. Nghĩa là: CHS * CSG là nối không mất nhờ phụ thuộc CS G CHSG * CT là nối không mất nhờ phụ thuộc C T, và CTHSG * HRS là nối không bị mất nhờ HS R. Trang 109
Trong mỗi trường hợp trên, phụ thuộc hàm cần phải có là phụ thuộc có dạng X A đã được xây dựng bởi thủ tục của Hình III.11 (b). Theo Bổ đề III.2, các nối này bảo đảm rằng phân rã đầy đủ (HRS, CT, CSG, CHS) có nối không mất. CÁC VẤN ĐỀ NẢY SINH TRONG CÁC PHÂN RÃ BCNF “TUỲ TIỆN” Trong phân rã của Thí dụ III.17 bốn lược đồ quan hệ trên lưu lại các loại thông tin sau: 1. Vị trí (phòng học) của mỗi sinh viên tại mỗi giờ học (lược đồ HRS). 2. Giảng viên của mỗi lớp (lược đồ CT) 3. Điểm cho khoá học của sinh viên (lược đồ CSG) 4. Thời khoá biểu các khoá học và giờ học cho mỗi sinh viên (lược đồ CHS) Các thông tin thu được không như kết quả thiết kế như khi chúng ta thực hiện phân rã nối không mất thành BCNF theo cách thủ công. Cụ thể là chúng ta không thể biết phòng học cho một khoá học nếu không nối các quan hệ CHS và HRS lại, và thậm chí không thể tìm ra phòng nếu không có sinh viên nào lấy khoá học đó. Có thể chúng ta sẽ thay HRS bằng CHR. Nó cho phép phân bổ các phòng học theo khoá học chứ không phải theo sinh viên, và phù hợp với các thời khoá biểu được sử dụng trong nhiều trường. Không may là, câu hỏi về “giá trị” của các phân rã khác nhau không phải là mục tiêu của lý thuyết này. Nếu không có sẵn một lược đồ cụ thể mà chỉ cần xác nhận lại rằng nó có một nối không mất và mỗi lược đồ thành phần có dạng BCNF, thế thì chúng ta có thể chọn cặp AB ngẫu nhiên trong Thuật toán III.3 với hy vọng rằng sau một vài lần chọn thử như thế, chúng ta sẽ thu được một phân rã có vẻ “tự nhiên”. Trang 110
Một vấn đề khác liên quan đến phân rã được chọn là một số phụ thuộc trong F, cụ thể là TH R và HR C không được bảo toàn trong phân rã này. Nghĩa là, hình chiếu của F trên HRS, CT, CSG và CHS là bao đóng của các phụ thuộc sau (bạn hãy kiểm chứng được điều này). CS G HS R C T HS C Chú ý rằng phụ thuộc cuối cùng, HS C, thuộc hình chiếu của F trên CHS nhưng không phải là một phụ thuộc cho trước; ba phần tử còn lại là của chính F. Bốn phụ thuộc này không kéo theo TH R hoặc HR C. Chẳng hạn quan hệ của CTHRSG được trình bày dưới đây không thoả TH R lẫn HR C, nhưng hình chiếu của nó trên HRS, CT, CSG và CHS thoả tất cả các phụ thuộc được chiếu. C THRSG c1 t h r1 s1 g1 c2 t h r2 s2 g2 c1 t h r1 s3 g3 HIỆU QUẢ CỦA PHÂN RÃ BCNF Chúng ta thấy rằng Thuật toán III.3 có chi phí thời gian là một hàm đa thức theo n, là chiều dài của lược đồ quan hệ R và các phụ thuộc F. Chúng ta cũng đã nhận xét rằng thuật toán tính bao đóng ứng với F có chi phí thời gian là hàm đa thức theo n; sự thực chỉ cần O(n) nếu sử dụng các cấu trúc dữ liệu đặc biệt. Thủ tục của Hình III.11 (b) chạy trên một tập con Z của các thuộc tính, mà chắc chắn không thể có nhiều hơn n thuộc tính. Mỗi lần chạy qua vòng lặp. tập Y giảm kích thước, vì thế chỉ có tối đa n vòng lặp. Cũng chỉ có tối đa n2 cặp thuộc tính A và B, vì thế phép kiểm tra (Y – AB) A được thực hiện tối đa n3 lần. Bởi vì phép kiểm tra này có chi phí theo hàm đa thức, và thời gian đó chiếm ưu thế trong thân vòng lặp, chúng Trang 111
ta kết luận rằng Thuật toán của Hình III.11 (b) thực hiện với thời gian theo hàm đa thức. Chi phí chủ yếu của chương trình chính của Hình III.11 (a) là gọi thủ tục con, và lời gọi này được thực hiện chỉ một lần cho mỗi lần thực hiện vòng lặp. Bởi vì Z giảm kích thước khi đi qua vòng lặp, tối đa có thể n vòng, vì thế toàn bộ thuật toán có chi phí theo hàm đa thức II.5. Phân rã thành 3NF có bảo toàn phụ thuộc Từ các Thí dụ III.6 và III.7, chúng ta đã thấy là không phải lúc nào cũng có thể phân rã một lược đồ thành dạng BCNF mà vẫn bảo toàn được các phụ thuộc. Tuy nhiên chúng ta luôn có thể tìm được một phân rã bảo toàn phụ thuộc thành dạng chuẩn cấp ba như thuật toán và định lý sau sẽ chứng minh. Thuật toán III.4: Phân rã bảo toàn phụ thuộc thành dạng chuẩn cấp ba. NHẬP: Lược đồ quan hệ R và tập phụ thuộc F, chúng ta có thể giả sử rằng F là phủ cực tiểu mà không mất đi tính tông quát. XUẤT: Một phân rã bảo toàn phụ thuộc của R sao cho mỗi lược đồ quan hệ đều có dạng 3NF ứng với hình chiếu của F trên lược đồ đó. PHƯƠNG PHÁP: Nếu có những thuộc tính của R không nằm trong một phụ thuộc nào của F dù ở vế phải hay trái, thì về nguyên tắc, mỗi thuộc tính nhưng thế đều có thể tạo ra một lược đồ và chúng ta có thể loại chúng ra khỏi R. Trang 112
Nếu một trong những phụ thuộc trong F có chứa tất cả các thuộc tính của R thì kết xuất chính là R. Ngược lại, phân rã kết xuất sẽ chứa lược đồ XA cho mỗi phụ thuộc X A trong F. Thí dụ III.18: Xét lại lược đồ CTHRSG của Thí dụ III.17, các phụ thuộc của nó có phủ cực tiểu F: C T CS G HR C HS R HT R Thuật toán III.4 sinh ra tập lược đồ quan hệ CT, CHR, THR, CSG và HRS. Định lý III.6: Thuật toán III.4 tạo một phân rã bảo toàn phụ thuộc thành dạng chuẩn cấp ba. Chứng minh: Bởi vì các phụ thuộc hình chiếu có chứa phủ của F, phân rã rõ rànglà bảo toàn phụ thuộc. Chúng ta phải chứng minh rằng lược đồ quan hệ YB, đối với mỗi phụ thuộc hàm Y B trong phủ cực tiểu, đều có dạng 3NF. Giả sử X A vi phạm 3NF trong YB; nghĩa là A không thuộc X, X không phải là khoá bao hàm của YB, và A làthuộc tính không tham gia khóa. Dĩ nhiên, chúng ta cũng biết rằng XA  YB, và X A được suy ra từ F. Chúng ta xét hai trường hợp, tuỳ vào A = B hay không. Trang 113
Trường hợp 1: A = B. Bởi vì A không thuộc X, chúng ta biết X  Y, và bởi vì X không phải là khoá bao hàm của YB, X phải là một tập con thật sự của Y. nhưng thế thì X B, và cũng là X A, có thể thay thế Y B trong phủ cực tiểu, mâu thuẫn với giả thiết rằng Y B là thành phần của phủ cực tiểu đã cho. Trường hợp 2: A B. Bởi vì Y là khoá bao hàm của YB, nên phải tồn tại một tập Z  Y là khoá của YB. Nhưng A thuộc Y, bởi vì chúng ta đang giả sử rằng A B, và A không thể thuộc Z vì A là phi nguyên tố. Do vậy Z là một tập con thực sự của Y, nên Z B có thể thay thế Y B trong phủ cực tiểu, cũng dẫn đến mâu thuẫn. Chúng ta cũng có thể hiệu chỉnh Thuật toán III.4 nhằm tránh các phân rã không cần thiết nếu X A1, .,X An ở vị trí của n lược đồ quan hệ XA1, .,XAn. Phần này dành cho bạn đọc tự chứng minh rằng lược đồ XA1 .An có dạng 3NF. II.6. Phân rã thành 3NF bảo toàn phụ thuộc và có nối không mất Như đã phân tích, chúng ta có thể dùng Thuật toán III.3 để phân rã một lược đồ quan hệ R bất kỳ thành một tập các lược đồ = (R1, , Rk) sao cho có nối không mất và mỗi Ri có dạng BCNF (vì thế có dạng 3NF). Hơn nữa, chúng ta cũng có thể dùng Thuật toán III.4 để phân rã R thành  = (S1, , Sm) sao cho  bảo toàn tập phụ thuộc F, và mỗi Sj có dạng 3NF. Liệu chúng ta có thể tìm được một phân rã thành 3NF mà vẫn có hai đặc tính bảo toàn phụ thuộc và nối không mất? Thật ra chúng ta có thể dùng Thuật toán III.4 để phân rã R thành , sau đó chỉ cần nối vào  một lược đồ quan hệ X, là khoá của R như định lý sau sẽ trình bày. Trang 114
Định lý III.7: Gọi  là một phân rã dạng 3NF của R được xây dựng bằng Thuật toán III.4, và X là khóa của R. Thế thì    X là một phân rã của R mà tất cả các lược đồ quan hệ đều có dạng 3NF; phân rã này có đặc tính bảo toàn phụ thuộc và nối không mất. Chứng minh: Có thể chứng minh được rằng bất kỳ vi phạm của 3NF nào trong X cũng khẳng định rằng một tập con thực sự của X xác định được X, và như thế xác định được R, do vậy X không thể là khoá trong trường hợp này. Vì thế X, cũng như các phần tử của , phải có dạng 3NF. Rõ ràng là  bảo toàn phụ thuộc vì  bảo toàn phụ thuộc. Để chứng minh rằng  có nối không mất, chúng ta xây dựng các bảng áp dụng Thuật toán III.1. Chúng ta có thể chứng minh rằng toàn bộ hàng của X sẽ trở thành a như sau. Xét thứ tự A1,A2, Ak , là thứ tự khi thêm các thuộc tính của R-X vào X+ trong thuật toán tính bao đóng. Chắc chắn rằng cuối cùng thì tất cả thuộc tính sẽ được thêm vào bởi vì X là khoá. Chúng ta chứng minh bằng quy nạp trên i rằng cột tương ứng với Ai trong hàng của X được đặt bằng ai trong phép kiểm của Thuật toán III.1. Bước cơ sở i = 0 là hiển nhiên. Giả sử rằng kết quả đúng + với i-1. Thế thì Ai được thêm vào X do có một phụ thuộc hàm Y Ai, trong đó: Y X  {A1, Ai-1} Thế thì YAi thuộc , và các hàng cho YAi và X giống nhau ở Y (tất cả đều là a) sau khi các cột cho A1, Ai-1 ở hàng X được đặt là các a. Vì thế những hàng này đuợc biến đổi thành giống nhau ở thuộc tính Ai trong khi thực hiện Thuật toán III.1. Bởi vì hàng YAi có ký hiệu ai nên hàng X cũng thế. Trang 115
Hiển nhiên là trong một số trường hợp,  không phải là tập lược đồ quan hệ nhỏ nhất có các đặc tính của Định lý III.7. Chúng ta có thể xoá bỏ các lược đồ quan hệ trong , mỗi lần một lược đồ, miễn là vẫn bảo toàn được các đặc tính mong muốn. Kết quả có thể là nhiều lược đồ CSDL, tuỳ thuộc vào thứ tự loại bỏ lược đồ, bởi vì loại bỏ một lược đồ có thể ngăn cản việc loại bỏ các lược đồ khác. Thí dụ III.19: Chúng ta có thể lấy hợp của lược đồ CSDL của CTHRSG được tạo ra trong Thí dụ III.18 với khoá SH, thu được một phân rã nối không mất và bảo toàn phụ thuộc. Tình cờ, SH lại là tập con của HRS, là một trong những lược đồ quan hệ có trong phân rã. Vì thế chúng ta có thể loại bỏ SH và chấp nhận lược đồ CSDL của Thí dụ 7.18, nghĩa là (CT, CHR, THR, CSG, HRS) Mặt dù một số tập con của tập gồm năm lược đồ quan hệ này là những phân rã có nối không mất, chúng ta có thể kiểm chứng rằng các phụ thuộc được chiếu trên bốn trong năm lược đồ này không khẳng định được tập phụ thuộc F. II.7. Một số vấn đề cần lưu ý khi phân rã Với những công cụ đã cho như Thuật toán III.3 và III.4, chúng ta thường bị “cám dỗ” phải phân rã các lược đồ quan hệ. Điều quan trọng cần nhớ là không phải mọi phân rã có nối không mất đều hữu ích, thậm chí một số còn có hại. Sai lầm hay gặp nhất là đi phân rã một lược đồ đã có dạng BCNF chỉ vì dường như có một phân rã có nối không mất và bảo toàn phụ thuộc. Trang 116
Chẳng hạn chúng ta có thể có một quan hệ cung cấp thông tin về nhân viên, giả tỉ như mã số nhân viên I, tên nhân viên N, gian hàng D và lương S.Bởi vì I là khoá duy nhất trong trường hợp này, chúng ta có I A với mọi thuộc tính A. Vì vậy hoàn toàn có thể phân rã lược đồ này thành IN, ID và IS.Dễ dàng thấy rằng phân rã này có nối không mất vì I, thuộc tính duy nhất trong phần giao của mỗi cặp, xác định tất cả các thuộc tính; cũng rõ ràng là nó bảo toàn phụ thuộc I NDS. Tuy nhiên chính lược đồ INDS lại có dạng BCNF, và có những ưu điểm khi phải trả lời những vấn tin có liên quan đến những thuộc tính khác I. Chẳng hạn nếu chúng ta muốn biết tên và lương của tất cả nhân viên của gian hàng đồ chơi trẻ em, chúng ta phải nối IN*ID*IS của lược đồ đã phân rã, nhưng có thể trả lời được câu hỏi mà không cần lấy bất cứ nối nào nếu chúng ta để nguyên lược đồ quan hệ cũ (và với một chỉ mục trên gian hàng D, chúng ta có thể trả lời câu vấn tin này hết sức hiệu quả). Hơn nữa, lược đồ được phân rã đòi hỏi rằng mã số nhân viên được lập lại ở nhiều vị trí mặc dù nó không phải là dư thừa. Tóm lại, khi áp dụng lý thuyết phân rã chúng ta cần phải nhớ rằng phân rã là “cứu cánh”, được sử dụng để giải quyết các vấn đề dư thừa và bất thường, chứ không phải là mục đích. Khi áp dụng Thuật toán III.3, chúng ta nên tránh phân rã nếu lược đồ đã có BCNF. Khi sử dụng Thuật toán III.4, chúng ta nên xem xét đến việc tổ hợp các lược đồ quan hệ được tạo ra nếu không có vi phạm 3NF. Trang 117
Chương IV: THIẾT KẾ CSDL Ở MỨC LOGIC I. MỤC ĐÍCH Quá trình thiết kế cơ sở dữ liệu bao gồm 3 giai đoạn tương ứng với 3 mức: Mức quan niệm : CÁI GÌ ? Xác định nội dung của CSDL Mức lôgic Chuẩn bị cho giai đoạn sau Mức vật lý NHƯ THẾ NÀO ? Chọn lựa cách cài đặt nội dung với một phần mềm cụ thể Giai đoạn thiết kế logic là một bước trung gian, nhằm chuẩn bị cho việc lựa chọn ở giai đoạn vật lý được dễ dàng. Đây hãy còn là một giai đoạn làm việc độc lập với các đặc trưng của phần mềm sẽ dùng sau này. Không những nó cần thiết trong trường hợp người thiết kế dùng một mô hình CSDL quan niệm (như mô hình dữ liệu quan hệ ) khác với mô hình CSDL của phần mềm (như mô hình dữ liệu mạng hoặc phân cấp ), mà còn cần thiết cả khi phần mềm cài đặt là một hệ quản trị CSDL quan hệ. Trang 118
Thí dụ IV.1: Cho cấu trúc quan niệm, kết quả của giai đoạn thiết kế quan niệm, như sau: Nhanvien (MANV, HOTENNV, MAPH) Tân từ: Mỗi nhân viên có một mã số (MANV) để phân biệt với các nhân viên khác, có họ và tên (HOTENNV) của nhân viên và trực thuộc một phòng (MAPH) Phong (MAPH, TENPH) Tân từ: Mỗi phòng ban có một mã số (MAPH) để phân biệt với các phòng khác, có tên phòng (TENPH) Dean (MADA, TENDA, MAPH) Tân từ: Mỗi đề án có một mã số (MADA) để phân biệt với các đề án khác, có tên đề án (TENDA) và đề án nầy được phụ trách bởi một phòng (MAPH) Phancong (MANV, MADA) với ràng buộc là một nhân viên được phân công vào tất cả đề án do phòng mà nhân viên đó trực thuộc phụ trách. Tân từ: Mỗi nhân viên có thể được phân công thực hiện nhiều đề án và ngược lại mỗi đề án có thể do nhiều nhân viên thực hiện. ++ Nếu phần mềm sẽ được dùng là một hệ quản trị cơ sở dữ liệu mạng, thì cần phải biểu diễn cấu trúc trên theo mô hình dữ liệu mạng như sau: Trang 119
Phong DS_NV_PH DS_DA_PH Nhanvien Dean DS_PC_NV DS_PC_DA Phancong - Hình IV.1 –Một cấu trúc lôgic theo mô hình DL mạng– Việc xác định cấu trúc trên sẽ được thực hiện trong giai đoạn thiết kế lôgic. Nếu một hệ quản trị CSDL quan hệ được dùng để cài đặt và nếu các quan hệ được khai báo y nguyên như trong cấu trúc quan niệm thì việc khai thác CSDL sau này có nhiều khả năng sẽ không được hiệu quả. Thật vậy, thao tác quan trọng thường xảy ra nhất trong một CSDL quan hệ là phép kết. Để thao tác này được thực hiện một cách hiệu quả, hệ quản trị CSDL dựa trên các chỉ mục của các quan hệ liên quan. Do đó, vai trò của người thiết kế là làm thế nào xác định được đủ các chỉ mục cần thiết với số thuộc tính đúng và vừa đủ để khai thác: chỉ mục bao gồm nhiều thuộc tính không cần thiết hoặc tạo ra quá nhiều chỉ mục sẽ gây tốn chỗ và tốn kém trong việc bảo trì hệ thống chỉ mục, và tất nhiên dẫn đến hậu quả là CSDL sẽ hoạt động chậm chạp. Trang 120
Cân nhắc để chọn lựa tạo chỉ mục nào sẽ được thực hiện trong giai đoạn thiết kế vật lý, tuy nhiên giai đoạn thiết kế lôgic sẽ chọn một biểu diễn ở dạng đồ thị để tạo việc cân nhắc đó được dễ dàng về sau. Dạng biểu diễn đồ thị này còn cho phép làm nổi bật các thuộc tính chung giữa 2 hay nhiều quan hệ (vì đây là cơ sở của phép kết), qua đó giúp cho người thiết kế sau này dễ dàng đánh giá và cân nhắc, cho những chỉ mục. Trong quá trình xác định cấu trúc lôgic của CSDL, người thiết kế cần chú ý cấu trúc kết quả phải hoàn toàn trung thực với cấu trúc quan niệm, cụ thể là các điều kiện sau cần được bảo đảm: Bảo toàn nội dung CSDL: Nội dung đã được xác định ở mức quan niệm phải được tôn trọng đầy đủ trong cấu trúc lôgic. Đây là một yêu cầu hiển nhiên, vì nội dung CSDL đã được phân tích, chọn lọc kỹ trong những giai đoạn phân tích nhu cầu và thiết kế quan niệm trước đó. Bảo toàn sự truy xuất “trực tiếp” đến các quan hệ cấu trúc quan niệm: Khi một lược đồ quan hệ con Ri hiện diện trong lược đồ cơ sở dữ liệu ở cấu trúc quan niệm, một bộ trong một thể hiện của Ri có thể được truy xuất thẳng, không thông qua một quan hệ nào khác. Cấu trúc lôgic không được thay đổi khả năng truy xuất đó. Bảo toàn tính hiệu quả trong việc kiểm tra ràng buộc toàn vẹn: Giai đoạn thiết kế quan niệm đã có chú ý đến yếu tố này thông qua tiêu chuẩn dạng chuẩn và bảo toàn phụ thuộc hàm. Cấu trúc lôgic cũng phải tôn trọng kết quả này. Trang 121
Thí dụ IV.2: Dựa trên cấu trúc quan niệm của Thí dụ IV.1, dưới đây là một số cấu trúc lôgic (được diễn đạt bằng mô hình quan hệ): Cấu trúc bảo toàn nội dung: Nhanvien (MANV, HOTENNV, MAPH) Phong (MAPH, TENPH) Da (MADA, TENDA) Phutrach (MADA, MAPH) Với ràng buộc toàn vẹn đi kèm quan hệ Phancong, ta có thể tìm thấy đầy đủ những bộ của quan hệ này qua quan hệ suy diễn sau: Nhanvien * Phutrach [MANV, MADA] Đây là phép nối tự nhiên giữa hai quan hệ Nhanvien và Phutrach, hai quan hệ nầy có thuộc tính chung là MAPH. Do đó, về mặt nội dung, nếu không cài đặt quan hệ Phancong, thông tin được lưu trong CSDL cũng không vì lý do đó mà bị thiếu. Cấu trúc không bảo toàn nội dung : Nhanvien (MANV, HOTENNV, MAPH) Phong (MAPH, TENPH) Da (MADA, TENDA) Cấu trúc nầy không bảo toàn nội dung vì thiếu thông tin của Dean (MADA, MAPH) Cấu trúc không bảo toàn truy xuất : Nhanvien (MANV, HOTENNV, MAPH) Phong (MAPH, TENPH) Da (MADA, TENDA) Phutrach (MADA, MAPH) Trang 122
Với cấu trúc nầy, ta không thể truy xuất trực tiếp đến quan hệ Phancong (MANV, MADA) như cấu trúc ở mức quan niệm, mà phải thông quan một phép kết giữa Nhanvien và Phutrach. Tuy quan hệ Phancong thừa về mặt nội dung, nhưng nó đã hiện diện trong cấu trúc quan niệm, nghĩa là đã được cân nhắc kỹ. Sự hiện diện đó có nghĩa các bộ của Phancong cần được truy xuất thẳng, chứ không phải tính toán từ những quan hệ khác. Nếu Phancong không hiện diện trong cấu trúc lôgic thì khả năng truy xuất thẳng cũng bị mất đi. Cấu trúc bảo toàn tính hiệu quả: Nhanvien (MANV, HOTENNV, MAPH) Phong (MAPH, TENPH) Da (MADA, TENDA) Phutrach (MADA, MAPH) Phancong (MANV, MADA) Tóm lại, giai đoạn thiết kế lôgic sẽ nhằm mục tiêu xác định một dạng biểu diễn đồ thị thỏa các điều kiện như đã trình bày ở trên. Nếu sau này, một hệ quản trị CSDL mạng được dùng để cài đặt thì việc chuyển từ dạng đồ thị này sang dạng biểu diễn mạng trở nên hiển nhiên. Chương này nhằm chủ yếu cho việc cài đặt với một hệ quản trị CSDL quan hệ, là phần mềm được dùng phổ biến hiện nay. Trang 123
II. BIỄU DIỄN CẤU TRÚC QUAN NIỆM DƯỚI DẠNG ĐỒ THỊ II.1. Một số khái niệm trong lý thuyết đồ thị Đồ thị: Một đồ thị ĐT (N, C) được định nghĩa trên một tập nút N = (n1, n2, , nn) và 1 tập cung C = (c1, c2, , cm). - Nếu hiện diện cung có hướng, đó là đồ thị có hướng, và các nút được gọi là nút đi hoặc nút đến. - Nếu tất cả cung là vô hướng, đó là đồ thị vô hướng, và các nút được gọi là nút xuất phát. Cung kề cận: Hai cung (c1, c2) được gọi là kề cận nhau khi: - đối với đồ thị vô hướng: chúng có chung một nút xuất phát; - đối với đồ thị có hướng: nút đến của c1 là nút đi của c2. Khuyên: Cung c là một khuyên nếu hai nút đi/đến (hoặc xuất phát) của c là một. Đường đi (đối với đồ thị vô hướng): Đó là một chuỗi cung (c1, c2, cp) sao cho: - ci và ci+1 có chung một nút xuất phát. - nếu ci không phải là khuyên hoặc cung đầu hoặc cung cuối thì ci có chung 1 nút xuất phát với ci-1 và nút xuất phát còn lại của ci cũng là nút xuất phát của ci+1 . ++ Một nút xuất phát của c1 (cung đầu trong chuỗi) không chung một nút xuất phát của c2 được gọi là nút đầu của đường đi. Trang 124
++ Một nút xuất phát của cp (cung cuối trong chuỗi) không chung một nút xuất phát của cp-1 được gọi là nút cuối của đường đi. Thí dụ IV.3: 2 c2 c c 1 1 3 3 4 c4 5 - Hình IV.2 –Một đồ thị vô hướng– - (c1, c2, c3, c4,) không phải là một đường đi - (c1, c3, c4,) là một đường đi với 1 là nút đầu và 5 là nút cuối. Mạch đi:(đối với đồ thị có hướng): Đó là một chuỗi cung (c1, c2, , cp) sao cho nút đến của cung ci-1 là nút đi của cung ci, với i p. Chu trình:(đối với đồ thị có hướng): Là mạch đi trong đó: - nút đầu và nút cuối trùng nhau - 1 cung không xuất hiện 2 lần trong chuỗi. Trang 125
Hai đường đi / mạch đi khác nhau khi chúng không có một cung chung nào. Một dòng có gốc n1 là một tập cung D=(c1, c2, , cp) sao cho : - một cung trong tập đó có nút xuất phát (hoặc nút đi) là n1 - ci, ni, nút xuất phát (hoặc nút đi/đến) của ci thuộc một đường đi (hoặc mạch đi)có nút đầu là n1, nút cuối là ni và gồm các cung của tập D. Thí dụ IV.4: n1 c1 n2 c2 n3 (c1, c2) là một dòng có gốc n1 (c1, c2) không phải là một dòng có gốc n2 n’1 c’1 n’2 c’2 n’3 (c’1, c’2) là một dòng có gốc n’1 (c’1, c’2) cũng là một dòng có gốc n’2 hoặc n’3 n4 c3 n5 c4 n6 (c3, c4 ) không phải là dòng của gốc nào cả. II.2. Đồ thị con đường truy xuất II.2.1. Định nghĩa Đồ thị con đường truy xuất (N, C, Q, Cđ, f, g, h, i, j) là một đồ thị có hướng với: N : tập nút C  (N x N) : tập cung có hướng Q : tập quan hệ Qi Trang 126
Cđ : tập các con đường truy xuất N : tập các số tư nhiên f: N Q : đơn ánh g: C Q : ánh xạ h: C Cđ : song ánh i: Cđ N x N x N : ánh xạ; N là tập các số tự nhiên j: N {0,1} : ánh xạ; khi j (ni)=1 thì ni là một nút vào. Điều kiện : f(N )  g(C) = Q QN được gọi là quan hệ nút nếu ni thuộc đồ thị con đường truy xuất sao cho: f (ni ) = QN QC được gọi là quan hệ cung nếu cj thuộc đồ thị con đường truy xuất sao cho: g (cj) = QC -1 Tồn tại tối đa 2 cung thuộc g (QC), 2 cung này có 2 chiều ngược nhau, nút đi của cung thứ nhất là nút đến của cung thứ hai và ngược lại. Ký hiệu : - cung : hoặc > - nút:  - nút vào:  II.2.2. Diễn giải cij *Ni Nj từ một quan hệ nút f (Ni ) có thể truy xuất đến một bộ của quan hệ nút f (Nj) thông qua con đường truy xuất h(cij) Trên mỗi con đường truy xuất có gắn 1 tổ hợp (x1, x2, x3) qua ánh xạ i(cdij): đó là x1 : số bộ tối thiểu x2 : số bộ trung bình x3 : số bộ tối đa Trang 127
của quan hệ nút f (Nj ) có thể truy xuất được từ 1 bộ của quan hệ nút f (Ni ) Thí dụ IV.5: Nhanvien_2 MANV //HOTENNV (1,1,1) Thuoc(MANV,MAPH) (1,-,n) Phong_2 MAPH Phancong(MADA,MANV) //TENPH (1,-,n) (1,1,1) (0,-,n) Phutrach(MADA,MAPH) MADA //TENDA Dean_2 - Hình IV.3 –Một đồ thị các con đường truy xuất– Có 2 ngõ vào CSDL: đó là Nhanvien_2 và Dean_2, nghĩa là ta có thể cung cấp giá trị của mã nhân viên để truy xuất ngay một bộ tương ứng trong quan hệ Nhanvien_2. Phong_2 không phải là một ngõ vào, nghĩa là mỗi khi muốn truy xuất một phòng cụ thể, ta phải hoặc duyệt tuần tự các bộ của Phong_2 để tìm, hoặc thông qua một con đường truy xuất đến từ Nhanvien_2 hoặc Dean_2. Từ một bộ của Nhanvien_2, ta có thể truy xuất trực tiếp một bộ của Phong_2 mà nhân viên trực thuộc, thông qua con đường truy xuất Nhanvien_2 Phong_2, ngược lại ta cũng Trang 128
có thể có ngay danh sách nhân viên của một phòng thông qua con đường truy xuất Phong_2 Nhanvien_2 .Nhưng ta không thể truy xuất trực tiếp danh sách đề án mà một nhân viên được phân công vào làm việc, vì không có con đường truy xuất Nhanvien_2 Dean_2; tất nhiên ta vẫn có thể có được danh sách trên một cách gián tiếp, chẳng hạn thông qua các con đường truy xuất Nhanvien_2 Phong_2 Dean_2 nếu có ràng buộc toàn vẹn trên quan hệ Phân công như đã ghi trong Thí dụ IV.1. Trong đồ thị con đường truy xuất, có một đồ thị đặc bịêt trong đó, giữa hai nút của đồ thị, nếu có một cung thì bao giờ cũng có một cung theo chiều ngược lại, và tất cả các nút là những nút vào: đó là đồ thị con đường truy xuất thô. Với đồ thị của Hình IV.3, nếu từ nút Đề án 2 đến nút Nhân viên_2 có thêm một con đường truy xuất, và nếu nút Phòng_2 cũng là nút vào thì đồ thị trở thành đồ thị con đường truy xuất thô. II.3. Đồ thị quan hệ Trong quá trình chuyển sang dạng biểu diễn đồ thị, một cấu trúc quan niệm có thể được biểu diễn thành nhiều đồ thị khác nhau, nhưng phải tôn trọng tiêu chuẩn của một biểu diễn trung thực (bảo toàn nội dung, bảo toàn tính truy xuất “ trực tiếp”, bảo toàn tính hiệu quả trong kiểm tra RBTV); tuy vậy không phải tất cả đều có những hiệu quả khai thác hoàn toàn như nhau. Một đồ thị con đường truy xuất được đơn giản hoá sẽ giúp người thiết kế đánh giá dễ dàng chất lượng của dạng biểu diễn đồ thị này: đó là đồ thị quan hệ. Khi xác định dạng biểu diễn đồ thị của một cấu trúc quan niệm thành 2 bước: 1. đồ thị quan hệ. 2. đồ thị con đường truy xuất. Trang 129
Người thiết kế có thể lần lượt phân tích các vấn đề đặt ra trong giai đoạn này dưới 2 khía cạnh: 1.khía cạnh quan niệm trước tiên, với công cụ phân tích là đồ thị quan hệ. 2.rồi đến khía cạnh phương tiện truy xuất dữ liệu, với công cụ phân tích là đồ thị con đường truy xuất. II.3.1. Định nghĩa Một đồ thị quan hệ là một đồ thị có hướng, được định nghĩa trên (NQ,CQ,QQ, fQ, gQ, kQ) với: NQ : tập nút CQ  NQ x NQ : tập cung có hướng hoặc không QQ : tập quan hệ Qi fQ :NQ QQ : đơn ánh gQ :CQ QQ : đơn ánh kQ :CQ {0,1} : ánh xạ : kQ(c) = 1 nếu là một cung có hướng, kQ(c) = 0 nếu là một cung vô hướng. II.3.2. Diễn giải cij Ni Nj có 1 phụ thuộc hàm KQi KQj với KQi ,KQj lần lượt là một fQ gQ fQ khoá của Qi ,Qj ; và quan hệ cung Q được hình thành từ tất Qi Qij Qj ij cả thuộc tính khóa của Qi ,Qj : + + + Qij = KQi  KQj .  Ni Nj : không có phụ thuộc hàm giữa KQi KQj và quan hệ cung Qij + + bao gồm KQi  KQj . Trang 130
Đồ thị này có thể đổi thành: Ni Nj : cả hai quan hệ cung Qiji ,Qijj và quan hệ nút Qij đều được hình + + Qiji Qijj thành từ tập KQi  KQj . Nij Hình dưới đây minh hoạ một đồ thị quan hệ. Nhanvien_2 MANV//TENNV, DCNV Thuoc(MANV,MAPH) Phong_2 MAPH //TENPH Phancong(MADA,MANV) Phutrach(MADA,MAPH) MADA //TENDA Dean_2 - Hình IV.4 –Một đồ thị quan hệ– Giữa hai quan hệ Nhanvien_2 và Phong_2 có một phụ thuộc hàm MANV MAPH ; phụ thuộc hàm này được biểu diễn bởi cung nối từ nút của quan hệ Nhanvien_2 sang nút của quan hệ Phong_2, quan hệ của cung này được đặt tên là Thuoc; nó được hình thành từ phép chiếu của quan hệ Trang 131
Nhanvien gốc (nằm trong cấu trúc quan niệm) trên các thuộc tính khoá của 2 quan hệ nút liên quan. II.3.3. Biến đổi một đồ thị quan hệ sang một đồ thị con đường truy xuất thô và ngược lại (a) Một đồ thị con đường truy xuất thô được biến đổi thành một đồ thị quan hệ như sau: ĐTCĐTX thô (N, C, Q, Cđ, f, g, h, i, j) ĐTQH (NQ,CQ,QQ, fQ, gQ, kQ) với:  NQ = N  QQ = Q  fQ = f  (c, c’) C có chiều ngược nhau, và g(c) = g(c’),  cQ CQ sao cho: gQ (cQ) = g(c) (= g(c’))  kQ(cQ) = 0 nếu max của c và cuả c’ > 1 (cung cQ là vô hướng) kQ(cQ) = 1 nếu ngược lại (cung cQ là có hướng)  cQ = c nếu cQ vô hướng hoặc max (c ) 1 cQ = c’ nếu ngược lại (b) Từ một đồ thị quan hệ có thể biến đổi thành một đồ thị con đường truy xuất thô như sau:  N = NQ  Q = QQ  f = fQ  cQ CQ, cQ = (n1, n2),  (c, c’) với c = (n1, n2) và c’ = (n2, n1) Trang 132
và g(c) = gQ (cQ) và g(c’) = gQ (cQ)  Nếu kQ(cQ) = 0 thì max (c ) và max (c’ ) > 1 Nếu kQ(cQ) = 1 thì một trong hai max(c),max(c’) 1   n NQ ; j(n) =1 (nút vào) II.4. Chuỗi kết được cài đặt trên đồ thị Như đã đề cập ở đầu chương, mối quan tâm hàng đầu của người thiết kế ở giai đoạn này là chọn một cấu trúc lô gic cho phép thực hiện hiệu quả phép kết. Cơ sở để đánh giá tiêu chuẩn này là khái niệm chuỗi kết được cài đặt trên đồ thị con đường truy xuất. II.4.1. Định nghĩa đối với đồ thị con đường truy xuất Một chuỗi kết = Q1 Q2 Qm được cài đặt trên đồ thị con đường truy xuất (N, C, Q, Cđ, f, g, h, i, j) nếu và chỉ nếu:  Qi, i (1 m), Qi QQ và   1 dòng D = (c1, c2, cp) trên đồ thị con đường truy xuất sao cho mỗi cung ci thoả 2 điều kiện sau: + g (ci ) = Qj , j (1 m) + Qi, i (1 m) : - hoặc  1 cung c của D sao cho g (c ) = Qi - hoặc  1 nút n của D sao cho f (n ) = Qi II.4.2. Định nghĩa đối với đồ thị quan hệ Một chuỗi kết = Q1 Q2 Qm được cài đặt trên đồ thị quan hệ (NQ,CQ,QQ, fQ, gQ, kQ) nếu và chỉ nếu:  Qi, i (1 m), Qi QQ và Trang 133
  1 dòng D = ( c1, c2, cp) trên đồ thị quan hệ sao cho mỗi cung ci thoả 2 điều kiện sau: + gQ(ci ) = Qj , j (1 m) + Qi, i (1 m) : - hoặc  c D sao cho gQ (c ) = Qi - hoặc  n D sao cho fQ (n ) = Qi Thí dụ IV.6: 1 AX AX AX AX (AB) (AB)(AB)(AB) 2 BY BY BY BY (BC)(BC)(BC)(BC) 3 CZ CZ CZ CZ ( 4.8a) ( 4.8b) ( 4.8c) ( 4.8d) = (AX) (AB) (BY) (BC) (CZ) được cài đặt trên ( 4.8a), ( 4.8b), ( 4.8d) nhưng không được cài đặt trên ( 4.8c). II.4.3. Diễn giải - Nếu một chuỗi kết được cài đặt trên đồ thị (con đường truy xuất hoặc quan hệ) thì sẽ tồn tại một dòng D có gốc ng. Từ quan hệ Qg của nút gốc ng thuộc dòng D, ta có thể truy xuất nhanh những bộ của Qi thông qua các mạch đi (đối với đồ thị con đường truy xuất) hoặc thông qua các đường đi (đối với đồ thị quan hệ) xuất phát từ ng . - Trong Vd 4.8 chuỗi kết Trang 134
= (AX) (AB) (BY) (BC) (CZ) được thể hiện như sau:  Trong (4.8a): ng = 1 mạch đi :{(1,2), (2,3)} : (AX) (AB) (BY) (BC) (CZ)  Trong (4.8b): ng = 2 mạch đi :{(2,1), (2,3)} : (BY) (AB) (AX) (BC) (CZ)  Trong (4.8c): chỉ có thể xuất phát từ 1 hoặc 3 nhưng: + từ 1 chỉ đến được 2, không đến được hoặc không đi qua 3; + từ 3 chỉ đến được 2, không đến được hoặc không đi qua 1. + hoặc với gốc ng = 1, dùng mạch đi (1,2), sau đó đọc tuần tự tất cả các bộ của (CZ) và đối sánh với kết quả của mạch đi. + hoặc với gốc ng = 3, dùng mạch đi (3,2), sau đó đọc tuần tự tất cả các bộ của (AX) và đối sánh với kết quả của mạch đi.  Trong (4.8d):có hai dòng gốc là 1 và 3 để thực hiện III. THUẬT TOÁN BIỂU DIỄN MỘT CẤU TRÚC CƠ SỞ DỮ LIỆU QUAN HỆ SANG ĐỒ THỊ QUAN HỆ III.1. Mục tiêu Ngoài 3 mục tiêu đã được đề ra cho quá trình biến đổi từ cấu trúc quan niệm (ở dạng quan hệ) sang cấu trúc ở dạng lô gic, thuật toán sẽ được trình bày trong phần này còn nhắm thêm 2 mục tiêu khác: - Đối với quan hệ có nhiều khoá, tất cả các khoá đều được gán cho một vai trò ngang nhau; thật vậy việc đánh giá Trang 135
ưu tiên cho khoá nào trong số các khoá của một quan hệ thuộc về lãnh vực cài đặt, và sẽ được cân nhắc ở giai đoạn thiết kế vật lý. Điều này giải thích bước thứ nhất của thuật toán. -Làm nổi bật những tập thuộc tính chung của mỗi cặp quan hệ, vì đó là cơ sở của phép kết. III.2. Thuật toán Vào : n Một phân rã của Q dựa trên F : {Qi} i=1, mỗi Qi có tập khoá (Ki) Ra : Đồ thị quan hệ tương ứng với . Các bước : B1: Biến đổi thành một phân rã đồng nhất d: 1.1. Với mọi cặp quan hệ con Qi,Qj, nếu Ki  Kj,Ki,Kj lần lượt là một khoá của Qi,Qj, thì gộp Qi,Qj lại thành một quan hệ con. + 1.2. Với mỗi Qi , nếu Qi có chứa một khoá Kj của Qj, + thì Qi phải chứa tất cả các khoá của Qj. B2:Tạo nút và quan hệ nút: Mỗi quan hệ Qi là một nút Ni với QNi = Qi . B3:Tạo nút bản lề và quan hệ (nút) bản lề: Mục đích làm nổi bật các thuộc tính chung của mỗi cặp quan hệ nút. + + + 3.1. Qi ,Qj,Qij = Qi  Qj . + 3.2. Chừng nào Qij <>  thì: + + - xác định tất cả khoá của Q [Qij ] ; KQij ký + hiệu tập thuộc tính khoá của Q [Qij ]. - Nếu  Qh d sao cho 1 khoá của Qh là một + khoá của Q [Qij ] Trang 136
thì tạo 1 nút bản lề Nb1 với quan hệ Qb1 = + Q [KQij ] Cuối nếu + + + - Qij := Qij - KQij Cuối chừng nào B4: Tạo cung: Chú ý : chỉ tạo số cung tối thiểu xuất phát từ một nút. 4.1. Ni với Qi , xác định: + + PTH (Ni) = {Nj với Qi  KQj } PTH_THỪA (Ni) = {Nj PTH (Ni) sao cho :  Nh PTH (Ni) với Qh sao cho + + KQh  KQj } + + LỒNG_KHOÁ(Ni)={Nj với Qj sao choKQi KQj } LỒNG_KHOÁ_THỪA(Ni)={Nj LỒNG_KHOÁ(Ni) sao cho:  Nh LỒNG_ KHOÁ (Ni ) với Qh + + sao cho: KQh  KQj } Cung (Ni ) = ( PTH (Ni) - PTH_THỪA (Ni))  (LỒNG_ KHOÁ (Ni ) - LỒNG_ KHOÁ_THỪA (Ni )) Cuối  4.2. Ni Cung (Ni ) thì tạo 1 cung có hướng từ Ni Nj : cij Cuối  + + 4.3. Qij = Qi [KQi  KQj ] Trang 137
B.5: Huỷ những nút bản lề thừa Ni sao cho : - có một khoá duy nhất là Kk - Không có thuộc tính nào khác ngoài khoá - Chỉ có một cung vào uất phát từ nút Ni Thì : /* vai trò bản lề của Nk không còn cần thiết nữa*/ - Nhập Nk vào Ni - huỷ cung cik Cuối  B.6: Min hoá các quan hệ nút: Ni với Qi thì: Nj Cung (Ni ) với Qj thì: + Huỷ khỏi Qi những thuộc tính khoá của Qj mà không phải thuộc tính khoá của Qi. Cuối  Cuối  B.7: Tạo cung vô hướng : Nk sao cho : + + - Qk = KQk (nghĩa là Qk không có thuộc tính không khoá) - Chỉ có 2 cung ra khỏi Nk (không có cung vào, + + đến Ni ,Nj với Qi,Qj sao cho KQk =KQi  + KQj thì  tạo 1 cung vô hướng nối Ni ,Nj với Qij = Qk  huỷ nút Nk  huỷ 2 cung xuất phát từ Nk Cuối  Trang 138
VD 4.9: Cho cấu trúc quan niệm như sau: 1. DDH (SODH, NGDH, TRIGIA) 2. Mathang (MAMH, TENMH, DONGIA) 3. ChitietDH (SODH, MAMH, SLDH ) 4. PGH (SOGH, NGGH, SODH ) 5. ChitietGH (SOGH, MAMH, SLGH, SODH) B1: Phân rã ban đầu không thay đổi, vì không có tình trạng khoá tương đương giữa hai quan hệ, và trong các quan hệ cũng không có nhiều khoá. B2: Tạo nút . 1. DDH 2. Mathang SODH//NGDH MAMH//TENMH TRIGIA DONGIA 3. ChitietDH MAMH,SODH// SLDH 4. PGH 5. ChitietGH SOGH// SOGH,MAMH// NGGH,SODH SLGH,SODH - Hình IV.5 –Kết quả tạo nút ở bước 2– Trang 139
B.3 Dưới đây là những tập thuộc tính chung không rỗng của từng cặp quan hệ. 1 và 3 : SODH, khoá của 1 1 và 4: -nt- 1 và 5: -nt- 2 và 3: MAMH, khoá cuả 2 2 và 5: -nt- 3 và 5: MAMH, SODH, khoá cuả 3 4 và 5: SOGH, SODH ==> khoá của tập này là SOGH, lại là khoá của 4, còn lại SODH lại là khoá 1. ==> kết luận: không tạo nút bản lề nào cả. B.4 : Tạo cung Lồng PTH PTH_THỪA LK_THỪA Cung Khóa (Qi) (Qi) (Qi) (Qi) (Qi) 1.ĐĐH  - - -  2.Mathang  - - -  3.ChitietDH 1,2  1,2  1,2 4.PGH 1   - 1 5.ChitietGH 1,2, 1,2 2,4  2,3,4 3,4 Ghi chú: “-“ có nghĩa là không cần thiết phải tính tập này, như trong trường hợp tập PTH(Qi) là rỗng thì không cần tính tập là LK(Qi) , vì theo định nghĩa, tập sau nằm trong tập trước. Trang 140
Các quan hệ cung là: - cung 31 : CTDH_DDH (MAMH, SODH) - cung 32 : CTDH_MH (MAMH, SODH) - cung 41 : PGH_DDH (SOGH, SODH) - cung 52 : CTGH_MH (SOGH, MAMH) - cung 53 : CTGH_CTDH(SOGH, MAMH,SODH) - cung 54 : CTGH_GH(SOGH, MAMH) Kết quả bước này được trình bày trong Hình IV.6 dưới đây: 1. DDH 2. Mathang SODH//NGDH MAMH//TENMH TRIGIA DONGIA 3. ChitietDH MAMH,SODH// SLDH 4. PGH 5. ChitietGH SOGH// SOGH,MAMH// NGGH,SODH SLGH,MAMH - Hình IV.5 –Kết quả của các bước từ 1 đến 4– B5 : Không thực hiện, vì đã không tạo nút bản lề nào cả. B6 : - Trong quan hệ nút PGH, loại bỏ thuộc tính SODH. - Trong quan hệ nút ChitietGH,loại bỏ thuộc tính SODH. B7 : Không tạo được cung vô hướng nào cả. Trang 141
Nhận xét : 1) 5 4 1 & 5 3 1: đây là 2 mạch đi khác nhau cùng xuất phát từ nút 5 và cùng đến nút 1; 2 mạch đi này kiểm tra rằng nếu một chi tiết giao hàng liên quan đến một chi tiết của một đơn đặt hàng (mạch đi 5 3 1) và liên quan đến một đợt giao hàng thì đợt giao hàng này phải của cùng đơn đặt hàng đã biết (mạch đi 5 4 1). Một khi cơ chế kiểm tra này hoạt động thường trực, thì dễ truy xuất thông tin sau: ”các chi tiết giao hàng của một dơn đặt hàng cùng với ngày đặt hàng”, nghĩa là thực hiện phép chiếu sau: Q{SOGH, MAMH, SLGH, SODH,NGDH}. Quan hệ này có thể truy xuất thông qua một trong hai chuỗi kết sau có gốc là 5 (cả hai chuỗi kết đều được cài đặt trên đồ thị quan hệ và đều cung cấp kết quả như nhau): (5 > <1 [ ] (mạch đi 5 4 1). 2) 5 3 2 & 5 2 : hiện tượng này do có sự lồng khoá giữa các quan hệ 3&2 và 5&2. III.3. Biến đổi ngược : từ một đồ thị quan hệ sang một cấu trúc cơ sở dữ liệu quan hệ Thực hiện quá trình biến đổi ngược này là để kiểm chứng lại xem cấu trúc quan hệ được biểu diễn qua đồ thị quan hệ có hoàn toàn tương đương với cấu trúc quan hệ ban đầu hay không (tương đương ở đây được hiểu theo nghĩa bảo toàn thông tin và bảo toàn phụ thuộc hàm). 1. Gọi -1, tập quan hệ con có được sau khi áp dụng quá trình biến đổi ngược. -1 = {Qi }  {Qij },Qi là quan hệ nút, Qij là quan hệ cung. 2. Gộp các quan hệ có cùng khoá lại thành một. Trang 142
-1 Quan sát và d , ta nhận thấy số lượng quan hệ, thành phần của từng quan hệ sẽ như nhau. Điều này được bảo đảm do chính nội dung thuật toán. Trang 143
IV. CÁC TRƯỜNG HỢP CẦN LƯU Ý IV.1. TRƯỜNG HỢP 1 Cho cấu trúc quan hệ sau: C0 = Và cấu trúc CSDL quan niệm: C1 = { ; ; ; } Có 4 cách biểu diễn khác nhau của C1 ở dạng đồ thị quan hệ : 3 Q3(AY) Q23(AB) Q12(SAB) 1 2 Q1(ST) Q2(ABX) Q14(AB) 4 (a) Q4(BZ) Trang 144
3 Q3(AY) 1 2 Q1(ST) Q2(ABX) 4 Q4(BZ) (b) 3 Q3(AY) 1 Q1(ST) 2 4 Q2(ABX) Q4(BZ) (c) 4 Q4(BZ) 1 Q1(ST) 2 3 Q3(AY) Q2(ABX) (d) - Hình IV.7 –Bốn đồ thị quan hệ của C1– Trang 145
Dưới góc độ thao tác quan hệ, cả 4 đồ thị quan hệ đều như nhau. Nếu ta xem xét mỗi chuỗi kết dựa trên thuộc tính chung có thể đặt ra cho cấu trúc quan hệ này, thì những chuỗi kết ấy đều được cài đặt trên cả 4 đồ thị quan hệ. Chẳng hạn như muốn truy xuất Q0[STAY], nghĩa là: (Q1 > < Q14 ) [AB]  Q2[AB]; hình 4.8 minh hoạ một tình trạng CSDL, qua đó mạch đi (13,14) sẽ cung cấp các bộ {(a1, b3), (a3, b2) }và nút 2 sẽ cung cấp các bộ {(a1, b1), (a1, b3)} với (c) & (d): truy xuất chỉ ở 2 nút là đủ; tuy nhiên 2 đồ thị quan hệ này có ý nghĩa khai thác hơi khác với đồ thị quan hệ (a) ở chỗ cho phép người sử dụng khả năng tạo một cách độc lập với những bộ Q0[SAB], những bộ Q0[SA] thông qua việc tạo các thể hiện của cung (13) đối với đồ thị (c), hoặc những bộ Q0[SB] thông qua việc tạo các thể hiện của cung (14) đối với đồ thị (d). Khả năng này không có được trong đồ thị (a). Trang 146
TQ1 TQ2 S A B T A B X s1 a1 b3 t1 a1 b1 x1 s2 a3 b2 t2 a1 b3 x2 TQ3 TQ4 A Y B Z a1 y1 b1 z1 a2 y2 b2 z2 a3 y3 b3 z3 (4.8.a) 3 a1,y1 a2,y2 a3,y3 1 2 s1,t1 a1,b1,x1 s2,t2 a1,b3,x2 b1,z1 b2,z2 4 b3,z3 - Hình IV.8 –Một tình trạng CSDL được trình bày dưới dạng bảng (a) và dưới dạng đồ thị quan hệ (b)– Trang 147
Nếu một hệ QTCSDLQH được chọn để cài đặt, trên quan hệ Q1 phải khai báo: một chỉ mục (AB) với đồ thị (a) hai chỉ mục (A) và (B) với đồ thị (b), không có chỉ mục (AB) hai chỉ mục (AB) và (A) với đồ thị (c) hai chỉ mục (AB) và (B) với đồ thị (d) Thuật toán trình bày ở trên đề nghị đồ thị quan hệ (a), với quan tâm hàng đầu là cung cấp một biểu diễn đồ thị không trùng lắp trên phương diện con đường truy xuất để người thiết kế có cái nhìn gọn nhất. Các dạng biến thể của đồ thị quan hệ, như các đồ thị (b), (c), (d) sẽ được cân nhắc ở một bước sau với các chỉ tiêu như ý đồ khai thác, tần suất khai thác, v.v . IV.2. TRƯỜNG HỢP 2 Cho quan hệ : C0 = Và cấu trúc CSDL quan niệm: C’1 = { ; ; } Q’12(ABC) Q’23(BC) 1 2 3 Q’1(ABCX) Q’2(BCY) Q’3(CZ) (a) Trang 148
1 2 3 Q’1(ABCX) Q’2(BCY) Q’3(CZ) (b) - Hình IV.9 –Hai đồ thị quan hệ của C’1– Trường hợp thứ hai này tương tự như trường hợp trước trong các đồ thị quan hệ (c) và (d). Với đồ thị (IV.9.b), người sử dụng có thể tạo những bộ dạng (a,-,c, x), nghĩa là chỉ mới biết cặp giá trị (a,c) và chưa biết cặp giá trị của (A,B) tương ứng với “a”. Ngược lại, với đồ thị (IV.9.a), người sử dụng chỉ có thể tạo hoặc (a,b,c,x) hoặc (a,-,-,x). Khi khai báo cấu trúc vật lý của quan hệ Q1, với (a) chỉ khai báo một chỉ mục (BC), với (b) phải khai báo hai chỉ mục (BC) và (C). Thuật toán đề nghị đồ thị quan hệ (a). IV.3. TRƯỜNG HỢP 3 Cho quan hệ: C’’0 = Và cấu trúc CSDL quan niệm: C’’1 = { <Q’’3(C/ AB) Z), Trang 149
F’’3 = {C ABZ ; A B CZ } >} Q’’3 Q’’3 C/AB//Z C/AB//Z Q’’13 (CDE/AE//B) Q’’23 (CD/AD//B) Q’’2 Q’’2 CD/AD//Y CD/AD//Y Q’’12 (CDE/AE//Y) Q’’1 Q’’1 CDE/AE//X CDE/AE//X (a) (b) - Hình IV.10 –Hai đồ thị quan hệ của C’’1– Khác với trường hợp ở trên, các quan hệ của C’’1 không có sự lồng khoá toàn bộ, giữa hai quan hệ Q1 và Q3 , ngoài hai khoá lồng nhau là CDE và C, còn có phụ thuộc hàm không hiển nhiên AE AB. Cung (13) thể hiện phụ thuộc hàm này. Thuật toán đề nghị đồ thị (b). Trang 150
V. QUI TRÌNH TỔNG THỂ CỦA GIAI ĐỌAN THIẾT KẾ LOGIC 1. Từ một cấu trúc CSDL quan niệm được xác định trong giai đoạn thiết kế quan niệm, giai đoạn thiết kế lôgic sẽ biến đổi nó thành một đồ thị quan hệ. Đồ thị này phải hoàn toàn trung thực với cấu trúc quan niệm theo 3 loại tiêu chuẩn được đề ra là: - bảo toàn nội dung CSDL. - bảo toàn sự truy xuất trực tiếp - bảo toàn tính hiệu quả trong việc kiểm tra ràng buộc toàn vẹn. Đồ thị quan hệ là một dạng tóm tắt của đồ thị con đường truy xuất thô. 2. Giai đoạn thiết kế vật lý tiếp theo sẽ dựa trên đồ thị này để lựa chọn một đồ thị con đường truy xuất sẽ cài đặt. Trang 151