Các thuật toán xử lý phụ thuộc hàm nới lỏng - Luận văn thạc sĩ CNTT Thái Nguyên

• Tác giả: Nguyễn Thị Linh
• Người hướng dẫn: PGS.TSKH. Nguyễn Xuân Huy
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Các thuật toán xử lý phụ thuộc hàm nới lỏng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về các thuật toán xử lý phụ thuộc hàm nới lỏng

Phụ thuộc hàm nới lỏng là một khái niệm mở rộng quan trọng trong lý thuyết cơ sở dữ liệu quan hệ. Khác với phụ thuộc hàm truyền thống, phụ thuộc hàm nới lỏng cho phép xác định mối quan hệ giữa các thuộc tính một cách linh hoạt hơn. Trong thiết kế cơ sở dữ liệu, việc xử lý phụ thuộc hàm đóng vai trò quyết định đến chất lượng lược đồ quan hệ. Các phép toán cơ bản bao gồm tính bao đóng của tập thuộc tính, tìm phủ không dư và phủ tối thiểu. Luận văn thạc sĩ của Nguyễn Thị Linh tại Đại học Thái Nguyên năm 2020 đã nghiên cứu chuyên sâu các thuật toán này. Công trình cung cấp cơ sở lý thuyết vững chắc về quan hệ, thuộc tính và các phép toán quan hệ. Phương pháp suy dẫn theo tiên đề được áp dụng để kiểm tra tính hợp lệ của các phụ thuộc hàm. Kết quả nghiên cứu hỗ trợ quá trình phân tích và chuẩn hóa lược đồ quan hệ hiệu quả hơn.

1.1. Định nghĩa phụ thuộc hàm và tính chất cơ bản

Phụ thuộc hàm X → Y thể hiện mối quan hệ ràng buộc giữa hai tập thuộc tính X và Y trong lược đồ quan hệ. Khi giá trị của X được xác định, giá trị của Y cũng được xác định duy nhất. Các tính chất quan trọng bao gồm tính phản xạ, tính bắc cầu và tính bổ sung. Phép suy dẫn logic sử dụng ba tiên đề Armstrong để suy ra các phụ thuộc hàm mới từ tập phụ thuộc hàm ban đầu. Bao đóng của tập thuộc tính X, ký hiệu X⁺, là tập tất cả thuộc tính suy ra được từ X.

1.2. Vai trò trong thiết kế cơ sở dữ liệu quan hệ

Phụ thuộc hàm nới lỏng giúp đánh giá mức độ phụ thuộc giữa các thuộc tính trong lược đồ quan hệ. Thông qua phân tích phụ thuộc hàm, nhà thiết kế có thể phát hiện các bất thường trong cơ sở dữ liệu. Phép tách không tổn thất dựa trên phụ thuộc hàm đảm bảo dữ liệu không bị mất mát khi phân tách bảng. Thuật toán kiểm tra tính tổn thất sử dụng kỹ thuật bảng để xác minh tính toàn vẹn. Việc chuẩn hóa lược đồ quan hệ nhờ đó đạt được dạng chuẩn cao hơn, giảm thiểu dư thừa dữ liệu.

II. Phân tích các vấn đề trong xử lý phụ thuộc hàm nới lỏng

Xử lý phụ thuộc hàm nới lỏng đặt ra nhiều thách thức về mặt thuật toán và độ phức tạp tính toán. Bài toán tìm bao đóng của tập thuộc tính đòi hỏi khả năng duyệt qua toàn bộ tập phụ thuộc hàm nhiều lần. Thuật toán phủ không dư phải loại bỏ các phụ thuộc hàm dư thừa mà không làm mất thông tin. Bài toán phủ tối thiểu yêu cầu tìm tập phụ thuộc hàm nhỏ nhất nhưng tương đương. Kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng cần xây dựng ma trận quan hệ mẫu. Mỗi bước trong quy trình đều có thể trở thành nút thắt cổ chai khi kích thước lược đồ lớn. Độ phức tạp thời gian của các thuật toán này thường là hàm bậc hai hoặc bậc ba theo số thuộc tính. Việc triển khai chương trình thử nghiệm cần xử lý chính xác các trường hợp biên và ngoại lệ. Thách thức lớn nhất nằm ở việc đảm bảo tính đúng đắn của kết quả trong mọi tình huống đầu vào.

2.1. Bài toán tìm bao đóng và phủ không dư

Bao đóng X⁺ của tập thuộc tính X được tính bằng thuật toán lặp. Ban đầu, X⁺ chính là X. Ở mỗi bước, thuật toán quét qua các phụ thuộc hàm X → Y. Nếu X là tập con của X⁺ hiện tại, thì Y được thêm vào X⁺. Quá trình lặp lại cho đến khi X⁺ không thay đổi. Phủ không dư yêu cầu mỗi phụ thuộc hàm trong tập đều cần thiết. Phụ thuộc hàm X → Y là dư thừa nếu bao đóng X⁺ theo tập F trừ đi phụ thuộc này vẫn chứa Y.

2.2. Thách thức trong kiểm tra tính tổn thất phép tách

Phép tách lược đồ quan hệ R thành R1 và R2 được gọi là không tổn thất nếu phép kết nối tự nhiên R1 ⋈ R2 bằng R. Kỹ thuật bảng sử dụng ma trận gồm các hàng tương ứng với các lược đồ con và các cột tương ứng với thuộc tính. Ban đầu, mỗi ô được gán ký hiệu phân biệt. Nếu có phụ thuộc hàm X → Y, các hàng có cùng giá trị tại cột X sẽ được gán cùng giá trị tại cột Y. Phép tách không tổn thất khi tồn tại hàng chứa toàn ký hiệu gốc.

III. Giải pháp triển khai thuật toán xử lý phụ thuộc hàm nới lỏng

3.1. Cấu trúc dữ liệu và triển khai lớp tập hợp

Lớp Set sử dụng bitset với kích thước cố định 26 bit để biểu diễn tập thuộc tính. Phương thức IsIn kiểm tra sự hiện diện của một phần tử trong tập hợp. Toán tử cộng (+) thực hiện phép hợp hai tập hợp bằng phép OR bit. Toán tử nhân (*) thực hiện phép giao bằng phép AND bit. Toán tử trừ (-) thực hiện phép hiệu bằng phép AND với bù. Toán tử so sánh (==, !=, <=) hỗ trợ kiểm tra quan hệ tập hợp con và bằng nhau.

3.2. Thuật toán tìm phủ tối thiểu và kiểm tra tính tổn thất

Phủ tối thiểu Fm được tìm theo ba bước chính. Bước đầu tiên đưa mỗi phụ thuộc hàm về dạng vế phải đơn thuộc tính. Bước hai loại bỏ các phụ thuộc hàm dư thừa bằng cách tính bao đóng. Bước ba rút gọn vế trái của từng phụ thuộc hàm nếu có thể. Thuật toán kiểm tra tính tổnất sử dụng ma trận kỹ thuật bảng. Chương trình xây dựng ma trận ban đầu và lặp cập nhật dựa trên các phụ thuộc hàm trong tập F.

IV. Kết luận và hướng ứng dụng của nghiên cứu

Nghiên cứu đã tổng hợp và phân tích hệ thống các thuật toán xử lý phụ thuộc hàm nới lỏng một cách có hệ thống. Kết quả chính bao gồm việc xây dựng và thử nghiệm thành công các thuật toán tính bao đóng, phủ không dư, phủ tối thiểu. Chương trình kiểm tra tính tổn thất phép tách bằng kỹ thuật bảng hoạt động chính xác trên nhiều trường hợp thử nghiệm. Cấu trúc dữ liệu bitset giúp tối ưu hiệu năng tính toán đáng kể so với cách triển khai truyền thống.Ứng dụng thực tiễn của nghiên cứu nằm trong quá trình thiết kế và chuẩn hóa cơ sở dữ liệu quan hệ. Các thuật toán này hỗ trợ nhà phát triển phát hiện và loại bỏ các bất thường dữ liệu. Công trình cũng là tài liệu tham khảo giá trị cho sinh viên và nghiên cứu sinh ngành khoa học máy tính. Hướng phát triển tiếp theo có thể mở rộng cho phụ thuộc hàm nới lỏng trong ngữ cảnh dữ liệu lớn và phân tán.

4.1. Đóng góp chính của luận văn thạc sĩ

Luận văn cung cấp tài liệu tiếng Việt hệ thống về các thuật toán xử lý phụ thuộc hàm. Việc triển khai chương trình thử nghiệm giúp kiểm chứng tính đúng đắn của lý thuyết. Cấu trúc lớp Set và FD được thiết kế modular, dễ tái sử dụng và mở rộng. Phương pháp tiếp cận từ cơ sở lý thuyết đến triển khai thực tế tạo nên giá trị toàn diện cho nghiên cứu.

4.2. Hướng phát triển và ứng dụng tương lai

Các thuật toán có thể được mở rộng để xử lý phụ thuộc hàm nới lỏng trong ngữ cảnh dữ liệu thời gian thực.Ứng dụng vào hệ thống cơ sở dữ liệu phân tán đòi hỏi cải tiến thuật toán cho môi trường song song. Tích hợp với công cụ CASE hỗ trợ thiết kế cơ sở dữ liệu tự động là hướng triển vọng. Nghiên cứu cũng mở ra khả năng áp dụng cho các loại phụ thuộc phức tạp hơn như phụ thuộc đa trị và phụ thuộc join.

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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ LINH CÁC THUẬT TOÁN XỬ LÝ PHỤ THUỘC HÀM NỚI LỎNG Chuyên ngành: Khoa học Máy tính Mã số: 8 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TSKH NGUYỄN XUÂN HUY Thái Nguyên năm 2020 1 LỜI CAM ĐOAN Tên tôi là: Nguyễn Thị Linh Sinh ngày: 18/08/1989 Học viên lớp Cao học CK17A - Trường Đại học Công nghệ Thông tin và Truyền thông - Thái Nguyên. Tôi xin cam đoan toàn bộ nội dung liên quan tới đề tài được trình bày trong luận văn là do bản thân tôi tìm hiểu và nghiên cứu, dưới sự hướng dẫn khoa học của Thầy giáo PGS. Nguyễn Xuân Huy. Các nội dung trong luận văn đúng như nội dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và trước pháp luật. Tác giả luận văn Nguyễn Thị Linh 2 LỜI CẢM ƠN Lời đầu tiên, em xin bày tỏ lòng cảm ơn và kính trọng sâu sắc đối với Thầy PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em trong suốt quá trình làm luận văn này. Thầy giúp em hiểu và tiếp cận những vấn đề khoa học rất lý thú, hướng em vào nghiên cứu các lĩnh vực rất thiết thực và bổ ích. Em đã học hỏi được rất nhiều ở Thầy cũng như phong cách làm việc, phương pháp tiếp cận tri thức. Em luôn được Thầy chỉ bảo tận tình trong suốt quá trình làm luận văn. Em cũng xin thể hiện sự kính trọng và biết ơn đến Quý Thầy Cô trong Trường ĐH CNTT&TT, trang bị cho chúng em đầy đủ về cơ sở vật chất cũng như tri thức để em hoàn thành khóa học. Cuối cùng em xin cảm ơn các bạn học viên trong lớp Cao học, những người luôn bên cạnh và cung cấp những thông tin quý báu trong suốt quá trình học tập, nghiên cứu để hoàn thành luận văn này. Thái Nguyên, ngày 26 tháng 8 năm 2020 Học viên Nguyễn Thị Linh 3 MỤC LỤC LỜI CAM ĐOAN . 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT . 8 DANH MỤC CÁC BẢNG . 9 DANH MỤC CÁC HÌNH .11 CHƯƠNG 1 CÁC KIẾN THỨC CƠ SỞ . Giới thiệu chung . Định nghĩa về quan hệ, bộ, thuộc tính. Bao đóng của tập thuộc tính . Các kí hiệu và một số quy ước . Lược đồ quan hệ và khóa của lược đồ quan hệ . Định nghĩa lược đồ quan hệ . Khóa của lược đồ quan hệ . Các phép toán quan hệ . Phép kết nối tự nhiên (Natural Join) . Thứ tự thực hiện các phép toán quan hệ . Một số hàm tiện ích . Một số ví dụ . Phụ thuộc hàm . Các tính chất của phụ thuộc hàm . Suy dẫn theo tiên đề (suy dẫn logic) . 30 CHƯƠNG 2 CÁC THUẬT TOÁN QUẢN LÝ LƯỢC ĐỒ QUAN HỆ . Thuật toán tập hợp . Thuật toán tìm hợp của hai tập hợp . Thuật toán tìm giao của hai tập hợp . Thuật toán tìm hiệu của hai tập hợp . Thuật toán tìm phủ không dư . Thuật toán tìm phủ tối tiểu . Thuật toán kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng . 37 CHƯƠNG 3 CHƯƠNG TRÌNH THỬ NGHIỆM . Lớp tập hợp Set . Cấu tử Set . Toán tử gán tập hợp . Toán tử lấy hợp của hai tập hợp . Toán tử lấy giao của hai tập hợp . Toán tử lấy hiệu của hai tập hợp. Toán tử in ra tập hợp. Toán tử so sánh. Lớp phụ thuộc hàm FD. Cấu tử khởi tạo phụ thuộc hàm. Hàm đặt vào phụ thuộc hàm. Hàm lấy vế trái của phụ thuộc hàm. Hàm lấy vế phải của phụ thuộc hàm. Hàm thêm vào vế trái của phụ thuộc hàm. Hàm thêm vào vế phải của phụ thuộc hàm. Toán tử gán phụ thuộc hàm. Toán tử in ra phụ thuộc hàm. Lớp lược đồ quan hệ RSC. Cấu tử khởi tạo lược đồ quan hệ. Hủy tử của lược đồ quan hệ. Hàm gán giá trị rỗng cho lược đồ quan hệ. Hàm gán giá trị cho lược đồ quan hệ. Hàm trả về khóa của lược đồ quan hệ. Hàm mở rộng để đưa thêm phụ thuộc hàm. Toán tử gán lược đồ quan hệ. Hàm chèn thêm một lược đồ quan hệ. Hàm chuẩn hóa tự nhiên. Hàm tìm bao đóng. Hàm kiểm tra siêu khóa. Hàm kiểm tra khóa. Hàm kiểm tra chuẩn BCNF. Hàm kiểm tra dẫn xuất. Hàm tìm phủ không dư. Toán tử in ra lược đồ quan hệ. Minh họa chương trình.63 TÀI LIỆU THAM KHẢO. 63 7 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu, chữ viết tắt Ý nghĩa CSDL Cơ sở dữ liệu ĐTB Điểm trung bình GV Giáo viên HB Học bổng HS Học sinh LĐQH Lược đồ quan hệ LĐQH Lược đồ quan hệ |X| Lực lượng của tập X 8 DANH MỤC CÁC BẢNG Bảng 3. Một số hàm và toán tử lớp tập hợp. Một số hàm và toán tử lớp phụ thuộc hàm. Một số hàm và toán tử lớp lược đồ quan hệ. 48 9 DANH MỤC CÁC HÌNH Hình 3. Thử nghiệp với lớp Set. Thử nghiệm với lớp FD. Thử nghiệm với lớp RSC. Thử nghiệm lớp RSC với cơ sở dữ liệu học sinh. Thử nghiệm lớp RSC với cơ sở dữ liệu thời khóa biểu. Thử nghiệm lớp RSC với cơ sở dữ liệu thiết bị. Đặt vấn đề Năm 1970 Codd đề xuất khái niệm phụ thuôc hàm như một cơ chế quản lý ngữ nghĩa dữ liệu trong cơ sở dữ liệu quan hệ [8], [9], [10]. Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng f: X  Y; X, Y  U trong đó ta gọi X là vế trái và Y là vế phải của PTH f. Cho quan hệ R(U) và một PTH f: X  Y trên U. Ta nói quan hệ R thoả PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống nhau trên Y, R(XY)  (u, vR): (u.Y) Nếu f: X  Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc hàm vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y. Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY). Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH F, và viết R(F), nếu R thoả mọi PTH trong F: R(F)  ( f  F): R(f) Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ trên U thoả tập PTH F. Cho tập  các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng trong mọi quan hệ của . Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F + là tập nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề Armstrong Ao sau đây [1], [2], [3]:  X,Y,ZU: F1. Tính phản xạ: Nếu X  Y thì X  Y  F + F2. Tính gia tăng: Nếu XY  F + thì XZYZ  F + F3. Tính bắc cầu: Nếu X  Y  F + và Y  Z  F + thì X  Z  F + 11 Sau đó hàng loạt công trình nghiên cứu đề xuất các loại phụ thuộc dữ liệu khác được xuất hiện trong lý thuyết cơ sở dữ liệu [4],[5],[10]. Các phụ thuộc dữ liệu đảm bảo cho dữ liệu trong các cơ sở dữ liệu phản ánh sát với thế giới thực, phi mâu thuẫn có tính nhất quán và trợ giúp tối ưu hóa trong tìm kiếm dữ liệu [6], [7]. Trong số các biến thể của phụ thuộc hàm thì các phụ thuộc nới lỏng (Relaxed Functional Dependencies) được nghiên cứu và ứng dụng với tần xuất cao vì các lý do sau đây. Thứ nhất, các điều kiện bổ sung cho phụ thuộc hàm để tạo ra các phụ thuộc nới lỏng thường khá gần với các yêu cầu trong đời thường. Thứ hai, các phụ thuộc nới lỏng có thể được dùng làm cơ sở để đặc tả các loại phụ thuộc khác [6], [7]. Cho tập thuộc tính U. Một phụ thuộc hàm nới lỏng trên U là công thức dạng f: (γ)X  (δ)Y; X, Y  U trong đó ta gọi X là vế trái và Y là vế phải của phụ thuộc hàm nới lỏng f. Cho quan hệ R(U) và một phụ thuộc hàm nới lỏng f: (γ)X  (δ)Y trên U. Ta nói quan hệ R thoả phụ thuộc hàm nới lỏng f, hoặc phụ thuộc hàm nới lỏng f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R thỏa điều kiện γ và giống nhau trên X thì chúng cũng giống nhau trên miền Y thỏa điều kiện δ, R(XY)  (γ)X, (δ)Y, (u,vR): (u.Y) Nếu f: (γ)X  (δ)Y là một phụ thuộc hàm nới lỏng trên U thì ta nói tập thuộc tính Y phụ thuộc (hàm) nới lỏng vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm nới lỏng tập thuộc tính Y. Dưới đây xin trích dẫn một số thí dụ về các phụ thuộc hàm nới lỏng. Trong bảng tuần hoàn các nguyên tố hóa học Mendelev, hai chất có cùng số electron tại lớp ngoài cùng thì có cùng ái lực, tức là chúng có cùng xu thế nhận thêm cho đủ số electron từ nguyên tố khác. 12 Phụ thuộc hàm nới lỏng f: (E = s)E  (true)A Ý nghĩa của phụ thuộc hàm nới lỏng trong trường hợp này là: Chỉ xét trên các bộ thỏa điều kiện số điện tử tại lớp ngoài cùng bằng s, E = s, thì hai nguyên tố có cùng lượng E sẽ có cùng ái lực. Một dạng khác của phụ thuộc hàm nới lỏng là phân loại học sinh. Hai học sinh có thể có điểm khác nhau nhưng vẫn được xếp vào cùng loại. g: (a  ĐTB  b)ĐTB  (true)Loại Phụ thuộc hàm nới lỏng g cho biết hai học sinh có điểm trung bình (ĐTB) trong cùng một đoạn [a; b] thì có cùng loại đánh giá. 13 Trong công trình của nhóm nghiên cứu Loredana Caruccio, Vincenzo Deufemia, và Giuseppe Polese [7] đã phân loại hầu hết các phụ thuộc hàm nới lỏng từ năm 1970 đến 2016. Trong khuôn khổ khóa luận thạc sĩ này, học viên chọn đề tài: “Các thuật toán xử lý phụ thuộc hàm nới lỏng”. Đối tượng và phạm vi nghiên cứu Luận văn tập trung khảo sát các đối tượng liên quan đến các lược đồ cơ sở dữ liệu quan hệ sau đây: - Lý thuyết phụ thuộc hàm và phụ thuộc hàm nới lỏng. - Các thuật toán cơ bản xử lý các đối tượng trong phụ thuộc hàm nới lỏng.