Đồ án Tìm hiểu các mô hình đã được sử dụng để mở rộng cơ sở dữ liệu quan hệ

và R(U2), U1ÇU2¹Æ. Đặt U=U1ÈU2, X=U1ÇU2, X1=U1-X, X2=U2-X. a) Kết nối tự nhiên chặt: Kết nối tự nhiên chặt theo aX của r với s là một quan hệ trên lược đồ R(U) kí hiệu là rVaXs, được xác định như sau: rVaXs={t=(t1, t’, t2)|t’1Îr, $t’2Îs: (t’1[X1]=t1, t’2[X2]=t2, t’1[X]»aXt’2[X] và t’=MaX{t’1[X], t’2[X]})}. b) Kết nối tự nhiên không chặt: Kết nối tự nhiên không chặt theo aX của r với s là một quan hệ trên lược đồ R(U) kí hiệu là rTaXs, được xác định như sau: rTaXs ={t=(t1, t’, t2)|$t’1Îr, t’2Îs: (t’1[X1]=t1, t’2[X2]=t2, "AÎX, t’1[A]t’2[A]Æ và t’[A]=t’1[A]t’2[A])}. Cả hai phép kết nối chặt và không chặt đều có tính kết hợp. Ví dụ 2.8: Cho quan hệ r4 (Hình 2.17). D E d1, d2 e1, e3 d2, d3 e2 Hình 2.17. Quan hệ r4. Căn cứ vào các quan hệ tương tự cho ở Hình 2.7, 2.8, 2.9. sự phân lớp tương đương trên miền trị các thuộc tính A, B, C theo các ngưỡng tương ứng 0.4, 0.6, 0.8 được biểu diễn ở Hình 2.18. Hình 2.19 cho sự phân lớp tương đương trên miền trị của thuộc tính D, E. A 0.4 a1 a3 a5 a2 B 0.6 b1 b3 b2 b4 C 0.8 c1 c3 c2 Hình 2.18. Các lớp tương đương trên miền trị của A, B, C. D 0.7 d1 d3 d2 E 0.9 e1 e2 e3 Hình 2.19. Các lớp tương đương trên miền trị của D, E. Với các quan hệ r1 ở Hình 2.10, quan hệ r4 ở Hình 2.17, tích đề các của r1 với r4 theo ngưỡng a=(aA, aB, aC, aD, aE)=(0.4, 0.6, 0.8, 0.7, 0.9) là quan hệ r6 ở Hình 2.20. A B C D E a1 b1, b3 c1, c2 d1, d2 e1, e3 a1 b1, b3 c1, c2 d2, d3 e2 a2, a3 b2 c3 d1, d2 e1, e3 a2, a3 b2 c3 d3, d3 e2 Hình 2.20. Quan hệ r6 = r1 ´a r4. C E c2, c3 e3 c1, c3 e2 c2 e1, e3 Hình 2.21. Quan hệ r5. A B C E a1 b1, b3 c1, c2, c3 e3 a2, a3 b2 c1, c3 e2 Hình 2.22. Quan hệ r7. A B C E a1 b1, b3 c2 e3 a1 b1, b3 c1, c3 e2 a1 b1, b3 c2 e1, e3 a2, a3 b2 c3 e3 a2, a3 b2 c1, c3 e2 Hình 2.23. Quan hệ r8. Kết nối tự nhiên chặt và không chặt của r1 với r5 (Hình 2.21) theo ngưỡng aC=0.8 là quan hệ r7, r8 ở Hình 2.22 và 2.23. Tính chất của phép kết nối tự nhiên: Cả hai phép kết nối chặt và không chặt đều có tính kết hợp và giao hoán. 2.8. Phép tính quan hệ trong trường hợp có kí hiệu NULL Khi xem xét các phép tính quan hệ ở trường hợp có sử dụng kí hiệu null trong các giá trị thuộc tính, có một số nhận xét sau: 1) Giá trị của một bộ trên một thuộc tính, chẳng hạn {a1, a2,…, at} có thể đã kể hết các lớp tương đương do ngưỡng aj phân hoạch Dj, nghĩa là về mặt ngữ nghĩa có thể coi {a1, a2,…, at} tương đương với {D}, trong khi đó hệ thống coi {a1, a2,…, at} không tương đương với {D}. Như vậy, trong trường hợp có kí hiệu null D, các định nghĩa về phép hợp, giao, hiệu, chiếu, tích Đề-các, chọn chặt và kết nối chặt nếu giữ nguyên như đã phát biểu (cho trường hợp không có kí hiệu null) có thể có một số nhược điểm sau: Kết quả của phép hợp, phép Đề-các, phép chiếu có thể chứa những bộ thừa đối với nhau (tương đương về ngữ nghĩa) như đã nêu. Kết quả của phép giao có thể sẽ thiếu mặt một số bộ vì hệ thống coi {a1, a2,…, at} không tương đương với {D}. Tương tự, việc thực hiện phép hiệu có thể sẽ còn lưu lại một số bộ đáng lẽ bị loại bỏ. Phép chọn chặt, kết nối chặt có thể sẽ bỏ qua một số bộ do hệ thống coi {a1, a2,…, at} không tương đương với {D}. 2) Nếu giá trị của một bộ trên một thuộc tính là {D}, về mặt ngữ nghĩa có thể coi là giá trị này đã kể hết các lớp tương đương do ngưỡng aj phân hoạch Dj. Nghĩa là các khả năng chung của một giá trị không chứa kí hiệu null như {a1, a2,…, at} và giá trị {D} chính là tất cả các khả năng do {a1, a2,…, at} đưa ra. Trong khi đó hệ thống đã tính {a1, a2,…, at}Çaj{D}=Æ. Như vậy, trong trường hợp có kí hiệu null D, các định nghĩa về phép chọn không chặt và phép kết nối không chặt nếu giữ nguyên như đã phát biểu, thì sẽ bỏ qua một số bộ mà đáng lẽ về mặt ngữ nghĩa những bộ này xứng đáng thuộc quan hệ kết quả. Tương ứng với nhận xét trên, có thể khắc phục như sau: 1) Bổsung cho hệ thống khả năng kiểm tra và quyết định rằng một giá trị {a1, a2,…, at} trên Dj có chứa hết mọi khả năng (với ngưỡng aj) hay không. Nghĩa là kiểm tra và quyết định rằng {a1, a2,…, at} có tương đương với {D} hay không. 2) Cần xác định việc lấy giao ÇPaAi của hai biểu thức trị trên một thuộc tính (nghĩa là bao gồm trường hợp có kí hiệu null). Định nghĩa phép giao khả năng (của hai biểu thức trị): Trên miền trị Di của thuộc tính Ai xét ngưỡng tương tự ai. Cho di, di’ tương ứng là biểu thức trị của t và t’ trên Ai, phép giao khả năng của di và di’ kí hiệu là ÇPaAi cho kết quả là một biểu thức trị trên Ai được xác định theo bảng sau: M M’ M ÇPaAiM’ M ÇPaAiM’ Æ M’ M’ M ÇPaAiM’ M’ Æ Æ M M Æ M Hình 2.24. Kết quả biểu thức trị trên thuộc tính Ai. Qua kiểm tra thấy được rằng biểu thức trị (diÇPaAidi’) trên Ai được xác định theo bảng trên có ngữ nghĩa (theo aAi) chính là giao của hai ngữ nghĩa của hai biểu thức trị di và di’. Tính kết hợp của phép kết nối tự nhiên vẫn còn đúng trong trường hợp có kí hiệu null. 2.9. Nhận xét Các phép toán quan hệ đã được trình bày ở trên thực sự là mở rộng của các phép toán quan hệ trong CSDLQH truyền thống. Khi trở lại điều kiện đơn trị cho mỗi giá trị thuộc tính và lấy ngưỡng tương tự là 1.0, sẽ có lại mô hình cổ điển với đại số quan hệ truyền thống. Đặc biệt phép chọn và phép kết nối được chia thành hai mức chặt và không chặt cho phép khai thác sự mở rộng về mặt ngữ nghĩa của mỗi bộ trong mô hình mới. Trường hợp mọi giá trị thuộc tính được khẳng định chỉ có một khả năng (theo một ngưỡng đã xác định) thì hai mức chặt và không chặt sẽ trùng nhau. 3. Cập nhật dữ liệu 3.1. Các qui tắc cập nhật dữ liệu Đối với mỗi nhóm người dùng CSDL, mức độ và quan niệm mờ hoá khi xử lý thông tin trong quan hệ r của họ được thể hiện qua việc họ xác định (hay chấp nhận) một ngưỡng a trên r. Người sử dụng có thể khai thác thông tin có trong quan hệ r của lược đồ R(U) bằng việc sử dụng quan hệ Ma(r). Quan hệ Ma(r) có được từ quan hệ r có trong lưu trữ gốc, nhờ phép trộn các bộ thừa (theo ngưỡng a). Ma(r) tồn tại trong thời gian triển khai một ứng dụng cụ thể, thậm chí có trường hợp nó phải được lưu trữ vật lý trong một thời gian nhất định nào đó. Một phép cập nhật cho một quan hệ Ma(r) như vậy sẽ xảy ra ở một trong hai trường hợp sau: Một phép cập nhật cho một quan hệ có trong lưu trữ gốc có thể kích hoạt việc cập nhật cho Ma(r). Người dùng quan hệ Ma(r) yêu cầu cập nhật một số thông tin để khai thác phục vụ cho ứng dụng của mình mà những thông tin này không cần hoặc không được ghi vào lưu trữ gốc. Trong CSDLQH truyền thống, các phép cập nhật thường được đề cập đến là: thêm một bộ, xoá đi một bộ vốn có trong quan hệ, thay đổi giá trị của một bộ đã có trong quan hệ, phép thay đổi một bộ có thể biểu diễn qua phép xoá và thêm bộ. Khác với CSDLQH truyền thống, tuy vẫn được nhận diện qua khoá, song mỗi bộ trong quan hệ ở mô hình CSDLQH mở rộng đang xem xét thường chứa thông tin không chính xác và không chắc chắn. Do vậy giá trị của một bộ đang có mặt trong quan hệ có thể bị thay đổi trong hai tình huống sau: Thực hiện phép CHANGE(r, t[K], t*[K]). Ngữ nghĩa của phép cập nhật này là các giá trị của bộ t trên các thuộc tính không khoá t[U-K] được đổi thành t*[U-K]. Bộ t của quan hệ r được nhận diện bởi giá trị trên khoá t[K] (K là khoá của r). Việc thực hiện phép CHANGE(r, t[K], t*[U-K]) tương với việc thực hiện lần lượt hai phép cập nhật: phép xoá bộ t trong r, phép thêm bộ t’=(t[K], t*[U-K]) vào r. Phép CHANGE(r, t[K], t*[U-K]) được sử dụng khi người dùng coi thông tin trong bộ t’ là mới hơn, phản ánh đúng đắn hơn về chính đối tượng mà thông tin trong bộ t vốn đang thể hiện. Thực hiện phép UPDATE(r, t[K], t’[U-K]). Ngữ nghĩa của phép cập nhật này là: các giá trị của t trên các thuộc tính không khoá t[U-K] được đổi thành t*[U-K]. Các giá trị trên thuộc tính không khoá t*[U-K] được hình thành kho đối chiếu t[U-K] với t’[U-K], với mục đích chứa những thông tin nói chung là chính xác hơn, chắc chắn hơn so với những thông tin cung cấp bởi bộ t vốn có cũng như những thông tin cung cấp bởi bộ t’=(t[K], t’[U-K]) mới xuất hiện trong lệnh UPDATE. Phép UPDATE(r, t[K], t’[U-K]) được sử dụng khi người dùng coi thông tin về một đối tượng (được xác định nhờ khoá) trong hai bộ t và t’ là bình đẳng và chính xác về độ chắc chắn. Việc xoá đi một bộ vốn có trong quan hệ hay thêm một bộ mới vào quan hệ được tiến hành bình thường (như CSDLQH truyền thống). Bộ được xoá phải được chỉ định bởi các giá trị trên các thuộc tính khoá. Như vậy chỉ có quy tắc cho phép cập nhật UPDATE là đáng bàn, còn các phép cập nhật còn lại khá đơn giản. Giả sử trên một lược đồ R đã xác định một khoá K (gồm k thuộc tính khoá, không mất tính tổng quát giả sử đó là các thuộc tính A1, A2,…, Ak tương ứng với các miền D1, D2,…, Dk). Đó là tập các thuộc tính mà bất cứ hai bộ nào ”đủ tương tự” trên khoá cũng ”đủ tương tự” trên các thuộc tính còn lại. Qui tắc 2.1. (Cho thao tác thêm một bộ vào quan hệ) Cho INS là một câu lệnh thêm một bộ t=(d1, d2,…, dm) vào quan hệ r của lược đồ R theo ngưỡng tương tự a=(a1, a2,…, am). Hệ thống sẽ kiểm tra và thực hiện tương ứng như sau: 1) Nếu trong quan hệ r không có bộ t’ nào để t[K]»aKt’[K] thì thêm t vào r, 2) Không xảy ra 1) thì không làm gì cả. Qui tắc 2.2. (Cho thao tác xóa một bộ trong quan hệ) Cho DEL là một câu lệnh xoá khỏi quan hệ r bộ t với t[K]»a(d1, d2,…, dm) và ngưỡng tương tự a=(a1, a2,…, am). Hệ thống sẽ kiểm tra và thực hiện tương ứng như sau: 1) Nếu trong quan hệ r có bộ t để t[K]»a(d1, d2,…, dm) thì loại bỏ t khỏi quan hệ r, 2) Không xảy ra 1) thì không làm gì cả. Qui tắc 2.3. (Cho thao tác thay đổi giá trị một bộ trong quan hệ) Cho CHANGE là một câu lệnh thay đổi bộ t trong quan hệ r trên những thuộc tính không khoá, với t được xác định bởi t[K]»a(d1, d2,…, dk) theo ngưỡng tương tự a=(a1, a2,…, ak). Hệ thống sẽ kiểm tra và thực hiện tương ứng như sau: 1) Nếu trong quan hệ r có bộ t để t[K]»a(d1, d2,…, dk) thì lần lượt thực hiện hai phép cập nhật sau: DEL, INS. 2) Nếu không xảy ra trường hợp 1) thì không là gì cả. Như đã nói ở trên, phép UPDATE(r, t[K], t’[U-K]) cho quan hệ r nhờ một bộ t’=(t[K], t’[U-K]) được dùng khi trong quan hệ r đã có bộ t’ cũng cung cấp thông tin về một đối tượng O nào đó, giờ đây lại biết thêm bộ t’ cũng cung cấp thông tin về O và coi như t và t’ bình đẳng về độ chính xác cũng như độ chắc chắn. Vì t và t’ là hai bộ thể hiện thông tin về cùng một đối tượng nên yêu cầu của mô hình này là thông tin trên các thuộc tính khoá của hai bộ này phải tương đương: t[K]»aKt’[K]. Với ngữ nghĩa của một bộ trong mô hình CSDL đang được xem xét thì: trên mỗi thuộc tính A, bộ t khẳng định rằng thông tin về O chỉ có các khả năng đã trình nằm trong các khả năng đã trình ra trong t[A], không thể xảy ra khả năng nào nằm ngoài những khả năng t[A] đã đưa ra. Mỗi khả năng được t[A] thể hiện bởi một hay một số giá trị xấp xỉ với nhau hiểu theo nghĩa “đủ tương tự” và cũng có nghĩa là xấp xỉ về tương tự (ở một ngưỡng nào đó) với giá trị chính xác trên thực tế. Tương tự đối với t’. Với một cặp bộ (t, t’) như vậy có 2 khả năng xảy ra: Thông tin không mâu thuẫn: (t[A]ÇPat’[A]¹Æ), nghĩa là tồn tại khả năng được cả t và t’ cùng đưa ra. Nếu thông tin ở cả hai bộ đều đúng thì những khả năng có mặt ở cả t[A] và t’[A] sẽ chứa những khả năng đúng với thực tế, những khả năng chỉ có mặt ở một trong hai bộ đều không thể xảy ra trong thực tế. Thông tin mâu thuẫn: tập các khả năng do t[A] đưa ra và tập các khả năng do t’[A] đưa ra không chạm nhau, nghĩa là không có khả năng nào vừa có mặt ở t[A] vừa có mặt ở t’[A]. Điều này được thể hiện bởi mệnh đề (t[A]ÇPat’[A]¹Æ). Suy ra thông tin (trên thuộc tính A) được cung cấp bởi t và t’ là mâu thuẫn, so với thực tế thì ít nhất thông tin (trên A) của một trong hai bộ là sai. Không biết bộ nào trong hai bộ đó là sai, cũng không loại trừ khả năng cả hai bộ cùng sai. Khi kết hợp thông tin của hai bộ t và t’ về cùng một đối tượng, thì cũng có nghĩa là đã lưu được thông tin mới phong phú hơn (theo nghĩa chính xác hơn, chắc chắn hơn). Qui tắc 2.4. (Cho thao tác thay đổi giá trị một bộ trong quan hệ nhờ kết hợp với thông tin của một bộ mới) Cho UPDATE là một câu lệnh thay đổi giá trị bộ t trong quan hệ r nhờ bộ t’=( d1, d2,…, dm). Với t được xác định bới t[K]»a(d1, d2,…, dk) theo ngưỡng tương tự a=(a1, a2,…, ak). Hệ thống sẽ lần lượt kiểm tra và thực hiện tương ứng như sau: 1) Nếu trong quan hệ r có bộ t để t[K]»aK( a1, a2,…, ak) thì lần lượt làm những việc sau: "AÎU tính t[A]ÇPaAt’[A] Nếu "AÎU: t[A]ÇPaAt’[A]¹Æ thì lập bộ t*, với t*[A]=M(t[A]ÇPaAt’[A]) và thực hiện lần lượt hai phép cập nhật sau: DEL, INS. Nếu $AÎU: t[A]ÇPaAt’[A]=Æ thì thông báo có mâu thuẫn đối với bộ t và không làm gì nữa. 2) Nếu không xảy ra 1) thì không làm gì cả. Ví dụ2.9: Xét quan hệ r3 ở Hình 2.16 cùng với các quan hệ tương tự đã cho ở Hình 2.2 và 2.3. Cho khoá chỉ gồm một thuộc tính là Tên, ngưỡng tương tự là (1.0, 0.6, 0.8) r3 TÊN MÀU XE NGHỀ NGHIỆP t1 An xanh đậm, xanh nhạt, hồng nhà văn, giáo sư t2 Bình xanh đen, tím đỏ đạo diễn, giáo viên t3 Phúc trắng, hồng, kem nhà thơ t4 Lộc trắng, kem nhà văn t5 Thọ xanh đen, đỏ phi công, đạo diễn t6 Tài xanh đậm, tím đỏ phi công Hình 2.25. Giả sử thực hiện thao tác cập nhật sau: UPDATE Do t=({Phúc}, {hồng, kem}, {nhà thơ}) và t3 đủ tương tự trên khoá (theo ngưỡng 1.0) và hơn thế t»at3 nên kết quả nhận được r3 như bảng cho ở Hình 2.25 trên đây. Giả sử muốn cập nhật cho r3 ở hình 3.19 trên bởi: UPDATE Thông tin về người tên là An được cung cấp bởi bộ t1 (vốn có trong r3) và thông tin mới ({An}, {xanh đậm, xanh đen}, {đạo diễn, phi công}) không mâu thuẫn (trên mọi thuộc tính). Kết quả thu được r3 như bảng cho ở Hình 3.26 dưới đây. Giả sử muốn cập nhật cho quan hệ r3 ở Hình 2.26 bởi: UPDATE Hệ thống sẽ chỉ thông báo rằng: thông tin cần cập nhật mâu thuẫn với bộ t5. r3 TÊN MÀU XE NGHỀ NGHIỆP t1 An xanh đậm, xanh nhạt, xanh đen nhà văn, đạo diễn t2 Bình xanh đen, tím đỏ đạo diễn, giáo viên t3 Phúc trắng, hồng, kem nhà thơ t4 Lộc trắng, kem nhà văn t5 Thọ xanh đen, đỏ phi công, đạo diễn t6 Tài xanh đậm, tím đỏ phi công Hình 2.26. r3 TÊN MÀU XE NGHỀ NGHIỆP t1 An xanh đậm, xanh nhạt, xanh đen nhà văn, đạo diễn t2 Bình xanh đen, tím đỏ đạo diễn, giáo viên t3 Phúc trắng, hồng, kem nhà thơ t4 Lộc trắng, đen phi công, đạo diễn t5 Thọ xanh đen, đỏ phi công, đạo diễn t6 Tài xanh đậm, tím đỏ phi công Hình 2.27. Giả sử muốn cập nhật cho quan hệ r3 ở Hình 2.26 bởi: CHANGE Kết quả bộ t4 bị xoá khỏi r3 và xuất hiện một bộ mới trong r3 như ở Hình 2.27. Ví dụ 2.10: Trong ví dụ này chúng ta xét việc cập nhật trong trường hợp các quan hệ có chứa kí hiệu null. Cho quan hệ mờ r trong Hình 2.28 dưới đây. Giả sử thực hiện 3 thao tác: UPDATE UPDATE UPDATE Với giả thiết các quan hệ tương tự và ngưỡng tương tự a giống như ví dụ trên, thì kết quả thu được như trong Hình 2.29. r TÊN MÀU XE NGHỀ NGHIỆP t1 An xanh đậm D t2 Ái ^ phi công t3 Bình xanh đen, tím đỏ D, ^ t4 Lạc trắng, kem giáo viên Hình 2.28. r TÊN MÀU XE NGHỀ NGHIỆP t1 An xanh đậm, xanh đen phi công, nhà văn t2 Ái ^ phi công t3 Bình đỏ, tím đỏ nhà văn, ^ t4 Lạc trắng, kem giáo viên Hình 2.29. Kết quả thực hiện ba thao tác Update. Bây giờ ta thực hiện phép cập nhật sau: UPDATE Hệ thống sẽ báo: thông tin muốn cập nhật mâu thuẫn với bộ t4 đang có trong r2. 3.2. Nhận xét Trên đây đã trình bày các qui tắc cập nhật dữ liệu trong mô hình CSDLQH đang xem xét. Từ các qui tắc cập nhật nêu trên có thể rút ra những nhận xét sau: Sau mỗi khi cập nhật, những thông tin lưu trữ trong quan hệ là không mâu thuẫn. Sau khi cập nhật, những thông tin lưu trữ trong quan hệ là đủ (không thiếu và không thừa) theo cách hiểu như sau: không thừa thông tin theo nghĩa quan hệ không chứa hai bộ nào thừa đối với nhau (theo ngưỡng tương tự a đang xét đến). Không thiếu thông tin theo nghĩa các thông tin vốn có trước khi cập nhật và các thông tin muốn cập nhật đều có mặt trong quan hệ (kết quả), ngoại trừ những thông tin bị phát hiện là mâu thuẫn. Do cập nhật, có thể một số thông tin chưa đầy đủ chưa chắc chắn trở nên đầy đủ hơn, chắc chắn hơn. Thông tin mâu thuẫn có thể được phát hiện. 4. Ngôn ngữ hỏi SQL S/P Trong phần này sẽ trình bày ý tưởng mở rộng SQL, ngôn ngữ hỏi trong CSDLQH truyền thống, để có một ngôn ngữ hỏi (tạm gọi là SQL s/p) phù hợp với mô hình đang xét. 4.1. Biểu thức điều kiện sau WHERE Một lược đồ CSDL mờ có thể bao gồm những thuộc tính mà trên miền trị của chúng có xác định một quan hệ mờ tương tự, những thuộc tính như vậy được gọi là thuộc tính loại s/p. Những thuộc tính còn lại mà giống như trong lược đồ CSDLQH truyền thống dạng chuẩn 1 được gọi là thuộc tính rõ (cũng có thể coi quan hệ mờ tương tự xác định trên miền trị của chúng có ngưỡng ngầm định là 1.0). a) Biểu thức nguyên tố Có các dạng biểu thức nguyên tố được xác định như sau: 1)(R.Ai: d) 1’)NOT(R.Ai: d) 2)(R.Ai: S.A) 2’)NOT(R.Ai: S.Aj) 3)(R.Ai q a) 4)(R.Ai q S.Aj) Trong đó R và S là tên quan hệ; Ai, Aj là tên thuộc tính; d là một giá trị thuộc miền trị của thuộc tính loại s/p Ai (thuộc tính có ngưỡng tương tự nhỏ hơn 1); a là một giá trị thuộc miền trị rõ Ai; qÎ{, £, , ¹, =}. Cần chú ý rằng Ai và Aj xuất hiện ở dạng 1), 1’) và 2), 2’) đều là những thuộc tính loại s/p, còn Ai, Aj ở 3) và 4) đều là các thuộc tính rõ. b) Biểu thức nguyên tố được mờ hoá Những biểu thức nguyên tố liên quan đến những thuộc tính s/p có thể được mờ hoá bằng cách viết thêm chỉ số s hoặc chỉ số p. Nếu Q là biểu thức nguyên tố dạng 1), 1’), 2), 2’) thì những biểu thức sau gọi là những biểu thức nguyên tố được mờ hoá từ Q: 5)(Q)sai 6)(Q)p 7)(Q)saip c) Biểu thức điều kiện sau WHERE Định nghĩa . Một biểu thức nguyên tố (1-4) là một biểu thức điều kiện. . Một biểu thức nguyên tố được mờ hoá (5-7) là một biểu thức điều kiện. . Nếu P và Q là hai biểu thức điều kiện thì (P AND Q) và (P OR Q) là các biểu thức điều kiện. 4.2. Ngữ nghĩa và đánh giá câu hỏi SQL s/p a) SQL s/p . Dạng câu lệnh truy vấn thông tin SQL s/p: SELECT Ri1.A1,…, Rik.Ak FROM R1, R2,…, Rn WHERE Y; Ở đây R1, R2, Rn là danh sách tên các quan hệ mờ và Ri1.A1,…, Rik.Ak là danh sách các thành phần được lấy ra; R.A chỉ thuộc tính A của quan hệ R. Nếu trong danh sách sau từ khoá FROM chỉ có một quan hệ có thuộc tính A thì có thể viết A thay cho R.A trong danh sách sau SELECT. Y là biểu thức điều kiện như đã được định nghĩa ở trên. Ý nghĩa của câu lệnh này có thể được diễn tả trong đại số quan hệ: trong tích Đề-các các quan hệ trong mệnh đề FROM chọn những bộ thoả biểu thức điều kiện Y rồi chiếu trên các thuộc tính có mặt ở mệnh đề SELECT. Việc chọn những bộ thoả biểu thức điều kiện Y được xác định như sau: Chọn bộ để thoả biểu thức nguyên tố (1-4): Trong biểu thức nguyên tố, dấu “:” có nghĩa sánh bằng (“=”). Ví dụ, biểu thức (r3.Màu_xe : {xanh đậm, xanh nhạt, hồng}) cho điều kiện chon những bộ trong quan hệ r3 có giá trị ở rhuộc tính Màu_xe là {xanh đậm, xanh nhạt, hồng}. Còn biểu thức (NOT(r3.Màu_xe : {xanh đậm, xanh nhạt, hồng})) cho chọn những bộ mà giá trị thuộc Màu_xe không phải là tập hợp {xanh đậm, xanh nhạt, hồng}. Kết quả chọn bộ để thoả mãn biểu thức nguyên tố được mờ hoá: Nếu biểu thức điều kiện Y là một biểu thức nguyên tố được mờ hoá từ biểu thức Q thì khi chọn bộ thoả Y với Y là: 5) (Q)sa kết quả trùng với kết quả của phép chọn aF trên những quan hệ xuất hiện trong Q với F=(a, Q). 6) (Q)p tương ứng với aF với F=(1.0, Q). 7) (Q)sa P tương ứng với aF với F=(a, Q). Ví dụ 2.11: Biểu thức điều kiện là Y1=(r3.Màu_xe : {xanh đen, hồng})s0.8, thì tập những bộ thoả điều kiện này chính là kết quả của phép chọn sF(r3), với F=(0.8, r3.Màu_xe : {xanh đậm, hồng}). Biểu thức điều kiện là Y3=((r3.Màu_xe : {xanh đen, hồng})p thì tập những bộ thoả điều kiện này chính là kết quả của phép chon sF(r3), với F=(1.0, r3.Màu_xe : {xanh đen, hồng}). Nói cách khác, những bộ mà giá trị tại thuộc tính Màu_xe là một tập có chứa phần tử “xanh đen” hay có chứa phần tử “hồng” đều thoả mãn biểu thức điều kiện Y2. Biểu thức điều kiện là Y3=(r3.Màu_xe : {xanh đen, hồng})s0.8p thì tập hợp những bộ thoả điều kiện này chính là kết quả của phép chọn sF(r3), với F=(0.8, r3.Màu_xe : {xanh đen, hồng}). Nói cách khác, những bộ mà giá trị tại thuộc tính Màu_xe là một tập có chứa phần tử đủ tương tự (theo 0.8) với “xanh đen” hay có chứa phần tử đủ tương tự (theo 0.8) với “hồng” đều thoả mãn biểu thức điều kiện Y3. Chọn bộ để thoả mãn biểu thức điều kiện dạng P AND Q, P OR Q: Nếu hai quan hệ P và Q tương ứng là kết quả của việc chon các bộ thoả P và Q thì kết quả chọn thoả (P AND Q) sẽ là (PQ), kết quả chọn thoả (P OR Q) sẽ là (PQ). Ví dụ 2.12: Giả sử muốn biết tất cả các loại thuốc có thể chọn cho mỗi bệnh nhân, từ hai quan hệ cho ở Hình 2.30 và 2.31 dưới đây, có thể dùng câu lệnh: SELECT R1.TÊN, R2.THUỐC FROM R1, R2 WHERE (R1.BỆNH : R2.CĐ)s0.8p AND (NOT(R1.BỆNH : R2.CCĐ))p kết quả cho trong bảng KẾT QUẢ (Hình 2.32). TÊN BỆNH N1 {b1, b2, b3} N2 {b4} N3 {b3, b5} Hình 2.30. Quan hệ R1. THUỐC CĐ CCĐ c1 {b1, b4, b5} {b3} c2 {b1, b2} {b5} c3 {b6} {b6} c4 {b3, b6} {b5} Hình 2.31. Quan hệ R2. TÊN THUỐC N1 c2 N1 c3 N1 c4 N2 c1 N2 c2 N3 c3 Hình 2.32. Bảng KẾT QUẢ. Giả thiết với ngưỡng tương tự 0.8 các bệnh b1, b2, b4 cùng một lớp tương đương, b3 và b6 cùng một lớp tương đương. b) Mờ hoá các thành phần sau SELECT Một cách tương tự có thể bổ sung chỉ số mờ hoá s, a cho các thành phần (loại s/p) đứng sau SELECT trên cơ sở phép chiếu với ngưỡng cho trước. 5. Các phụ thuộc dữ liệu Trong lý thuyết CSDLQH, các phụ thuộc dữ liệu biểu diễn những tính chất của dữ liệu, những tính chất mà có thể được xem như sự phụ thuộc về miền, liên quan đến hệ thức giữa các giá trị. Các phụ thuộc dữ liệu đã phản ánh được một số vấn đề thuộc về ngữ nghĩa, do đó đặc tả các phụ thuộc dữ liệu rất quan trọng trong quá trình thiết kế các lược đồ CSDL. Việc nghiên cứu các phụ thuộc dữ liệu chính là cơ sở để đảm bảo tính quán dữ liệu trong thực tế. Trong phần còn lại của Chương II này sẽ trình bày các vấn đề về phụ thuộc dữ liệu trong mô hình CSDL đang xem xét và các kết quả về việc tách không mất thông tin. 5.1. Phụ thuộc hàm và tập các luật suy dẫn Trong mô hình cổ điển của CSDLQH, ngữ nghĩa tự nhiên của một phụ thuộc hàm có thể được hiểu là có một thuộc tính hoặc một tập thuộc tính mà các giá trị của nó xác định duy nhất một bộ của quan hệ thoả phụ thuộc hàm này. Như vậy, về trực giác có thể thấy rằng phụ thuộc hàm liên quan trực tiếp đến dư thừa dữ liệu và vì vậy nó là một trong những vấn đề trung tâm được nghiên cứu trong lý thuyết thiết kế CSDL. Cho R(U) là một lược đồ quan hệ có m thuộc tính U={A1, A2,…, Am} tương ứng với các miền D1, D2,…, Dm. Cho X là tập các thuộc tính (XÍU), hai bộ t1=(d11, d12,…, d1m) và t2=(d21, d22,…, d2m), nói rằng t1, t2 thừa (hay tương đương) đối với nhau trên X và viết t1[X]»t2[X] nếu "j: DjÍX ta có "xÎd1j $x’Îd2j: x~x’, và ngược lại "xd2j x’d2j: x~x’. Định nghĩa 2.12. Một phụ thuộc hàm mờ X»®aY được gọi là được thoả trong quan hệ r (với ngưỡng a) khi với hai bộ bất kỳ t1, t2Îr: nếu có t1[X]»t2[X] thì cũng có t[Y]t[Y]. Khi xét quan hệ r với một ngưỡng a đã xác định, không sợ nhầm lẫn chúng ta viết X»®Y thay vì viết X»®aY. Có những trường hợp cần thiết chúng ta sẽ viết cụ thể XaX»®YaY. Trong phần tiếp theo sẽ giả sử rằng một lược đồ quan hệ mờ R(U) đã cho với tập các thuộc tính U, một tập các phụ thuộc hàm mờ chỉ chứa các thuộc tính trong tập U. Với một ngưỡng a xác định, các luật suy dẫn tương tự với các tiên đề suy dẫn Amstrong trong trường hợp cổ điển là: FFD1: phản xạ Nếu YÍX thì có X»®Y. FFD2: tăng trưởng Nếu có X»®Y thì có XZ»®YZ. FFD3: bắc cầu Nếu có X»®Y và Y»®Z thì có X»®Z. Bổ đề 2.7. Tập các tiên đề suy dẫn (FFD1-FFD3) là xác đáng . Nghĩa là, nếu X»®Y được suy dẫn từ một tập các phụ thuộc hàm mờ F nhờ sử dụng các tiên đề này thì X»®Y được thoả trong bất kỳ quan hệ mờ nào thoả tất cả các phụ thuộc hàm trong F. Chứng minh: (FFD1) Dễ dàng thấy tiên đề phản xạ đúng. (FFD2) Giả sử t1, t2Îr sao cho t1[XZ]»t2[XZ] (1) từ định nghĩa của “»” chúng ta có t1[X]»t2[X]. Vì có X»®Y nên t1[Y]»t2[Y] (2) (1) cho thấy "j: DjÎXZ thì "xÎd1j $x’Îd2j: x»x’ và ngược lại. cho thấy "j: DjÎY thì "xÎd1j $x’Îd2j: x»x’, và ngược lại. Do vậy chúng ta có "j: DjÎYZ thì "xÎd1j $x’Îd2j: x»x’, và ngược lại. Điều này cũng có nghĩa là chúng ta có XZ»®YZ. (FFD3) Nếu t1[X]»t2[X] thì t1[Y]»t2[Y] do X»®Y và t1[Z]»t2[Z] do Y»®Z. Từ các tiên đề trên chúng ta có thể suy dẫn ra các tiên đề sau: FFD4: Hợp Nếu có X»®Y và có X»®Z thì có X»®YZ. FFD5: Tách Nếu có X»®YZ thì có X»®Y và có X»®Z. FFD6 : Giả bắc cầu Nếu có X»®Y và có YW»®Z thì có XW»®Z. Định lý 2.2. Tập các tiên đề suy diễn (FFD1-FFD3) là xác đáng và đầy đủ. Chứng minh tính đủ của hệ tiên đề tương tự trường hợp cổ điển. 5.2. Phụ thuộc đa trị và tập các luật suy dẫn Ở mô hình cổ điển, ngoài phụ thuộc hàm còn có phụ thuộc đa trị được quan tâm nhiều, do nó cũng thường xuất hiện trên thực tế. Về trực giác, ta nói rằng “X đa xác định Y” kí hiệu là X»®®Y nếu với những giá trị đã biết cho các thuộc tính của X, tồn tại một tập gồm không hay nhiều giá trị cho các thuộc tính của Y, và tập giá trị Y này không có liên hệ gì với những giá trị của các thuộc tính trong U-X-Y. Trong mô hình mờ đang xem xét, quan niệm về phụ thuộc đa trị cũng nhất quán với cách mở rộng đã sử dụng. Đó là: mở rộng quan hệ đồng nhất của mô hình cổ điển thành quan hệ đủ tương tự (theo ngưỡng) và hai bộ là tương đương (hay thừa) với nhau nếu chúng cùng chung tập các khả năng. Như vậy với X, Y là tập các thuộc tính (X, YÍU), r là một quan hệ mờ của lược đồ R(U), với một ngưỡng a xác định, có thể định nghĩa: Xr(x)={x’| $tÎr, sao cho t[X]=x’, x » x’}. Yr(x)= {y| $tÎr, sao cho t[X]ÎXr(x), t[Y]=y}. Đặt Z=R-XY. Rõ ràng Yr(x) không phụ thuộc vào những giá trị ở thuộc tính Z. Nói rằng hai tập Yr(x) và Yr(xz) tương đương với nhau nếu với mọi giá trị y thuộc tập này, tồn tại một giá trị y’ thuộc tập kia sao cho yy’ và ngược lại. Dùng kí hiệu Yr(x)Yr(xz) để chỉ sự tương đương theo nghĩa đó của hai tập Yr(x) và Yr(xz). Định nghĩa 2.13. Một phụ thuộc đa trị mờ (FMVD) trên lược đồ R(U) là một phát biểu m: X»®®aY, với ngưỡng a và X, Y là các tập con của tập thuộc tính U. Với Z=R-XY. Một quan hệ r trên lược đồ R(U) gọi là thoả FMVD m: X»®®aY nếu với giá trị xz xuất hiện (của một bộ t bất kỳ trong r) chúng ta có Yr(x)@Yr(xz). Trong đó x là giá trị của bộ t trên thuộc tính X và z là giá trị của bộ t trên thuộc tính Z. Ví dụ 2.13: Cho quan hệ r như sau: r X Y Z t1 a, b, c g, h z1 t2 a’, c’ g’, i z2 t3 a, c’ g, i’ z1’ t4 a’, c g’, h’ z2’ Hình 2.33. Một quan hệ mờ. Giả sử với ngưỡng a đã cho trên r có: a ~ b ~ a’; c ~ c’; g ~ g’; h ~ h’; i ~ i’; z1 ~ z1’; z2 ~ z2’. Khi đó nếu đặt x1={a, b, c} thì: Xr(x1)={{a, b, c}, {a’, c’}, {a, c’}, {a’, c}}, Yr(x1)={{g, h}, {g’, i}, {g, i’}, {g’, h’}}, Yr(x1z1)= {{g, h}, {g, i’}}. Dễ nhận thấy: {g’, i} @ {g, i’}, {g’, h’} @ {g, h}, do vậy Yr(x1) @ Yr(x1z1) và một cách tương tự cũng có Yr(x1) @ Yr(x1z2). Như vậy, có thể nói rằng quan hệ r (với ngưỡng tương tự a đã xác định) thoả phụ thuộc đa trị mờ X»®®aY. Khi xét quan hệ r với một ngưỡng a đã xác định, không sợ nhầm lẫn có thể viết X»®®Y thay vì viết X»®®aY. Bổ đề 2.8. Cho r là một quan hệ mờ trên lược đồ R(U), X, Y là tập các thuộc tính (X, YÍU), Z=U-X-Y. Ba mệnh đề sau tương đương. Yr(x) @ Yr(xz), "y0 Î Yr(x) $y’ Î Yr(xz): y’ » y0, "y0 Î (Yr(x) – Yr(xz)) $y’ Î Yr(xz): y’ » y0. Chứng minh: Theo khái niệm quan hệ @ ta có: Điều kiện cần và đủ xảy ra i) là xảy ra đồng thời hai mệnh đề sau "y0 Î Yr(x) $y’ Î Yr(xz): y’ » y0 ii) "y0 Î Yr(xz) $y’ Î Yr(x): y’ » y0 ii’) Dễ nhận thấy ii’) bao giờ cũng đúng bởi chính y0 có thể đóng vai trò của y’. Do đó i) Û ii). Rõ ràng ii) Þ iii) vì nếu có y0 Î (Yr(x) – Yr(xz)) thì hiển nhiên y0 Î Yr(x). Ngược lại, iii) Þ ii), thật vậy, chỉ cần để ý rằng Yr(x)=(Yr(x)-Yr(xz))È(Yr(x)ÇYr(xz)) và (Yr(x)ÇYr(xz))=Yr(xz), nên Yr(x)=(Yr(x)-Yr(xz))ÈYr(xz). Tương tự trong mô hình cổ điển, tiếp theo sẽ xem xét các luật suy dẫn cho phụ thuộc hàm mờ và phụ thuộc đa trị mờ: A1: Tính phản xạ của phụ thuộc hàm mờ (FFD) Nếu YÍX thì có X»®Y. A2: Tính tăng trưởng của FFD Nếu có X»®Y thì có XZ»®YZ. A3: Tính bắc cầu của FFD Nếu có X»®Y và có Y»®Z thì có X»®Z. A4: Tính bù của phụ thuộc đa trị mờ (FMVD) Nếu có X»®®Y thì có X»®®Z, trong đó Z=U-XY. A5: Tính tăng trưởng của FMVD Nếu có X»®®Y thì có XZ»®®Y. A6: Tính bắc cầu của FMVD Nếu có X»®®Y và có Y»®®A thì có X»®® (Z-Y). Hai tiên đề cuối cùng có liên quan đến FFD và FMVD: A7: Nếu có X»®Y thì có X»®®Y. A8: Nếu có X»®®Y, ZÍY, WÇY=Æ, và W»®Z thì có W»®Z. Bổ đề 2.9. Tập các tiên đề (A1-A8) là xác đáng. Nghĩa là, một phụ thuộc mờ có thể suy dẫn được từ tập G các phụ thuộc mờ, bằng các tiên đề (A1-A8) thì nó sẽ được thoả trong bất kỳ quan hệ r nào nếu r thoả mọi phụ thuộc có mặt trong tập G. 5.3. Tách không mất thông tin Giống như trong mô hình cổ điển, khi xuất hiện các phụ thuộc dữ liệu trong một lược đồ quan hệ, cần thiết phải khảo sát xem có thể tách-kết nối một quan hệ ban đầu thành những quan hệ nào đó sao cho có thể dùng phép kết nối tự nhiên để khôi phục lại được quan hệ ban đầu hay không. Ở mô hình đang xem xét, tương ứng với quan niệm đã đưa ra về dư thừa dữ liệu, có thể coi một phép tách-kết nối là không mất thông tin nếu có thể dùng phép kết nối tự nhiên mờ để có được một quan hệ mờ r’ tương đương (theo một ngưỡng a) với quan hệ ban đầu r. Định lý 2.3. Cho r là một quan hệ mờ với ngưỡng a trên lược đồ R(U). X, YU và XY=. Quan hệ r thoả FMVD X»®®Y khi và chỉ khi rr[XY]Vr[X(U-Y)]. Chứng minh: a) Giả sử với ngưỡng a, quan hệ r thoả X»®®Y, cần chứng tỏ rằng r@r[XY]Vr[XZ]. Với Z=U–Y. Lấy tÎr[XY]Vr[XZ], khi đó $t1Îr[XY] và $t2Îr[XZ] sao cho xảy ra đồng thời: t1[]»t2[], (1) t[]=MaX{t1[X], t2[X]}, (1’) t[Y]=t1[Y], (2) t[Z]=t2[Z] (3) Theo Định lý 2.1 từ (1’) ta được t[X]»t1[X]»t2 [X] (1’’) Do có X»®®Y, nên Y(t2[X])@Y(t2[X], t2[Z]) (4) Từ (1) được t1[Y]ÎY(t2[X]), kết hợp với (4) suy ra $t3ÎY(t2[X], t2[Z]) sao cho t3[Y]»t1[Y], nói cách khác đồng thời có t3[X]»t2[X] (5) t3[Y]»t1[Y] (6) t3[Z]»t2[Z] (7) Đối chiếu với (1’’), (2) và (3) được t»t3. Lấy tÎr, xét t[XY] và t1[XZ]. Nếu không có bộ t0Îr[XY] sao cho t0=t[XY] thì chứng tỏ phép chiếu r[XY] đã trộn t[XY] với một hay một số bộ của r[XY] và theo Định lý 2.1 thì $t1Îr[XY] : t1[XY]»t[XY]. Một cách tương tự có thể thấy $t2Îr[XZ]: t2[XZ]»t[XZ]. Khi kết nối tự nhiên r[XY] và r[XZ], vì có t1[]»t[X]»t2[X] nên $t’Îr[XY]Vr[XZ] sao cho: t’[X]=Ma {t1[X], t2[X]}»t[X], t’[Y]=t1[Y]»t[Y], t’[Z]=t2[Z]»t[Z] Vậy t’»t. b) Giả sử r@r[XY]Vr[XZ], cần chứng tỏ rằng quan hệ r thoả X»®®Y. Cần phải chỉ ra rằng Yr(x)@Yr(xz). Từ Bổ đề 2.8, chỉ cần chứng minh "y0ÎYr(x) $y’ÎYr(xz) sao cho y0»y’. Thật vậy, giả sử x là giá trị của bộ t trên thuộc tính X, t=Îr. Với y0ÎYr(x), gọi t0 là bộ mà y0 chính là giá trị của nó trên thuộc tính Y, t0=Îr. Rõ ràng là $t1=Îr[XY] sao cho t1[XY]=t0[XY] hoặc t1 là kết quả của việc trộn t0[XY] với một số bộ khác khi thực hiện phép chiếu r[XY]. Cả hai tình huống này đều cho thấy x1y1»x0y0. Với t=Îr, lập luận tương tự cũng có $t2=Îr[XZ] sao cho x2z2»xz. Vì y0ÎYr(x) nên x0»x. Lại có x1»x0 và x2»x. Nhờ tính bắc cầu của quan hệ », rõ ràng là x1»x2»x»x0. Do đó, khi thực hiện phép kết nối r[XY]Vr[XZ], t1 và t2 kết nối được với nhau và $t*=Îr[XY]Vr[XZ] với : x*=Ma{x1, x2}»x»x0 (1) y*=y1»y0 (2) z*=z2»z (3) Do giả thiết r@r[XY]Vr[XZ] nên $t’=Îr sao cho t*»t’. Đối chiếu với (1), (2), (3) được: x’»x (1’) y’»y0 (2’) z’»z (3’) Vậy "y0ÎYr(x) $y’ÎYr(xz) sao cho y’»y0. Từ định lý trên, có thể suy ra được hệ quả sau: Hệ quả. Cho r là một quan hệ mờ với ngưỡng a trên lược đồ R(U). X, YU và XY=. Nếu quan hệ r thoả FFD XY thì rr[XY]Vr[X(U-Y)]. 6. Kết luận Như vậy, trên đây đã trình bày mô hình mở rộng CSDLQH truyền thống dựa trên tính tương tự nhằm nắm bắt được các thông tin không chính xác và không chắc chắn. Các kết quả đạt được là tương đối đầy đủ và hoàn thiện, tuy nhiên trên thực tế vẫn chưa tìm được một mô hình nào để có thể áp dụng một cách có hiệu quả. Nhưng có thể thấy rằng khả năng cho phép thay đổi ngưỡng tương tự tuỳ theo mức độ và quan niệm mờ hoá tuỳ vào nhóm người dùng rất phù hợp và cần thiết trong các hệ trợ giúp quyết định, điều này sẽ cho phép người sử dụng tuỳ biến theo mức độ trợ giúp mà họ cần. Chương III. Chuẩn hóa mô hình CSDLQH dựa trên tính tương tự Chương này gồm có hai phần: phần thứ nhất sẽ trình bày định nghĩa về các dạng chuẩn của lược đồ CSDLQH dựa trên tính tương tự, dựa trên các định nghĩa này, trong phần thứ hai sẽ trình bày các thuật toán để chuẩn hoá một lược đồ CSDLQH dựa trên tính tương tự. 1. Các dạng chuẩn của CSDLQH dựa trên tính tương tự Trong các phần trước cũng đã đề cập đến khoá của các quan hệ trong mô hình CSDLQH dựa trên tính tương tự, nhưng vẫn chưa đưa ra một định nghĩa hình thức. Trong phần này để nghiên cứu về các dạng chuẩn trong CSDL mờ trước hết cần thiết phải đưa ra một định nghĩa về khoá cho mô hình CSDL này. Định nghĩa 3.1. Khoá của quan hệ r với ngưỡng tương tự a=(a1, a2,…, am) trên tập thuộc tính U={A1, A2,…, Am} là tập con KÍU sao cho bất kỳ hai bộ không dư thừa với nhau t1, t2 Î r luôn thoả t1(K)t2(K), bất kỳ tập con thực sự K’ÌK nào đó đều không có tính chất đó. Trước khi trình bày định nghĩa các dạng chuẩn cho mô hình này cần thiết phải đưa ra các khái niệm về thuộc tính khoá, phụ thuộc hàm mờ đầy đủ và phụ thuộc hàm mờ không đầy đủ. Định nghĩa 3.2. Cho một lược đồ quan hệ R(U) với ngưỡng tương tự a=(a1, a2,…, am) trên tập thuộc tính U={A1, A2,…, Am}. Thuộc tính A Î U được gọi là thuộc tính khoá nếu A là thành phần thuộc một khoá nào đó của R, ngược lại A được gọi là thuộc tính không khoá. Ví dụ 3.1: Cho lược đồ quan hệ R trên tập thuộc tính U={A, B, C, D}, với ngưỡng tương tự a cho trước, tồn tại các phụ thuộc hàm mờ AB»®C, B»®D và BC»®A. Rõ ràng AB và BC là khoá của lược đồ R. Khi đó A, B và C là thuộc tính khoá, còn D là thuộc tính không khoá. Định nghĩa 3.3. Cho lược đồ quan hệ R(U) với ngưỡng tương tự a=(a1, a2,… am) trên tập thuộc tính U={A1, A2,…, Am}, X và Y là hai tập thuộc tính khác nhau XÍU và YÍU. Ta nói Y phụ thuộc hàm mờ đầy đủ vào X nếu Y là phụ thuộc hàm mờ vào X nhưng không phụ thuộc hàm mờ vào bất kỳ một tập hợp con thực sự nào của X. Định nghĩa 3.4. Lược đồ quan hệ mờ R(U) với ngưỡng tương tự a cho trước được gọi là ở dạng chuẩn mờ thứ nhất nếu mỗi thuộc tính không khoá của R đều phụ thuộc hàm mờ đầy đủ vào khoá chính. Ví dụ 3.2: Cho lược đồ quan hệ R trên tập thuộc tính U={S, I, D, M} và các phụ thuộc hàm mờ SI»®D, SD»®M tương ứng với ngưỡng a đã cho trước. Ở đây chỉ có một khoá chính là SI và R là ở dạng chuẩn mờ thứ nhất. Có thể nhận thấy, dạng chuẩn mờ thứ nhất trong mô hình đang xem xét tương ứng với dạng chuẩn thứ hai trong mô hình CSDLQH truyền thống. Dạng chuẩn mờ thứ hai sắp được trình bày tới đây sẽ tương ứng với dạng chuẩn thứ ba trong mô hình CSDLQH truyền thống, do đó ở đây sẽ đưa thêm khái niệm về phụ thuộc bắc cầu tương ứng cho mô hình mới. Định nghĩa 3.5. Cho một lược đồ quan hệ mờ R(U) với ngưỡng tương tự a cho trước, X là một tập con các thuộc tính XÍU, A là một thuộc tính AÎU. A được gọi là phụ thuộc bắc cầu vào X trên R nếu tồn tại một tập con Y của R sao cho X»®Y, Y»®A nhưng Y »/®X (không xác định hàm) với AXY. Định nghĩa 3.6. Lược đồ quan hệ mờ R(U) với ngưỡng tương tự a cho trước được gọi là ở dạng chuẩn mờ thứ hai nếu nó là ở dạng chuẩn mờ thứ nhất và mỗi thuộc tính không khoá của R không phụ thuộc hàm mờ bắc cầu vào khoá chính. Ví dụ 3.3: Cho lược đồ quan hệ R trên tập thuộc tính U={C, S, Z} với một ngưỡng a đã xác định tồn tại các phụ thuộc hàm mờ CS»®Z, Z»®C. Trong lược đồ này mọi thuộc tính đều là thuộc tính khoá. Do vậy R là ở dạng chuẩn mờ thứ hai. Ví dụ 3.4: Cho lược đồ quan hệ R trên tập thuộc tính U={S, A, I, P} với một ngưỡng a đã xác định tồn tại các phụ thuộc hàm mờ IS»®P, S»®A. R không ở dạng chuẩn mờ thứ hai và cũng không ở dạng chuẩn mờ thứ nhất. Ở đây chỉ có một khoá chính là SI, nhưng A lại không phụ thuộc đầy đủ vào khoá chính và IS»®S và S»®A tức là A phụ thuộc bắc cầu vào khoá chính. 2. Chuẩn hoá lược đồ CSDLQH dựa trên tính tương tự Với các dạng chuẩn mờ đã nêu trong phần trên, phần này sẽ mở rộng các thuật toán được áp dụng cho quá trình chuẩn hoá CSDLQH truyền thống để chuẩn hoá một lược đồ CSDLQH dựa trên tính tương tự. Để có thể trình bày các thuật toán chuẩn hoá trong ngữ cảnh của mô hình mới, trước hết cần phải định nghĩa lại một số khái niệm về bao đóng của tập phụ thuộc hàm mờ, bao đóng của tập các thuộc tính đối với tập các phụ thuộc hàm mờ, hai tập phụ thuộc hàm mờ tương đương, tập phụ thuộc hàm mờ tối thiểu. Các khái niệm này sẽ lần lượt được phát biểu lại dưới đây. Định nghĩa 3.7. Cho lược đồ quan hệ R trên tập thuộc tính U={A1, A2,…, Am} với ngưỡng tương tự a=(a1, a2,…, am) cho trước, F là một tập phụ thuộc hàm mờ trên U. Bao đóng của tập phụ thuộc hàm mờ F được định nghĩa là tập tất cả các phụ thuộc hàm mờ được suy ra từ F bằng cách áp dụng các luật suy dẫn. Định nghĩa 3.8. Cho lược đồ quan hệ R trên tập thuộc tính U={A1, A2,…, Am} với ngưỡng tương tự a cho trước, F là tập phụ thuộc hàm mờ trên U tương ứng với ngưỡng tương tự a. XÍU, X+ gọi là bao đóng của X được định nghĩa là X+={AÎU/ X»®AÎF+}. Định nghĩa 3.9. Cho lược đồ quan hệ R(U), U={A1, A2,…, Am} với ngưỡng tương tự a cho trước. Cho hai tập phụ thuộc hàm mờ F và G trên U tương ứng với ngưỡng a. Ta nói F tương đương với G nếu F+=G+. Định nghĩa 3.10. Cho lược đồ quan hệ R(U), U={A1, A2,…, Am} với ngưỡng tương tự a cho trước. F là tập phụ thuộc hàm mờ trên U tương ứng với ngưỡng a. F được gọi là tập phụ thuộc hàm mờ tối thiểu nếu: Vế phải của các phụ thuộc hàm mờ của F chỉ chứa một thuộc tính. F={Li»®Ai/ LiÍU, Ai là một thuộc tính của U, i=1,2,…,m} F không dư thừa một phụ thuộc hàm mờ nào. "i=1,2,…,m có (F\{Li »®Ai})+¹F+. F không dư thừa một thuộc tính nào. "i= 1,2,…,m, xét Li»®Ai với Li=Ai1Ai2…Ain (n>1) thì "j=1,2,…,n (F\{Li»®Ai})È{Li\Aij»®Ai} không tương đương với F. Với các khái niệm trên, tiếp theo đây sẽ lần lượt nêu các thuật toán cần thực hiện trong quá trình chuẩn hoá một lược quan hệ dựa trên tính tương tự. Trong các thuật toán này cần phải qui ước rằng tập phụ thuộc hàm mờ F trên tập thuộc tính U là tương ứng với một ngưỡng tương tự a đã xác định trước nếu không đề cập đến. Thuật toán 3.1. (Thuật toán tính X+) Đầu vào: Tập hữu hạn các thuộc tính U, tập phụ thuộc hàm mờ F trên U tương ứng với ngưỡng a cho trước, tập thuộc tính XÍU. Đầu ra: X+, bao đóng của X đối với F. Cách tính: Tính liên tiếp tập các thuộc tính X0, X1,… theo qui tắc: Bước 0: Đặt X0=X. Bước i: Xi+1=XiÈA nếu $(Y»®A)ÎF, AÎZ và YÍXi. Ngược lại thì Xi+1=Xi. Do X=X0Í …ÍU, U là hữu hạn cho nên sẽ tồn tại một chỉ số i nào đó mà Xi=Xi+1, khi đó thuật toán sẽ dừng và đặt X+=Xi. Định lý 3.1. Thuật toán 3.1 tính X+ là đúng. Việc chứng minh định lý này tương tự như trường hợp cổ điển. Bổ đề 3.1. X»®Y nếu và chỉ nếu YÍX+. Thuật toán 3.2. Kiểm tra X»®YÎF+. Vào: tập thuộc tính U, tập phụ thuộc hàm mờ F, XÍU, YÍU. Ra: X»®YÎF+ đúng hay sai. Cách tính: Bước 1: Tính X+ theo Thuật toán 3.1. Bước 2: Kiểm tra YÍX+ đúng hay sai, nếu đúng thì X»®YÎF+ còn sai thì X»®YÏF+. Thuật toán 3.3. Kiểm tra tính tương đương của hai tập phụ thuộc hàm. Vào: F, G – các tập phụ thuộc hàm mờ trên U. F={Li»®Ri/ i=1,2,…,m}, G={Lj’»®Rj’/ j=1,2,…,n}. Ra: kết luận F tương đương với G hoặc F không tương đương với G. F tương đương với G khi và chỉ khi F+=G+ tức là đồng thời F+ÍG+ và G+ÍF+. Cách làm: Bước 1: "i=1,2,…,m kiểm tra Li»®RiÎG+ đúng hay sai theo Thuật toán 3.2, nếu đúng thì thực hiện Bước 2 còn nếu sai thì kết luận F không tương đương với G. Bước 2: "j=1,2,…,n kiểm tra Lj’»®Rj’ÎF+ đúng hay sai theo Thuật toán 3.2, nếu đúng thì kết luận F tương đương với G còn nếu ngược lại thì kết luận F không tương đương với G. Thuật toán 3.4. Tìm phủ không dư thừa. Vào: tập phụ thuộc hàm mờ F trên tập thuộc tính U. Ra: F’ tương đương với F và F’ không dư thừa một phụ thuộc hàm mờ nào. Cách làm: Bước 0: đặt F0=F. Bước i: Tính Fi=Fi-1\{Li»®Ri}nếu Li»®RiÎ(Fi-1\{Li»®Ri})+. Ngược lại Fi=Fi-1. Do F là hữu hạn cho nên sẽ tồn tại một chỉ số i nào đó mà Fi+1=Fi, khi đó thuật toán sẽ dừng và cho F’=Fi. Thuật toán 3.5. Tìm phủ tối thiểu. Vào: F - tập phụ thuộc hàm mờ trên U, F={Li»®Ri/ i=1,2,…,m}. Ra: F’ tương đương với F và F’ là tập phụ thuộc hàm mờ tối thiểu. Cách làm: Bước 1: "i=1,2,…,m, nếu Ri=Ai1Ai2…Aik, k>1 thì thay Li»®Ri bởi Li»®Aij, j=1,2,..k. Khi đó sẽ được F1={Li»®Ai/ i=1,2,..,m1} Bước 2: Tìm phủ không dư thừa của F1 theo Thuật toán 3.4. kết quả được F2={Li»®Ai/ i=1,2,…,m2}. Bước 3: "i=1,2,…,m2, nếu Li=Ai1Ai2…Aik, k>1: 1) Đặt Li0=Li. 2) Lặp Lij= Lij-1\Aij nếu Lij-1\Aij»®Ai. Ngược lại Lij=Lij-1. Khi nào tồn tại chỉ số j mà Lij+1=Lij thì dừng và đặt Li =Lij. Kết quả cuối cùng được F3={Li»®Ai/ i=1,2,..,m3}, đặt F’=F3 là tập phụ thuộc hàm mờ tối thiểu. Thuật toán 3.6. Chuẩn hoá sơ đồ quan hệ về dạng chuẩn mờ thứ hai bảo toàn tập phụ thuộc hàm mờ. Vào: Lược đồ quan hệ R trên tập thuộc tính U và tập phụ thuộc hàm mờ F. Ra: Phép tách t chuẩn hoá R về dạng chuẩn mờ thứ hai bảo toàn tập phụ thuộc hàm mờ. Cách làm: Bước1: Tính U0=U\LiAi. Bước 2: Kiểm tra nếu $Li»®AiÎF mà LiAi=U\U0 thì t= và dừng thuật toán. Bước 3: Với mọi phụ thuộc hàm mờ xét "i=1,2,..,m nếu Li»®Ai1,…, Li»®Aik thì Si=, Fi={Li»®Ai1,…, Li»®Aik}. Cuối cùng được phép tách t={Si} Thuật toán 3.7. Tìm một khoá tối thiểu. Vào: Tập thuộc tính U={A1, A2,…, An} và tập phụ thuộc hàm mờ F trên U. Ra: K – Khoá tối thiểu. Cách làm: Bước 0: Đặt K0=U. Bước 2: Lặp Ki=Ki-1\{Ai} nếu Ki-1\{Ai}»®U. Ngược lại thì Ki=Ki-1, và bước lặp sẽ dừng. Đặt K=Ki. Thuật toán 3.8. Chuẩn hoá lược đồ quan hệ R về dạng chuẩn mờ thứ hai không làm mất mát thông tin và bảo toàn tập phụ thuộc hàm mờ. Vào: Lược đồ quan hệ mờ R trên tập thuộc tính U và tập phụ thuộc hàm mờ F. Ra: Phép tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm mờ sao cho mỗi lược đồ con đều ở dạng chuẩn mờ thứ hai. Cách làm: Bước 1: Tìm phép tách t bảo toàn tập phụ thuộc hàm mờ theo Thuật toán 3.6. Bước 2: Tìm một khoá tối thiểu theo Thuật toán 3.7. Bước 3: t’=, nếu tồn tại Si mà KÍUi thì t=t’ ngược lại thì t=t’È. 3. Kết luận Như vậy chương này đã trình bày hai dạng chuẩn của một lược đồ CSDLQH dựa trên tính tương tự. Hai dạng chuẩn này tương ứng với hai dạng chuẩn một và chuẩn hai trong mô hình CSDLQH truyền thống. Về các dạng chuẩn hoá có thể tiếp tục nghiên cứu các dạng tương ứng với dạng chuẩn bốn và dạng chuẩn Boye-Codd. Chương này cũng đã đưa ra những thuật toán để tiến hành chuẩn hoá một lược đồ quan hệ dựa trên tính tương tự khi trên lược đồ đó đã xác định một ngưỡng tương tự a và một tập các phụ thuộc hàm mờ tương ứng với ngưỡng a đó. Chương IV. Cài đặt thử nghiệm Chương này trình bày phần cài đặt một mô đun cho phép thực hiện các thao tác xử lý với các dữ liệu của các quan hệ trên một lược đồ thuộc mô hình đang xem xét, tiếp theo sẽ sử dụng mô đun đó để thao tác thử nghiệm trên CSDL được sử dụng minh hoạ trong Chương II. 1. Yêu cầu cần thực hiện Mặc dù hiện tại, trong thực tế chưa có những bài toán thích hợp để có thể sử dụng có hiệu quả mô hình đã đưa ra, tuy nhiên như đã nêu trong các phần trên, mô hình này có triển vọng ứng dụng rất lớn trong các Hệ trợ giúp quyết định, do đó cần thiết phải có một mô đun cho phép thực hiện các phép toán xử lý dữ liệu, các thao tác cập nhật dữ liệu trong mô hình. Có thể nêu lên các nhiệm vụ của một chương trình ứng dụng sử dụng mô hình này như sau: - Đối với những người dùng khác nhau họ sử dụng các ngưỡng tương tự khác nhau. Do vậy cần thiết phải lưu trữ CSDL dưới dạng một ngưỡng cơ sở nào đó. Khi một người sử dụng bắt đầu thao tác trên cơ sở dữ liệu, cho phép họ chọn ngưỡng tương tự mà họ mong muốn, và chương trình cần phải tiến hành tạo ra một CSDL với ngưỡng tương tự đó bằng cách tiến hành trộn các bộ dữ liệu ở ngưỡng cơ sở theo ngưỡng người sử dụng đưa vào. - Khi đã tạo ra CSDL tương ứng với một người sử dụng thì cho phép họ tiến hành các thao tác trích rút các thông tin cần thiết thông qua việc thực hiện các phép toán đại số quan hệ mở rộng. Đối với các phép chọn và kết nối chỉ xét các phép chọn chặt và kết nối chặt. - Đối với những người có đủ thẩm quyền có thể thực hiện các thao tác thay đổi CSDL gốc thông qua các thao tác cập nhật như chèn một bộ, xoá một bộ và thay đổi một bộ. Từ đó có thể thấy mô đun cần thiết kế phải cho phép trộn các bộ, thực hiện các phép toán quan hệ, cập nhật dữ liệu. Còn tuỳ thuộc vào đối tượng sử dụng mà chương trình ứng dụng sử dụng mô đun này sẽ hạn chế bớt các thao tác không được phép. Qua định nghĩa của các phép toán trong Chương II có thể thấy rằng thao tác trộn các bộ theo một ngưỡng a cho trước là thao tác được hầu hết các phép toán sử dụng. Do đó cài đặt thao tác này là nhiệm vụ trung tâm của toàn bộ quá trình. Tiếp theo sẽ đi phân tích chi tiết đầu vào và đầu ra của các phép xử lý dữ liệu. Phép trộn: Đầu vào: một quan hệ r, ngưỡng tương tự a, cần thiết phải có tập các miền trị của các thuộc tính trong r cùng với quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: một quan hệ r’ là kết quả của việc trộn các bộ trong r theo ngưỡng tương tự a. Phép hợp: Đầu vào: hai quan hệ r và s đã được trộn theo ngưỡng a, cũng cần thiết phải có tập các miền trị của các thuộc tính trong r và s cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: quan hệ u là kết quả của việc trộn các bộ của r và s theo ngưỡng tương tự a. Phép giao: Đầu vào: hai quan hệ r và s đã được trộn theo ngưỡng a, cũng cần thiết phải có tập các miền trị của các thuộc tính trong r và s cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: là một quan hệ u kết quả của việc tiến hành trộn chỉ các bộ thuộc r với các bộ thuộc s mà chúng tương đương nhau theo ngưỡng a. Phép hiệu: Đầu vào: hai quan hệ r và s đã được trộn theo ngưỡng a, cũng cần thiết phải có tập các miền trị của các thuộc tính trong r và s cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: là quan hệ u kết quả của việc loại những bộ thuộc r mà chúng có các bộ tương đương thuộc s. Phép chiếu: Đầu vào: quan hệ r, các thuộc tính sẽ chiếu và tập các miền trị của các thuộc tính sẽ chiếu cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: là quan hệ r’ kết quả của việc trộn các bộ trong r trên các thuộc tính được chiếu theo ngưỡng tương tự a. Phép chọn chặt: Đầu vào: quan hệ r đã được trộn theo ngưỡng a, điều kiện chọn f và miền trị của các thuộc tính trong r cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: là các bộ thoả mãn điều kiện chọn f. Phép kết nối chặt: Đầu vào: hai quan hệ r, s đã được trộn theo ngưỡng a, các thuộc tính kết nối và miền trị của các thuộc tính trong r và s cùng quan hệ tương tự giữa các giá trị trong cùng một miền. Đầu ra: quan hệ u là các bộ gồm các thuộc tính kết nối và các thuộc tính không kết nối của r và s thoả mãn điều kiện hai bộ thuộc r và s hợp thành bộ mới trong u phải có giá trị trên các thuộc tính kết nối tương tự nhau theo ngưỡng a. 2. Thiết kế mô đun Từ những phân tích nêu trên thì mô đun cần thiết kế cần phải có các thành phần như trong Hình 4.1. Hình 4.1. Các thành phần chính của mô đun. Khối Vào các quan hệ tương tự có nhiệm vụ nhận các quan hệ tương tự của các miền trị của các thuộc tính, phân hoạch chúng theo ngưỡng tương tự được xác định trên mỗi miền thành các lớp tương đương. Khối Vào các quan hệ, các ngưỡng tương tự có nhiệm vụ nhận các quan hệ cần xử lý và các ngưỡng tương tự cần xử lý. Khối Trộn các quan hệ có nhiệm vụ thông qua các lớp tương đương của các miền trị của các thuộc tính, kết hợp với các ngưỡng tương tự cần xử lý, trộn các bộ của các quan hệ được đưa vào. Khối Thực hiện các thao tác xử lý sẽ tiến hành các thao tác xử lý như: thêm, xoá, sửa, chiếu, hợp,… Và trong khối này có thể có các thao tác xử lý vẫn cần phải thực hiện phép trộn các quan hệ. Khối Kết quả sẽ đưa ra các kết quả tương ứng với từng thao tác xử lý. Công cụ được sử dụng để cài đặt mô đun này là ngôn ngữ lập trình C#.Net. 3. Một số kết quả thử nghiệm Trong phần này sẽ sử dụng mô đun đã được cài đặt ở trên để xây dựng một ứng dụng nhỏ cho phép thao tác với CSDL ví dụ đã đề cập đến trong Chương II. Ví dụ này có các quan hệ tương tự của trên các miền trị của các thuộc tính thể hiện trong các hình: Hình 2.5, Hình 2.6. Ở đây sẽ đưa vào quan hệ tương tự trên trị của thuộc tính Tên trong Hình 4.1 dưới đây. An Bình Phúc Lộc Thọ Tài An 1 0.5 0 0 0 0 Bình 0.5 1 0 0 0 0 Phúc 0 0 1 0.5 0 0 Lộc 0 0 0.5 1 0 0 Thọ 0 0 0 0 0 0 Tài 0 0 0 0 0 0 Hình 4.2. Quan hệ tương tự trên miền thuộc tính Tên. Với các điều kiện đã nêu. dưới đây là một số kết quả thử nghiệm. Hình 4.3. Kết quả phép chọn. Hình 4.4. Kết quả phép chiếu trên hai thuộc tính Tên và Màu xe Hình 4.5. Kết quả của thao tác xóa. Hình 4.6. Kết quả của thao tác sửa. Hình 4.7. Kết quả của thao tác thêm một bộ không hợp lệ. Hình 4.8. Kết quả của thao tác thêm một bộ khi đã thay đổi ngưỡng tương tự. Tài liệu tham khảo: [1]. Lê Tiến Vương, Nhập môn cơ sở dữ liệu quan hệ, Nhà xuất bản Khoa học và kỹ thuật, 1996. [2]. Hồ Cẩm Hà, Cơ sở dữ liệu quan hệ với thông tin không đầy đủ, Luận án tiến sĩ, Hà Nội, 2001. [3]. Bùi Thị Thuý Hiền, Hệ hỗ trợ quyết định với thông tin không đầy đủ theo cách tiếp cận null ngữ cảnh, Luận án tiến sĩ, Hà Nội, 1999. [4]. Nguyễn Kim Anh, Bài giảng môn cơ sở dữ liệu I, Đại học Bách khoa Hà Nội. [5]. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Thống kê, 2000. [6]. Phương Lan, Lập trình Windows với C#.Net, Nhà xuất bản Lao động xã hội, 2002. [7]. Jeffrey D.Ulman, Principles of database systems, Computer science press, 1983.