Bối cảnh và vấn đề nghiên cứu
Trong mô hình cơ sở dữ liệu quan hệ, việc quản trị và đảm bảo tính nhất quán của dữ liệu đóng vai trò thiết yếu. Quá trình khám phá tri thức và khai phá dữ liệu thường tập trung vào các mẫu phổ biến như phân lớp dữ liệu hay khai phá luật kết hợp; ngược lại, việc phát hiện các phần tử ngoại lai (outliers)—những dữ liệu khác biệt đáng kể so với phần còn lại hoặc vi phạm các ràng buộc toàn vẹn—đang dần trở thành một hướng nghiên cứu quan trọng để phục vụ công tác làm sạch dữ liệu, kiểm toán và phát hiện gian lận.
Đồ án tốt nghiệp đại học ngành Công nghệ Thông tin của sinh viên Lưu Thế Dũng, dưới sự hướng dẫn của TS. Lê Văn Phùng, tập trung vào việc nghiên cứu cơ sở lý thuyết về phụ thuộc hàm và phần tử ngoại lai, từ đó xây dựng giải pháp tự động kiểm tra tính chính xác của dữ liệu kết quả học tập tại trường phổ thông.
Nhiệm vụ nghiên cứu được xác định cụ thể qua 3 nội dung:
- 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ệ.
- 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ệ.
- Ứ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 trung học phổ thông (THPT) ở Hải Phòng.
Đối tượng và phạm vi nghiên cứu:
- Đối tượng nghiên cứu: Lý thuyết phụ thuộc hàm (bao gồm phụ thuộc hàm tổng quát, phụ thuộc hàm dạng bằng nhau, phụ thuộc hàm dạng tỉ lệ), các định lý và thuật toán xác định phần tử ngoại lai trong cơ sở dữ liệu quan hệ; các quy định xếp loại học lực và danh hiệu học sinh theo tiêu chuẩn của Bộ Giáo dục và Đào tạo.
- Phạm vi không gian và dữ liệu: Bảng điểm và kết quả xếp loại học lực, hạnh kiểm, danh hiệu của học sinh một lớp học thuộc trườ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 tháng 12/2021.
Cơ sở lý thuyết và phương pháp
Đồ án dựa trên nền tảng lý thuyết cơ sở dữ liệu quan hệ và các kỹ thuật toán học rời rạc để mô hình hóa ràng buộc dữ liệu:
1. Khung lý thuyết và mô hình toán học
- Phụ thuộc hàm (Functional Dependency): Do Edgar F. Codd đề xuất. Với lược đồ quan hệ $R = {A_1, A_2, \dots, A_n}$ và quan hệ $r$ trên $R$, phụ thuộc hàm $X \to Y$ ($X, Y \subseteq R$) xác định rằng với mọi cặp bộ $h_i, h_j \in r$, nếu $h_i(X) = h_j(X)$ thì $h_i(Y) = h_j(Y)$.
- Hệ tiên đề Armstrong (Armstrong, 1974): Gồm 3 luật suy diễn cơ bản:
- Luật phản xạ ($A_1$): Nếu $Y \subseteq X$ thì $X \to Y$.
- Luật tăng trưởng ($A_2$): Nếu $X \to Y$ và $Z \subseteq R$ thì $XZ \to YZ$.
- Luật bắc cầu ($A_3$): Nếu $X \to Y$ và $Y \to Z$ thì $X \to Z$.
Hệ tiên đề này phục vụ việc tính bao đóng $F^+$ từ tập phụ thuộc hàm $F$.
- Khái niệm phần tử ngoại lai: Dựa trên quan điểm thống kê của Barnett và Lewis kết hợp với mô hình dữ liệu quan hệ. Một phần tử ngoại lai là phần tử trong quan hệ $r$ không tuân thủ tập các quy tắc, ràng buộc $T$ của cơ sở dữ liệu.
- Phụ thuộc hàm dạng bằng nhau: Xét $r$ trên $R$, nếu với hai thuộc tính $A_p, A_q \in R$ mà với mọi $t_i \in r$ đều có $t_i(A_p) = t_i(A_q)$, ta có phụ thuộc hàm dạng bằng nhau $A_p \to A_q$ (đồng thời $A_q \to A_p$). Phần tử $t_k \in r$ là ngoại lai khi $t_k(A_p) \neq t_k(A_q)$.
- Phụ thuộc hàm dạng tỉ lệ: Với các thuộc tính số $A_s, A_{s1}, \dots, A_{sk} \in R$ và các hệ số $p_1, \dots, p_k$ thỏa mãn $\sum_{j=1}^k p_j = 1$, phụ thuộc hàm tỉ lệ xác định $t_i(A_{sj}) = p_j \cdot t_i(A_s)$. Phần tử $t_i$ bị coi là ngoại lai với sai số $\varepsilon$ khi:
$$\left| \frac{t_i(A_{sj})}{t_i(A_s)} - p_j \right| > \varepsilon$$
- Hệ bằng nhau (Equality System - $E_r$): Tập hợp $E_r = {E_{i,j} \mid 1 \le i < j \le m \text{ và } E_{i,j} = {a \in R \mid t_i(a) = t_j(a)}}$.
- Định lý nhận biết cặp ngoại lai: Cặp $(t_i, t_j)$ trong quan hệ $r$ 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}$.
2. Phương pháp nghiên cứu
- 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ý, thuật toán phát hiện ngoại lai tổng quát và các biến thể đặc biệt.
- Phương pháp thực nghiệm - phát triển ứng dụng: Xây dựng phần mềm xử lý dữ liệu thực tế bằng cách nhập tệp bảng điểm, tính toán các trường quy chuẩn theo quy chế Bộ Giáo dục và Đào tạo, thực hiện phép nối dữ liệu và áp dụng thuật toán kiểm tra so khớp vế trái - vế phải của phụ thuộc hàm dạng bằng nhau.
Thiết kế và triển khai
Hệ thống được thiết kế nhằm tự động hóa việc đối soát giữa số liệu do giáo viên chủ nhiệm nộp và số liệu tính toán chuẩn xác từ bảng điểm thành phần.
1. Kiến trúc và công nghệ sử dụng
- Hệ quản trị cơ sở dữ liệu: MySQL.
- Ngôn ngữ lập trình: PHP.
- Tệp dữ liệu đầu vào: File định dạng Microsoft Excel chứa bảng điểm chi tiết các môn học, điểm trung bình, xếp loại học lực báo cáo và danh hiệu báo cáo.
2. Quy trình xử lý dữ liệu
Quy trình thực hiện gồm 4 bước chính:
- Bước 1 (Nhập liệu): Nhập tệp dữ liệu ban đầu (Tệp Input 1) từ Excel do giáo viên chủ nhiệm gửi, tiến hành loại bỏ các cột thông tin không cần thiết để tối ưu hóa việc xử lý.
- Bước 2 (Tính toán quy chuẩn): Hệ thống tự động tính lại điểm trung bình, xếp loại học lực tính toán (Học lực TT) và danh hiệu thi đua tính toán (Danh hiệu TT) theo đúng tiêu chuẩn quy chế.
- Bước 3 (Tạo tệp trung gian): Sử dụng phép toán xử lý tệp nối (Join) kết hợp giữa tệp dữ liệu báo cáo và tệp tính toán để sinh ra Tệp trung gian (Tệp 3).
- Bước 4 (Phát hiện ngoại lai): Áp dụng thuật toán phụ thuộc hàm dạng bằng nhau để rà soát theo từng dòng trên Tệp 3:
- Kiểm tra điều kiện: $\text{Học lực_TT}_i = \text{Học lực_BC}_i$ (tương ứng phụ thuộc hàm $p \to q$).
- Kiểm tra điều kiện: $\text{Danh hiệu_TT}_i = \text{Danh hiệu_BC}_i$.
- Nếu xuất hiện sự sai khác, hàng đó được gắn cờ ngoại lai (lỗi) và tăng biến đếm lỗi.
3. Giao diện chức năng
Phần mềm triển khai hệ thống giao diện trực quan trên nền tảng web:
- Giao diện trang chủ: Điều hướng hệ thống.
- Giao diện nhập tệp Excel: Tải dữ liệu bảng điểm vào cơ sở dữ liệu.
- Giao diện xem dữ liệu báo cáo: Hiển thị dữ liệu gốc do giáo viên lập.
- Giao diện tính toán trung gian (Tệp 3): Thể hiện song song cột dữ liệu báo cáo và cột tính toán lại.
- Giao diện phát hiện phần tử ngoại lai: Xuất bảng kết quả đánh dấu đỏ các trường hợp sai lệch hoặc thông báo không tìm thấy phần tử ngoại lai.
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 cơ sở lý thuyết toán học và phân tích tổng quan ứng dụng của khai phá ngoại lai:
- Định nghĩa phụ thuộc hàm $A \to B$ và ý nghĩa trong thiết kế cơ sở dữ liệu (tìm khóa, chuẩn hóa, phân rã không mất thông tin).
- Trình bày hệ tiên đề Armstrong và định nghĩa bao đóng $F^+$.
- Giới thiệu hai dạng phụ thuộc hàm đặc biệt: phụ thuộc hàm dạng bằng nhau ($A_p \to A_q$) và phụ thuộc hàm dạng tỉ lệ ($A_s \to A_{s1}, \dots, A_{sk}$).
- Định nghĩa phần tử ngoại lai theo quan điểm thống kê và trong mô hình dữ liệu quan hệ (vi phạm tập luật $T$).
- Phân tích mối quan hệ giữa khai phá ngoại lai và khai phá dữ liệu lớn nằm ở bộ nhớ ngoài (Disk-resident Data).
- Tổng hợp các lĩnh vực ứng dụng của phát hiện ngoại lai: phát hiện xâm nhập an ninh mạng, phát hiện gian lận ngân hàng/thẻ tín dụng, phát hiện gian lận bảo hiểm xe hơi, phát hiện bất thường y tế công cộng, phát hiện lỗi hỏng hóc cơ khí (động cơ, tua-bin, nứt dầm), phân tích bất thường trong xử lý ảnh/video, mạng cảm biến, thị trường chứng khoán (dự đoán biến động cổ phiếu bất thường) và thể thao chuyên nghiệp (tối ưu hóa tuyển dụng cầu thủ theo chỉ số hiệu suất).
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 tập trung vào việc mô tả các định lý toán học và cấu trúc thuật toán phát hiện ngoại lai:
- Đưa ra định nghĩa cặp phần tử ngoại lai $(t_1, t_2)$ đối với phụ thuộc hàm $X \to Y$: $t_1(X) = t_2(X)$ nhưng $t_1(Y) \neq t_2(Y)$.
- Xây dựng khái niệm Hệ bằng nhau $E_r$ và chứng minh Định lý nhận biết cặp ngoại lai thông qua việc kiểm tra $X \subseteq E_{i,j}$ và $Y \not\subseteq E_{i,j}$.
- Trình bày thuật toán tổng quát tìm tập các cặp ngoại lai
OUTLI trên tập phụ thuộc hàm $F$.
- Xây dựng thuật toán chuyên biệt cho hai dạng phụ thuộc hàm đặc biệt:
- Đối với phụ thuộc hàm dạng bằng nhau: Thuật toán quét từng bộ $t_i \in r$, nếu $t_i(A_p) \neq t_i(A_q)$ thì đưa $t_i$ vào tập ngoại lai
OTL. Tác giả đưa ra ví dụ thực tế trên bảng kê 10 hợp đồng nhập khẩu hàng hóa:
| NGAY |
SO HD |
MA HANG |
THANH TIEN |
TIEN THUE |
TL_THUE (Kê khai) |
TL_THUE_QĐ (Quy định) |
Đánh giá ngoại lai |
| 16/4/2015 |
HD80000 |
M1001 |
305,415 |
106,895 |
35% |
35% |
Bình thường |
| 17/4/2015 |
HD80100 |
M1011 |
11,360 |
5,680 |
50% |
50% |
Bình thường |
| 17/4/2015 |
HD80100 |
M1020 |
76,000 |
15,200 |
20% |
35% |
Ngoại lai (kê khai thấp) |
| 17/4/2015 |
HD80100 |
M1014 |
683,090 |
341,545 |
50% |
50% |
Bình thường |
| 17/4/2015 |
HD80100 |
M1001 |
162,888 |
57,011 |
35% |
35% |
Bình thường |
| 28/4/2015 |
HD80500 |
M1002 |
17,600 |
1,760 |
10% |
25% |
Ngoại lai (kê khai thấp) |
| 28/4/2015 |
HD80500 |
M1005 |
90,000 |
18,000 |
20% |
40% |
Ngoại lai (kê khai thấp) |
| 28/4/2015 |
HD80700 |
M1006 |
271,200 |
40,680 |
15% |
100% |
Ngoại lai (kê khai thấp) |
| 28/4/2015 |
HD80800 |
M1007 |
50,000 |
20,000 |
40% |
55% |
Ngoại lai (kê khai thấp) |
| 29/4/2015 |
HD80900 |
M1001 |
203,610 |
71,264 |
35% |
35% |
Bình thường |
- Đối với phụ thuộc hàm dạng tỉ lệ: Thuật toán kiểm tra sai lệch tỷ lệ so với định mức với ngưỡng sai số $\varepsilon$. Minh họa thực tế với quan hệ gồm các thuộc tính ${A_s, A_1, A_2, A_3, A_4}$, khi chọn sai số $\varepsilon = 0.01$, thuật toán đã phát hiện chính xác các hàng số 3 và hàng số 5 là các phần tử ngoại lai do tỷ lệ thực tế sai khác vượt mức 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 trình bày bài toán nghiệp vụ, thuật toán cài đặt và kết quả kiểm thử phần mềm:
- Tiêu chuẩn xếp loại học lực:
- Loại Giỏi: Điểm trung bình các môn ($\text{ĐTB}) \ge 8.0$; ít nhất 1 trong 2 môn Toán hoặc Ngữ văn $\ge 8.0$; không có môn nào dưới $6.5$; các môn nhận xét đạt loại Đ.
- Loại Khá: $\text{ĐTB} \ge 6.5$; Toán hoặc Ngữ văn $\ge 6.5$; không có môn nào dưới $5.0$; các môn nhận xét đạt loại Đ.
- Loại Trung bình: $\text{ĐTB} \ge 5.0$; Toán hoặc Ngữ văn $\ge 5.0$; không có môn nào dưới $3.5$; các môn nhận xét đạt loại Đ.
- Loại Yếu: $\text{ĐTB} \ge 3.5$; không có môn nào dưới $2.0$.
- Loại Kém: Các trường hợp còn lại.
- Quy tắc điều chỉnh (chiếu cố): Nếu đạt tiêu chuẩn ĐTB loại Giỏi nhưng do 1 môn bị tụt xuống Trung bình thì được nâng lên Khá; nếu do 1 môn tụt xuống Yếu thì điều chỉnh lên Trung bình. Nếu đạt tiêu chuẩn ĐTB loại Khá nhưng do 1 môn tụt xuống Yếu thì nâng lên Trung bình; nếu do 1 môn tụt xuống Kém thì nâng lên Yếu.
- Tiêu chuẩn danh hiệu:
- Học sinh giỏi (HSG): Học lực Giỏi + Hạnh kiểm Tốt.
- Học sinh tiên tiến (HSTT): Học lực Khá trở lên + Hạnh kiểm Khá trở lên.
- Thuật toán xử lý trong ứng dụng: Trình bày mã giả chi tiết thuật toán kiểm tra xếp loại học lực và thuật toán kiểm tra danh hiệu bằng việc duyệt tuần tự $N$ bản ghi và so sánh giá trị tính toán lại với giá trị báo cáo của giáo viên.
Kết quả và đóng góp
1. Kết quả chính
- Đồ án đã hệ thống hóa lý thuyết về phụ thuộc hàm và các định lý xác định phần tử ngoại lai trong mô hình dữ liệu quan hệ, làm rõ cấu trúc toán học của hệ bằng nhau $E_r$.
- Xây dựng thành công thuật toán và ứng dụng phần mềm trên nền tảng PHP/MySQL để đối soát kết quả xếp loại học tập.
- Phần mềm đã thực hiện thử nghiệm trên bảng dữ liệu điểm thực tế của trường THPT Kiến Thụy, thực hiện thành công hai trường hợp kiểm thử:
- Trường hợp không phát hiện phần tử ngoại lai (dữ liệu báo cáo khớp 100% với tính toán quy chuẩn).
- Trường hợp phát hiện phần tử ngoại lai (tự động phát hiện, đếm số lỗi và đánh dấu trực quan các bản ghi có sự sai lệch giữa báo cáo và tính toán thực tế).
2. Đóng góp của đề tài
- Đưa các khái niệm lý thuyết trừu tượng về phụ thuộc hàm đặc biệt (dạng bằng nhau, dạng tỉ lệ) vào giải quyết một bài toán thực tiễn cụ thể trong quản lý giáo dục phổ thông.
- Cung cấp công cụ hỗ trợ ban giám hiệu các trường THPT rà soát sai sót chủ quan hoặc khách quan của giáo viên chủ nhiệm trước khi kết xuất dữ liệu nộp lên Sở Giáo dục và Đào tạo.
Hạn chế và hướng nghiên cứu tiếp
Theo đánh giá của cán bộ phản biện (TS. Lương Thanh Nhạn) và tự đánh giá của đề tài, công trình còn tồn tại một số điểm hạn chế:
- Về tính năng thuật toán: Phần mềm chưa hỗ trợ quy chế tính điểm và xếp loại cho đối tượng học sinh các lớp chuyên (chưa tích hợp điều kiện điểm môn chuyên $\ge 8.0$ hoặc $\ge 6.5$).
- Về xử lý ngoại lệ: Chương trình chưa giải quyết triệt để trường hợp học sinh có đồng thời 2 lỗi tính toán sai (chưa hiển thị đầy đủ chú thích chi tiết nguyên nhân lỗi).
- Về quy mô thực nghiệm: Dữ liệu thử nghiệm mới chỉ dừng lại ở phạm vi một lớp học tại một trường THPT, chưa tiến hành đánh giá thực nghiệm định lượng trên các tập dữ liệu lớn hoặc so sánh hiệu năng thuật toán.
- Về định dạng và học thuật: Đồ án còn một số lỗi chính tả, câu văn chưa rõ nghĩa và định dạng văn bản chưa hoàn toàn đồng nhất; đề mục 1.4 cần điều chỉnh tên gọi cho phản ánh đúng nội dung tổng quan.
Hướng nghiên cứu tiếp:
- Mở rộng thuật toán cho hệ thống trường THPT chuyên và các mô hình đào tạo theo tín chỉ.
- Tối ưu hóa xử lý lỗi đồng thời và hoàn thiện tính năng chú thích nguyên nhân phát sinh phần tử ngoại lai.
- Mở rộng kiểm nghiệm trên các bộ dữ liệu quy mô toàn trường hoặc toàn sở.
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, Hệ thống Thông tin: Tham khảo cách vận dụng lý thuyết phụ thuộc hàm, hệ tiên đề Armstrong và cấu trúc hệ bằng nhau $E_r$ vào bài toán khai phá dữ liệu và làm sạch dữ liệu quan hệ.
- Người phát triển ứng dụng quản lý giáo dục: Tham khảo logic mã giả cài đặt các điều kiện xếp loại học lực, danh hiệu và quy tắc chiếu cố điểm theo quy định của Bộ Giáo dục và Đào tạo.
- Cán bộ quản lý dữ liệu trường học: Cung cấp phương pháp luận để xây dựng các mô-đun kiểm tra tính toàn vẹn và đối soát tự động báo cáo học kỳ/năm học.
Câu hỏi thường gặp
1. Phụ thuộc hàm dạng bằng nhau là gì và làm thế nào để phát hiện phần tử ngoại lai của nó?
Phụ thuộc hàm dạng bằng nhau xuất hiện trên quan hệ $r$ khi hai thuộc tính $A_p, A_q$ luôn có giá trị bằng nhau trên mọi bộ ($t_i(A_p) = t_i(A_q)$). Phần tử $t_k$ được xác định là ngoại lai khi xảy ra sự sai khác giữa hai thuộc tính này ($t_k(A_p) \neq t_k(A_q)$). Thuật toán chỉ cần duyệt từng bộ và so sánh trực tiếp giá trị của vế trái và vế phải.
2. Tiêu chuẩn xếp loại học lực Giỏi theo quy chế được cài đặt trong đồ án gồm những điều kiện nào?
Học sinh được xếp loại Giỏi khi đáp ứng đủ 3 tiêu chuẩn: (1) Điểm trung bình các môn từ 8,0 trở lên, trong đó điểm trung bình môn Toán hoặc môn Ngữ văn đạt từ 8,0 trở lên; (2) Không có môn học nào có điểm trung bình dưới 6,5; (3) Các môn học đánh giá bằng nhận xét đều đạt loại Đạt (Đ).
3. Phần mềm sử dụng công nghệ và quy trình xử lý dữ liệu nào?
Phần mềm được xây dựng bằng ngôn ngữ lập trình PHP kết hợp hệ quản trị cơ sở dữ liệu MySQL. Quy trình gồm việc nhận tệp bảng điểm Excel từ giáo viên chủ nhiệm, xử lý lọc cột, tính toán các trường quy chuẩn, sử dụng phép nối (Join) để tạo tệp trung gian và chạy thuật toán so khớp giá trị để tìm phần tử ngoại lai.
4. Dữ liệu thực nghiệm của đồ án được lấy từ đâu?
Dữ liệu thực nghiệm là bảng điểm và kết quả xếp loại học lực, hạnh kiểm, danh hiệu của một lớp học tại trường THPT Kiến Thụy, thành phố Hải Phòng.
5. Điểm hạn chế chính của phần mềm được hội đồng chấm phản biện chỉ ra là gì?
Phần mềm chưa áp dụng được cho học sinh các lớp chuyên, chưa hiển thị chú thích chi tiết khi một học sinh có 2 lỗi tính toán sai cùng lúc, và dữ liệu thử nghiệm thực tế còn hạn chế về mặt quy mô.
Kết luận
Đồ án tốt nghiệp của sinh viên Lưu Thế Dũng đã hoàn thành việc nghiên cứu lý thuyết phụ thuộc hàm và các giải pháp xác định phần tử ngoại lai trong cơ sở dữ liệu quan hệ. Tác giả đã cụ thể hóa mô hình phụ thuộc hàm dạng bằng nhau vào việc xây dựng phần mềm trên nền tảng PHP/MySQL nhằm kiểm tra tính chính xác của kết quả xếp loại học sinh THPT Kiến Thụy theo quy chế của Bộ Giáo dục và Đào tạo. Mặc dù quy mô thực nghiệm và phạm vi áp dụng cho các lớp chuyên còn hạn chế, công trình đã thể hiện được tính ứng dụng thực tiễn của các phương pháp khai phá dữ liệu trong quản lý giáo dục.
