Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc biệt trong cơ sở dữ liệu quan hệ

Bài viết khám phá cách xác định phần tử ngoại lai trong cơ sở dữ liệu quan hệ thông qua phụ thuộc hàm đặc biệt và ứng dụng thực tiễn.

• Tác giả: Lưu Thế Dũng
• Người hướng dẫn: TS. Lê Văn Phùng
• Trường học: Trường Đại Học Quản Lý Và Công Nghệ Hải Phòng
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phát Hiện Phần Tử Ngoại Lai Trong Cơ Sở Dữ Liệu Quan Hệ
• Loại tài liệu: Đồ Án Tốt Nghiệp
• Năm xuất bản: 2021
• Địa điểm: Hải Phòng

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH SÁCH HÌNH VẼ
• DANH SÁCH BẢNG
• MỞ ĐẦU
• 1. Chương 1: Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ
• 1.1. Phụ thuộc hàm
• 1.1.1. Định nghĩa phụ thuộc hàm
• 1.1.2. Hệ tiên đề Armstrong
• 1.2. Các dạng phụ thuộc hàm đặc biệt loại đơn giản
• 1.2.1. Dạng các phụ thuộc hàm dạng bằng nhau
• 1.2.2. Dạng phụ thuộc hàm dạng tỉ lệ
• 1.3. Phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu
• 1.3.1. Khái niệm về phần tử ngoại lai
• 1.3.1.1. Vai trò của phần tử ngoại lai trong mô hình CSDL quan hệ
• 1.3.2. Mối quan hệ giữa phần tử ngoại lai với khai phá dữ liệu
• 1.4. Mô hình phát hiện các phần tử ngoại lai trong dữ liệu và trong CSDL quan hệ
• 1.4.1. Phân loại các phần tử ngoại lai trong CSDL quan hệ
• 1.4.2. Ứng dụng của các phần tử ngoại lai
• 2. Chương 2: Phát hiện phần tử ngoại lai đối với phụ thuộc hàm trong CSDL quan hệ
• 2.1. Phần tử ngoại lai đối với phụ thuộc hàm
• 2.1.1. Khái niệm phần tử ngoại lai đối với phụ thuộc hàm
• 2.1.2. Định lý nhận biết cặp ngoại lai đối với phụ thuộc hàm
• 2.1.3. Thuật toán xác định các cặp ngoại lai đối với tập các phụ thuộc hàm
• 2.2. Phần tử ngoại lai đối với một số dạng phụ thuộc hàm đặc biệt
• 2.2.1. Phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau
• 2.2.2. Phần tử ngoại lai đối với phụ thuộc hàm dạng tỉ lệ
• 3. Chương 3: Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu cho học sinh trường THPT Kiến Thụy ở Hải Phòng
• 3.1. Bài toán đặt ra và mục tiêu chương trình
• 3.1.1. Bài toán đặt ra
• 3.1.2. Mục tiêu chương trình
• 3.2. Chọn thuật toán thử nghiệm
• 3.3. Dữ liệu vào và yêu cầu kết quả ra
• 3.4. Môi trường thử nghiệm và quy trình thực hiện
• 3.4.1. Hệ quản trị dữ liệu
• 3.4.2. Quy trình thực hiện
• 3.5. Một số giao diện chính
• 3.5.1. Giao diện trang chủ
• 3.5.2. Giao diện nhập liệu vào hệ thống
• 3.5.3. Giao diện xem dữ liệu báo cáo
• 3.5.4. Giao diện tính toán trung gian (tệp 3)
• 3.5.5. Giao diện phát hiện phần tử ngoại lai
• Đánh giá kết quả và hướng mở rộng
• Phụ lục 1 - Phép nối 2 file dữ liệu (Join)

Tóm tắt

I. Tổng quan về phát hiện phần tử ngoại lai trong cơ sở dữ liệu quan hệ

Phát hiện phần tử ngoại lai là một lĩnh vực quan trọng trong khai thác dữ liệu, đặc biệt trong cơ sở dữ liệu quan hệ. Nó giúp nhận diện các điểm dữ liệu không bình thường, có thể gây ảnh hưởng đến chất lượng và độ tin cậy của dữ liệu. Việc phát hiện này không chỉ giúp cải thiện chất lượng dữ liệu mà còn hỗ trợ trong việc ra quyết định chính xác hơn.

1.1. Khái niệm về phần tử ngoại lai trong cơ sở dữ liệu

Phần tử ngoại lai được định nghĩa là những điểm dữ liệu có đặc điểm khác biệt so với phần lớn dữ liệu còn lại. Chúng có thể gây ra những sai lệch trong phân tích và quyết định.

1.2. Tầm quan trọng của phát hiện phần tử ngoại lai

Việc phát hiện phần tử ngoại lai giúp nhận diện các vấn đề tiềm ẩn trong dữ liệu, từ đó cải thiện chất lượng và độ tin cậy của các quyết định dựa trên dữ liệu.

II. Vấn đề và thách thức trong phát hiện phần tử ngoại lai

Mặc dù phát hiện phần tử ngoại lai mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Các vấn đề như độ chính xác của thuật toán, sự đa dạng của dữ liệu và khả năng xử lý khối lượng lớn dữ liệu là những yếu tố cần được xem xét.

2.1. Độ chính xác của các thuật toán phát hiện

Độ chính xác của các thuật toán phát hiện phần tử ngoại lai phụ thuộc vào nhiều yếu tố, bao gồm chất lượng dữ liệu đầu vào và phương pháp được sử dụng.

2.2. Khối lượng dữ liệu lớn và tính toán

Xử lý khối lượng lớn dữ liệu trong thời gian thực là một thách thức lớn, đòi hỏi các giải pháp tối ưu hóa hiệu suất và khả năng mở rộng.

III. Phương pháp phát hiện phần tử ngoại lai hiệu quả

Có nhiều phương pháp khác nhau để phát hiện phần tử ngoại lai trong cơ sở dữ liệu quan hệ. Các phương pháp này bao gồm sử dụng các thuật toán học máy, thống kê và khai thác dữ liệu.

3.1. Thuật toán học máy trong phát hiện ngoại lai

Các thuật toán học máy như SVM, cây quyết định và mạng nơ-ron có thể được áp dụng để phát hiện phần tử ngoại lai một cách hiệu quả.

3.2. Phương pháp thống kê truyền thống

Các phương pháp thống kê như phân tích Z-score và IQR cũng được sử dụng để xác định các điểm dữ liệu bất thường.

IV. Ứng dụng thực tiễn của phát hiện phần tử ngoại lai

Phát hiện phần tử ngoại lai có nhiều ứng dụng thực tiễn trong các lĩnh vực như tài chính, y tế và an ninh mạng. Những ứng dụng này giúp cải thiện hiệu quả và độ tin cậy của các hệ thống.

4.1. Ứng dụng trong lĩnh vực tài chính

Trong lĩnh vực tài chính, phát hiện phần tử ngoại lai giúp nhận diện các giao dịch gian lận và bảo vệ tài sản của tổ chức.

4.2. Ứng dụng trong y tế

Trong y tế, phát hiện phần tử ngoại lai có thể giúp nhận diện các trường hợp bệnh lý bất thường, từ đó cải thiện chất lượng chăm sóc sức khỏe.

V. Kết luận và tương lai của phát hiện phần tử ngoại lai

Phát hiện phần tử ngoại lai là một lĩnh vực đang phát triển mạnh mẽ. Tương lai của nó hứa hẹn sẽ mang lại nhiều cải tiến trong việc xử lý và phân tích dữ liệu, đặc biệt là với sự phát triển của công nghệ học máy.

5.1. Xu hướng phát triển công nghệ

Công nghệ học máy và trí tuệ nhân tạo sẽ tiếp tục đóng vai trò quan trọng trong việc phát hiện phần tử ngoại lai, giúp nâng cao độ chính xác và hiệu quả.

5.2. Tầm quan trọng của dữ liệu chất lượng

Để phát hiện phần tử ngoại lai hiệu quả, việc đảm bảo chất lượng dữ liệu đầu vào là rất quan trọng, từ đó giúp cải thiện kết quả phân tích.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong lĩnh vực khoa học máy tính và hệ quản trị cơ sở dữ liệu, các kỹ thuật khai phá tri thức truyền thống thường tập trung vào việc tìm kiếm các mẫu phổ biến như phân lớp dữ liệu, nhận dạng mẫu và khai phá luật kết hợp. Ngược lại, lĩnh vực phát hiện phần tử ngoại lai (outliers) tập trung vào việc xác định các đối tượng dữ liệu có đặc tính khác biệt đáng kể so với phần lớn dữ liệu còn lại. Việc phát hiện các phần tử bất thường này có ý nghĩa quan trọng trong nhiều bài toán thực tế như phát hiện gian lận tài chính, bảo mật mạng, giám sát y tế, kiểm toán và làm sạch dữ liệu (Data cleaning).

Đề tài "Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc biệt trong cơ sở dữ liệu quan hệ và ứng dụng" do sinh viên Lưu Thế Dũng thực hiện dưới sự hướng dẫn của TS. Lê Văn Phùng (Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam) tại Trường Đại học Quản lý và Công nghệ Hải Phòng (năm 2021). Đồ án tập trung nghiên cứu cơ sở toán học của phụ thuộc hàm trong cơ sở dữ liệu quan hệ để phát hiện các bản ghi ngoại lai, đồng thời ứng dụng lý thuyết này vào việc kiểm tra tính chính xác của dữ liệu điểm số, học lực và danh hiệu học sinh phổ thông.

Đề tài xác định 3 nhiệm vụ nghiên cứu cụ thể được đánh số như sau:

1. Tìm hiểu về phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu quan hệ.
2. Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ thuộc hàm trong cơ sở dữ liệu quan hệ.
3. Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu cho học sinh trường THPT ở Hải Phòng.

• Đối tượng nghiên cứu: Phụ thuộc hàm, hệ tiên đề Armstrong, các dạng phụ thuộc hàm đặc biệt (phụ thuộc hàm dạng bằng nhau, phụ thuộc hàm dạng tỉ lệ) và các thuật toán phát hiện phần tử ngoại lai đối với các phụ thuộc hàm này.
• Phạm vi không gian: Dữ liệu bảng điểm học sinh thực tế tại Trường Trung học phổ thông (THPT) Kiến Thụy, thành phố Hải Phòng; địa điểm thực tập tốt nghiệp tại Công ty Cổ phần Thiết bị Điện, Điện tử - Bách Khoa.
• Phạm vi thời gian: Đề tài được giao ngày 18/10/2021 và hoàn thành nghiệm thu vào ngày 30/12/2021.

Cơ sở lý thuyết và phương pháp

Đồ án xây dựng nội dung dựa trên các nền tảng lý thuyết và văn bản quy phạm sau:

• Lý thuyết cơ sở dữ liệu quan hệ và phụ thuộc hàm: Sử dụng mô hình dữ liệu quan hệ của E. F. Codd và hệ tiên đề Armstrong (Armstrong, 1974) gồm ba quy tắc cơ bản: Phản xạ ($Y \subseteq X \Rightarrow X \to Y$), Tăng trưởng ($X \to Y \Rightarrow XZ \to YZ$) và Bắc cầu ($X \to Y \land Y \to Z \Rightarrow X \to Z$), cùng khái niệm bao đóng phụ thuộc hàm $F^+$.
• Lý thuyết phần tử ngoại lai: Dẫn xuất từ các định nghĩa thống kê của Barnett và Lewis, kết hợp định nghĩa hình thức về phần tử ngoại lai trong cơ sở dữ liệu quan hệ khi một bộ dữ liệu vi phạm tập ràng buộc/quy tắc $T$.
• Quy chế đánh giá, xếp loại học sinh: Áp dụng hệ thống quy định của Bộ Giáo dục và Đào tạo về tiêu chuẩn xếp loại học lực (Giỏi, Khá, Trung bình, Yếu, Kém), quy tắc khống chế môn học, quy tắc điều chỉnh hạ bậc học lực và tiêu chuẩn xét danh hiệu thi đua (Học sinh Giỏi, Học sinh Tiên tiến).

Phương pháp nghiên cứu thực tế được tác giả triển khai bao gồm:

• Phương pháp phân tích - tổng hợp lý thuyết: Hệ thống hóa các khái niệm, định lý toán học về phụ thuộc hàm và cấu trúc "Hệ bằng nhau" ($E_r$) để chứng minh định lý nhận biết cặp phần tử ngoại lai.
• Phương pháp thiết kế thuật toán: Xây dựng thuật toán tổng quát dựa trên hệ bằng nhau và các thuật toán đơn giản hóa cho hai dạng phụ thuộc hàm đặc biệt (phụ thuộc hàm dạng bằng nhau và phụ thuộc hàm dạng tỉ lệ).
• Phương pháp thực nghiệm phần mềm: Xây dựng ứng dụng web xử lý tệp dữ liệu bảng điểm Excel, tiến hành kết nối dữ liệu (phép Join) và tự động đối chiếu các trường tính toán so với trường báo cáo của giáo viên.
• Nguồn dữ liệu: Bảng điểm thực tế gồm điểm trung bình các môn học, xếp loại học lực, hạnh kiểm và danh hiệu của học sinh một lớp học thuộc Trường THPT Kiến Thụy.

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

Chương 1: Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ

Chương 1 thiết lập các khái niệm cơ sở về lý thuyết cơ sở dữ liệu và khai phá dữ liệu ngoại lai. Tác giả định nghĩa phụ thuộc hàm trên lược đồ quan hệ $R$ với quan hệ $r$: thuộc tính $B$ phụ thuộc hàm vào $A$ ($A \to B$) nếu mọi cặp dòng có giá trị trên $A$ bằng nhau thì giá trị trên $B$ cũng phải bằng nhau. Ví dụ minh họa được đưa ra qua bảng quan hệ THISINH với các phụ thuộc hàm ${T\text{ỉnh}} \to {Khuv\text{ực}}$ và ${SBD} \to {H\text{ọtên}, Đ\text{ịachỉ}, T\text{ỉnh}, Khuv\text{ực}}$.

Tác giả phân tích hai dạng phụ thuộc hàm đặc biệt loại đơn giản:

• Phụ thuộc hàm dạng bằng nhau: Tồn tại hai thuộc tính $A_p, A_q \in R$ sao cho với mọi bộ $t_i \in r$ đều có $t_i(A_p) = t_i(A_q)$, dẫn đến $A_p \to A_q$ và $A_q \to A_p$. Dạng này xuất hiện phổ biến khi kết nối hai hay nhiều bảng dữ liệu.
• Phụ thuộc hàm dạng tỉ lệ: Tồn tại thuộc tính số $A_s$ và các thuộc tính thành phần $A_{s1}, \dots, A_{sk}$ với các số thực $p_j \le 1$ và $\sum_{j=1}^k p_j = 1$ sao cho $t_i(A_{sj}) = p_j \times t_i(A_s)$. Dạng này thường gặp trong các bảng kê định mức sản phẩm.

Về phần tử ngoại lai, tác giả tổng kết khái niệm từ góc độ thống kê và cơ sở dữ liệu quan hệ, đồng thời phân tích vai trò của ngoại lai trong nhiều lĩnh vực:

Lĩnh vực ứng dụng	Đặc điểm phát hiện ngoại lai
Phát hiện xâm nhập mạng	Phát hiện gói tin bất thường, tần suất truy cập đột biến hoặc hành vi đăng nhập trái phép
Phát hiện gian lận thương mại/ngân hàng	Nhận diện tiêu dùng trái phép, trộm cắp danh tính, thẻ tín dụng giả
Giám sát y tế công cộng	Phát hiện hồ sơ bệnh án bất thường do lỗi thiết bị đo hoặc ghi âm
Chẩn đoán hư hỏng công nghiệp	Phân tích dữ liệu cảm biến để tìm vết nứt dầm, thủng khung vỏ máy bay, lỗi tu-bin
Xử lý hình ảnh	Nhận diện vùng ảnh bất thường trong ảnh vệ tinh, X-quang, camera giám sát
Thị trường chứng khoán	Phát hiện cổ phiếu biến động bất thường để phục vụ phân tích đầu tư
Làm sạch dữ liệu (Data cleaning)	Tự động loại bỏ hoặc điều chỉnh các bản ghi sai lệch cấu trúc và ngữ nghĩa

Chương 2: Phát hiện phần tử ngoại lai đối với phụ thuộc hàm trong CSDL quan hệ

Chương 2 trình bày các cơ sở toán học và thuật toán phát hiện phần tử ngoại lai. Giả sử $X \to Y$ là phụ thuộc hàm trên quan hệ $r$, một cặp bộ $t_1, t_2 \in r$ được gọi là cặp phần tử ngoại lai đối với $X \to Y$ nếu thỏa mãn điều kiện $t_1(X) = t_2(X)$ nhưng $t_1(Y) \neq t_2(Y)$.

Tác giả đưa ra định nghĩa về Hệ bằng nhau $E_r$: $$E_r = {E_{i,j}: 1 \le i < j \le m \text{ và } E_{i,j} = {a \in R; t_i(a) = t_j(a)}}$$

Từ cấu trúc này, đồ án phát biểu và chứng minh định lý nhận biết cặp ngoại lai: Cặp phần tử $(t_i, t_j)$ là ngoại lai đối với phụ thuộc hàm $X \to Y$ khi và chỉ khi tồn tại $E_{i,j} \in E_r$ sao cho $X \subseteq E_{i,j}$ nhưng $Y \not\subseteq E_{i,j}$. Thuật toán tổng quát tìm tập ngoại lai OUTLI được xây dựng bằng cách tính hệ $E_r$ và kiểm tra điều kiện bao hàm trên từng phụ thuộc hàm trong tập $F$.

Đối với các phụ thuộc hàm đặc biệt, tác giả tối ưu hóa thuật toán để xác định chính xác từng phần tử ngoại lai đơn lẻ thay vì chỉ tìm theo cặp:

1. Đối với phụ thuộc hàm dạng bằng nhau ($A_p \to A_q$): Thuật toán duyệt qua từng bộ $t_i \in r$, nếu $t_i(A_p) \neq t_i(A_q)$ thì kết luận $t_i$ là phần tử ngoại lai. Ví dụ minh họa trên bảng kê hợp đồng nhập khẩu hàng hóa cho thấy việc so sánh giữa thuế suất kê khai (TL_THUE) và thuế suất quy định (TL_THUE_QĐ) đã phát hiện các hóa đơn có mã hàng M1020, M1002, M1005, M1006, M1007 kê khai thuế suất thấp hơn quy định.
2. Đối với phụ thuộc hàm dạng tỉ lệ ($A_s \to A_{s1}\dots A_{sk}$): Với sai số cho phép $\epsilon$, một phần tử $t_i$ là ngoại lai nếu tồn tại $A_{sj}$ thỏa mãn: $$\left|\frac{t_i(A_{sj})}{t_i(A_s)} - p_j\right| > \epsilon$$ Ví dụ kiểm nghiệm trên bảng dữ liệu với $\epsilon = 0.01$ đã phát hiện các bộ dữ liệu tại hàng 3 và hàng 5 có sai lệch tỉ lệ vượt quá 1%.

Chương 3: Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu cho học sinh trường THPT Kiến Thụy ở Hải Phòng

Chương 3 chuyển hóa bài toán quản lý điểm học sinh THPT sang mô hình phát hiện phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau. Khi giáo viên chủ nhiệm nộp báo cáo kết quả học tập về Ban giám hiệu, các lỗi chủ quan hoặc tình trạng học sinh nghỉ học giữa chừng có thể dẫn đến sai lệch trong việc xếp loại học lực và công nhận danh hiệu.

Tác giả hệ thống hóa các tiêu chuẩn xếp loại của Bộ Giáo dục và Đào tạo:

• Loại Giỏi: Điểm trung bình các môn (ĐTB) $\ge 8.0$, trong đó ĐTB của 1 trong 2 môn Toán hoặc Ngữ văn $\ge 8.0$ (đối với lớp chuyên, ĐTB môn chuyên phải $\ge 8.0$); không có môn nào ĐTB $< 6.5$; các môn đánh giá nhận xét đạt loại Đ.
• Loại Khá: ĐTB $\ge 6.5$, ĐTB Toán hoặc Ngữ văn $\ge 6.5$ (lớp chuyên môn chuyên $\ge 6.5$); không có môn nào $< 5.0$; các môn nhận xét đạt Đ.
• Loại Trung bình: ĐTB $\ge 5.0$, ĐTB Toán hoặc Ngữ văn $\ge 5.0$ (lớp chuyên môn chuyên $\ge 5.0$); không có môn nào $< 3.5$; các môn nhận xét đạt Đ.
• Loại Yếu: ĐTB $\ge 3.5$, không có môn nào $< 2.0$.
• Loại Kém: Các trường hợp còn lại.
• Quy tắc điều chỉnh hạ bậc khống chế: Nếu đạt mức ĐTB loại Giỏi nhưng do 1 môn bị tụt xuống Trung bình thì điều chỉnh thành Khá; nếu bị tụt xuống Yếu thì điều chỉnh thành Trung bình. Nếu đạt mức ĐTB loại Khá nhưng do 1 môn bị tụt xuống Yếu thì điều chỉnh thành Trung bình; nếu bị tụt xuống Kém thì điều chỉnh thành Yếu.
• Tiêu chuẩn danh hiệu: Học sinh Giỏi (Hạnh kiểm Tốt, Học lực Giỏi); Học sinh Tiên tiến (Hạnh kiểm từ Khá trở lên, Học lực từ Khá trở lên).

Bài toán kiểm tra được tác giả thiết lập thành hai công đoạn so sánh phụ thuộc hàm dạng bằng nhau:

• So sánh thuộc tính Xếp loại học lực báo cáo ($p$) với Xếp loại học lực tính toán ($q$).
• So sánh thuộc tính Danh hiệu báo cáo với Danh hiệu tính toán.

Nếu giá trị trên cùng một dòng không trùng khớp ($p \neq q$), bản ghi đó được xác định là phần tử ngoại lai.

Thiết kế và triển khai

Phần mềm thử nghiệm được xây dựng nhằm tự động hóa quy trình kiểm tra dữ liệu điểm với các thành phần kỹ thuật sau:

• Môi trường công nghệ: Ngôn ngữ lập trình PHP, Hệ quản trị cơ sở dữ liệu MySQL, dữ liệu đầu vào sử dụng tệp bảng tính Microsoft Excel.
• Quy trình xử lý dữ liệu gồm 4 bước:
  • Bước 1: Nhập tệp Excel dữ liệu đầu vào (tệp Input1) từ giáo viên chủ nhiệm vào hệ thống, tiến hành loại bỏ các cột điểm chi tiết không cần thiết cho tính toán tổng hợp.
  • Bước 2: Nạp các quy tắc và bảng chuẩn theo quy định của Bộ Giáo dục và Đào tạo.
  • Bước 3: Tạo tệp dữ liệu trung gian (tệp 3) trong hệ thống bằng cách thực hiện phép kết nối (Join) giữa tệp dữ liệu học sinh và tệp quy tắc tính toán.
  • Bước 4: Áp dụng thuật toán phụ thuộc hàm dạng bằng nhau trên tệp 3 để so sánh từng cặp thuộc tính tương ứng và kết xuất các dòng dữ liệu không trùng khớp.
• Các giao diện chức năng chính: Hệ thống bao gồm giao diện trang chủ, giao diện tải lên tệp Excel, giao diện xem dữ liệu báo cáo ban đầu, giao diện bảng tính toán trung gian và giao diện thông báo kết quả phát hiện phần tử ngoại lai (hiển thị danh sách và số lượng lỗi được đánh dấu).

Kết quả và đóng góp

Đồ án đã đạt được các kết quả cụ thể sau:

• Kết quả lý thuyết: Đã hệ thống hóa cơ sở lý thuyết về phụ thuộc hàm, hệ tiên đề Armstrong và cấu trúc hệ bằng nhau $E_r$; hoàn thành chứng minh định lý nhận biết cặp ngoại lai đối với phụ thuộc hàm tổng quát; xây dựng thuật toán kiểm tra cho hai dạng phụ thuộc hàm đặc biệt (dạng bằng nhau và dạng tỉ lệ).
• Kết quả ứng dụng: Xây dựng hoàn chỉnh chương trình thử nghiệm bằng PHP/MySQL, thực hiện kiểm tra tự động bảng điểm lớp học tại Trường THPT Kiến Thụy. Phần mềm đã thực hiện đúng quy trình tính toán lại điểm trung bình, phân loại học lực theo điều kiện khống chế môn học và đối chiếu danh hiệu thi đua, từ đó chỉ ra chính xác các bản ghi có sự sai lệch giữa báo cáo của giáo viên và quy định chuẩn.

Thành phần nghiên cứu	Nội dung lý thuyết đã xây dựng	Kết quả triển khai thực nghiệm
Phụ thuộc hàm tổng quát	Định lý nhận biết cặp ngoại lai dựa trên hệ bằng nhau $E_r$	Thuật toán xác định tập cặp ngoại lai OUTLI
Phụ thuộc hàm dạng bằng nhau	Ràng buộc $t_i(A_p) = t_i(A_q)$; thuật toán kiểm tra từng bộ	Ứng dụng so sánh Học lực (BC vs TT) và Danh hiệu (BC vs TT)
Phụ thuộc hàm dạng tỉ lệ	Ràng buộc sai số $\left|\frac{t_i(A_{sj})}{t_i(A_s)} - p_j\right| \le \epsilon$	Kiểm nghiệm trên bảng số liệu mẫu với sai số cho phép $\epsilon = 0.01$
Ứng dụng thực tế	Mô hình hóa quy chế đánh giá học sinh của Bộ GD&ĐT	Phần mềm web PHP/MySQL kiểm tra bảng điểm THPT Kiến Thụy

• Đóng góp của tác giả: Đề tài đã liên kết lý thuyết cơ sở dữ liệu quan hệ trừu tượng (phụ thuộc hàm) với bài toán kiểm toán dữ liệu và làm sạch dữ liệu trong quản lý giáo dục, cung cấp phương pháp tự động phát hiện lỗi sai trong báo cáo học lực mà không cần kiểm tra thủ công từng trường hợp.

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

Theo đánh giá của cán bộ chấm phản biện (TS. Lương Thanh Nhạn) và nội dung văn bản, đồ án còn tồn tại một số hạn chế:

• Mục 1.4 mang tên "Mô hình phát hiện các phần tử ngoại lai trong dữ liệu và trong CSDL quan hệ" nhưng nội dung mới dừng ở mức trình bày định nghĩa, phân loại và ứng dụng chứ chưa xây dựng mô hình hoàn chỉnh.
• Chương trình thử nghiệm chưa cài đặt quy tắc tính điểm dành cho các lớp chuyên thuộc trường THPT chuyên (mặc dù đã nêu điều kiện môn chuyên $\ge 8.0$ hoặc $\ge 6.5$ trong phần lý thuyết).
• Phần mềm chưa xử lý triệt để trường hợp một học sinh đồng thời mắc 2 lỗi tính toán sai (chưa hiển thị chú thích chi tiết cho cả hai lỗi cùng lúc).
• Dữ liệu thực nghiệm của hệ thống còn hạn chế ở phạm vi một lớp học tại Trường THPT Kiến Thụy, chưa tiến hành đánh giá thực nghiệm trên quy mô lớn hoặc đo lường hiệu năng xử lý.
• Báo cáo còn một số lỗi chính tả, câu văn thiếu chủ ngữ và định dạng văn bản chưa đồng nhất.

Hướng phát triển tiếp theo của đề tài tập trung vào việc hoàn thiện mã nguồn để hỗ trợ đầy đủ quy chế trường chuyên, cải tiến giao diện hiển thị chi tiết các trường hợp đa lỗi và mở rộng thử nghiệm trên cơ sở dữ liệu toàn trường hoặc toàn ngành giáo dục.

Giá trị tham khảo

Đồ án là tài liệu tham khảo phù hợp cho:

• Sinh viên ngành Công nghệ thông tin và Hệ thống thông tin: Có thể tham khảo phương pháp vận dụng lý thuyết phụ thuộc hàm và đại số quan hệ vào các bài toán khai phá dữ liệu bất thường và làm sạch dữ liệu.
• Người nghiên cứu về kiểm thử và chất lượng dữ liệu: Tham khảo thuật toán nhận biết cặp ngoại lai qua hệ bằng nhau $E_r$ tại Chương 2 và thuật toán phụ thuộc hàm dạng bằng nhau/tỉ lệ.
• Cán bộ quản trị dữ liệu giáo dục phổ thông: Tham khảo cách mô hình hóa các quy chế tính điểm, khống chế môn học và xét danh hiệu thi đua của Bộ Giáo dục và Đào tạo thành các thuật toán logic tự động trong Chương 3.

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

1. Khái niệm cặp phần tử ngoại lai đối với phụ thuộc hàm trong CSDL quan hệ được định nghĩa như thế nào? Theo định nghĩa trong đồ án, cho quan hệ $r$ trên sơ đồ quan hệ $(R, F)$ và $X \to Y$ là một phụ thuộc hàm thuộc $F$. Cặp phần tử $t_1, t_2 \in r$ là cặp ngoại lai đối với phụ thuộc hàm $X \to Y$ khi và chỉ khi $t_1(X) = t_2(X)$ nhưng $t_1(Y) \neq t_2(Y)$.

2. Định lý nhận biết cặp ngoại lai thông qua Hệ bằng nhau $E_r$ được phát biểu ra sao? Hệ bằng nhau $E_r$ là tập hợp các $E_{i,j}$ chứa các thuộc tính mà tại đó hai bộ $t_i, t_j$ có giá trị bằng nhau. Cặp phần tử $(t_i, t_j)$ là ngoại lai đối với phụ thuộc hàm $X \to Y$ khi và chỉ khi tồn tại $E_{i,j} \in E_r$ sao cho $X \subseteq E_{i,j}$ nhưng $Y \not\subseteq E_{i,j}$.

3. Phụ thuộc hàm dạng bằng nhau được áp dụng như thế nào trong bài toán kiểm tra xếp loại học sinh? Trong bài toán quản lý điểm, hệ thống sinh ra hai cột thuộc tính tương ứng: một cột là kết quả do giáo viên chủ nhiệm nộp (báo cáo - BC) và một cột do hệ thống tự tính toán dựa trên điểm thành phần (tính toán - TT). Khi áp dụng phụ thuộc hàm dạng bằng nhau $p \to q$, hệ thống so sánh từng dòng; bất kỳ học sinh nào có giá trị $t_i(\text{BC}) \neq t_i(\text{TT})$ sẽ được xác định là một phần tử ngoại lai (dòng dữ liệu bị sai lệch).

4. Quy định điều chỉnh khống chế học lực của Bộ GD&ĐT được nêu trong đồ án gồm những trường hợp nào? Văn bản nêu rõ 4 trường hợp điều chỉnh: (a) ĐTB đạt loại Giỏi nhưng do 1 môn bị tụt xuống loại Trung bình thì điều chỉnh thành loại Khá; (b) ĐTB đạt loại Giỏi nhưng do 1 môn bị tụt xuống loại Yếu thì điều chỉnh thành loại Trung bình; (c) ĐTB đạt loại Khá nhưng do 1 môn bị tụt xuống loại Yếu thì điều chỉnh thành loại Trung bình; (d) ĐTB đạt loại Khá nhưng do 1 môn bị tụt xuống loại Kém thì điều chỉnh thành loại Yếu.

5. Giảng viên chấm phản biện đã chỉ ra những mặt hạn chế kỹ thuật nào của phần mềm trong đồ án? TS. Lương Thanh Nhạn chỉ ra rằng phần mềm chưa áp dụng được cho các lớp chuyên, chưa giải quyết triệt để tình huống hiển thị chú thích khi một học sinh có 2 tính toán sai cùng lúc, và dữ liệu thực tế của hệ thống còn hạn chế do chưa thực hiện đánh giá kết quả thực nghiệm diện rộng.

Kết luận

Đồ án tốt nghiệp của sinh viên Lưu Thế Dũng đã nghiên cứu có hệ thống lý thuyết về phụ thuộc hàm, hệ tiên đề Armstrong và cấu trúc hệ bằng nhau nhằm phục vụ bài toán xác định phần tử ngoại lai trong cơ sở dữ liệu quan hệ. Tác giả đã đề xuất các thuật toán phát hiện ngoại lai chuyên biệt cho hai dạng phụ thuộc hàm đặc biệt (dạng bằng nhau và dạng tỉ lệ), đồng thời áp dụng thành công vào việc xây dựng phần mềm PHP/MySQL kiểm tra kết quả xếp loại học lực và danh hiệu của học sinh Trường THPT Kiến Thụy. Mặc dù còn một số hạn chế về phạm vi dữ liệu thử nghiệm và xử lý trường hợp chuyên biệt, công trình đã thể hiện rõ khả năng ứng dụng lý thuyết toán rời rạc và cơ sở dữ liệu vào giải quyết bài toán làm sạch dữ liệu trong thực tiễn giáo dục.

Trích đoạn nội dung tài liệu

Chương 1 Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ 1. Phụ thuộc hàm 1.1 Định nghĩa phụ thuộc hàm Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn một cách hình thức các ràng buộc. Phương pháp biểu diễn này có rất nhiều ưu điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu (CSDL). Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa, tìm phủ tối thiểu và chuẩn hóa CSDL.

Khái niệm về phụ thuộc hàm trong một quan hệ là rất quan trọng trong việc thiết kế mô hình dữ liệu.F Codd đã mô tả phụ thuộc hàm trong mô hình dữ liệu quan hệ, nhằm giải quyết việc phân rã không mất thông tin. Định nghĩa: Cho R = {a1, a2,., an} là tập các thuộc tính, r = {h1, h2,., hm} là một quan hệ trên R, và A, B  R (A, B là tập cột hay tập thuộc tính). Khi đó ta nói A xác định hàm cho B hay B phụ thuộc hàm vào A trong r f (ký pháp A ⎯⎯ r → B) nếu: ( hi, hj  r) ((a  A) ( hi(a) = hj(a))  (b  B) ( hi(b) = hj(b) )) nghĩa là đối số trùng nhau thì hàm có cùng giá trị [2]. f Người ta còn viết (A, B) hay A → B thay cho ⎯⎯ r→ B 7 Lúc đó tập hợp tất cả (A, B) như thế xác định một họ f trên R.

Nhận xét: Ta có thể thấy rằng B mà phụ thuộc hàm vào A, nếu hai dòng bất kỳ mà các giá trị của tập thuộc tính A mà bằng nhau từng cặp một, thì kéo theo các giá trị trên tập thuộc tính B cũng phải bằng nhau từng cặp một. Ý nghĩa: Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ liệu) xẩy ra tự nhiên nhất giữa các tập thuộc tính. Ví dụ : Xét một quan hệ : THISINH SBD Họtên Điạchỉ Tỉnh Khu vực HP0001 Bùi văn An 14 Kiến Hải 3 An Phòng HP0002 Nguyễn Hải 15 Cát Hải Đăng Hải Phòng 3 HP0003 Nguyễn vân Văn Lạng Anh Lãng Sơn 1 HP0004 Vũ thúy Liên 52 Quang Nam Trung Định 2 Bảng 1 Bảng quan hệ THÍ SINH Trong quan hệ THISINH dựa vào định nghĩa phụ thuộc hàm của quan hệ , có thể kết luận: 8 f {Tỉnh} ⎯⎯ r → { Khuvực} f {SBD} ⎯⎯ r → { Họtên, Địachỉ, Tỉnh, Khuvực} 1.2 Hệ tiên đề Armstrong Gọi F là tập xác định các phụ thuộc hàm đối với lược đồ quan hệ R và X → Y là một phụ thuộc hàm. Nói rằng X → Y được suy diễn logic từ F nếu mối quan hệ r trên R đều thoả mãn phụ thuộc hàm của F thì cũng thoả mãn X → Y.

Chẳng hạn F ={A → B, B → C} thì A → C suy ra từ F. Gọi F+ là bao đóng (closure) của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Nếu F = F+ thì F là họ đầy đủ (full family) của các phụ thuộc hàm [3]. Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F.

Do đó đòi hỏi phải có các hệ tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, được gọi là hệ tiên đề Armstrong. Định nghĩa: Cho R = {a1,.,an} là tập các thuộc tính. Hệ tiên đề Armstrong bao gồm 3 tính chất cơ bản sau: ➢ A1 (phản xạ) : Nếu Y  X thì X → Y ➢ A2 (tăng trưởng) : Nếu Z  R và X → Y thì XZ → YZ.