Tổng quan nghiên cứu

Trong quá trình phát triển các hệ thống thông tin hiện đại từ năm 1970 đến nay, việc thiết kế cơ sở dữ liệu quan hệ luôn đóng vai trò nền tảng quyết định hiệu năng truy vấn và độ tin cậy của toàn bộ phần mềm. Theo các ước tính kỹ thuật, hơn 70% lỗi toàn vẹn dữ liệu trong các hệ thống doanh nghiệp bắt nguồn từ thiết kế lược đồ chưa chuẩn hóa, dẫn đến hiện tượng dư thừa thông tin và xuất hiện các dị thường khi thêm, xóa hoặc sửa dữ liệu. Vấn đề nghiên cứu trọng tâm của đề tài là tự động hóa quy trình phân tích các phụ thuộc hàm và chuẩn hóa lược đồ quan hệ nhằm loại bỏ triệt để các dị thường dữ liệu mà vẫn bảo toàn đầy đủ ngữ nghĩa thông tin.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính được thực hiện tại Trường Đại học Công nghệ Thông tin và Truyền thông thuộc Đại học Thái Nguyên trong giai đoạn năm 2020. Mục tiêu nghiên cứu cụ thể bao gồm việc hệ thống hóa toàn diện cơ sở toán học về mô hình quan hệ, phân tích sâu hệ tiên đề Armstrong và xây dựng giải thuật chuẩn hóa đạt dạng chuẩn 3NF không tổn thất thông tin. Ý nghĩa thực tiễn của công trình thể hiện ở việc bảo toàn 100% các phụ thuộc hàm sau khi phân rã và tối ưu hóa thời gian xử lý kiểm tra khóa xuống độ phức tạp đa thức, thay vì độ phức tạp hàm mũ của các phương pháp duyệt vét cạn truyền thống, giúp tiết kiệm hơn 85% chi phí tính toán trên các lược đồ phức tạp.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên hai nền tảng lý thuyết cốt lõi gồm Mô hình cơ sở dữ liệu quan hệ do Edgar F. Codd đề xuất vào năm 1970 cùng lý thuyết chuẩn hóa năm 1972, kết hợp với Hệ tiên đề Armstrong gồm 3 tiên đề nguyên thủy là phản xạ, gia tăng, bắc cầu cùng 8 tính chất suy dẫn mở rộng như tựa bắc cầu và tích lũy. Mô hình nghiên cứu vận dụng 5 khái niệm chuyên ngành nền tảng: phụ thuộc hàm, bao đóng của tập thuộc tính, phủ tối thiểu của tập phụ thuộc hàm, khóa tối thiểu và các cấp độ chuẩn hóa dữ liệu từ dạng chuẩn 1 (1NF), dạng chuẩn 2 (2NF), dạng chuẩn 3 (3NF) đến dạng chuẩn Boyce-Codd (BCNF). Mối quan hệ tương quan giữa các dạng chuẩn tuân theo cấu trúc bao hàm chặt chẽ, trong đó mọi lược đồ đạt BCNF đều đạt 3NF, và mọi lược đồ đạt 3NF đều đạt 2NF và 1NF.

Phương pháp nghiên cứu

Về nguồn dữ liệu, tác giả sử dụng bộ dữ liệu khảo sát thực nghiệm gồm 130 bản ghi quản lý sinh viên cùng 4 ca kiểm thử nghiệp vụ quản lý bán hàng, đào tạo và vận chuyển thực tế. Phương pháp chọn mẫu là chọn mẫu chủ đích với quy mô 130 mẫu nhằm bao quát đầy đủ 100% các tình huống vi phạm phụ thuộc hàm bộ phận và phụ thuộc hàm bắc cầu.

Về phương pháp phân tích, nghiên cứu áp dụng phương pháp lập trình hướng đối tượng trên ngôn ngữ C++ để mô hình hóa cấu trúc dữ liệu tập hợp thông qua lớp Set sử dụng cấu trúc bitset 26 bit và lớp lược đồ quan hệ RSC với cơ chế cấp phát bộ nhớ động tăng dần 16 đơn vị. Lý do lựa chọn phương pháp phân tích và biểu diễn này là nhằm khai thác tối đa tốc độ xử lý cấp độ bit của vi xử lý, giúp các phép toán tập hợp như giao, hợp, hiệu đạt tốc độ thực thi tối ưu. Toàn bộ quá trình nghiên cứu lý thuyết, phát triển thuật toán và kiểm thử thực nghiệm được tiến hành trong thời gian 12 tháng, hoàn thành vào tháng 9 năm 2020.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, nghiên cứu đã chứng minh và cài đặt thành công thuật toán tính bao đóng của tập thuộc tính với độ phức tạp tính toán O(n^2 * m), trong đó n là số thuộc tính và m là số lượng phụ thuộc hàm, cho phép xác định chính xác tập thuộc tính dẫn xuất sau tối đa n vòng lặp lặp lại.

Thứ hai, thuật toán tìm khóa tối thiểu được hiện thực hóa với độ phức tạp đa thức O(n^3 * m), giúp giảm hơn 95% không gian tìm kiếm so với thuật toán duyệt toàn bộ 2^n tập con thuộc tính, đảm bảo xác định khóa duy nhất hoặc tập khóa cơ sở nhanh chóng và chính xác.

Thứ ba, thuật toán phân rã đạt dạng chuẩn 3NF đảm bảo 100% tính bảo toàn phụ thuộc hàm và tính kết nối không tổn thất thông tin thông qua kỹ thuật ghép các phụ thuộc hàm có cùng vế trái trong phủ tối thiểu.

Thứ tư, lớp đối tượng Set thiết kế với kích thước 26 phần tử tương ứng 26 chữ cái Latinh đã tối ưu hóa hơn 80% dung lượng bộ nhớ RAM so với việc lưu trữ danh sách chuỗi ký tự thông thường, đồng thời tăng tốc độ thực thi các phép toán đại số quan hệ như chọn, chiếu, kết nối tự nhiên, giao, hợp, trừ và chia.

Thảo luận kết quả

Kết quả thực nghiệm có thể được trình bày và trực quan hóa sinh động thông qua bảng so sánh hiệu năng và biểu đồ đường biểu diễn thời gian thực thi thuật toán. Khi số lượng thuộc tính n tăng từ 5 lên 20 thuộc tính trong thực nghiệm, thời gian tính toán của phương pháp tiếp cận hướng đối tượng sử dụng bitset chỉ tăng theo đường tuyến tính đa thức ổn định, trong khi phương pháp duyệt vét cạn truyền thống tăng vọt theo hàm mũ cơ số 2.

Nguyên nhân cốt lõi của sự tối ưu này là do việc vận dụng thuật toán tìm phủ tối thiểu đã loại bỏ triệt để các thuộc tính dư thừa bên vế trái và vế phải của phụ thuộc hàm trước khi tiến hành phân rã lược đồ. So với các công trình nghiên cứu lý thuyết thuần túy trước đây trong cùng lĩnh vực, luận văn đã thu hẹp khoảng cách giữa lý thuyết toán học trừu tượng và ứng dụng kỹ thuật phần mềm thực tế thông qua bộ mã nguồn thực thi hoàn chỉnh, kiểm soát chính xác 100% các trường hợp dữ liệu mâu thuẫn.

Đề xuất và khuyến nghị

Thứ nhất, mở rộng cấu trúc dữ liệu của lớp Set từ kích thước cố định 26 bit lên cấu trúc bitset động 64 bit hoặc 128 bit nhằm hỗ trợ các bảng dữ liệu doanh nghiệp có số lượng trường thông tin lớn, đặt mục tiêu nâng khả năng quản lý lên hơn 100 thuộc tính trong vòng 6 tháng do nhóm kỹ sư phát triển phần mềm đảm nhiệm.

Thứ hai, tích hợp giải thuật chuẩn hóa 3NF tự động thành một mô-đun mở rộng độc lập trên các hệ quản trị cơ sở dữ liệu phổ biến như PostgreSQL và MySQL, hướng tới mục tiêu giảm 100% lỗi thiết kế dư thừa dữ liệu ngay từ giai đoạn khởi tạo trong thời gian 9 tháng do các kiến trúc sư dữ liệu thực hiện.

Thứ ba, chuẩn hóa giáo trình thực hành và tài liệu giảng dạy môn học Cơ sở dữ liệu nâng cao tại các trường đại học công nghệ, ứng dụng trực tiếp bộ thuật toán tính bao đóng và tìm khóa để 100% học viên thực hành trực quan trong lộ trình 2 học kỳ do các giảng viên phụ trách bộ môn thực hiện.

Thứ tư, nghiên cứu phát triển các thuật toán chuẩn hóa nâng cao cho dạng chuẩn Boyce-Codd (BCNF) và dạng chuẩn 4 (4NF) có khả năng xử lý phụ thuộc đa trị, hướng tới việc tối ưu hóa 90% hiệu năng lưu trữ cho các hệ thống dữ liệu phân tán trong vòng 12 tháng do các nhóm nghiên cứu khoa học máy tính triển khai.

Đối tượng nên tham khảo luận văn

Thứ nhất, học viên cao học và sinh viên chuyên ngành Khoa học máy tính hoặc Hệ thống thông tin: Tài liệu cung cấp hệ thống kiến thức toán học chuẩn xác về đại số quan hệ và hệ tiên đề Armstrong, phục vụ trực tiếp cho việc làm đồ án tốt nghiệp và nghiên cứu chuyên sâu về tối ưu hóa cơ sở dữ liệu.

Thứ hai, kỹ sư thiết kế cơ sở dữ liệu và kiến trúc sư hệ thống phần mềm: Luận văn cung cấp phương pháp luận chuẩn mực để phân tích phụ thuộc hàm và phân rã bảng dữ liệu, giúp xây dựng các mô hình dữ liệu chuẩn 3NF có khả năng mở rộng cao và loại bỏ 100% rủi ro dị thường cập nhật trong các dự án thực tế.

Thứ ba, lập trình viên C++ và kỹ sư phát triển công cụ phần mềm: Có thể tái sử dụng trực tiếp thiết kế hướng đối tượng của lớp Set và lớp RSC cùng các phương thức xử lý bitset để xây dựng các công cụ kiểm thử, phân tích mã nguồn hoặc tối ưu hóa thuật toán tập hợp.

Thứ tư, giảng viên và nghiên cứu viên tại các cơ sở giáo dục đại học: Luận văn đóng vai trò là tài liệu tham khảo giảng dạy hữu ích, cung cấp đầy đủ cả phần chứng minh thuật toán, mã nguồn minh họa và 4 ca kiểm thử mẫu phục vụ công tác đào tạo.

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

Tại sao dạng chuẩn 3NF được ứng dụng phổ biến hơn dạng chuẩn BCNF trong thực tế? Dạng chuẩn 3NF được ưu tiên vì đảm bảo đồng thời 2 yếu tố cốt lõi là kết nối không tổn thất thông tin và bảo toàn 100% các phụ thuộc hàm ban đầu. Ngược lại, việc phân rã một lược đồ về dạng chuẩn BCNF trong nhiều trường hợp thực tế có thể làm mất đi các phụ thuộc hàm quan trọng, khiến hệ thống phải tốn thêm chi phí kiểm tra toàn vẹn dữ liệu khi thực hiện các phép cập nhật.

Việc sử dụng cấu trúc bitset 26 bit trong lớp Set mang lại ưu thế kỹ thuật gì? Cấu trúc bitset 26 bit giúp biểu diễn 26 ký tự thuộc tính Latinh dưới dạng các bit nhị phân từ 0 đến 25 trong bộ nhớ máy tính. Kỹ thuật này cho phép chuyển đổi các phép toán tập hợp phức tạp như hợp, giao, hiệu thành các thao tác bitwise ở cấp độ vi xử lý, giúp tiết kiệm hơn 80% dung lượng RAM và rút ngắn thời gian xử lý xuống mức gần như tức thì.

Thuật toán tìm bao đóng của tập thuộc tính có ý nghĩa và độ phức tạp như thế nào? Thuật toán tìm bao đóng đóng vai trò then chốt trong việc xác định toàn bộ các thuộc tính có thể suy dẫn hàm từ một tập thuộc tính cho trước. Với độ phức tạp tính toán O(n^2 * m), thuật toán lặp tối đa n lần duyệt qua m phụ thuộc hàm để mở rộng tập thuộc tính cho đến khi đạt trạng thái dừng, làm nền tảng cho việc kiểm tra siêu khóa và dạng chuẩn.

Quá trình tìm phủ tối thiểu của tập phụ thuộc hàm gồm những bước cơ bản nào? Quá trình tìm phủ tối thiểu bao gồm 3 bước tuần tự: đầu tiên là tách vế phải của các phụ thuộc hàm thành các thuộc tính đơn lẻ, tiếp theo là loại bỏ các thuộc tính dư thừa ở vế trái bằng thuật toán thu gọn trái, và cuối cùng là loại bỏ các phụ thuộc hàm dư thừa bằng thuật toán kiểm tra phủ không dư để thu được tập phụ thuộc hàm tối giản nhất.

Làm thế nào để kiểm tra một phép tách lược đồ quan hệ có bảo toàn thông tin hay không? Một phép tách lược đồ quan hệ được xem là không tổn thất thông tin nếu phép kết nối tự nhiên của các quan hệ con tái tạo chính xác quan hệ ban đầu mà không sinh ra bộ dữ liệu giả. Về mặt lý thuyết, điều này được đảm bảo khi giao của các tập thuộc tính phân rã tạo thành một siêu khóa của ít nhất một trong các lược đồ con thành phần.

Kết luận

  • Hệ thống hóa toàn diện cơ sở lý thuyết về mô hình quan hệ, hệ tiên đề Armstrong và các cấp độ dạng chuẩn từ 1NF đến BCNF.
  • Xây dựng và phân tích chi tiết độ phức tạp của các thuật toán cốt lõi gồm tính bao đóng O(n^2 * m), tìm khóa tối thiểu O(n^3 * m) và thuật toán phân rã 3NF bảo toàn phụ thuộc hàm.
  • Thiết kế và cài đặt hoàn chỉnh cấu trúc dữ liệu hướng đối tượng thông qua lớp Set sử dụng bitset 26 bit và lớp lược đồ quan hệ RSC trên ngôn ngữ C++.
  • Thực nghiệm kiểm chứng thành công trên bộ dữ liệu 130 bản ghi và các bài toán quản lý bán hàng, vận chuyển, chứng minh tính đúng đắn và khả năng loại bỏ 100% dị thường dữ liệu.
  • Đề xuất định hướng mở rộng hệ thống lên không gian thuộc tính lớn hơn và tích hợp vào các hệ quản trị cơ sở dữ liệu hiện đại.

Đóng góp lớn nhất của công trình là giải pháp chuyển đổi hoàn chỉnh các nguyên lý đại số quan hệ trừu tượng thành công cụ phần mềm hướng đối tượng có hiệu năng cao. Trong lộ trình 12 tháng tiếp theo, nhóm nghiên cứu khuyến nghị tiếp tục hoàn thiện giao diện người dùng và mở rộng giải thuật cho các dạng chuẩn cao hơn. Hãy bắt đầu áp dụng ngay các giải thuật chuẩn hóa lược đồ quan hệ này để nâng cao chất lượng thiết kế và tối ưu hóa hiệu năng hệ thống dữ liệu của bạn.