Luận án Tiến sĩ ngành Máy tính: Một số Phụ thuộc logic mở rộng trong Mô hình dữ liệu dạng khối

Chia sẻ: Tần Mộc Phong | Ngày: | Loại File: PDF | Số trang:117

Thêm vào BST

Báo xấu

39
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ ngành Máy tính: Một số Phụ thuộc logic mở rộng trong Mô hình dữ liệu dạng khối được thực hiện với mục tiêu nhằm 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;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ ngành Máy tính: Một số Phụ thuộc logic mở rộng trong Mô hình dữ liệu dạng khối

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
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
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
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
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
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
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
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
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
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
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 01 Sữa chua 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ả
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
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ô
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].
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
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ị
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:
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.
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.
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: t  r ( R)  t  t i : id  dom( Ai ) i 1..n . Đô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.