Tổng quan luận án

Luận án tiến sĩ chuyên ngành Hệ thống thông tin (mã số: 9 48 01 04) với đề tài "Phát triển phụ thuộc Boole dương xấp xỉ trong cơ sở dữ liệu quan hệ" do nghiên cứu sinh Nguyễn Thị Vân thực hiện dưới sự hướng dẫn khoa học của PGS. TSKH. Nguyễn Xuân Huy tại Học viện Khoa học và Công nghệ – Viện Hàn lâm Khoa học và Công nghệ Việt Nam (bảo vệ năm 2023).

Tính cấp thiết và khoảng trống nghiên cứu

Trong lĩnh vực quản trị và thiết kế cơ sở dữ liệu quan hệ (CSDLQH), các phụ thuộc dữ liệu đóng vai trò nền tảng nhằm phản ánh ngữ nghĩa của thế giới thực, đồng thời đảm bảo tính toàn vẹn, tính nhất quán và tối ưu hóa truy vấn khi khai thác tri thức. Khái niệm phụ thuộc hàm (PTH) truyền thống do E. F. Codd đề xuất năm 1970 vận hành dựa trên hai giới hạn cốt lõi:

  1. Ràng buộc suy dẫn cứng nhắc chỉ biểu diễn dưới dạng $X \to Y$.
  2. Phép so sánh giữa các giá trị thuộc tính của các bộ dữ liệu hoàn toàn bị giới hạn bởi phép sánh trị đẳng thức tuyệt đối ($=$).

Trong các ứng dụng thực tế với khối lượng dữ liệu lớn và đa dạng, phụ thuộc hàm truyền thống bộc lộ những điểm bất cập:

  • Hiện tượng dữ liệu nhiễu và ngoại lệ: Trong một quan hệ có số lượng lớn các bộ, sự tồn tại của một vài bộ vi phạm do sai sót ngoại lệ hoặc lỗi thu thập có thể làm vô hiệu hóa toàn bộ phụ thuộc hàm, dù phần lớn dữ liệu vẫn tuân thủ quy luật ngữ nghĩa.
  • Sự hạn chế của phép so sánh bằng: Nhiều ngữ cảnh thực tế đòi hỏi biểu diễn sự chênh lệch có ngưỡng (ví dụ: quy chuẩn may mặc dựa trên chiều cao chênh lệch dưới 3 cm và cân nặng chênh lệch dưới 1 kg; hoặc kiểm soát gian lận ngân hàng khi hai giao dịch cùng thẻ có khoảng cách vị trí $\ge 60\text{ km}$ nhưng chênh lệch thời gian $< 30\text{ phút}$).
  • Nhu cầu biểu diễn các mối quan hệ logic phức tạp: Ràng buộc thực tế không chỉ dừng ở phép kéo theo đơn nhất $X \to Y$ mà cần mở rộng thành các biểu thức Boole tổng quát trên tập thuộc tính.

Khoảng trống nghiên cứu được xác định là sự thiếu vắng một mô hình toán học tổng quát thống nhất, có khả năng tích hợp cả ba yếu tố: biểu thức logic Boole dương tùy ý, phép sánh trị nới lỏng tổng quát $\alpha$, và cơ chế lượng hóa định lượng thông qua hàm $\lambda$ cùng các độ đo không gian (Euclid, Hamming) áp dụng cho cả thuộc tính số lẫn thuộc tính phi số.

Mục tiêu nghiên cứu

Mục tiêu tổng quát của luận án là phát triển các lớp phụ thuộc mới gồm phụ thuộc Boole dương xấp xỉ, phụ thuộc Boole dương xấp xỉ tổng quát và phụ thuộc yếu xấp xỉ; từ đó xây dựng một mô hình toán học tổng quát thống nhất cho các lớp phụ thuộc dữ liệu và thiết lập các thuật toán xử lý lược đồ quan hệ tương ứng.

Luận án xác định ba mục tiêu nghiên cứu cụ thể:

  1. Đề xuất một số loại phụ thuộc mới: phụ thuộc Boole dương xấp xỉ (PTBDXX), mở rộng thành phụ thuộc Boole dương xấp xỉ tổng quát (PTBDXXTQ) và phụ thuộc yếu xấp xỉ tổng quát (PTYXXTQ), làm tiền đề xác lập mối tương quan giữa các lớp phụ thuộc.
  2. Xây dựng các lớp phụ thuộc dữ liệu dựa trên hai đặc trưng cốt lõi là phép sánh trị và công thức suy dẫn; phân tích các dạng của phụ thuộc Boole dương tổng quát (PTBDTQ); chỉ ra đặc tả chung cho phụ thuộc nới lỏng tổng quát và chứng minh phụ thuộc nới lỏng (PTNL) cùng phụ thuộc hàm nới lỏng (PTHNL) là các trường hợp riêng của PTBDTQ.
  3. Phát triển lớp phụ thuộc logic tổng quát; đề xuất quy trình giải bài toán suy dẫn theo ba tiếp cận hình thức (thuật giải Vương Hạo, chứng minh trực tiếp theo dạng chuẩn hội CNF, chứng minh phản chứng theo nguyên lý hợp giải Unif); đề xuất thuật toán tìm bao đóng (LClosure) và thuật toán tìm khóa cho lược đồ quan hệ theo phụ thuộc Boole dương tổng quát.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các khái niệm, tính chất và đặc trưng toán học của các phụ thuộc logic trong cơ sở dữ liệu quan hệ (phụ thuộc Boole dương, phụ thuộc Boole dương xấp xỉ, phụ thuộc Boole dương tổng quát, phụ thuộc yếu, phụ thuộc yếu xấp xỉ, phụ thuộc Boole dương xấp xỉ tổng quát); mối tương quan giữa các lớp phụ thuộc logic; các bài toán kinh điển trong lý thuyết phụ thuộc dữ liệu gồm bài toán suy dẫn (thành viên), bài toán bao đóng, bài toán tìm phủ không dư, phủ tối thiểu và bài toán tìm khóa.
  • Phạm vi nghiên cứu: Các biến thể mở rộng của phụ thuộc hàm và phụ thuộc Boole dương tổng quát; mối quan hệ tương đương giữa suy dẫn logic và suy dẫn quan hệ; các giải thuật xử lý hình thức trên lược đồ quan hệ trong phạm vi mô hình dữ liệu quan hệ mở rộng.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trên thế giới

Lý thuyết phụ thuộc dữ liệu khởi đầu từ công trình của Codd (1970) [1, 2] đặt nền móng cho mô hình CSDLQH và phụ thuộc hàm. Sau đó, Armstrong (1974) [3] thiết lập hệ tiên đề suy dẫn cho phụ thuộc hàm. Trên cơ sở đó, nhiều biến thể và hệ tiên đề mở rộng đã được công bố:

  • Phụ thuộc mạnh, phụ thuộc yếu và phụ thuộc đối ngẫu: Được đề xuất bởi J. Fagin, Zaniolo và các cộng sự [4, 5, 6], cùng với việc phát triển phụ thuộc đa trị với tập giá trị mở rộng trên đoạn $[0, 1]$.
  • Phụ thuộc Boole dương (PTBD): Berman, Delobel và cộng sự (1981, 1985) [7, 8] mở rộng phụ thuộc hàm thành các ràng buộc biểu diễn bằng công thức Boole dương (CTBD), nhưng vẫn duy trì phép sánh trị đẳng thức ($=$).
  • Phụ thuộc hàm xấp xỉ: Jyrki Kivinen và cộng sự (1995) [10] đề xuất khái niệm phụ thuộc hàm xấp xỉ dựa trên việc loại bỏ $n$ bộ lỗi trong quan hệ $r$ để thu được quan hệ con $r'$ thỏa mãn $X \to Y$ với độ xấp xỉ $1 - \frac{#r'}{#r}$. Huhtala Y. và cs (1999) [11], Ronald S. [12] tiếp tục phát triển các thuật toán khai phá cho lớp phụ thuộc này.
  • Các dạng phụ thuộc nới lỏng khác:
    • Ilyas và cs (2004) [12] đề xuất phụ thuộc hàm mềm nhằm mô hình hóa mức độ không chắc chắn cho trước.
    • Bohannon và cs (2007) [13, 14, 15] đề xuất phụ thuộc hàm có điều kiện ứng dụng trong làm sạch dữ liệu.
    • Phụ thuộc hàm đối sánh [16, 17, 18] được nghiên cứu trên dữ liệu mờ.
    • Phụ thuộc hàm độ đo [19] xuất hiện năm 2009.
    • Golab và cs (2008) [20] giới thiệu phụ thuộc tuần tự để biểu diễn ràng buộc trên các thuộc tính có thứ tự.
    • Song S. và cs (2011, 2013) [20, 21] đề xuất phụ thuộc sai khác ($\gamma_X \to \gamma_Y$) và phụ thuộc so sánh để xử lý bài toán toàn vẹn và tối ưu hóa truy vấn.
    • Baixeries J. (2015) [22] nghiên cứu phân tích ràng buộc theo cấu trúc mẫu.
    • Li W. (2016) [23] mở rộng phụ thuộc hàm xấp xỉ trên môi trường dữ liệu lớn phân tán.
    • Vincenzo Deufemia, Loredana Caruccio, Giuseppe Polese (2016) [24] tổng kết 35 loại phụ thuộc dữ liệu mở rộng dưới nhóm phụ thuộc hàm nới lỏng (PTHNL).

Các hướng nghiên cứu trong nước

Tại Việt Nam, các hướng nghiên cứu mở rộng phụ thuộc dữ liệu được phát triển song song bởi nhiều nhóm tác giả:

  • Nguyễn Xuân Huy và Lê Thị Thanh (1993) [9] mở rộng phụ thuộc Boole dương thành phụ thuộc Boole dương tổng quát (PTBDTQ), phụ thuộc Boole dương theo nhóm bộ và phụ thuộc Boole dương đa trị bằng việc thay thế phép so sánh bằng bằng phép sánh trị tổng quát $\alpha$ thỏa ba tiên đề phản xạ, đối xứng, bộ phận; đồng thời chứng minh định lý tương đương giữa suy dẫn quan hệ và suy dẫn logic hình thức.
  • Đàm Gia Mạnh [25], Vũ Ngọc Loãn [26], Bùi Đức Minh [27], Nguyễn Hoàng Sơn [28], Lương Nguyễn Hoàng Hoa [29, 30], Lê Xuân Vinh [31], Trương Thị Thu Hà [32] đã khảo sát sâu về phụ thuộc yếu, phụ thuộc sai khác, phụ thuộc đối ngẫu và cấu trúc đại số của các lớp Boole dương tổng quát.

Khoảng trống luận án giải quyết

Mặc dù báo cáo tổng quan của Deufemia và cs (2016) đã thống kê 35 loại phụ thuộc nới lỏng, các phụ thuộc logic tổng quát, phụ thuộc theo nhóm bộ và phụ thuộc Boole dương xấp xỉ vẫn chưa được đặt trong một khuôn khổ lý thuyết thống nhất. Luận án giải quyết khoảng trống này bằng cách mở rộng đồng thời ba yếu tố:

  1. Mở rộng công thức suy dẫn $X \to Y$ thành công thức Boole dương tùy ý.
  2. Mở rộng phép sánh trị đẳng thức thành phép sánh trị $\alpha$ tổng quát.
  3. Thiết lập hàm định lượng $\lambda$ và cấu trúc độ đo (Euclid, Hamming) cho cả thuộc tính số và phi số để lượng hóa các ràng buộc xấp xỉ theo giá trị thay vì chỉ dựa vào số lượng bộ.

Cơ sở lý thuyết và phương pháp nghiên cứu

Lý thuyết, khái niệm và khung phân tích

Luận án vận dụng hệ thống lý thuyết đại số Boole, logic mệnh đề hình thức và lý thuyết cơ sở dữ liệu quan hệ:

  • Lược đồ quan hệ: Cặp $\rho = (U, F)$, trong đó $U = {a_1, a_2, \dots, a_n}$ là tập hữu hạn các thuộc tính ($n \ge 1$), mỗi thuộc tính $a$ có miền trị $V_a$ chứa ít nhất hai giá trị; $F$ là tập các ràng buộc dữ liệu.
  • Công thức Boole dương ($P(U)$): Tập các công thức logic xây dựng trên $U$ chỉ chứa các phép toán hội ($\wedge$), tuyển ($\vee$), suy dẫn ($\to$) và hằng đúng $1$. Bảng trị $V_g$ của công thức $g$ có kích thước $2^n \times (n+1)$, bảng chân lý $T_g = {v \in \mathcal{B}^n \mid g(v) = 1}$.
  • Phép sánh trị tổng quát $\alpha$: Ánh xạ $\alpha_x: d_x^2 \to \mathcal{B}$ trên miền trị $d_x$ thỏa mãn ba tiên đề:
    • $A_1$ (Phản xạ): $\forall a \in d_x, \alpha_x(a, a) = 1$.
    • $A_2$ (Đối xứng): $\forall a, b \in d_x, \alpha_x(a, b) = \alpha_x(b, a)$.
    • $A_3$ (Bộ phận): $\exists a, b \in d_x, \alpha_x(a, b) = 0$.
  • Hàm định lượng $\lambda$: Ánh xạ $\lambda_A: V_A \to \mathbb{R}$ thỏa mãn tính đơn trị ($\forall a, b \in V_A, a = b \Rightarrow \lambda_A(a) = \lambda_A(b)$) và tính khác biệt ($\exists a, b \in V_A, \lambda_A(a) \neq \lambda_A(b)$).
  • Hệ thống độ đo: Độ đo khoảng cách $d: V \times V \to \mathbb{R}^+$ (thỏa tính không âm, đối xứng, bất đẳng thức tam giác), độ đo Euclid $e(x, y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}$, khoảng cách Hamming $h(u, v) = #{u_i \neq v_i \mid 1 \le i \le n}$, và độ đo cảm sinh $d^*(u, v) = d(\lambda(u), \lambda(v))$.

Phương pháp nghiên cứu thực tế

Luận án sử dụng phương pháp nghiên cứu toán học và khoa học máy tính lý thuyết:

  • Phương pháp tiên đề hóa và hình thức hóa: Xây dựng các định nghĩa chính xác về các lớp phụ thuộc, thiết lập hệ tiên đề và chứng minh các tính chất bằng lập luận logic mệnh đề và đại số Boole.
  • Phương pháp chứng minh tương đương: Chứng minh sự tương đương giữa suy dẫn theo quan hệ ($S \vdash g$), suy dẫn theo quan hệ có không quá hai bộ ($S \vdash_2 g$) và suy dẫn logic ($S \vDash g$).
  • Phương pháp phân tích thuật toán: Xây dựng và phân tích độ phức tạp của các giải thuật chuyển đổi dạng chuẩn hội (CNF), thuật giải chứng minh hằng đúng Vương Hạo, thuật giải hợp giải (Unification/Resolution), thuật toán tính bao đóng (LClosure) và thuật toán tìm khóa tối tiểu.
  • Phương pháp quy nạp toán học và mô hình hóa: Phân loại các lớp phụ thuộc (lớp IE, lớp LA) nhằm tích hợp các biến thể phụ thuộc hàm nới lỏng thành các trường hợp đặc biệt của phụ thuộc Boole dương tổng quát.

Nguồn tư liệu và dữ liệu minh họa

Nghiên cứu sử dụng các tập dữ liệu bảng và mô hình ví dụ kinh điển trong lý thuyết cơ sở dữ liệu để minh chứng cho các định lý và thuật toán (ví dụ: quan hệ bảng giá cước taxi/Grab, dữ liệu khảo sát môi trường đào tạo và độ hài lòng của sinh viên, dữ liệu xếp hạng cuộc thi đồng diễn với các thuộc tính Trang phục, Âm nhạc, Kỹ thuật và Giải thưởng).

Nội dung chính theo từng chương

Chương 1: Các lớp phụ thuộc dữ liệu trong cơ sở dữ liệu

Chương 1 hệ thống hóa cơ sở lý thuyết về các lớp phụ thuộc dữ liệu từ mô hình cổ điển đến các dạng nới lỏng hiện đại, đồng thời chứng minh cấu trúc phân lớp toán học của chúng.

Luận điểm và nội dung cốt lõi:

  • Phụ thuộc hàm và bảng trị: Định nghĩa quan hệ $r$ thỏa mãn phụ thuộc hàm $f: X \to Y$ (ký hiệu $r(f)$). Xây dựng véc-tơ bảng trị $t(u, v) = (t_1, \dots, t_n) \in \mathcal{B}^n$ với $t_i = 1 \Leftrightarrow u.x_i = v.x_i$. Bảng trị của quan hệ $r$ là tập hợp $T_r = {t(u, v) \mid u, v \in r}$. Quan hệ $r$ thỏa $X \to Y \Leftrightarrow T_r[XY] \subseteq T_{X \to Y}$.
  • Ba tiếp cận giải bài toán suy dẫn:
    1. Suy dẫn theo quan hệ: $F \vdash f \Leftrightarrow \forall r \in SAT(F) \Rightarrow r(f)$.
    2. Suy dẫn theo quan hệ có không quá 2 bộ: $F \vdash_2 f \Leftrightarrow \forall r \in REL_2(U), r(F) \Rightarrow r(f)$.
    3. Suy dẫn theo logic (tiên đề Armstrong): $F \vDash f \Leftrightarrow F \to f$ là công thức hằng đúng.
    • Định lý khẳng định tính tương đương: $F \vdash f \Leftrightarrow F \vdash_2 f \Leftrightarrow F \vDash f$, do đó bao đóng $F^+ = F^*$.
  • Phụ thuộc hàm nới lỏng (PTHNL): Dạng tổng quát $X(\lambda) \to Y(\gamma)$ với $\lambda, \gamma$ là điều kiện nới lỏng phép so sánh hoặc lực lượng bộ vi phạm $X(\delta) \to Y$.
  • Phụ thuộc Boole dương tổng quát (PTBDTQ): Thay thế phép so sánh đẳng thức bằng phép sánh trị tổng quát $\alpha$ thỏa $A_1, A_2, A_3$. Bảng trị $T_r = {\alpha(u, v) \mid u, v \in r}$. Chứng minh định lý tương đương cho PTBDTQ: $S \vdash g \Leftrightarrow S \vdash_2 g \Leftrightarrow S \vDash g$.
  • Phân loại các lớp phụ thuộc Boole dương:
    • Lớp IE: Gồm các lớp con IE-1, IE-2, IE-3, IE-4 thể hiện các biến thể phụ thuộc hàm nới lỏng cổ điển.
    • Lớp LA (Logic Formula & Alpha Comparison): Lớp LA-1 kết hợp công thức suy dẫn và phép sánh trị $\alpha$, bao gồm phụ thuộc sai khác ($\alpha_X \to \alpha_Y$ với $f_X = \bigwedge_{a \in X} f_a$) và phụ thuộc nới lỏng theo lực lượng $X(\delta) \to Y$.
    • Luận án chứng minh các lớp phụ thuộc nới lỏng này đều là trường hợp riêng của PTBDTQ.
Lớp phụ thuộc Công thức logic Phép sánh trị trên thuộc tính Bản chất ngữ nghĩa
Phụ thuộc hàm (PTH) $X \to Y$ Đẳng thức tuyệt đối ($=$) Hai bộ bằng nhau trên $X$ thì bằng nhau trên $Y$
Phụ thuộc Boole dương (PTBD) $g \in P(U)$ Đẳng thức tuyệt đối ($=$) Ràng buộc đa biến Boole dương trên các cột bằng nhau
Phụ thuộc sai khác (PTSK) $\alpha_X \to \alpha_Y$ Hàm sai khác $\gamma_a$ Chênh lệch trên $X$ kéo theo chênh lệch trên $Y$
PTH nới lỏng lực lượng $X(\delta) \to Y$ Đẳng thức ($=$) sau loại bộ Tỷ lệ bộ thỏa mãn PTH đạt tối thiểu ngưỡng $\delta$
PTBD tổng quát (PTBDTQ) $g \in P(U)$ Phép sánh trị $\alpha$ ($A_1, A_2, A_3$) Mô hình tổng quát bao hàm toàn bộ các lớp trên

Chương 2: Các lớp phụ thuộc xấp xỉ trong cơ sở dữ liệu

Chương 2 trình bày các đóng góp lý thuyết cốt lõi về việc xây dựng hàm định lượng $\lambda$, hệ thống độ đo không gian và định nghĩa các lớp phụ thuộc xấp xỉ mới.

Luận điểm và nội dung cốt lõi:

  • Xây dựng hàm định lượng $\lambda$: Ánh xạ $\lambda_A: V_A \to \mathbb{R}$ chuyển đổi các miền trị phi số (chuỗi ký tự, thang đo định tính, cấp bậc) thành các giá trị thực. Ví dụ: $\lambda_A(s) = \text{len}(s)$ cho chuỗi; $\lambda_C(\text{rất hài lòng}) = 4, \lambda_C(\text{hài lòng}) = 3, \lambda_C(\text{tạm được}) = 2, \lambda_C(\text{không hài lòng}) = 1$.
  • Định lý 2.1: Chứng minh ánh xạ $\alpha_A$ xây dựng từ hàm $\lambda_A$ thỏa mãn đầy đủ ba tiên đề $A_1$ (phản xạ), $A_2$ (đối xứng), $A_3$ (bộ phận) của phép sánh trị tổng quát.
  • Độ đo và Định lý 2.2: Với mỗi bộ $u = (u_1, \dots, u_n)$, thiết lập véc-tơ $\lambda(u) = (\lambda_{a_1}(u_1), \dots, \lambda_{a_n}(u_n))$. Luận án chứng minh ánh xạ $d^*(u, v) = d(\lambda(u), \lambda(v))$ là một độ đo cảm sinh hợp lệ trong không gian véc-tơ $n$ chiều, thỏa mãn tính không âm, tính đối xứng và bất đẳng thức tam giác.
  • Đề xuất Phụ thuộc hàm xấp xỉ tổng quát: Ký hiệu $X \xrightarrow{\varepsilon_1 \to \varepsilon_2} Y$ với hai ngưỡng thực không âm $\varepsilon_1, \varepsilon_2$. Quan hệ $r$ thỏa mãn phụ thuộc nếu $\forall u, v \in r: d(u.X, v.X) \le \varepsilon_1 \Rightarrow d(u.Y, v.Y) \le \varepsilon_2$.
  • Phân loại ngưỡng độ đo: Ngưỡng $\varepsilon \ge 0$ được phân loại thành ngưỡng không tầm thường ($\exists a, b \in D: d(a, b) > \varepsilon$) và ngưỡng tầm thường ($\forall a, b \in D: d(a, b) \le \varepsilon$).
  • Mở rộng các lớp phụ thuộc xấp xỉ mới: Định nghĩa và thiết lập cấu trúc toán học cho phụ thuộc yếu xấp xỉ (PTYXX), phụ thuộc Boole dương xấp xỉ (PTBDXX) và phụ thuộc Boole dương xấp xỉ tổng quát (PTBDXXTQ), cho phép biểu diễn các ràng buộc xấp xỉ trên miền giá trị định lượng kết hợp với các toán tử logic Boole.

Chương 3: Các thuật toán xử lý lược đồ quan hệ

Chương 3 tập trung xây dựng các thuật toán giải quyết các bài toán nền tảng trên lược đồ quan hệ theo mô hình phụ thuộc Boole dương tổng quát.

Luận điểm và nội dung cốt lõi:

  • Phương pháp chuyển đổi công thức logic về dạng chuẩn hội (CNF):
    • Phương pháp logic: Sử dụng các luật tương đương De Morgan, luật phân phối và luật loại bỏ suy dẫn để đưa biểu thức Boole về dạng hội của các tuyển sơ cấp $\bigwedge_i (\bigvee_j l_{ij})$.
    • Phương pháp lập bảng: Sử dụng bảng chân lý để trích xuất các phép gán trị nhận giá trị 0 và thiết lập các mệnh đề tuyển tương ứng.
  • Xây dựng phương pháp chứng minh công thức hằng đúng (Tautology):
    • Phương pháp chứng minh trực tiếp theo CNF: Một công thức ở dạng CNF là hằng đúng khi và chỉ khi mọi mệnh đề tuyển thành phần đều chứa ít nhất một cặp kí biến đối ngẫu ($x_i \vee \neg x_i$).
    • Phương pháp Vương Hạo: Sử dụng giải thuật phân tích hình thức trên dãy biến đổi ngữ nghĩa để kiểm tra tính hằng đúng của công thức $S \to g$.
    • Phương pháp hợp giải (Unification / Resolution): Biến đổi công thức về dạng các mệnh đề chuẩn hội và áp dụng quy tắc hợp giải phản chứng để tìm mệnh đề rỗng ($\Box$).
  • Thuật toán suy dẫn và bài toán thành viên: Ứng dụng ba phương pháp chứng minh hằng đúng để kiểm tra phụ thuộc $g$ có được suy dẫn từ tập phụ thuộc $S$ ($S \vDash g$) trong lược đồ quan hệ mở rộng.
  • Thuật toán tìm bao đóng (LClosure): Xây dựng thuật toán tính bao đóng của tập thuộc tính và tập phụ thuộc logic dưới ràng buộc Boole dương tổng quát, phục vụ trực tiếp cho bài toán thành viên và bài toán thiết kế lược đồ.
  • Thuật toán tìm khóa của lược đồ quan hệ: Thiết lập thuật toán xác định khóa tối tiểu cho lược đồ quan hệ theo phụ thuộc Boole dương tổng quát, trong đó khóa $T \subseteq U$ là tập thuộc tính đủ nhỏ xác định duy nhất không quá một bộ dữ liệu trong quan hệ.

Kết quả và những đóng góp mới

Đóng góp mới về lý luận khoa học

  1. Phát triển các lớp phụ thuộc mới: Đề xuất thành công các khái niệm phụ thuộc Boole dương xấp xỉ (PTBDXX), phụ thuộc Boole dương xấp xỉ tổng quát (PTBDXXTQ) và phụ thuộc yếu xấp xỉ tổng quát (PTYXXTQ).
  2. Xây dựng khung lý thuyết toán học cho thuộc tính phi số: Đề xuất hàm định lượng $\lambda$ và chứng minh tính hợp lệ của độ đo cảm sinh $d^*$, cung cấp công cụ toán học vững chắc để lượng hóa không gian thuộc tính hỗn hợp trong CSDL quan hệ.
  3. Mô hình hóa thống nhất các lớp phụ thuộc: Chứng minh định lý tương đương giữa suy dẫn logic và suy dẫn quan hệ đối với phụ thuộc Boole dương tổng quát; đồng thời chứng minh rằng các dạng phụ thuộc hàm nới lỏng (lớp IE, lớp LA, phụ thuộc sai khác, phụ thuộc nới lỏng lực lượng) đều là các trường hợp riêng của mô hình PTBDTQ.

Đóng góp mới về mặt thực tiễn và giải pháp kỹ thuật

  1. Hệ thuật toán xử lý lược đồ quan hệ hoàn chỉnh: Đề xuất quy trình giải bài toán suy dẫn hình thức thông qua ba công cụ (CNF, giải thuật Vương Hạo, nguyên lý hợp giải Unif); thiết lập thuật toán tìm bao đóng (LClosure) và thuật toán tìm khóa tối tiểu theo PTBDTQ.
  2. Ứng dụng trong quản trị và thiết kế dữ liệu: Cung cấp công cụ biểu diễn ràng buộc sát với thế giới thực, giúp các nhà quản trị CSDL thiết kế lược đồ linh hoạt, hỗ trợ xử lý dữ liệu lớn có nhiễu, làm sạch dữ liệu, kiểm soát gian lận giao dịch và tối ưu hóa truy vấn trong các hệ thống thông tin phức hợp.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên phạm vi và nội dung trình bày trong luận án, các hạn chế và định hướng nghiên cứu tiếp theo bao gồm:

  • Độ phức tạp tính toán: Việc xử lý các công thức logic Boole tổng quát và chuyển đổi CNF/hợp giải trên không gian thuộc tính lớn tiềm ẩn bài toán thuộc lớp NP-đầy đủ (NPC), cần nghiên cứu thêm các kỹ thuật xấp xỉ hóa để giảm chi phí tính toán.
  • Mở rộng trên kiến trúc phân tán: Cần tiếp tục mở rộng mô hình phụ thuộc Boole dương xấp xỉ trên các hệ quản trị cơ sở dữ liệu phi quan hệ (NoSQL) và hệ thống xử lý dữ liệu lớn phân tán (Big Data).
  • Phụ thuộc dữ liệu bậc cao: Tiếp tục phát triển các lớp phụ thuộc logic bậc cao và phụ thuộc theo nhóm bộ trên các cấu trúc dữ liệu đa phương tiện và đồ thị tri thức.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu có giá trị đối với các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Hệ thống thông tin, Khoa học máy tính: Tham khảo phương pháp hình thức hóa toán học trong lý thuyết CSDL, kỹ thuật chứng minh định lý tương đương và cách thức xây dựng hệ tiên đề cho các cấu trúc dữ liệu mở rộng.
  • Giảng viên đại học: Sử dụng nội dung Chương 1 và Chương 3 làm tài liệu giảng dạy chuyên đề nâng cao về Cơ sở dữ liệu quan hệ, Lý thuyết thông tin và Logic toán ứng dụng.
  • Kỹ sư thiết kế và quản trị cơ sở dữ liệu: Ứng dụng các thuật toán tìm bao đóng, tìm khóa tối tiểu và mô hình hàm định lượng $\lambda$ để thiết kế ràng buộc toàn vẹn, làm sạch dữ liệu và tối ưu hóa hệ thống thông tin quản lý trong doanh nghiệp.

Câu hỏi thường gặp

1. Phụ thuộc Boole dương tổng quát (PTBDTQ) khác phụ thuộc hàm (PTH) truyền thống ở những điểm cốt lõi nào?

PTBDTQ mở rộng PTH ở hai khía cạnh:

  • Về mặt công thức: Thay thế dạng suy dẫn đơn nhất $X \to Y$ bằng một công thức Boole dương tùy ý $g \in P(U)$ xây dựng từ các phép toán $\wedge, \vee, \to$ và hằng 1.
  • Về phép so sánh: Thay thế phép so sánh bằng tuyệt đối ($=$) bằng phép sánh trị tổng quát $\alpha$ thỏa mãn ba tiên đề phản xạ ($A_1$), đối xứng ($A_2$) và bộ phận ($A_3$).

2. Hàm định lượng $\lambda$ đóng vai trò gì trong việc xử lý các thuộc tính phi số?

Hàm định lượng $\lambda_A: V_A \to \mathbb{R}$ thực hiện ánh xạ các giá trị thuộc tính phi số (như chuỗi văn bản, thang đo định tính) thành các số thực nhưng vẫn đảm bảo tính đơn trị ($a = b \Rightarrow \lambda(a) = \lambda(b)$) và tính khác biệt ($\exists a, b: \lambda(a) \neq \lambda(b)$). Nhờ đó, ta có thể áp dụng các độ đo khoảng cách không gian (như khoảng cách Euclid $e(x, y)$) lên các thuộc tính phi số thông qua độ đo cảm sinh $d^*(u, v) = d(\lambda(u), \lambda(v))$.

3. Ba tiếp cận giải bài toán suy dẫn trong phụ thuộc Boole dương tổng quát có quan hệ với nhau như thế nào?

Luận án chứng minh định lý tương đương khẳng định ba tiếp cận sau là hoàn toàn trùng khớp:

  1. Suy dẫn theo quan hệ ($S \vdash g$): Mọi quan hệ thỏa mãn $S$ đều thỏa mãn $g$.
  2. Suy dẫn theo quan hệ có không quá hai bộ ($S \vdash_2 g$).
  3. Suy dẫn theo logic ($S \vDash g$): Công thức $S \to g$ là công thức hằng đúng (tautology).

4. Thuật giải nào được đề xuất trong luận án để kiểm tra tính hằng đúng nhằm giải bài toán thành viên?

Luận án đề xuất ba phương pháp hình thức:

  • Phương pháp kiểm tra trực tiếp trên dạng chuẩn hội (CNF).
  • Thuật giải phân tích hình thức Vương Hạo.
  • Phương pháp chứng minh phản chứng dựa trên nguyên lý hợp giải (Unification / Resolution).

5. Khái niệm phụ thuộc hàm xấp xỉ tổng quát được định nghĩa như thế nào?

Phụ thuộc hàm xấp xỉ tổng quát có dạng $X \xrightarrow{\varepsilon_1 \to \varepsilon_2} Y$, trong đó $\varepsilon_1, \varepsilon_2 \ge 0$ là các ngưỡng khoảng cách. Quan hệ $r$ thỏa mãn phụ thuộc này nếu với mọi cặp bộ $u, v \in r$, khi khoảng cách giữa hai bộ trên tập thuộc tính $X$ không vượt quá $\varepsilon_1$ ($d(u.X, v.X) \le \varepsilon_1$) thì khoảng cách giữa chúng trên tập thuộc tính $Y$ cũng không vượt quá $\varepsilon_2$ ($d(u.Y, v.Y) \le \varepsilon_2$).

Kết luận

Luận án của tác giả Nguyễn Thị Vân đã giải quyết trọn vẹn bài toán mở rộng lý thuyết phụ thuộc dữ liệu trong cơ sở dữ liệu quan hệ thông qua việc thiết lập mô hình phụ thuộc Boole dương xấp xỉ tổng quát. Bằng việc kết hợp công thức Boole dương, phép sánh trị tổng quát $\alpha$, hàm định lượng $\lambda$ và hệ thống độ đo không gian, công trình đã chứng minh tính bao hàm của mô hình mới đối với các lớp phụ thuộc nới lỏng đã biết. Đồng thời, luận án cung cấp hệ thống giải thuật hoàn chỉnh cho các bài toán suy dẫn hình thức, tìm bao đóng và tìm khóa tối tiểu, đóng góp cơ sở khoa học và thực tiễn giá trị cho lĩnh vực thiết kế và quản trị dữ liệu.