Luận án Một số phụ thuộc logic mở rộng trong mô hình dữ liệu dạng khối

Nội dung text: Luận án Một số phụ thuộc logic mở rộng trong mô hình dữ liệu dạng khối

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ TRỊNH NGỌC TRÚC MỘT SỐ PHỤ THUỘC LOGIC MỞ RỘNG TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH Hà Nội - 2021
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Trịnh Ngọc Trúc MỘT SỐ PHỤ THUỘC LOGIC MỞ RỘNG TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS Trịnh Đình Thắng 2. TS. Nguyễn Như Sơn Hà Nội - 2021
3. i LỜI CẢM ƠN Lời đầu tiên, cho phép tác giả xin bày tỏ lòng biết ơn sâu sắc và chân thành tới PGS. TS Trịnh Đình Thắng, TS Nguyễn Như Sơn, người thầy đã tận tình hướng dẫn, chỉ bảo cho tác giả trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án này. Tác giả xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học thuộc Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam; Khoa Công nghệ Thông tin, Học viện Khoa học và Công nghệ; Viện Công nghệ Thông tin, Phòng Đào tạo, Trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ về chuyên môn và tạo điều kiện thuận lợi cho tác giả trong suốt thời gian học tập và nghiên cứu. Cuối cùng, tác giả xin gửi tới gia đình, người thân, bạn bè lời cảm ơn chân thành nhất vì đã ủng hộ, đồng hành, là chỗ dựa vững chắc và là động lực giúp tác giả hoàn thành luận án này. Tác giả luận án Trịnh Ngọc Trúc
4. ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của PGS.TS. Trịnh Đình Thắng, TS. Nguyễn Như Sơn. Các kết quả được viết chung với các đồng tác giả đã được sự chấp thuận của các tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả luận án Trịnh Ngọc Trúc
5. iii MỤC LỤC MỞ ĐẦU 1 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 11 1.1. Mô hình dữ liệu dạng khối 11 1.1.1. Khối, lát cắt của khối 11 1.1.2. Đại số khối 13 1.1.3. Phụ thuộc hàm trong mô hình dữ liệu dạng khối 17 1.1.4. Phụ thuộc đa trị trong mô hình dữ liệu dạng khối 19 1.2. Đại số Boolean 20 1.2.1. Công thức Boolean 20 1.2.2. Bảng trị và bảng chân lý 21 1.2.3. Suy dẫn logic 21 1.2.4. Công thức Boolean dương 22 1.2.5. Công thức Boolean đa trị 22 1.2.6. Bảng trị và bảng chân lý 24 1.2.7. Suy dẫn logic 24 1.2.8. Công thức Boolean dương đa trị 24 1.3. Phụ thuộc Boolean dương trong mô hình dữ liệu dạng khối 25 1.3.1. Khối chân lý của khối 25 1.3.2. Phụ thuộc Boolean dương trên khối 25 1.4. Kết luận chương 1 28 CHƯƠNG 2. HỘI SUY DẪN VÀ PHỤ THUỘC BOOLEAN DƯƠNG ĐA TRỊ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI 29 2.1. Đặt vấn đề 29 2.2. Hội suy dẫn trong mô hình dữ liệu dạng khối 30 2.2.1. Công thức suy dẫn trong lược đồ khối 30 2.2.2. Tính chất của họ tập đóng và khối chân lý 32 2.3.3. Tính chất của hội suy dẫn và khối chân lý 33 2.3. Các thuật toán xây dựng hội suy dẫn 35 2.3.1. Thuật toán XDF 35 2.3.2. Thuật toán XDF-S 40 2.3.3. Cài đặt thực nghiệm thuật toán XDF 44
6. iv 2.4. Phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối 45 2.4.1. Khối m-chân lý của khối dữ liệu 45 2.4.2. Công thức Boolean dương đa trị 48 2.4.3. Phép gán trị 49 2.4.4. Phụ thuộc Boolean dương đa trị trên khối 52 2.4.5. Bao đóng tập phụ thuộc Boolean dương đa trị 57 2.4.6. Thể hiện và thể hiện chặt tập phụ thuộc Boolean dương đa trị 58 2.5. Cài đặt minh họa bài toán tìm Phụ thuộc Boolean dương đa trị trên khối 60 2.6. Tổng kết chương 2 65 CHƯƠNG 3. PHỤ THUỘC BOOLEAN DƯƠNG THEO NHÓM BỘ VÀ PHỤ THUỘC BOOLEAN DƯƠNG ĐA TRỊ THEO NHÓM BỘ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI 66 3.1. Đặt vấn đề 66 3.2. Phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối 66 3.2.1. Phép gán trị 66 3.2.2. Khối chân lý theo nhóm bộ của khối dữ liệu 67 3.2.3. Phụ thuộc Boolean dương theo nhóm bộ của khối dữ liệu 69 3.2.4. Bao đóng tập phụ thuộc Boolean dương theo nhóm bộ 74 3.2.5. Thể hiện và thể hiện chặt tập phụ thuộc Boolean dương theo nhóm bộ 77 3.3. Phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu dạng khối 78 3.3.1. Phép gán trị 78 3.3.2. Khối chân lý đa trị theo nhóm bộ của khối dữ liệu 78 3.3.3. Phụ thuộc Boolean dương đa trị theo nhóm bộ của khối dữ liệu 81 3.3.4. Bao đóng tập phụ thuộc Boolean dương đa trị theo nhóm bộ 86 3.3.5. Thể hiện, thể hiện chặt 89 3.4. Cài đặt minh họa bài toán tìm Phụ thuộc Boolean dương theo nhóm bộ và Phụ thuộc Boolean dương đa trị theo nhóm bộ trên khối 90 3.4. Tổng kết chương 3 95 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 97 TÀI LIỆU THAM KHẢO 100
7. v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu Ý nghĩa của kí hiệu XY Biểu diễn hợp của hai tập X và Y REL(U) Tập toàn thể các quan hệ trên tập thuộc tính U Tập toàn thể các quan hệ có không quá p bộ trên tập thuộc RELp(U) tính U, p 1 t * v Phép kết nối hai bộ t và v t * S Phép kết nối bộ t với quan hệ S t[X], t.X hạn chế của bộ (ánh xạ) t trên tập thuộc tính X id × id’ Kí hiệu tích rời rạc của id và id’ M  P Hợp của 2 tập con M và P M   {MX| X }    {XY | X  , Y } f * g Hội của hai ánh xạ đóng f và g u&v Phép tính nhân của 2 bộ u và v SubSet(U) Tập tất cả các tập con của U ╞ Suy dẫn logic ├ hoặc Suy dẫn theo khối ╞2 hoặc 2 Suy dẫn theo khối có không quá 2 phần tử ╞p, p Suy dẫn theo khối có không quá p phần tử ╞p,m p,m m suy dẫn theo khối có không quá p phần tử CTB Công thức Boolean CTBD Công thức Boolean dương CTBDĐT Công thức Boolean dương đa trị PTBD Phụ thuộc Boolean dương PTBDTQ Phụ thuộc Boolean dương tổng quát PTBDĐT Phụ thuộc Boolean dương đa trị PTBDTNB Phụ thuộc Boolean dương theo nhóm bộ PTBDĐTTNB Phụ thuộc Boolean dương đa trị theo nhóm bộ Fix(f) Tập toàn bộ các điểm bất động của f Gen(G) Tập sinh của giàn giao G CSDL Cơ sở dữ liệu
8. vi DANH MỤC CÁC BẢNG Bảng i: Biểu diễn quan hệ MAT_HANG. 1 Bảng 1.1: Biểu diễn lát cắt của khối DIEM_DG 12 Bảng 1.2: Biểu diễn lát cắt thể hiện phụ thuộc hàm 19 Bảng 2.1: Bảng T và bảng h trên lát cắt 1 38 Bảng 2.2: Bảng T và bảng h trên lát cắt 2 38 Bảng 2.3: Bảng T và bảng h trên lát cắt 3 39
9. vii DANH MỤC CÁC HÌNH Hình 1: Biểu diễn khối MAT_HANG 2 Hình 2: Biểu diễn khối BAN_HANG 3 Hình 3: Biểu diễn mô hình dữ liệu đa chiều 5 Hinh 1.1: Biểu diễn khối DIEM_DG 11 Hinh 1.2: Biểu diễn khối dữ liệu r(R) 18 Hinh 1.3: Ví dụ về khối chân lý Tr 27 Hình 2.1: Khối chân lý Tr 31 Hình 2.2: Sơ đồ thuật toán XDF 36 Hình 2.3: Biểu diễn khối chân lý Tr 37 Hình 2.4: Sơ đồ thuật toán XDF-S 41 Hình 2.5: Khối dữ liệu Ban_hang_DT 50 Hình 2.6: Khối chân lý Tr 51 Hình 2.7: Khối chân lý Tf,m 54 Hình 2.8: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa hè 62 Hình 2.9: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa xuân 63 Hình 2.10: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa đông 64 Hình 3.1: Khối dữ liệu r: Ban_hang_NB 68 Hình 3.2: Khối chân lý Tf_nb 71 Hình 3.3: Khối dữ liệu r: Ban_hang_DTNB 79 Hình 3.4: Khối chân lý Tr_dtnb 80 Hình 3.5: Khối chân lý Tf_dtnb,m 83 Hình 3.6: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa hè 92 Hình 3.7: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa xuân 93
10. 1 MỞ ĐẦU 1. Lý do chọn đề tài Việc quản lý, lưu trữ và khai thác dữ liệu để giải quyết bài toán thực tế trong cuộc sống đang được nhiều nhà khoa học quan tâm nghiên cứu. Mô hình dữ liệu quan hệ do E-Codd đề xuất năm 1970 đã góp phần giải quyết bài toán lưu trữ, khai thác dữ liệu và mô tả các ràng buộc dữ liệu thông qua khái niệm phụ thuộc hàm (X Y), nhưng mô hình này chưa đủ mạnh và còn nhiều hạn chế trong việc lưu trữ và truy xuất dữ liệu có cấu trúc phi tuyến tính. Do vậy, nhiều nhà khoa học trong nước và quốc tế quan tâm nghiên cứu nhằm mở rộng mô hình dữ liệu quan hệ để giải quyết được các bài toán động, các bài toán có cấu trúc phi tuyến tính. Một số mở rộng đã được đề xuất là: Mô hình dữ liệu dạng khối (Database model of block form) [1], Khối dữ liệu (Data Cube) [2], Mô hình dữ liệu đa chiều (Multidimensional data model) [3], Kho dữ liệu (Data Warehouse) [4]. Sự ra đời của các mô hình dữ liệu này đã khắc phục được những bất cập, khó khăn trong việc theo dõi sự vận động của dữ liệu theo thời gian, Chẳng hạn, theo mô hình dữ liệu quan hệ do E-codd đề xuất, trong quản lý bán hàng các mặt hàng (bánh mì, bơ, sữa), ta có bảng dữ liệu (Bảng i) sau: Bảng i: Biểu diễn quan hệ MAT_HANG. MAT_HANG: MaHang TenHang Gia 01 Bánh mì 10.000đ 02 Bơ 15.000đ 03 Sữa 20.000đ Bảng 1 gồm các trường: MaHang (mã hàng), TenHang (tên hàng), Gia (Giá). Bảng này chính là một quan hệ trong mô hình dữ liệu quan hệ. Mỗi khi có sự điều chỉnh lại mã hàng nhằm đồng bộ, phân cấp để quản lý mã hàng được thống nhất. Theo đó, người quản lý cập nhật mã hàng mới ứng với mỗi loại hàng. Như vậy, giá trị của mã hàng cũ bị mất đi và được thay bằng giá trị mã hàng mới. Tình trạng này cũng diễn ra tương tự với thuộc tính TenHang (tên hàng), Gia (giá) khi tên hàng hoặc giá được thay đổi. Như vậy, với cách quản lý hàng theo Bảng, người quản lý không thể theo dõi được sự thay đổi các giá trị: mã hàng, tên hàng, giá của các mặt
11. 2 hàng theo sự vận động của thời gian. Vì vậy, có thể nói, theo dõi quá trình thay đổi các giá trị hàng hóa theo cách quản lý trên Mô hình dữ liệu quan hệ là một công việc khó khăn. Mô hình dữ liệu dạng khối ra đời đã khắc phục được hạn chế trên, giúp cho việc quản lý trở lên đơn giản hơn, thuận tiện hơn. Ta có thể mô phỏng cách quản lý mặt hàng theo Mô hình dữ liệu dạng khối bằng Hình 1 như sau: MAT_HANG: MaHang TenHang Gia 03 B.Mỳ 10 lớn 03 B.Mỳ 10 02 Bơ sáp 20 03 B.Mỳ 10 02 Bơ sáp 20 Sữa chua 01 20 10/5/2021 02 Bơ 10 01 Sữa 20 5/5/2021 chua 01 Sữa 10 01/5/2021 Hình 1: Biểu diễn khối MAT_HANG Với khối MAT_HANG, mỗi khi các giá trị của mã hàng hoặc tên hàng hoặc giá thay đổi thì trên trục thời gian và khối sẽ sinh tương ứng một lát cắt mới ứng với ngày vừa bổ sung để người quản lý cập nhật thông tin (trục thời gian có thể tính theo ngày, tháng, ). Từ khối MAT_HANG trên, ta có thể dễ dàng theo dõi quá trình thay đổi mã hàng, tên hàng hoặc giá của mặt hàng. Nói cách khác, người quản lí có thể theo dõi được sự biến đổi các giá trị: mã hàng, tên hàng, giá cả tương ứng với các mốc thời gian cụ thể. Đây chính là Mô hình dữ liệu dạng khối được đề xuất vào năm 1998 [1]. Mô hình dạng khối này đã được xây dựng thành công cả về lý thuyết và cài đặt thực nghiệm. Với việc bổ sung một trục id, Mô hình dữ liệu dạng khối cho phép theo dõi sự thay đổi dữ liệu theo thời gian hoặc giai đoạn, khoảng cách Theo lí thuyết này, đến nay, đã có nhiều công trình nghiên cứu khoa học được đề xuất, trong đó có các nghiên cứu về các phụ thuộc dữ liệu như Phụ thuộc hàm, Phụ thuộc đa trị, Phụ thuộc Boolean dương tổng quát. Những kết quả của các công trình nghiên cứu này đã góp phần quan trọng trong việc mô tả
12. 3 các ràng buộc dữ liệu trên khối. Mặc dù kết quả mang lại đã giải quyết được nhiều bài toán thực tiễn, nhưng trong thực tế vẫn còn tồn tại ràng buộc dữ liệu mà các phụ thuộc trên chưa mô tả được trên khối. Chẳng hạn: Cho khối dữ liệu BAN_HANG (Bán hàng) gồm các thuộc tính: Bánh mì (A1), Bơ (A2), Sữa (A3) và tập chỉ số theo mùa: Mùa thu (1), Mùa hè (2), Mùa đông (3) với các phép gán trị các phần tử ti, i=1 n trên các thuộc tính Bánh mì (A1), Bơ (A2), Sữa (A3) đều có các loại: CC: Cao cấp; L1: Loại 1; L2: Loại 2 như Hình 2 dưới đây: Bánh mì Bơ Sữa (A1) (A2) (A3) BAN_HANG L2 L2 L2 CC null CC t1 CC CC null CC L2 CC CC CC L2 t2 CC L2 CC CC CC null L2 L2 L2 t3 L2 L2 L2 L2 null L2 L2 L2 null t4 L2 null L2 L2 null L1 Mùa đông (3) L2 L1 null Mùa hè (2) tn L2 null L1 Mùa xuân (1) Hình 2: Biểu diễn khối BAN_HANG Bài toán đặt ra, với khối dữ liệu trên có thể tìm được mối liên hệ nào giữa các thuộc tính trên khối, chúng có ràng buộc với nhau như thế nào. Giả sử, khách hàng mua Bánh mì thì thường mua kèm Bơ hoặc mua kèm Sữa, biểu diễn bằng công thức logic ta có: Bánh mì Bơ  Sữa. Như vậy, với ràng buộc trên, khái niệm phụ thuộc hàm không diễn tả được, do đó mở rộng phụ thuộc dữ liệu sang phụ thuộc Boolean dương tổng quát là cần thiết. Tuy nhiên, với khối dữ liệu đã cho ở trên, ta không thể tìm được Phụ thuộc
13. 4 Boolean dương tổng quát trên khối và phụ thuộc Boolean dương tổng quát trên từng lát cắt thể hiện khách hàng mua Bánh mì thường mua kèm Bơ hoặc mua kèm Sữa. Bằng chứng là, với cặp phần tử (t1, t2), xét trên lát cắt mùa xuân ta thấy t1, t2 có giá trị bằng nhau trên bánh mì nhưng không bằng nhau trên bơ và không bằng nhau trên sữa. Điều này có nghĩa: Bánh mì  not Bơ  Sữa. Mặt khác, nếu mở rộng cách tiếp cận dữ liệu theo kiểu: khách hàng mua Bánh mì (không phân biệt loại cao cấp, loại 1 hoặc loại 2) thì rõ ràng đều mua kèm Bơ hoặc kèm Sữa. Do đó, với cách tiếp cận này, ta có thể biểu diễn Bánh mì Bơ  Sữa (thông qua việc mở rộng phép sánh trị các cặp phần tử). Thêm vào đó, dữ liệu được lưu trữ theo mùa, từ đó khách hàng được theo dõi, với mùa nào thì có xu hướng mua các mặt hàng nào, với loại hàng như thế nào. Đó chính là một hướng nghiên cứu mà luận án tiếp cận. Một hướng mở rộng khác luận án muốn tiếp cận, nếu mỗi lần so sánh các phần tử, thay vì so sánh các cặp phần tử, ta so sánh p phần tử (p ≥ 2), thì có kết luận được tồn tại phụ thuộc dữ liệu trên khối hay không, hoặc so sánh p phần tử, chúng giống hay khác nhau như thế nào và theo ngưỡng nào. Trong mô hình dữ liệu quan hệ, hướng mở rộng này đã được đề xuất. Tuy nhiên, với mô hình dữ liệu quan hệ, việc đánh giá này chỉ có giá trị tại một thời điểm nhất định, để theo dõi cả một quá trình thay đổi là một công việc khó khăn, nhưng trong mô hình dữ liệu dạng khối, việc này trở lên đơn giản hơn. Đó chính là một hướng nghiên cứu mà luận án tiếp cận. Với các dạng bài toán này không chỉ xảy ra trong lĩnh vực kinh doanh mà còn cả trong lĩnh vực giáo dục, y tế, du lịch, do đó, việc mở rộng các phụ thuộc dữ liệu trên khối là cần thiết. Xuất phát từ những lí do trên, luận án chọn đề tài “Một số Phụ thuộc logic mở rộng trong Mô hình dữ liệu dạng khối” với mục đích tiếp tục nghiên cứu các phụ thuộc dữ liệu trên khối nhằm tìm ra các phụ thuộc logic mới góp phần mở rộng các ràng buộc dữ liệu trong thực tiễn. 2. Tổng quan tình hình nghiên cứu liên quan đến luận án Các nghiên cứu nhằm mở rộng mô hình dữ liệu quan hệ được nhiều nhà khoa học quan tâm. Một số hướng nghiên cứu chính: - Mở rộng mô hình dữ liệu quan hệ thành các khối dữ liệu (data cube) và mô
14. 5 hình dữ liệu đa chiều (Multidimensional Databases): Theo hướng này, tác giả C. Dyreson đã đề xuất khối dữ liệu (data cube), theo đó dữ liệu được thể hiện dưới dạng đa chiều, mỗi chiều mô tả một đặc trưng của dữ liệu để phản ánh ngữ nghĩa của dữ liệu [2]. Tiếp cận theo hướng này, một mở rộng của mô hình dữ liệu quan hệ đã được đề xuất bởi R. Agrawal, A. Gupta, and S. Sarawagi, đó là mô hình dữ liệu đa chiều (Multidimensional Databases) [3]. Với đề xuất này, dữ liệu được xây dựng với cấu trúc gồm một bảng trung tâm (fact table) được kết nối với các bảng còn lại (dimention table), mỗi dimention table là một thuộc tính, một đặc trưng của dữ liệu. Với cấu trúc của khối dữ liệu đa chiều thì mỗi chiều tương ứng với một thuộc tính, cung cấp cho người quản lý một khung nhìn đa chiều về dữ liệu. Một ví dụ về cách thể hiện dữ liệu đa chiều như hình 3. Trong ví dụ dữ liệu được thể hiện gồm thuộc tính thời gian: Jan-01, Feb-01, Mar-01, Apr-01; thuộc tính địa chỉ: Tokyo, Rome; thuộc tính tên mặt hàng: Standard PC, Executive PC, Ambassador PC. Hình 3. Biểu diễn mô hình dữ liệu đa chiều Trong hệ thống này, một kỹ thuật thường được dùng để truy xuất dữ liệu là sử dụng công cụ phân tích trực tuyến - OLAP (On- Line Analytical Processing). Công cụ này giúp phân tích, truy xuất dữ liệu và thể hiện dữ liệu đa chiều dưới dạng các khối (cube) nhằm cung cấp cho người sử dụng một khung nhìn đa chiều về dữ liệu. Theo hướng tiếp cận này, một số công trình nghiên cứu được đề xuất như: Mô hình dữ liệu đa chiều cho dữ liệu phức tạp [6]; khối dữ liệu động (Dynamic Data Cube) [7] và một số công trình nghiên cứu khác [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21].
15. 6 Theo hướng nghiên cứu này, dữ liệu không hiển thị trực quan. Do vậy, để truy xuất dữ liệu theo yêu cầu, hệ thống cần sử dụng công cụ phân tích trực tuyến - OLAP để chuẩn hóa dữ liệu nhằm khai phá, chắt lọc thông tin theo yêu cầu, vì vậy mất nhiều thời gian cho việc chuẩn hóa, phân tích dữ liệu. - Mở rộng dữ liệu thành nhà kho dữ liệu (Data Warehousing): Theo hướng này, nhóm tác giả S. Chaudhuri and U. Dayal đã đề xuất tổng quan nhà kho dữ liệu (Data Warehousing) [4]. Với đề xuất này Data Warehousing được coi là một tập dữ liệu, được tích hợp từ nhiều nguồn dữ liệu khác nhau, nhiều kiểu dữ liệu khác nhau, có tính hướng chủ đề và biến đổi theo thời gian được dùng để hỗ trợ cho việc xử lý dữ liệu, hỗ trợ đưa ra các quyết định. Tiếp cận theo hướng này, Paulraj Ponniah đã đề xuất một số nguyên tắc cơ bản của nhà kho dữ liệu [22], trong đó đề cấp đến một số nguyên tắc như: làm sạch dữ liệu, chuyển đổi dữ liệu, kiến trúc kho dữ liệu và cơ sở hạ tầng, các phương thức khác nhau để cung cấp, xử lý thông tin và một số công trình nghiên cứu khác [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33]. Những năm gần đây, theo hướng nghiên cứu này, một số công trình khoa học được đề xuất đó là: Mô hình lô-gic kho dữ liệu theo thời gian, được đề xuất bởi nhóm tác giả Garani, G., Adam, G., Ventzas, năm 2016 [34]; Đề xuất các phương thức để cải thiện chất lượng dữ liệu nhà kho dữ liệu [35], [36], [37], [38], [39], [40], [41]. Mô hình khái niệm kho dữ liệu theo thời gian và chuyển đổi thành mô hình quan hệ theo thời gian được đề xuất bởi nhóm tác giả Soumiya Ain El Hayat, Mohamed Baha, năm 2019 [42]; Thiết kế nhà kho dữ liệu cho phép lưu trữ các biến có thể trích xuất dữ liệu theo thời gian được đề xuất bởi nhóm tác giả Reddy, Chittineni, Suneetha năm 2020 [43]. Cũng giống như hướng mở rộng dữ liệu thành các khối dữ liệu và mô hình dữ liệu đa chiều, dữ liệu không hiển thị trực quan. Do vậy, để truy xuất dữ liệu theo yêu cầu, bắt buộc cần xây dựng công cụ để khai phá dữ liệu để chắt lọc thông tin theo yêu cầu, do đó mất nhiều thời gian cho việc chuẩn hóa, phân tích dữ liệu. - Mở rộng dữ liệu theo cách tiếp cận bằng công nghệ Blockchain: Blockchain lần đầu tiên được đề xuất bởi Nakamoto vào năm 2008, với tên
16. 7 gọi Bitcoin đã đề cập đến giao dịch tiền tệ trên máy tính không thông qua trung gian, sau đó được nhiều tác giả quan tâm nghiên cứu. Năm 2017, nhóm tác giả Zeng, Xie, Dai, Chen và Wang [5] đã đề cập tổng quan về công nghệ Blockchain, theo đó Blockchain được hiểu là một hệ thống dữ liệu phân cấp, lưu trữ trong các khối thông tin, được liên kết với nhau bằng mã hóa và mở rộng theo thời gian, mỗi khối đều chứa thông tin về thời gian khởi tạo và được liên kết tới khối trước đó, kèm một mã thời gian và dữ liệu giao dịch. Bằng cách đó, Blockchain được thiết kế để chống lại việc thay đổi của dữ liệu, chỉ có thể bổ sung thêm dữ liệu khi đạt được sự đồng thuận của các đối tượng tham gia giao dịch. Với cách tiếp cận theo hướng này, công nghệ Blockchain thích hợp để giải quyết các bài toán thực tế đảm bảo không một giao dịch nào được thực hiện 2 lần để ghi lại những sự kiện, hồ sơ y tế, xử lý giao dịch tiền tệ, công chứng, danh tính và chứng minh nguồn gốc, [44], [45], [46], [47], [48] , [49] , [50] , [51]. - Mở rộng phụ thuộc dữ liệu sang phụ thuộc Boolean dương: Theo hướng nghiên cứu này, nhóm tác giả Berman J. and Blok W.J. đề xuất mở rộng khái niệm phụ thuộc hàm sang Phụ thuộc Boolean dương, bao gồm những ràng buộc dữ liệu được mô tả thông qua các công thức Boolean dương trên mô hình dữ liệu quan hệ [52], [53]; Mở rộng theo hướng nghiên cứu này, một số nghiên cứu được đề xuất trong mô hình dữ liệu quan hệ: Phụ thuộc Boolean dương tổng quát, phụ thuộc Boolean dương đa trị, phụ thuộc Boolean dương đa trị theo nhóm bộ, [54], [55], [56], [57], [58], [59], [60], [61], [62] , [63], [64]. Các mở rộng này được xây dựng trên nền tảng toán học chặt chẽ, đó là lý thuyết về đại số và logic, đại số Boolean. Đây chính là kiến thức nền tảng quan trọng, là định hướng để nghiên cứu sinh xây dựng các mục tiêu và triển khai thực hiện trong luận án. - Mở rộng phụ thuộc dữ liệu sang mô hình dữ liệu dạng khối: Theo hướng nghiên cứu này, nhóm tác giả Nguyễn Xuân Huy, Trịnh Đình Thắng đã đề xuất một mở rộng của mô hình quan hệ là mô hình dữ liệu dạng khối, bằng cách thêm trục id, cho phép theo dõi được sự thay đổi của dữ liệu theo thời gian, địa điểm, khoảng cách, Tiếp cận theo hướng mở rộng này, một loạt các nghiên cứu được đề xuất trên mô hình dữ liệu dạng khối, như: Các phép toán đại số trên khối, Phụ thuộc hàm [65], [66], [67], [68], [69], phụ thuộc đa trị
17. 8 [70],[71], các nghiên cứu về khóa, bao đóng, phụ thuộc Boolean dương tổng quát trên khối , [72], [73], [74], [75], [76], . Các nghiên cứu về khai phá dữ liệu trong mô hình dữ liệu dạng khối cũng được nghiên cứu và đề xuất [77], [78], [79], [80], [81], [82]. Kết hợp các nghiên cứu về việc mở rộng phụ thuộc dữ liệu sang phụ thuộc Boolean dương do Berman J. and Blok W.J. đề xuất, cùng với các kiến thức nền tảng trong mô hình dữ liệu dạng khối, từ các kết quả của các công trình nghiên cứu này là tiền đề để nghiên cứu sinh đặt mục tiêu nghiên cứu và triển khai thực hiện các mục tiêu đặt ra trong luận án. 3. Mục tiêu nghiên cứu - Tìm ra Hội suy dẫn của các Công thức Boolean dương trong mô hình dữ liệu dạng khối nhằm tìm được tập các công thức suy dẫn nhỏ nhất của các thuộc tính trên khối góp phần loại bỏ các thuộc tính dư thừa trong thiết kế cơ sở dữ liệu. - Tìm ra Phụ thuộc Boolean dương đa trị, Phụ thuộc Boolean dương theo nhóm bộ, Phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu dạng khối nhằm tìm được các ràng buộc dữ liệu, các quyphun luật của các thuộc tính theo hướng đa trị hoặc theo nhóm bộ, đa trị theo nhóm bộ của các thuộc tính trên khối, góp phần mở rộng phụ thuộc dữ liệu trên khối. 4. Đối tượng và phương pháp nghiên cứu Đối tượng nghiên cứu chính của luận án là các phụ thuộc logic, đại số Boolean trên mô hình dữ liệu quan hệ và mô hình dữ liệu dạng khối. Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết, sử dụng các công cụ toán học và logic học, các phương pháp suy luận, phân tích, chứng minh, lập bảng chân lý, để nghiên cứu nhằm tìm ra các kết quả mới về Hội suy dẫn, Phụ thuộc Boolean dương đa trị, Phụ thuộc Boolean dương theo nhóm bộ, Phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu dạng khối. Cài đặt thuật toán tìm Hội suy dẫn của các công thức Boolean dương. 5. Nội dung nghiên cứu Với những lý do và mục tiêu ở trên, luận án thực hiện các nghiên cứu sau:
18. 9 - Đề xuất khái niệm về Công thức suy dẫn trong Mô hình dữ liệu dạng khối, phát biểu và chứng minh một số định lý, tính chất về công thức suy dẫn, tính chất của họ tập đóng và khối chân lý trong lược đồ khối, từ đó suy ra hội suy dẫn F và các tính chất của Hội suy dẫn. Xây dựng các thuật toán tìm hội suy dẫn F nhận một khối nhị phân cho trước làm khối chân lý. Điều kiện cần và đủ để một công thức logic biểu diễn qua một hội suy dẫn. Cài đặt thuật toán tìm hội suy dẫn F nhận một khối nhị phân cho trước làm khối chân lý. - Đề xuất khái niệm về phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối, phát biểu và chứng minh các định lý, các tính chất của Phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối, chứng minh tính đầy đủ của họ hàm I,  và , khẳng định được sự tương đương của 3 loại suy dẫn (suy dẫn logic, suy dẫn theo khối, suy dẫn theo khối có không quá p phần tử), mối quan hệ giữa phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối và phụ thuộc Boolean dương đa trị trong mô hình dữ liệu quan hệ. Từ các kết quả của phụ thuộc Boolean dương đa trị trên khối, luận án tiếp tục đề xuất bao đóng của tập phụ thuộc Boolean đa trị trên khối, điều kiện cần và đủ của một thể hiện chặt của tập phụ thuộc Boolean dương đa trị trên khối Ngoài ra, một số tính chất liên quan đến khái niệm này khi khối suy biến thành quan hệ cũng đã được phát biểu và chứng minh. - Đề xuất các khái niệm về khối chân lý theo nhóm bộ của khối, phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối, từ đó phát biểu và chứng minh định lý tương đương để khẳng định sự tương đương của ba loại suy dẫn trên lược đồ khối: suy dẫn logic, suy dẫn theo khối và suy dẫn theo khối có không quá p phần tử. Từ các kết quả của phụ thuộc Boolean dương theo nhóm bộ trên khối, luận án tiếp tục đề xuất bao đóng của tập phụ thuộc Boolean dương theo nhóm bộ trên khối, điều kiện cần và đủ để một khối là thể hiện chặt của tập phụ thuộc Boolean dương theo nhóm bộ trên khối Ngoài ra, một số tính chất liên quan đến khối chân lý của khối và khối chân lý của tập phụ thuộc Boolean dương theo nhóm bộ trên khối cũng đã được phát biểu và chứng minh. - Kết hợp kết quả nghiên cứu về phụ thuộc Boolean dương đa trị trên khối và Phụ thuộc Boolean dương theo nhóm bộ trên khối, chúng tôi đề xuất khái niệm về phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu dạng khối.
19. 10 Phát biểu và chứng minh các định lý, các tính chất của phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối, khẳng định được sự tương đương của 3 loại suy dẫn (suy dẫn logic, suy dẫn theo khối, suy dẫn theo khối có không quá p phần tử), tìm mối liên hệ giữa phụ thuộc Boolean dương đa trị theo nhóm bộ với phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối, cũng như mối liên hệ giữa phụ thuộc Boolean dương đa trị theo nhóm bộ với phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu quan hệ. 6. Bố cục của luận án Luận án gồm phần mở đầu, 3 chương tiếp theo và cuối cùng là phần kết luận. Chương 1 trình bày những kiến thức nền tảng liên quan đến luận án: Mô hình dữ liệu dạng khối - một mở rộng của mô hình dữ liệu quan hệ; các khái niệm về công thức Boolean, Boolean dương, phụ thuộc Boolean dương trong mô hình dữ liệu dạng khối. Chương 2 trình bày kết quả nghiên cứu về hội suy dẫn trong mô hình dữ liệu dạng khối. Tiếp theo là các kết quả nghiên cứu về Phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối. Chương 3 trình bày kết quả nghiên cứu về Phụ thuộc Boolean dương theo nhóm bộ và phụ thuộc Boolean dương đa trị theo nhóm bộ trong mô hình dữ liệu dạng khối.
20. 11 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Mô hình dữ liệu dạng khối 1.1.1. Khối, lát cắt của khối Định nghĩa 1.1. Gọi R = (id; A1, A2, , An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1 n) là các thuộc tính. Mỗi thuộc tính Ai (i=1 n) có miền giá trị tương ứng là dom(Ai). Một khối r trên R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến dom(Ai), (i=1 n). Nói một cách khác: trRttiddomA ():() i . i in 1 Đôi khi, nếu không sợ nhầm lẫn, ta kí hiệu khối này đơn giản là r. [1] Ví dụ 1.1: Để theo dõi điểm học tập của học sinh theo thời gian, ta xây dựng khối Điểm đánh giá (ký hiệu DIEM_DG) của học sinh theo thang điểm 10 như sau: R = (id; A1, A2, A3, A4), trong đó: id = {1/2019, 2/2019, 3/2019}, các thuộc tính là A1 = maHS (mã học sinh), A2 = Toán, A3 = Vật lý, A4 = Hóa học. Khối dữ liệu được gán trị như ở hình 1.1: Khối: DIEM_DG maHS Toán Vật lý Hóa học a2 9,0 5,0 9,0 a1 8,0 6,0 7,0 t1 a1 7,0 8,0 9,0 b1 7,5 8,5 10 b1 7,5 5,0 8,0 t2 b1 7,0 7,0 9,0 c1 8,5 9,5 10 c1 6,5 7,0 9,0 t3 c1 7,0 8,0 8,0 d1 8,5 10 8,0 3/2019 d1 7,5 7,0 9,0 2/2019 t4 d1 7,0 9,0 10 1/2019 Hinh 1.1: Biểu diễn khối DIEM_DG Với khối DIEM_DG như ở hình 1.1, ta có: - Mã của học sinh t1 vào tháng 1/2019 là: t1(1/2019, maHS) = a1. - Điểm môn Toán của học sinh t2 ở tháng 2/2019 là: t2(2/2019, Toán) = 7,5.
21. 12 - Điểm môn Hóa của học sinh t3 ở tháng 3/2019 là: t3(3/2019, Hóa) = 10. Định nghĩa 1.2 Cho R = (id; A1, A2, , An), r(R) là một khối trên R. Với mỗi x id ta kí hiệu r(Rx) là một khối với Rx = ({x}; A1, A2, , An) sao cho: i i tx r(Rx) tx = {t x = t } i=1 n , x i ở đây t r(R), t = {t : id dom(Ai)}i=1 n, Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x. [1] Ví dụ 1.2: Với khối r là khối DIEM_DG đã cho ở trên, nếu x = 1/2019 id thì lát cắt r(R1/2019) có dạng như sau: Bảng 1.1: Biểu diễn lát cắt của khối DIEM_DG r(R1/2019 ) maHS Toán Vật lý Hóa học a1 7,0 8,0 9,0 b1 7,0 7,0 9,0 c1 7,0 8,0 8,0 d1 7,0 9,0 10 Khi đó, ở lát cắt này ta có: - Mã của học sinh t2 vào tháng 1/2019 là: t2(1/2019, maHS) = b1. - Điểm đánh giá môn Toán của học sinh t2 ở tháng 1/2019 là: t2(1/2019, Toán) = 7,0. - Điểm đánh giá môn Vật lý của học sinh t3 ở tháng 1/2019 là: t3(1/2019, Vật lý) = 8,0. - Điểm đánh giá môn Hóa học của học sinh t1 ở tháng 1/2019 là: t1(1/2019, Hóa học) = 9,0. Ta có các nhận xét sau: Nhận xét 1: Cho R = (id; A1, A2, , An), r(R) là một khối trên R. Với mỗi x id thì lát cắt r(Rx) là một quan hệ. Trong trường hợp tập chỉ số id chỉ gồm một phần tử
22. 13 thì r(R) trở thành một quan hệ. Như vậy, mỗi quan hệ r(A1, A2, , An) là một trường hợp đặc biệt của khối, đó chính là khối r(R) với R = ({x}; A1, A2, , An). Nhận xét 2: Cho R = (id; A1, A2, , An), r(R) là một khối trên R, khi đó tồn tại một họ rR() quan hệ duy nhất biểu diễn họ x xid các lát cắt của khối r(R). Ngược lại không đúng, nghĩa là với một họ quan hệ cho trước biểu diễn họ các lát cắt của một khối nào đó thì khối tìm được không duy nhất. 1.1.2. Đại số khối Cho r(R) là một khối trên R=(id; A1, A2, , An). Ta giả thiết rằng r(R) là một khối gồm một tập hữu hạn các phần tử. Cũng như đại số quan hệ trong mô hình cơ sở dữ liệu quan hệ, đại số khối cũng có các phép toán như của đại số quan hệ, ngoài ra còn có thêm các phép toán khác, đó là: tích Đề các theo tập chỉ số và phép nối dài. Hai khối r(R) và r’(R) được gọi là khả hợp nếu chúng có cùng một lược đồ khối R. 1.1.2.1. Phép hợp Cho hai khối r(R) và r’(R) khả hợp, R=(id; A1, A2, , An), khi đó hợp của r(R) và r’(R), kí hiệu rr ' là một khối gồm các phần tử thuộc một trong hai khối r(R) và r’(R) đã cho [65]. Ta có: ={t | t r(R) hoặc t r'(R)}. 1.1.2.2. Phép giao Cho hai khối r(R) và r’(R) khả hợp, R=(id; A1, A2, , An), khi đó giao của r(R) và r’(R), kí hiệu là rr ' là một khối mà các phần tử của nó thuộc đồng thời cả hai khối r(R) và r’(R) đã cho [65]. Ta có: rrt tr'|( R )'( và ) rr R . 1.1.2.3. Phép trừ Cho hai khối r(R) và r’(R) khả hợp, R=(id; A1, A2, , An), khi đó hiệu của