Luận án: Discovering Functional Dependencies And Relaxed Functional Dependencies In Databases.

Discovering Functional Dependencies and Relaxed Functional Dependencies in Databases

Tác giả: VU QUOC TUAN

Lĩnh vực: Math Fundamentals for Informatics

Nội dung tài liệu:

Luận án này tập trung nghiên cứu các vấn đề liên quan đến khám phá các phụ thuộc chức năng (FD) và các phụ thuộc chức năng nới lỏng (RFD) trong cơ sở dữ liệu. Phụ thuộc chức năng đóng vai trò quan trọng trong thiết kế cơ sở dữ liệu, quản lý chất lượng dữ liệu và biểu diễn tri thức. Quá trình trích xuất các phụ thuộc này từ dữ liệu hiện có được gọi là khám phá phụ thuộc.

Mục tiêu của khám phá phụ thuộc là tìm ra các phụ thuộc quan trọng trong dữ liệu. Các phụ thuộc được khám phá này biểu diễn tri thức miền và có thể được sử dụng để xác minh thiết kế cơ sở dữ liệu và đánh giá chất lượng dữ liệu. Với sự phát triển của các thiết bị kỹ thuật số, lượng dữ liệu tăng nhanh đã đặt ra những thách thức trong lưu trữ và quản lý dữ liệu, đặc biệt là vấn đề khám phá tri thức từ các tập dữ liệu lớn này. Việc khám phá FDs và RFDs trong cơ sở dữ liệu là một trong những vấn đề quan trọng của khám phá tri thức.

Luận án xem xét ba loại phụ thuộc dữ liệu điển hình là FD, AFD (Approximate Functional Dependency) và CFD (Conditional Functional Dependency). AFD là một dạng mở rộng của FD, sử dụng một thước đo sai số để xác định mức độ vi phạm. CFD là một dạng mở rộng khác của FD, sử dụng một bảng mẫu để ràng buộc các giá trị dữ liệu có liên quan ngữ nghĩa.

Các hướng nghiên cứu được đề cập bao gồm việc giải quyết vấn đề khám phá RFD trong cơ sở dữ liệu, bắt đầu từ việc khám phá FD vì FD là trường hợp riêng của mọi loại RFD. Thời gian phức tạp của bài toán khám phá FD là đa thức theo số bộ dữ liệu nhưng lại là hàm mũ theo số thuộc tính. Do đó, cần phát triển các quy tắc cắt tỉa hiệu quả để giảm thời gian xử lý. Một vấn đề quan trọng khác là làm thế nào để loại bỏ sự dư thừa trong tập hợp các phụ thuộc dữ liệu đã được khám phá.

Luận án cũng trình bày các phương pháp khám phá FD, bao gồm phương pháp từ trên xuống (top-down) và phương pháp từ dưới lên (bottom-up), cùng với các thuật toán tương ứng. Ngoài ra, luận án còn đề cập đến việc khám phá AFD và CFD, cùng với các thách thức và thuật toán đề xuất. Cuối cùng, luận án thảo luận về một hệ thống phân cấp thống nhất cho FDs, CFDs và ARs (Attribute Reduction), nhấn mạnh lợi ích của việc sử dụng hệ thống phân cấp này để thích ứng các thuật toán khám phá và tạo ra một tập hợp các phụ thuộc được rút gọn.

Mục lục chi tiết:

• Chapter 1: Functional Dependencies and Relaxed Functional Dependencies in the Relational Data Model
• Chapter 2: Approximate Functional Dependencies and Conditional Functional Dependencies