Luận án tiến sĩ toán học: Siêu đồ thị và lược đồ CSDL phi chu trình

Luận án nghiên cứu siêu đồ thị (hypergraph) trong lý thuyết cơ sở dữ liệu. Trọng tâm là cơ sở dữ liệu phi chu trình (PCT). Cấu trúc phi chu trình mang lại nhiều tính chất quý. Truy vấn nhanh hơn. Kết nối an toàn hơn. Lưu trữ gọn hơn. Siêu đồ thị mô hình hóa lược đồ quan hệ một cách tự nhiên. Mỗi đỉnh là một thuộc tính. Mỗi siêu cạnh là một quan hệ. Tính phi chu trình loại bỏ vòng lặp ẩn trong lược đồ. Nhờ vậy phép kết nối tự nhiên không sinh dữ liệu thừa. Lý thuyết này nền tảng cho thiết kế cơ sở dữ liệu quan hệ. Nó cũng nền tảng cho cơ sở dữ liệu phân tán. Luận án đặt vấn đề rõ ràng. Mục tiêu là xây dựng công cụ toán học cho lược đồ phi chu trình.

1.1. Khái niệm siêu đồ thị và siêu cạnh

1.2. Tính phi chu trình trong cơ sở dữ liệu

Phụ thuộc hàm (FD) là ràng buộc dữ liệu cơ bản. FD ràng buộc giá trị thuộc tính này theo thuộc tính khác. Luận án biểu diễn FD bằng cấu trúc đồ thị. FD-đồ thị (FD-graph) mô tả tập phụ thuộc hàm. FD-đường đi (FD-path) mô tả suy diễn phụ thuộc. Siêu đồ thị nối kết CHG tổng quát hóa các cấu trúc này. CHG biểu diễn quan hệ giữa nhiều tập thuộc tính cùng lúc. Cách tiếp cận đồ thị làm rõ phép suy diễn. Bao đóng thuộc tính tính được nhờ duyệt đường đi. Khóa và siêu khóa nhận diện trực tiếp trên đồ thị. Mô hình hóa bằng CHG giảm độ phức tạp tính toán. Nó cung cấp ngôn ngữ hình học cho lý thuyết phụ thuộc.

2.1. Phụ thuộc hàm FD và phép suy diễn

2.2. Biểu diễn FD bằng FD đồ thị và FD đường đi

2.3. Siêu đồ thị nối kết CHG cho lược đồ

Phụ thuộc đa trị (MVD) tổng quát hóa phụ thuộc hàm. MVD mô tả quan hệ một-nhiều giữa các tập thuộc tính. Phụ thuộc kết nối (JD) còn tổng quát hơn. JD ràng buộc khả năng tách và ghép quan hệ. Cả hai liên hệ chặt chẽ với tính phi chu trình. Lược đồ phi chu trình tương đương một tập JD đặc biệt. Luận án dùng siêu đồ thị để phân tích MVD và JD. Phép tách quan hệ ánh xạ thành phép chia siêu cạnh. Tính chất kết nối không mất mát kiểm tra được bằng đồ thị. Kết quả làm rõ mối liên hệ giữa các loại phụ thuộc. Nó thống nhất lý thuyết chuẩn hóa ở bậc cao.

3.1. Phụ thuộc đa trị MVD và dạng chuẩn

3.2. Phụ thuộc kết nối JD và phép tách

Tính nhất quán bảo đảm dữ liệu không mâu thuẫn. Luận án phân biệt hai mức. Tính nhất quán từng cặp (PC) xét từng cặp quan hệ. Tính nhất quán toàn phần (TC) xét toàn bộ hệ. Trên lược đồ phi chu trình hai mức này trùng nhau. Đó là tính chất quan trọng của cấu trúc PCT. Bộ rút gọn đầy đủ (FRs) loại bỏ bộ dữ liệu thừa. Rút gọn đầy đủ (FR) cho kết quả gọn nhất của một quan hệ. Phép rút gọn siêu đồ thị RED(H) thu nhỏ cấu trúc. RED(H) giữ nguyên ngữ nghĩa kết nối. Kết quả tăng hiệu năng xử lý truy vấn. Nó giảm chi phí truyền dữ liệu.

4.1. Nhất quán từng cặp PC và toàn phần TC

4.2. Bộ rút gọn đầy đủ FRs và rút gọn FR

4.3. Phép rút gọn siêu đồ thị RED H

Cơ sở dữ liệu phân tán (SDD) lưu dữ liệu trên nhiều nút. Truy vấn cần kết nối dữ liệu giữa các nút. Chi phí truyền tin là vấn đề lớn. Lược đồ phi chu trình giảm chi phí này. Siêu đồ thị định hướng chiến lược kết nối tối ưu. Cây kết nối xác định thứ tự xử lý hiệu quả. Phép nửa kết nối lọc dữ liệu trước khi truyền. Bộ rút gọn đầy đủ áp dụng trực tiếp cho SDD. Tính nhất quán từng cặp đủ bảo đảm toàn hệ. Kết quả luận án có giá trị lý thuyết. Nó cũng có giá trị ứng dụng thực tế. Hệ phân tán hiện đại hưởng lợi từ cấu trúc phi chu trình.

5.1. Tối ưu truy vấn trong cơ sở dữ liệu phân tán

5.2. Đóng góp lý thuyết và hướng phát triển