Luận án Tiến sĩ: Một số phụ thuộc logic mở rộng trong mô hình dữ liệu dạng khối - Trịnh Ngọc Trúc

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 luan an 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.TS Trịnh Đình Thắng 2. Nguyễn Như Sơn Hà Nội - 2021 luan an 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 luan an 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. Trịnh Đình Thắng, TS. 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 luan an iii MỤC LỤC MỞ ĐẦU. MỘT SỐ KIẾN THỨC CƠ SỞ. Mô hình dữ liệu dạng khối.

Khối, lát cắt của khối. Đại số khối. Phụ thuộc hàm trong mô hình dữ liệu dạng khối. Phụ thuộc đa trị trong mô hình dữ liệu dạng khối.

Đại số Boolean. Công thức Boolean. Bảng trị và bảng chân lý. Suy dẫn logic.

Công thức Boolean dương. Công thức Boolean đa trị. Bảng trị và bảng chân lý. Suy dẫn logic.

Công thức Boolean dương đa trị. Phụ thuộc Boolean dương trong mô hình dữ liệu dạng khối. Khối chân lý của khối. Phụ thuộc Boolean dương trên khối.

Kết luận chương 1. 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. Hội suy dẫn trong mô hình dữ liệu dạng khối. Công thức suy dẫn trong lược đồ khối.

Tính chất của họ tập đóng và khối chân lý. Tính chất của hội suy dẫn và khối chân lý. Các thuật toán xây dựng hội suy dẫn. Thuật toán XDF.

Thuật toán XDF-S. Cài đặt thực nghiệm thuật toán XDF .44 luan an iv 2. Phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối. Khối m-chân lý của khối dữ liệu.

Công thức Boolean dương đa trị. Phụ thuộc Boolean dương đa trị trên khối. Bao đóng tập phụ thuộc Boolean dương đa trị. Thể hiện và thể hiện chặt tập phụ thuộc Boolean dương đa trị.

Cài đặt minh họa bài toán tìm Phụ thuộc Boolean dương đa trị trên khối. Tổng kết chương 2. 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. Phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối.

Khối chân lý theo nhóm bộ của khối dữ liệu. Phụ thuộc Boolean dương theo nhóm bộ của khối dữ liệu. Bao đóng tập phụ thuộc Boolean dương theo nhóm bộ. Thể hiện và thể hiện chặt tập 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. Khối chân lý đa trị theo nhóm bộ của khối dữ liệu. Phụ thuộc Boolean dương đa trị theo nhóm bộ của khối dữ liệu. Bao đóng tập phụ thuộc Boolean dương đa trị theo nhóm bộ.

Thể hiện, thể hiện chặt. 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. 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 luan an 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 luan an vi DANH MỤC CÁC BẢNG Bảng i: Biểu diễn quan hệ MAT_HANG.1: Biểu diễn lát cắt của khối DIEM_DG .2: Biểu diễn lát cắt thể hiện phụ thuộc hàm .1: Bảng T và bảng h trên lát cắt 1 .2: Bảng T và bảng h trên lát cắt 2 .3: Bảng T và bảng h trên lát cắt 3 .39 luan an 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 .1: Biểu diễn khối DIEM_DG .2: Biểu diễn khối dữ liệu r(R) .3: Ví dụ về khối chân lý Tr .1: Khối chân lý Tr .2: Sơ đồ thuật toán XDF .3: Biểu diễn khối chân lý Tr .4: Sơ đồ thuật toán XDF-S .5: Khối dữ liệu Ban_hang_DT .6: Khối chân lý Tr .7: Khối chân lý Tf,m .8: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa hè .9: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa xuân .10: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa đông .1: Khối dữ liệu r: Ban_hang_NB .2: Khối chân lý Tf_nb .3: Khối dữ liệu r: Ban_hang_DTNB .4: Khối chân lý Tr_dtnb .5: Khối chân lý Tf_dtnb,m .6: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa hè .7: Biểu đồ mô tả xu hướng khách hàng mua hàng vào mùa xuân .93 luan an 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đ 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 luan an 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.