BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN HỌC VIỆN NÔNG NGHIỆP VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN PGS.TS NGUYỄN VĂN ĐỊNH BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ NGÀNH CƠNG NGHỆ THÔNG TIN HÀ NỘI 2015 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Chương TỔNG QUAN VỀ CSDL PHÂN TÁN Chương này, đề cập đến số khái niệm kết liên quan đến việc thiết kế CSDL phân tán 1.1 CẤU TRÚC CỦA HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Dữ liệu thành phần thiếu ứng dụng cơng nghệ thơng tin Q trình phát triển CNTT kéo theo trình phát triển công nghệ CSDL 1.1.1 Sự phát triển công nghệ CSDL Công nghệ lưu trữ xử lý liệu trải qua giai đoạn phát triển sau: - Xử lý tệp truyền thống: Trong mơ hình này, liệu lưu trữ thành tệp riêng rẽ, mô tả gắn kết với chương trình ứng dụng Hình 1.1 Sơ đồ xử lý tệp truyền thống Cách xử lý phát sinh vấn đề dư thừa liệu dị thường cập nhật Chẳng hạn, có chương trình ứng dụng với tệp liệu riêng, tệp liệu lại có thơng tin giống nhau, tạo nên dư thừa liệu, gây lãng phí cho lưu trữ quản lý Nguy hại cập nhật thay đổi thông tin thực thể tệp liệu phải thay đổi tệp với đối tượng Điều khó thực triệt để có nhiều tệp liệu có chứa thông tin trùng lặp, gây dị thường cập nhật (thông tin không quán, thông tin mâu thuẫn ) - Xử lý CSDL (Database-DB): Để khắc phục nhược điểm mơ hình xử lý tệp, liệu ứng dụng lưu trữ tập trung, mô tả xử lý thống cho chương trình ứng dụng Các liệu tập trung lại thành CSDL, xử lý theo cách thống cho tất ứng dụng có liên quan Như vấn đề tập trung liệu mấu chốt xử lý CSDL Công nghệ CSDL bước tiến lớn công nghệ xử lý liệu Rõ ràng nhờ tập trung liệu, CSDL khắc phục dư thừa liệu, hạn chế dị thường cập nhật Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Hình 1.2 Sơ đồ xử lý CSDL Các hệ CSDL xuất từ năm 1960, từ đến chứng kiến nhiều hệ quản trị CSDL đời FoxBase, FoxPro, MS Access, MySQL, SQL Server, Firebird, Oracle Hình 1.3 Sơ đồ hình thành CSDL phân tán - Công nghệ CSDL phân tán (Distributed Database-DDB): Khi cơng nghệ mạng máy tính đời, người ta phân chia CSDL tập trung thành CSDL cục đặt máy tính khác (các trạm/ sites) kết nối mạng truyền thông Các CSDL cục tích hợp với qua mạng máy tính mà khơng cần có tập trung liệu Do xây dựng hệ thống CSDL, liệu phân tán mạng máy tính Đó cách tiếp cận CSDL phân tán Có thể nhận thấy điều thú vị là: Cơng nghệ mạng máy tính xúc tiến kiểu làm việc ngược lại nỗ lực tập trung hóa cơng nghệ CSDL, hai xu hướng trái ngược Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn lại tổng hợp lại đời công nghệ mạnh mẽ nhiều so với công nghệ riêng lẻ: cơng nghệ CSDL phân tán Do thấy mục tiêu quan trọng công nghệ CSDL tích hợp liệu khơng phải tập trung hóa, có nghĩa tích hợp liệu để quản lý sử dụng chung mà khơng cần tập trung hóa chất CSDL phân tán Một số ứng dụng CSDL phân tán Có nhiều lý để cần phải có nhiều CSDL hệ thống phân tán như: + Nhiều database gắn với nhiều chức hệ thống như: Bộ phận sản xuất, phận quản lý nhân sự, phận bán hàng… chức lại hệ thống độc lập có nhu cầu lấy thơng tin lẫn + Đơn vị sử dụng hệ thống database có nhiều trụ sở đặt nhiều vị trí địa lý khác cách xa nhau, Thí dụ hệ thống quản lý tài khoản mạng điện thoại di động, server game… + Những ứng dụng đòi hỏi liệu có tốc độ truy xuất cao đặt copy nhiều server, việc truy xuất phân tải cho server để đảm bảo hiệu năng, liệu phần copy phải đảm bảo đồng tuyệt + Nhiều ứng dụng khác địi hỏi phải truy xuất vào liệu theo cách khác nhau, địi hỏi phải có chế truy xuất khác Hình 1.4 Một ứng dụng CSDL phân tán Hình 1.4 mơ tả ứng dụng điển hình CSDL phân tán doanh nghiệp gồm có phận chính: Trụ sở nơi điều hành hoạt động doanh nghiệp, cân đối dự báo tài chính…, Bộ phận sản xuất nơi sản xuất, lập kế hoạch SX kế hoạch nguyên liệu… Bộ phận bán hàng nhận đơn đặt hàng, phân phối hàng hóa, dịch vụ sau bán hàng… Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Các phận doanh nghiệp đặt vị trí địa lý khác nhau, CSDL doanh nghiệp kết nối theo mơ hình CSDL phân tán 1.1.2 Cấu trúc hệ CSDL phân tán Có thể đưa định nghĩa cho CSDL phân tán theo cách mô tả sau: Định nghĩa 1.1: CSDL phân tán tập hợp CSDL hợp tác hoạt động, lưu trữ máy tính khác (gọi trạm/sites) kết nối với mạng truyền thông quản lý hệ quản trị CSDL phân tán Một cách lý tưởng, người dùng trạm truy cập thao tác liệu trạm nào, CSDL người dùng nhìn thấy xử lý CSDL tập trung, người dùng khơng biết khơng cần biết đến phân tán liệu Tính chất phát biểu: “sự phân tán liệu suốt người dùng” Các thành phần CSDL phân tán: * Về mặt vật lý: Yếu tố để phân biệt sở liệu phân tán với sở liệu tập trung là: - Cơ sở liệu phân tán phải có nhiều máy tính gọi trạm (sites/nodes) - Các trạm phải kết nối kênh truyền thơng để truyền liệu (trao đổi liệu) bao gồm giao thức truyền thơng Hình 1.4 Các thành phần CSDL phân tán * Về mặt logic: Phần mềm quản trị CSDL phân tán gồm module sau: - Xử lý liệu (DP-Database Processing): Quản lý liệu cục trạm giống với sở liệu tập trung - Xử lý ứng dụng (AP-Application Processing): Module xử lý ứng dụng liệu trạm, xử lý giao dịch trạm truy cập thông tin phân tán trạm - Xử lý truyền thông (CP-Communication Processing): Module có nhiệm vụ liên kết (kết nối) trạm với kênh truyền thông Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn * Ngoài hệ quản trị sở liệu phân tán cịn có thêm số chức năng: - Quản lý từ điển liệu tổng thể lưu trữ thông tin liên quan đến liệu phân tán (các thông tin xem siêu liệu - Super Data) - Định nghĩa liệu phân tán - Kiểm tra ngữ nghĩa liệu - Định giá (trả lời) câu hỏi phân tán - Quản lý giao dịch phân tán * Một số ưu điểm tiềm hệ CSDL phân tán: - Thích hợp cho chất phân tán nhiều ứng dụng sở liệu - Cho phép dùng chung liệu trì điều khiển cục - Nâng cao hiệu hệ thống: CSDL phân tán bao gồm nhiều CSDL cục nhiều trạm, nên cho phép tăng khả truy cập, thực nhiều xử lý song song, tăng hiệu suất, tốc độ xử lý liệu ứng dụng - Tăng độ tin cậy an toàn liệu: liệu lưu trữ nhiều đồng nên có khả khôi phục liệu xảy cố vài trạm Kết luận: Như vậy, xem CSDL phân tán sưu tập liệu mà mặt logic thuộc hệ thống CSDL mặt vật lý phân bố trạm mạng máy tính Hệ quản trị CSDL phân tán (để cho gọn ta gọi chung hệ quản trị CSDL hay DBMS, không gây nhầm lẫn) hệ thống phần mềm cho phép quản lý CSDL phân tán, làm cho việc phân tán trở nên suốt với người dùng (Hồ Thuần Hồ Cẩm Hà, 2007) 1.2 CÁC MƠ HÌNH PHÂN TÁN DỮ LIỆU 1.2.1 Tính khơng hệ CSDL phân tán Để xây dựng CSDL phân tán, người ta phải phân bố liệu trạm khác Mỗi cách tiếp cận cho việc phân bố liệu nhận CSDL phân tán với tính chất khác 1.2.1.1 CSDL phân tán (Homogeneous DDB) Tính CSDL phân tán thể tính chất bản: (i) Các CSDL cục có mơ hình CSDL có cấu trúc liệu (ii) Các CSDL cục quản trị hệ quản trị CSDL Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Hình 1.5 Thiết kế CSDL phân tán Nói chung điều kiện (ii) thường bao gồm điều kiện (i), CSDL cục quản trị hệ QTCSDL CSDL phải có mơ hình (chẳng hạn mơ hình quan hệ) Một CSDL phân tán thường có từ việc chia CSDL tập trung thành tập CSDL cục Như vậy, CSDL phân tán thường kết cách thiết kế “từ xuống” Theo cách này, ta thiết kế CSDL phân tán từ CSDL tập trung, tách thành trạm, tạo thuận lợi cho cho tăng trưởng tổ chức (cơ quan, doanh nghiệp…) Mơ hình cải thiện hiệu việc quản lý khai thác liệu nhờ khả xử lý song song cung cấp có mặt nhiều trạm 1.2.1.2 CSDL phân tán khơng (Hetorogeneous DDB) Tính khơng CSDL phân tán thể việc khơng thỏa (hoặc hai) tính chất (i) (ii) Một CSDL phân tán không thường xây dựng việc tích hợp CSDL cục có thành hệ thống CSDL Các CSDL cục thiết kế theo nhiều mơ hình liệu khác nhau, có cấu trúc liệu khác quản trị hệ quản trị liệu khác Như vậy, CSDL phân tán không thường kết thiết kế “từ lên”, cho phép tích hợp CSDL có độc lập với nhau, vậy, tạo CSDL hoàn toàn Như vậy, chức chung, hệ quản trị CSDL phân tán không phải cung cấp giao diện để hệ quản trị CSDL cục giao tiếp với nhau, việc thường giải cách xây dựng “mơ hình trụ cột” chung cho tất CSDL cục bộ, thao tác CSDL cục thơng qua mơ hình trụ cột Rõ ràng tiếp cận không cho việc phân tán liệu phức tạp nhiều so với cách tiếp cận Oracle hệ quản trị CSDL hỗ trợ việc liên kết liệu CSDL phân tán không Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Hình 1.6 Thiết kế CSDL phân tán khơng 1.2.2 Các mơ hình phân tán liệu 1.2.2.1 Cơ sở liệu từ xa (Remote Database) - Khái niệm: Cơ sở liệu từ xa (remote database) CSDL đặt máy tính khác với máy tính người dùng truy cập nhờ vào lệnh truyền thông xác định người dùng - Các đặc điểm remote DB: + Máy tính người dùng trì CSDL riêng nạp từ CSDL từ xa máy chủ + Việc quản trị CSDL từ xa thực DBMS máy chủ + Việc quản trị CSDL người dùng thực máy trạm người dùng, phiên micro DBMS máy chủ, người dùng phải đảm bảo quán dự liệu riêng với liệu máy chủ + Nói chung việc truy cập CSDL từ xa thường hạn chế việc tra cứu thông tin, phép cập nhật làm theo cách tập trung máy chủ Cách tiếp cận CSDL từ xa cho chức hạn chế, không vấp phải vấn đề khó khăn CSDL phân tán (quản lý từ điển liệu, xử lý giao dịch phân tán…) Thí dụ 1.1 Phịng đào tạo có CSDL đặt máy chủ gồm danh sách SV khóa mơn học, điểm kiểm tra, điểm chuyên cần, điểm thi Giáo viên sinh viên truy cập tải đề sử dụng Đây mơ hình CSDL từ xa 1.2.2.2 Cơ sở liệu liên hiệp (federated database) Cơ sở liệu liên hiệp (federated database) mô hình phân tán liệu bao gồm CSDL cục bộ, CSDL cục khơng tích hợp thành CSDL với CSDL phân tán mà chúng tạo thành liên tác, phạm vi chúng trao đổi liệu Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn Cách tiếp cận CSDL liên hiệp nhằm tránh gặp phải khó khăn lớn việc quản trị tập trung CSDL phân tán, có số lớn CSDL cục tham gia, là: - Việc quản trị tập trung CSDL phân tán phức tạp số trạm lớn - Mọi truy cập tới CSDL phân tán thông qua hệ quản trị CSDL - Khi truy cập tới đơn vị liệu dù trạm cục thông qua hệ quản trị CSDL phân tán làm cho tốc độ xử lý liệu cục chậm lại chi phí việc quản lý liệu phân tán Trong CSDL liên hiệp, người ta nới lỏng ràng buộc chặt giừa CSDL cục cung cấp cho người dùng ngôn ngữ để định nghĩa mối quan hệ CSDL khác thao tác nhiều CSDL lúc nhờ ngôn ngữ đa sở liệu (multidatabase language) Thường khơng có q nhiều máy trạm CSDL liên hiệp Một số đặc điểm CSDL liên hiệp: - Nhằm ưu tiên người dùng thao tác CSDL cục xem việc truy cập tới CSDL khác không thường xuyên - Sự phân tán không suốt người dùng Sự khác hệ quản trị CSDL liên hiệp hệ quản trị CSDL phân tán là: - Không quản lý từ điển liệu tổng thể - Hỗ trợ ngôn ngữ để định nghĩa phụ thuộc có CSDL liên hiệp (multidatabase language) - Hỗ trợ ngôn ngữ để định nghĩa thao tác CSDL thuộc liên hiệp (multidatabase language) 1.2.2.3 Cơ sở liệu song song (parallel database) Một mơ hình phân tán liệu khai thác nhiều thời gian gần việc phân bố liệu tập nút (nodes) máy tính song song (siêu máy tính với đa xử lý) để tăng hiệu việc quản lý liệu Mơ hình cịn gọi sở liệu song song (parallel database) (Hình 1.7) CSDL song song mơ tả sau: - Phần cứng: Là máy tính song song (siêu máy tính với nhiều vi xử lý), node máy tính song song xử lý CSDL cục Các liên hệ node thông qua bus liệu máy tính - Phần mềm: Dùng chung phần mềm quản trị CSDL Cơ sở liệu song song xem hộp đen xử lý liệu thường gọi “máy Cơ sở liệu” (database machine) Sự giống khác CSDL phân tán CSDL song song: - Giống nhau: Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn + Cùng có nhiều CSDL cục + Có chung phần mềm quản lý CSDL + Hoạt động CSDL phân tán - Khác nhau: + Chỉ có máy đặt trạm + Khơng dùng kênh truyền thơng Hình 1.7 Cơ sở liệu song song (Máy sở liệu) 1.3 CÁC TÍNH CHẤT CƠ BẢN CỦA MỘT HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Các hệ quản trị CSDL phân tán phải làm cho người sử dụng hệ thống không cần biết tới phân tán liệu việc sử dụng CSDL phân tán phải khơng khó CSDL tập trung Như hệ quản trị CSDL phân tán phải cung cấp mức độc lập khác liệu người dùng, nói cách khac, hệ quản trị CSDL phân tán phải tạo nên tính chất hệ CSDL phân tán, mục tiêu hệ CSDL phân tán 1.3.1 Tính độc lập phân bố liệu Nhờ tính chất này, người dùng không cần quan tâm tới phân tán liệu khơng biết có phân tán Thông tin phân tán liệu (chẳng hạn quan hệ phân tán thành quan hệ đặt trạm khác nhau) lưu trữ từ điển liệu tổng thể hệ quản trị CSDL phân tán tham khảo để xác định vị trí thơng tin Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn C(Y[t1, t2])  {  , C(X[t1, t2])} Ở   [0, 1], độ mạnh ngữ nghĩa phụ thuộc hàm, tức mức độ khẳng định phát biểu phụ thuộc hàm mờ, nói chung  lớn phát biểu phụ thuộc hàm có ý nghĩa, thường chọn  < C(X[t1, t2], tốt nên chọn  = C(X[t1, t2]) Nếu khơng quan tâm đến ngữ nghĩa, ta có bỏ qua độ mạnh phụ thuộc hàm mờ điển: Nhận xét 7.1.2 Một vài so sánh định nghĩa phụ thuộc hàm mờ với phụ thuộc hàm kinh  Y thỏa quan hệ r: với cặp (t1, t2) r Phụ thuộc hàm (rõ) X  t1[X] = t2[X] suy t1[Y] = t2[Y]  Phụ thuộc hàm mờ X  Y thỏa quan hệ r: với cặp (t1, t2) r t1[X] t2[X] gần với mức  = C(X[t1, t2]), suy t1[Y] t2[Y] phải gần với mức > min(, )  Tức là: X  Y C(Y[t1, t2])  {  , C(X[t1, t2])}  Y thỏa quan hệ r, coi phụ thuộc hàm Nếu có phụ thuộc hàm (rõ) X   Y thỏa r mờ (với độ mạnh 1) X  Thí dụ 7.5 Xét quan hệ mờ VEHICLE cho bảng 7.4 đây, với quan hệ tương tự thuộc tính COLOR PRICE cho hai bảng 7.2 7.3 Bảng 7.4 Quan hệ mờ VIHICLE VIHICLE (TYPE, COLOR, PRICE) VIHICLE TYPE COLOR PRICE t1 {sportcar} {blue, green} {very expensive} t2 {wagon} {red} {modest, affordable} t3 {motorbile} {green} { modest } Hãy kiểm tra phụ thuộc hàm mờ COLOR  PRICE có thỏa quan hệ mờ khơng? 0,6 0,6 Giải: Quan hệ VIHICLE gọi thỏa phụ thuộc hàm mờ COLOR   PRICE cặp thỏa phụ thuộc hàm Theo định nghĩa FFD, ta cần kiểm tra điều kiện: C(Y[t1, t2])  {  , C(X[t1, t2])}, với X = {COLOR}, Y = {PRICE},  = 0.6 - Với hai t1 t2, ta có: t1 = , hay t1 = t2 = , hay t2 = Ta tính mức độ gần t1 t2 thuộc tính COLOR PRICE: - Với thuộc tính COLOR d1 = {B, G} giá trị t1 miền giá trị COLOR d2 = {R} giá trị t2 miền giá trị COLOR C(COLOR[t1, t2]) = {min{max[s(B, R), s(G, R)]}, min{max[s(R, B), s(R, G)]}} = min{min{max[0, 0]}, min{max[0, 0]}} =0 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 137 Vậy min{0,6, C(COLOR[t1, t2]) } = min{0,6, 0} = - Với thuộc tính PRICE: d1 = {VE} giá trị t1 miền giá trị PRICE d2 = {M, AF} giá trị t2 miền giá trị PRICE C(PRICE[t1, t2]) = min{min{max[s(VE, M), s(VE, AF)]}, min{max[s(M, VE), s(VF, AF)]}} = min{min{max[0, 0]}, min{max[0, 0]}} =0 Vậy C(PRICE[t1, t2]) > min{0,6, C(COLOR[t1, t2])}, theo định nghĩa t1 t2 thỏa mãn phụ 0,6 thuộc hàm COLOR   PRICE - Với hai t1 t3: Tương tự ta tính mức độ gần t1 t3 thuộc tính PRICE COLOR: C(COLOR[t1, t3]) = C(PRICE[t1, t3]) = Vậy ta có C(PRICE[t1, t3]) > Min{0,6, C(COLOR[t1, t3])}, hay t1 t3 thỏa mãn phụ 0,6 thuộc hàm COLOR   PRICE Với hai t2 t3 Tương tự ta tính mức độ gần t2 t3 thuộc tính PRICE COLOR: C(COLOR[t2, t3]) = C(PRICE[t2, t3]) = 0,8 Vậy ta có C(PRICE[t2, t3]) > Min{0,6, C(COLOR[t2, t3])} = 0,6, t2 t3 thỏa mãn 0,6 phụ thuộc hàm COLOR   PRICE Vậy quan hệ mờ VEHICLE thỏa phụ thuộc hàm COLOR 0.6  PRICE Phụ thuộc hàm mờ phát biểu: “Màu sắc - nhiều xác định giá xe”, ‘ít nhiều’ với mức độ 0.6, tức màu sắc có tác động chút đến giá xe 6.5.3 Quy tắc suy diễn cho phụ thuộc hàm mờ Một khái niệm quan trọng có liên quan tới phụ thuộc liệu quy tắc suy diễn Cho quan hệ tập phụ thuộc hàm, quy tắc suy diễn phép sinh phụ thuộc hàm thỏa quan hệ cho, chúng có quan hệ gần gũi với định nghĩa ngữ nghĩa phụ thuộc hàm Đối với CSDL quan hệ kinh điển, biết hệ tiên đề Armstrong tập quy tắc suy diễn cho phụ thuộc hàm Nhắc lại hệ tiên đề Armstrong quy tắc suy diễn: Hệ tiên đề Armstrong: Cho lược đồ quan hệ R = < U, F >, với U = {A1, A2, , An} tập thuộc tính Giả sử X, Y, Z  U; ký hiệu XY thay cho XY, ta có tiên đề sau: (A1) Tiên đề phản xạ: Nếu Y  X X  Y Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 138 (A2) Tiên đề gia tăng: Nếu X  Y XZ  YZ (A3) Tiên đề bắc cầu: Nếu X  Y Y  Z X  Z Từ hệ tiên đề Armstrong, dễ dàng chứng minh luật sau: (L1) Luật hợp: Nếu X  Y Z  V XZ  YV (L2) Luật tựa bắc cầu: Nếu X  Y YW  Z XW  Z (L3) Luật tách (chiếu) Nếu X  Y Z  Y X  Z Ký hiệu: F+ = { g | F ├A g } (ký hiệu F├A g để phụ thuộc hàm g suy diễn cách áp dụng số hữu hạn lần quy tắc hệ tiên đề Armstrong) Dưới trình bày quy tắc suy diễn cho phụ thuộc hàm mờ (FFD) Bằng trực quan ta thấy quy tắc gần giống quy tắc suy diễn hệ tiên đề Armstrong cho phụ thuộc hàm (FD) CSDL quan hệ kinh điển, nhiên quy tắc có thêm vài tính chất đặc trưng cho quan hệ mờ Ta có quy tắc suy diễn cho phụ thuộc hàm mờ: Cho lược đồ quan hệ mờ R tập thuộc tính U = {A1, A2,…., An}, tập phụ thuộc hàm mờ F R Giả sử X, Y, Z tập U, ta có: (1) Quy tắc bao hàm (chỉ có với phụ thuộc hàm mờ) 1 2 Nếu X   Y 1  2 X  Y (2) Quy tắc phản xạ (tương tự A1)  Nếu X  Y, X   Y cho   [0, 1] (3) Quy tắc gia tăng (tương tự A2)   R thỏa mãn X   Y, thỏa mãn XZ   YZ (4) Quy tắc bắc cầu (tương tự A3) 1 2 min( 1 ,2 ) R thỏa mãn X   Z  Y, Y   Z thỏa mãn X  Những quy tắc suy diễn bổ sung cho FFD phát biểu sau: (5) Quy tắc hợp (tương tự L1) 1 2 min( 1 ,2 )  YZ  Y, X   Z thỏa mãn X  R thỏa mãn X  (6) Quy tắc tựa bắc cầu (tương tự L2) 1 min( 1 ,2 ) 2 Z  Y, WY   Z thỏa mãn WX  R thỏa mãn X  (7) Quy tắc tách (tương tự L3)   Nếu X   Y Z  Y, X   Z Chúng ta liệt kê quy tắc để làm sở cho vấn đề lý thuyết phần sau Các chứng minh vấn đề chi tiết cho quy tắc trên, ban đọc xem tài liệu tham khảo [8] 6.5.4 Phụ thuộc hàm mờ phần Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 139 Sử dụng định nghĩa phụ thuộc hàm mờ, định nghĩa phụ thuộc hàm mờ phần Khái niệm sử dụng định nghĩa khóa mờ dạng chuẩn mờ Fuzzy 2NF  Định nghĩa 7.4 (định nghĩa phụ thuộc hàm mờ phần): Phụ thuộc hàm mờ X   Y phụ thuộc hàm mờ phần, tồn tập thuộc tính X’  X, X’  Ø, cho  X’   Y, với độ mạnh    Khi Y gọi phụ thuộc hàm mờ phần vào X với độ mạnh   Theo cách hiểu khác, FFD: X   Y FFD phần, tồn thuộc tính A  X cho ta bớt A khỏi X phụ thuộc hàm Nghĩa X \{A} xác định Y với độ mạnh    0,6 0,7 Thí dụ 7.6 Cho lược đồ quan hệ R = {A, B, C} FFD AB   C A  C Sau bớt thuộc tính B khỏi vế trái AB phụ thuộc hàm đầu tiên, phụ thuộc hàm 0,6 AB   C phụ thuộc hàm mờ phần 6.5.5 Cập nhật sở liệu mờ Khi cập nhật CSDL quan hệ, phải xem xét đến phụ thuôc liệu, thường phụ thuộc hàm Việc chèn thêm bộ, hay việc thay đổi giá trị phải đảm bảo quan hệ thỏa phụ thuộc hàm Với CSDL mờ vậy, với thao tác cập nhật, phải kiểm tra có phá vỡ phụ thuộc hàm mờ có CSDL hay khơng Một thí dụ câp nhật CSDL mờ Cho lược đồ quan hệ R= {COUNTRY, INF, IND}, Giải thích: - COUNTRY: Tên quốc gia, - INF (quality of infrastructure): chất lượng sở hạ tầng - IND (industrialization): mức độ cơng nghiệp hóa Giả sử ta cần chèn vào quan hệ r (R) sau: - t1: - t2: - t3: - t4: - t5: Giả sử quan hệ tương tự miền trị cho sau: Bảng 7.5 Quan hệ tương tự miền COUNTRY COUNTRY A P V N Australia (A) 0 Philippines (P) 0 Venezuela (V) 0 Nigeria (N) 0 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 140 Bảng 7.6 Quan hệ tương tự miền INF INF Excellent (E) Normally good (NG) Satisfactory (S) Adequate (A) Inadequate (I) No infrastructure (NI) E 0,8 0,1 0,1 0 NG 0,8 0,1 0,1 0 S 0,1 0,1 0,75 0 A 0,1 0,1 0,75 0 I 0 0 0,6 NI 0 0 0,6 Bảng 7.7 Quan hệ tương tự miền IND IND Very high (VH) Fair (F) Moderate (M) Low (L) Poor (P) Litle (LI) VH 0,25 0,25 0 F 0,25 0,81 0 M 0,25 0,81 0 L 0 0,75 0,75 P 0 0,75 0,81 LI 0 0,75 0,81 0,6 Giả sử lược đồ quan hệ có xác định phụ thuộc hàm mờ INF   IND (có nghĩa là: sở hạ tầng quốc gia “ít- nhiều” xác định mức độ cơng nghiệp hóa quốc gia đó) Hãy kiểm tra xem chèn vào quan hệ, phá vỡ phụ thuộc hàm mờ cho Trình bày quan hệ cuối với thỏa phụ thuộc hàm mờ 0,6 INF   IND Giải: ta chèn vào r, sau lần chèn, tính độ gần cho cặp theo định nghĩa 7.1 kiểm tra r có thỏa phụ thuộc hàm mờ theo định nghĩa 7.3 Nếu trình chèn thêm mà phá vỡ FFD loại khỏi r Bước Chèn t1 vào quan hệ r, r có nên ln thỏa FFD cho, ta có: r COUNTRY t1 INF {Australia} IND {normally good, excellent} {very high} Bước Chèn t2 = vào quan hệ r: r COUNTRY INF IND t1 {Australia} {normally good, excellent} {very high} t2 {Philippines} {adequate} {fair, moderate} Tính mức độ gần t1 t2 với thuộc tính INF IND: C(INF[t1, t2]) = 0,1 C(IND[t1, t2]) = 0,25  C(IND[t1, t2]) > {0,6, C(INF[t1, t2])}  0,6 r thỏa phụ thuộc hàm INF   IND Bước Chèn t3 = vào quan hệ r: Bảng 7.8 Quan hệ r sau bước r COUNTRY INF IND t1 {Australia} {normally good, excellent} {very high} t2 {Philippines} {adequate} {fair, moderate} t3 {Venezuela} {adaquate, satisfactory} {fair} Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 141 Tính mức độ gần cặp [t1, t3] [t2, t3] với thuộc tính INF IND: C(INF[t1, t3]) = 0,1 C(IND[t1, t3]) = 0,25  C(IND[t1, t3]) > {0,6, C(INF[t1, t3])} C(INF[t2, t3]) = 0,75 C(IND[t2, t3]) = 0,81  C(IND[t2, t3]) > {0.6, C(INF[t2, t3])} 0,6  việc chèn thêm t3 không phá vỡ phụ thuộc hàm mờ INF   IND, quan hệ r lúc có bảng 7.8 Bước Chèn t4 = vào quan hệ r: Bảng 7.9 Quan hệ r sau bước r COUNTRY INF IND t1 {Australia} {normally good, excellent} {very high} t2 {Philippines} {adequate} {fair, moderate} t3 {Venezuela} {adaquate, satisfactory} {fair} t4 {Nigeria} {satisfactory} {poor} Tính mức độ gần cặp [t2, t4 ] với thuộc tính INF với IND: C(INF[t2, t4]) = 0,75 C(IND[t2, t4]) =  C(IND[t2, t4]) < {0,6, C(INF[t2, t4])}, 0,6 việc chèn thêm t4 vào phá vỡ phụ thuộc hàm mờ INF   IND, t4 chèn vào r (Bảng 7.9) quan hệ r sau bước gồm bảng 7.8 Bước Chèn t5 = vào quan hệ r: Bảng 7.10 Quan hệ r sau bước r COUNTRY INF IND t1 {Australia} {normally good, excellent} {very high} t2 {Philippines} {adequate} {fair, moderate} t3 {Venezuela} {adaquate, satisfactory} {fair} t5 {Nigeria} {no infrastructure} {poor} Tính mức độ gần cặp [t1, t5 ], [t2, t5] [t3, t5] với thuộc tính INF với thuộc tính IND: C(INF[t1, t5]) = C(IND[t1, t5]) =  C(IND[t1, t5]) > {0,6, C(INF[t1, t5])}, C(INF[t2, t5]) = C(IND[t2, t5]) =  C(IND[t2, t5]) > {0,6, C(INF[t2, t5])}, C(INF[t3, t5]) = C(IND[t3, t5]) =  C(IND[t2, t5]) > {0,6, C(INF[t3, t5])} 0,6 Vậy việc thêm t5 vào quan hệ r không vi phạm phụ thuộc hàm mờ INF   IND Vậy sau bước chèn vào r, ta nhận quan hệ r thỏa phụ thuộc hàm 0,6  IND bảng 7.10 INF  6.6 KHÓA MỜ VÀ BAO ĐÓNG MỜ TRÊN CƠ SỞ DỮ LIỆU MỜ 6.6.1 Khóa mờ Giống CSDL kinh điển, dạng chuẩn mờ dựa khái niệm phụ thuộc hàm mờ khóa mờ Trước hết ta nhắc lại số khái niệm khóa CSDL quan hệ kinh điển: Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 142 Siêu khóa: Là vế trái phụ thuộc hàm đặc biệt X   U, U tập tất thuộc tính Như hiểu là, tập X thuộc tính U siêu khóa, thuộc tính U xác định thuộc tính X Vậy tập thuộc tính X siêu khóa X xác định U Khóa (hay khóa dự tuyển): Là siêu khóa K, mà khơng có tập K xác định U Trong mơ hình CSDL quan hệ kinh điển, giá trị đồng khóa K kéo theo giá trị đồng U Còn mơ hình CSDL quan hệ mờ, khái niệm đồng tập thuộc tính thay khái niệm tương đương ngữ nghĩa, hay gần tập thuộc tính Vậy K khóa mờ CSDL quan hệ mờ gần K kéo theo gần U Khi phụ thuộc hàm mờ gắn với độ mạnh ngữ nghĩa khóa quan hệ mờ gắn với độ mạnh ngữ nghĩa  Ta phát biểu định nghĩa khóa mờ sau: Định nghĩa 6.5: Cho lược đồ quan hệ R tập thuộc tính U = {A1, A2,…., An}, tập phụ thuộc hàm mờ F R Tập thuộc tính K  U gọi khóa mờ R với độ mạnh  thỏa mãn hai điều kiện sau:  - K   U  F+  - K   U không phụ thuộc hàm mờ phần Ở  = {i | i = 1, 2,…, n}, với i độ mạnh FFD sử dụng để  suy diễn FFD: K   U, < i < Nếu K thỏa mãn điều kiện K siêu khóa Thí dụ 7.7 Cho lược đồ quan hệ R = {A, B, C, D}, tập phụ thuộc hàm mờ: 0,7 0,9 F = {A   CD} Hãy tìm khóa mờ R  B, A  0,7 0,7 0,9 Ta có: A  B, A  AB (1), mặt khác ta lại có A  CD (2) F 0,7 0,7 Áp dụng quy tắc hợp cho (1) (2) ta có A   ABCD  ABCD, dễ thấy A  không phụ thuộc hàm mờ phần Theo định nghĩa 7.5 A khóa mờ lược đồ quan hệ R với độ mạnh 0,7 6.6.2 Bao đóng mờ tập thuộc tính Bao đóng mờ tìm ta muốn biết liệu phụ thuộc hàm mờ (FFD) cho nhận việc sử dụng tập phụ thuộc hàm mờ F quan hệ quy tắc suy diễn cho phụ thuộc hàm mờ hay không Tuy nhiên, không đơn giản để tính tốn tập tất FFD nhận từ F việc sử dụng quy tắc suy diễn, tập có số FFD lớn Thay việc phải tính tốn tồn tập này, tìm tập tồn thuộc tính xác định từ X nhờ phụ thuộc hàm mờ FFD, gọi bao đóng mờ X, ký hiệu X+(), đơn giản X+ Định nghĩa 7.6: Cho lược đồ quan hệ R tập thuộc tính U = {A1, A2,…., An}, tập phụ thuộc hàm mờ F R Với tập thuộc tính X  U, bao đóng mờ X với độ mạnh , ký hiệu X+() tập tất thuộc tính xác định từ X phụ thuộc hàm F, với  độ mạnh nhỏ phụ thuộc hàm tham gia tính X+ Thuật tốn tìm bao đóng mờ tập thuộc tính X tóm tắt sau: Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 143 Bước khởi tạo: X+ khởi tạo gồm tất thuộc tính X, độ mạnh bao đóng khởi tạo 1, ta có X+(1):= X Các bước lặp: Lần lượt xét tất phụ thuộc hàm mờ F, có vế trái thuộc tính X+, vế phải phụ thuộc hàm mờ kết nạp vào X+, độ mạnh X+ gán giá trị nhỏ độ mạnh cũ X+ độ mạnh phụ thuộc hàm mờ vừa sử dụng Thuật toán dừng xét hết phụ thuộc hàm mờ với bao đóng mới, khơng thể kết nạp thêm thuộc tính vào X+, độ mạnh bao đóng độ mạnh nhỏ phụ thuộc hàm sử dụng Thí dụ 7.8 Xét lược đồ quan hệ R thí dụ 7.7, lược đồ có tập thuộc tính U = {A, B, C, 0,9 0,7 D} tập FFD: F = {A   B, A  CD} Ta tính bao đóng thuộc tính X = {A} theo bước sau: (1) Khởi tạo: đặt X+(1) = {A} (2) Các bước lặp: 0,7 Xét phụ thuộc hàm F có vế trái thuộc X+ = {A}, ta có A   B, + kết nạp thêm B vào X , độ mạnh bao đóng min{1 ; 0,7} = 0.7, ta X+(0,7) = {A, B} 0,9 Tiếp tục xét phụ thuộc hàm A  CD, kết nạp thêm C, D vào bao đóng, độ mạnh bao đóng là: min{0,7 ; 0,9}= 0,7, bao đóng có độ mạnh 0,7, ta X+(0.7) = {A, B, C, D} Với bao đóng mới, lại quay lại xét phụ thuộc hàm, khơng có thêm thuộc tính kết nạp Thuật tốn kết thúc, bao đóng cuối A+(0,7) = {A, B, C, D} 6.6.3 Tìm khóa mờ quan hệ mờ Cũng giống CSDL quan hệ kinh điển, việc tìm khóa mờ lược đồ quan hệ dựa việc tính bao đóng tập thuộc tính dựa vào định nghĩa khóa mờ Có nhiều thuật tốn để tìm khóa mờ, dựa việc tính bao đóng mờ, đưa phương pháp chung, mà khơng đưa thuật tốn cụ thể, nhiên, với phương pháp này, dễ dàng phát triển thành thuật tốn hiệu để tìm khóa mờ Phương pháp chung để tìm khóa mờ quan hệ r lược đồ quan hệ R với tập thuộc tính U: Với tập thuộc tính X  U, tính bao đóng X, X+() = U, X siêu khóa mờ R với độ mạnh   Nếu có X   U phụ thuộc hàm mờ phần X khóa mờ với độ mạnh  Thí dụ 7.9 Cho lược đồ quan hệ R tập thuộc tính U = {A, B, C, D, E}, tập phụ thuộc 0,6 0,7 0,8 0,9  DE, DE  C }  B, B   A, AC  hàm mờ F = {A  Ta tìm khóa mờ sau: K1 = AC với độ mạnh 0,6, K2 = BC với độ mạnh 0,7, K3 = ADE(0,6), K4 = BDE(0,7) Sinh viên tự kiểm tra lại q trình tìm khóa trên, dựa việc tính bao đóng mờ Trong thí dụ 7.8, dễ thấy A khóa mờ với độ mạnh 0,7 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 144 6.7 CHUẨN HÓA CƠ SỞ DỮ LIỆU MỜ Trước hết, ta định nghĩa khái niệm thuộc tính khóa mờ thuộc tính khơng khóa mờ Định nghĩa 7.7: Cho lược đồ quan hệ R, với tập thuộc tính U tập khóa mờ K R Thuộc tính A U gọi thuộc tính khóa mờ A  Ki với Ki khóa thuộc K Những thuộc tính mà khơng phải thuộc tính khóa mờ (khơng xuất khóa mờ nào) gọi thuộc tính khơng khóa mờ Từ trở đi, thay gọi thuộc tính khóa mờ, thuộc tính khơng khóa mờ ta gọi đơn giản thuộc tính khóa thuộc tính khơng khóa, khơng gây nhầm lẫn Một thuộc tính thuộc tính khóa, phần khóa dự tuyển mờ quan hệ Tương tự vậy, thuộc tính thuộc tính khơng khóa, khơng xuất khóa dự tuyển mờ quan hệ Trong thí dụ 7.8 thuộc tính A thuộc tính khóa với độ mạnh 0.7, thuộc tính cịn lại thuộc tính khơng khóa Với thí dụ 7.9, tất thuộc tính U thuộc tính khóa Khi thiết kế CSDL, phải thiết kế lược đồ quan hệ đạt đến tiêu chuẩn Việc chuẩn hóa lược đồ quan hệ mờ nhằm làm cho việc cập nhật liệu không gây dị thường làm dư thừa thông tin, phá vỡ ràng buộc toàn vẹn Cũng tương tự với CSDL quan hệ kinh điển, người ta phân lớp CSDL quan hệ mờ thành dạng chuẩn, giáo trình xem xét dạng chuẩn mờ 1NF, 2NF 3NF Những dạng chuẩn cao bạn đọc tìm hiểu tài liệu tham khảo 6.7.1 Dạng chuẩn mờ thứ (fuzzy 1NF - F1NF) Định nghĩa 7.8: Một lược đồ quan hệ R gọi dạng chuẩn mờ 1NF với quan hệ r R, khơng thuộc tính r đa trị Thí dụ 7.10 Xét lược đồ quan hệ R với thuộc tính {Tên, Tuổi, Nghề nghiệp} Một quan hệ r R chứa cho sau: t1 = t2 = t3 = Quan hệ r có thứ hai với thuộc tính nghề nghiệp nhận hai giá tri, An làm nghề ‘Giáo viên’ ‘Luật sư’vậy R không thỏa mãn dạng chuẩn mờ 1NF, lược đồ R không thuộc dạng chuẩn mờ 1NF Chú ý tuổi Thanh khoảng [rất trẻ, trẻ] giá trị mờ, đa trị Có thể sửa quan hệ trở thành thỏa dạng chuẩn mờ 1NF cách tách t2 thành bộ, quan hệ R trở thành: t1 = t2 = t3 = t4 = Quan hệ dạng chuẩn fuzzy 1NF 6.7.2 Dạng chuẩn mờ thứ hai (fuzzy 2NF - F2NF) Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 145 Định nghĩa 7.9 (dạng chuẩn mờ thứ hai): Với F tập FFD lược đồ quan hệ R, K khóa mờ R với độ mạnh  R gọi thuộc dạng chuẩn mờ 2NF khơng có thuộc tính khơng khóa phụ thuộc hàm mờ phần vào khóa K Thí dụ 7.11 Cho lược đồ quan hệ R(A, B, C, D), với tập phụ thuộc hàm mờ: 0,7 0,9 F = {A   CD}  B, A  Dễ thấy lược đồ có A khóa mờ R với độ mạnh 0,7 Vì khơng có thuộc tính khơng khóa R phụ thuộc hàm mờ phần vào khóa mờ R A nên R thuộc dạng chuẩn mờ 2NF - Kiểm tra dạng chuẩn mờ thứ hai Định nghĩa dạng chuẩn mờ 2NF bao gồm việc kiểm tra FFD phần cho thuộc tính khơng khóa vào khóa mờ lược đồ quan hệ R Chúng ta kiểm tra phụ thuộc hàm mờ phần dựa thực tế rằng: “Nếu tập thực vế trái FFD định vế phải theo độ mạnh độ mạnh FFD đó, FFD phụ thuộc hàm phần” Muốn biết quan hệ cho trước có dạng chuẩn mờ 2NF hay khơng tồn thuộc tính khơng khóa quan hệ kiểm tra để biết xem liệu chúng có phụ thuộc hàm phần vào khóa mờ quan hệ không Chú ý 7.3.2: Nếu vế trái FFD chứa thuộc tính đơn, phép kiểm tra khơng cần thiết phải áp dụng, FFD phụ thuộc hàm mờ phần Thí dụ 7.12 Xét lược đồ quan hệ R = {A, B, C, D} tập phụ thuộc hàm mờ là: F = { 0,8 0,9 AB   D, A   C } Dễ thấy AB khóa mờ R với độ majnh 0.8 Vì thuộc tính khơng khóa C phụ thuộc hàm mờ phần vào khóa mờ R AB nên R không thuộc dạng chuẩn mờ 2NF - Phân tách lược đồ quan hệ dạng chuẩn mờ 2NF Định nghĩa 7.10 (khóa mờ phần): Giả sử X khóa mờ lược đồ quan hệ R  Nếu có FDD: X   Y phụ thuộc hàm mờ phần, X gọi khóa mờ phần Nếu lược đồ quan hệ không dạng chuẩn mờ 2NF, chuẩn hóa thành tập quan hệ dạng chuẩn mờ 2NF, theo bước sau: (i) Nếu quan hệ xét không chuẩn 2NF, tìm khóa mờ phần thuộc tính khơng khóa phụ thuộc hàm phần vào chúng (ii) Phân tách khởi tạo quan hệ cho khóa mờ phần với thuộc tính phụ thuộc vào chúng (iii) Loại thuộc tính khơng khóa phụ thuộc hàm phần vào khóa mờ quan hệ khỏi quan hệ ban đầu tạo quan hệ với thuộc tính cịn lại 0,8 Thí dụ 7.13 Xét lược đồ quan hệ R = {A, B, C, D}, tập FFD: F = { AB   D, 0,9 A  C} Dễ thấy AB khóa mờ phần, R không thuộc dạng chuẩn 2NF, Áp dụng bước trên, phân tách R thành hai lược đồ quan hệ dạng chuẩn mờ 2NF: R1 = {A, C} với A khóa mờ R1 với độ mạnh 0,9 R2 = {A, B, D} với AB khóa mờ R2 với độ mạnh 0,8 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 146 Người ta chứng minh phép phân tách R tách thành R1 R2 phép kết nối không thông tin, tức kết nối quan hệ lược đồ lại, ta nhận quan hệ ứng với lược đồ ban đầu [1] 6.7.3 Dạng chuẩn mờ thứ ba (fuzzy 3NF - F3NF) Dạng chuẩn mờ F3NF dạng chuẩn phổ biến nhất, thường sử dụng thiết kế CSDL Với dạng chuẩn F3NF, dị thường thực phép cập nhật hạn chế tới mức thấp Định nghĩa 7.11 (dạng chuẩn mờ thứ 3): Cho F tập phụ thuộc hàm mờ FFD R, K khóa mờ R với độ mạnh  R gọi thuộc dạng chuẩn mờ 3NF  R dạng chuẩn mờ 2NF với phụ thuộc hàm mờ X   Y F, Y  X, thì: X chứa khóa mờ, Y thuộc tính khóa mờ - Kiểm tra dạng chuẩn mờ thứ ba: Định nghĩa dạng chuẩn mờ 3NF trực tiếp sử dụng để kiểm tra xem liệu quan hệ cho có dạng chuẩn mờ 3NF hay khơng Tồn FFD kiểm tra để so sánh với điều kiện sau: + Nếu thuộc tính vế trái FFD chứa tồn thuộc tính vế phải, FFD khơng vi phạm dạng chuẩn mờ 3NF + Nếu thuộc tính vế trái FFD chứa khóa mờ quan hệ, dạng chuẩn mờ 3NF khơng bị vi phạm + Nếu thuộc tính vế phải FFD thuộc tính khóa, dạng chuẩn mờ 3NF khơng bị vi phạm Thí dụ 7.14 Xét lược đồ quan hệ R = {A, B, C, D}, tập phụ thuộc hàm FFD: 0,7 0,9 F = {A   CD}  B, A  Dễ thấy A khóa mờ R với độ mạnh 0,7 Vì R dạng chuẩn mờ 2NF A khóa mờ nên R dạng chuẩn 3NF Thí dụ 7.15 Xét lược đồ quan hệ R = {A, B, C, D, E} tập FFD: 0,9 0,8 0,6 F = { AB   D, C   C, AC   E } 0,9 Dễ thấy AB khóa mờ R, phụ thuộc hàm mờ AB   C có vế trái chứa 0,8 0,6  E vi khóa mờ nên khơng vi phạm dạng chuẩn mờ 3NF Hai FFD cịn lại AC  D, C  phạm dạng chuẩn mờ 3NF vế trái khơng chứa khóa mờ AB, hai thuộc tính vế phải khơng phải thuộc tính khóa Vậy R khơng thuộc dạng chuẩn mờ 3NF - Phân tách lược đồ quan hệ dạng chuẩn mờ F3NF Tương tự việc phân tách lược đồ dạng chuẩn mờ F2NF (fuzzy 2NF), ta phân tách lược đồ R dạng chuẩn mờ F3NF theo bước: (1) Tìm phụ thuộc hàm thỏa F3NF, vế trái chung khóa, gộp vế trái vế phải thành thuộc tính lược đồ R1 Tiếp tục với tất phụ thuộc hàm thỏa F3NF (2) Với phụ thuộc hàm khơng thỏa F3NF, gộp thuộc tính vế trái vế phải thành lược đồ Ri, khóa vế trái phụ thuộc hàm Các lược đồ R1, R2, … thỏa F3NF Có thể chứng minh phép phân tách R phân tách không thơng tin [1] Chẳng hạn với thí dụ trên, ta có phân tách R thành tập lược đồ thỏa F3NF là: R = {ABC, ACD, CE} Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 147 BÀI TẬP CHƯƠNG Cho A, B tập cổ điển tập vũ trụ X Có thể dùng hàm thuộc để biểu diễn tập A, B sau: x  X ,  A ( x)  if x  A if x A x  X ,  B ( x)  if x  B if x  B Hãy xây dựng hàm thuộc để biểu diễn tập AB ; AB A Cho tập mờ A không gian X = R, xác định  A ( x)  , x X  | x  3| Hãy xác định chiều cao A, lõi A Tìm nhát cắt A0,5 ; A0,25 Tìm phần bù A với phép phủ định: n(a) 1  a , a [0,1] Quan hệ A chuẩn hóa chưa Xét tập U gồm ứng viên vào chức vụ quản đốc phân xưởng, U = {u1, u2, u3, u4, u5}, họ lựa chọn theo hai tiêu chuẩn: A – trình độ nghiệp vụ (mức độ lành nghề), B - kinh nghiệm nghề nghiệp Tập thể có ý kiến đánh giá mức độ phù hợp ứng viên với tiêu chuẩn A B sau: U Tiêu chuẩn A Tiêu chuẩn B u1 Khá phù hợp Tương đối phù hợp u2 Hoàn toàn phù hợp Khá phù hợp u3 Rất phù hợp Hoàn toàn phù hợp u4 Ít phù hợp Khơng phù hợp u5 Tương đối phù hợp Rất phù hợp Các mức độ phù hợp lượng hóa sau: - Hồn tồn phù hợp: mức độ phù hợp: 1; - Rất phù hợp: mức độ phù hợp: 0,8; - Khá phù hợp: mức độ phù hợp: 0,6; - Tương đối phù hợp: mức độ phù hợp: 0,4; - Ít phù hợp: mức độ phù hợp: 0,2 - Không phù hợp: mức độ phù hợp: 0; Gọi A B tập mờ người thỏa tiêu chuẩn A B tương ứng Hãy xác định tập mờ A B a Tìm tập mờ U ứng viên thỏa hai tiêu chuẩn b Thỏa mãn hai tiêu chuẩn c Không thỏa tiêu chuẩn A d Tìm nhát cắt mức  tập mờ ứng viên thỏa tiêu chuẩn, với  = 0,6  = 0,8 Hãy xem xét tập hợp nhà “gần bãi biển” địa phương, ta coi khoảng cách từ nhà đến bãi biển 200 m chắn gần, hay cách bãi biển 200 m coi gần, tính chất “gần bãi biển” dần đi, từ 500m trở lên khơng thể coi gần bãi biển Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 148 a Theo tri thức trên, xây dựng vẽ đồ thị tập mờ A khoảng cách đến bãi biển nhà ‘gần bãi biển’ b Hãy xây dựng vẽ đồ thị hàm thuộc tập mờ B khoảng cách đến bãi biển nhà ‘không gần bãi biển’ c Hãy xây dựng vẽ đồ thị hàm thuộc tập mờ C khoảng cách đến bãi biển nhà cách biển khoảng 300 đến 400 m, chấp nhận sai số đến 50 m Cho A tập mờ tập vũ trụ U, chứng minh với , ‘  [0, 1], ’  A  A‘, với A A‘ nhát cắt mức  ‘ tập mờ A Cho A, B tập mờ tập vũ trụ U, chứng minh với  [0, 1], nhát cắt mức  tập mờ A, B, A  B, A  B thỏa mãn tính chất sau: a (A  B) = A  B b (A  B) = A  B c A  B A  B Cho tập số nguyên: U = {1, 2, 3, 4, 5} Xét R quan hệ “nhỏ hay bằng” U sau: a, b  U, ta nói aRb a < b a Hãy biểu diễn quan hệ R tập tích Đề U x U b Hãy viết ma trận quan hệ R c Quan hệ có tính chất tính chất sau: phản xạ, đối xứng bắc cầu? Cho tập số nguyên: U = {1, 2, 3, 4, 5} S quan hệ mờ hai U xác định hàm thuộc sau:  x y  x, y U , f S  x, y   max 0,     a Hãy biểu diễn quan hệ mờ S tập mờ tích Đề U × U b Hãy xác định ma trận quan hệ mờ S c Quan hệ có tính chất tính chất sau: phản xạ, đối xứng bắc cầu maxmin? Cho quan hệ mờ RA miền trị A = {a1, a2, a3} sau: a1 a2 a3 a1 RA 0,8 0,6 a2 0,8 0,6 a3 0,6 0,6 a Chứng minh RA quan hệ tương tự A b Phân cụm phần tử tập A theo mức  10 Cho quan hệ mờ RD miền trị D = {d1, d2, d3, d4} sau: RD d1 d2 d3 d4 d1 0,8 0,7 0,8 d2 0,8 0,6 0,7 d3 0,7 0,6 0,8 d4 0,8 0,7 0,8 a Quan hệ RD có phải quan hệ tương tự D khơng? Tại sao? b Tìm quan hệ mức  liên kết với quan hệ RD Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 149 11 Các loại thông tin coi thông tin khơng hồn hảo? (mỗi loại trình bày vắn tắt khơng q dịng) 12 CSDL mờ gì? Giới thiệu mơ hình CSDL mờ với đặc trưng chủ yếu mơ hình Cho thí dụ cho mơ hình 13 Thế mức độ gần hai thuộc tính tập thuộc tính 14 Định nghĩa phụ thuộc hàm mờ dựa mức độ gần hai tập thuộc tính, so sánh giống khác với phụ thuộc hàm kinh điển (rõ) 15 Phát biểu (7) quy tắc suy diễn cho phụ thuộc hàm mờ 16 a Định nghĩa phụ thuộc hàm mờ phần, b Cho lược đồ quan hệ mờ R= {A, B, C} tập FFD: 0,8 0,7 F = {CB   A; C   CA} Hãy phụ thuộc hàm mờ phần F, giải thích? 17 a Định nghĩa khóa mờ lược đồ quan hệ mờ Thế thuộc tính khóa mờ thuộc tính khơng khóa mờ Định nghĩa khóa mờ phần lược đồ CSDL mờ b Cho lược đồ quan hệ R = {A, B, C, D}, tập phụ thuộc hàm mờ: 0,7 0,6 F = {B   CD} Hãy tìm khóa mờ R Xác định thuộc tính khóa thuộc  A, B  tính khơng khóa c Cho lược đồ quan hệ R tập thuộc tính U = {A, B, C, D, E}, tập phụ thuộc hàm mờ F = 0,6 0,7 0,8 0,9 {C   DE, DE   CA} Xác định khóa mờ lược đồ R  B, B   C, AC  18 a.Định nghĩa dạng chuẩn mờ thứ (F1NF) dạng chuẩn mờ thứ hai (F2NF) 0,7 b.Cho lược đồ quan hệ mờ R(A, B, C, D), với tập phụ thuộc hàm mờ: F = {B   A, 0,9 B  CD} Kiểm tra xem R có thỏa dạng chuẩn mờ thứ hai không c Xét lược đồ quan hệ mờ R = {A, B, C, D} tập phụ thuộc hàm mờ là: 0,8 0,9 F = { AC   D, A   B } Kiểm tra xem R có thỏa dạng chuẩn mờ thứ hai khơng? d Xét lược đồ quan hệ mờ R = {A, B, C, D}, tập phụ thuộc hàm mờ 0,8 0,9 F = { BC   D, C   A} Xác định dạng chuẩn cao lược đồ R Nếu R chưa F2NF tách lược đồ thành lược đồ dạng chuẩn F2NF 19 a Phát biểu định nghĩa dạng chuẩn mờ thứ ba (F3NF) b Cho lược đồ quan hệ mờ R = {A, B, C, D}, tập phụ thuộc hàm mờ: 0,7 0,9  AD} Xác định dạng chuẩn cao lược đồ R  A, C  F = {B  c Cho lược đồ quan hệ mờ R = {A, B, C, D, E}, tập phụ thuộc hàm mờ: 0,9 0,8 0,6 F = { AB   E} Xác định dạng chuẩn cao lược đồ R,  C, C   D, AD  R chưa F3NF hãy tách lược đồ thành lược đồ dạng chuẩn F3NF Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 150 TÀI LIỆU THAM KHẢO Hồ Thuần, Hồ Cẩm Hà (2007) Các hệ sở liệu - Lý thuyết thực hành (Tập 1, 2) Nhà xuất Giáo dục Đỗ Trung Tuấn (2010) Cơ sở liệu suy diễn Nhà xuất Giáo dục B.Bouchon, Meunier, Hồ Thuần, Đặng Thanh Hà (2007) Logic mờ ứng dụng Nhà xuất Đại học Quốc gia Hà Nội Nguyễn Văn Định (2004) Siêu đồ thị Lược đồ CSDL phi chu trình Luận án Tiến sĩ Toán học, Đại học Khoa học Tự nhiên, ĐHQG Hà Nội Đồn Văn Ban, Tính đắn lược đồ sở liệu hướng đối tượng, Tạp chí Tin học Điều khiển học, 16 (3), tr 7– 5, 2000 Đoàn Văn Ban, Nguyễn Thị Tĩnh, Giáo trình phân tích, thiết kế hệ thống hướng đối tượng UML, Nhà xuất Đại học Sư Phạm 2011 Đoàn Văn Ban, Viện CNTT, Viện HLKH-CN Việt nam (2010) ,“Bài giảng Cơ sở liệu đối tượng” hướng M Tamer Ozsu, Patrick Valduriez (1999) Nguyên lý hệ sở liệu phân tán (Bản dịch) Nhà xuất Thống kê Michael L Horowitz, An Introduction to Object-Oriented Databases and Database Carnegie Mellon University, 1991 Systems, 10 Mishra J and Ghosh S (2012) Normalization in a fuzzy relational database model International journal of computing engineer and technology, 3(2): 506-517 11 Buckles P.B., Petry F.E (1982) A fuzzy representation of data for relational database” Fuzzy Set Syst., 7: 213-229 12 Yazici A., Sozat I (1999) The integrity constraints for similarity-based fuzzyralational database International journal of Intelligent Syst 1999; 13: 641-660 13 G.M Bierman, A Trigoni, Towards a formal typ e system for ODMG OQL, University of Cambridge Computer Laboratory, 2000 14 Cettell R G G., Barry D K., The Object – Oriented Standard: ODMG, San Francisco, CA: Morgan Kaufmann, 1997 15 Hamouz, S and Biswas, R (2006) Fuzzy Functional Dependencies in Relational Databases International Journal of Computational Cognition, 4(1): 39-43 16 J.D Ullman (1992) Principles of Database and Knowledgebase system 1, ISBN 0888-2096 17 Jarke M., Koch J (1990) Query optimization in databas system ACM Computing Surveys, 16(2): 73-170 18 Zadeh, L.A (1965) Fuzzy sets Information and Control, 8, 338-353 Bài giảng “Cơ sở liệu nâng cao” | nvdinh@vnua.edu.vn 151 ... tán Bài giảng ? ?Cơ sở liệu nâng cao? ?? | nvdinh@vnua.edu.vn 16 Chương TỐI ƯU HÓA CÂU HỔI VÀ QUẢN LÝ CÁC GIAO DỊCH PHÂN TÁN 2.1 ĐỊNH NGHĨA DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN là: Việc định nghĩa liệu. .. 1.7 Cơ sở liệu song song (Máy sở liệu) 1.3 CÁC TÍNH CHẤT CƠ BẢN CỦA MỘT HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Các hệ quản trị CSDL phân tán phải làm cho người sử dụng hệ thống không cần biết tới phân tán liệu. .. thông Bài giảng ? ?Cơ sở liệu nâng cao? ?? | nvdinh@vnua.edu.vn * Ngoài hệ quản trị sở liệu phân tán cịn có thêm số chức năng: - Quản lý từ điển liệu tổng thể lưu trữ thông tin liên quan đến liệu phân