Bài viết tập trung nghiên cứu về việc mở rộng tập thuộc tính A thành một tập cực tiểu A’ chứa A sao cho A'-> b là phụ thuộc hàm đúng trên cơ sở dữ liệu mới. nội dung chi tiết của tài liệu. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học – Đại học Huế Tập 6, Số 1 (2016) MỞ RỘNG PHỤ THUỘC HÀM TRONG CƠ SỞ DỮ LIỆU BỊ NHIỄU Hoàng Thị Lan Giao Khoa Công nghệ Thông tin, Trường Đại học Khoa học – Đại học Huế Email: TÓM TẮT Trong một cơ sở dữ liệu quan hệ với phụ thuộc hàm cho trước A b giá trị của thuộc tính b được xác định duy nhất bởi tập thuộc tính A. Tuy nhiên, qua quá trình truyền dữ liệu, dữ liệu nhận được đã bị nhiễu và có thể không còn đúng như nguyên bản. Rõ ràng, trên bộ dữ liệu mới này phụ thuộc hàm A b không còn đúng nữa. Nói cách khác, nếu chỉ dựa vào dữ liệu trên tập thuộc tính A chúng ta không thể xác định được chính xác các đối tượng. Trong bài báo này, chúng tôi sẽ nghiên cứu việc mở rộng tập thuộc tính A thành một tập cực tiểu A’ chứa A sao cho A' b là phụ thuộc hàm đúng trên cơ cở dữ liệu mới. Từ khóa: cơ sở dữ liệu quan hệ, phụ thuộc hàm, phụ thuộc hàm bị lỗi. 1. MỞ ĐẦU Giả sử ta có một cơ sở dữ liệu thực gồm m đối tượng và là tập n thuộc tính, được biểu diễn bằng một ma trận Mmxn, khi đó mỗi dòng tương ứng là một bản ghi và không có hai dòng giống nhau. Gọi K là họ các khóa cực tiểu. Những dữ liệu này được chuyển dịch thông qua một kênh có lỗi, ta ký hiệu M* là ma trận nhận được sau khi dịch chuyển. M và M* khác nhau ít nhất là e giá trị trên mỗi dòng. Trong M không có hai dòng giống nhau nhưng trong M* điều này không chắc chắn. Chẳng hạn cặp thuộc tính (ten, ho) là một khóa trong cơ sở dữ liệu M và ta có hai dòng tương ứng với cặp này là (Trần, Chi) và (Trần, Nhi). Tuy nhiên, khi chuyển dịch ta nhận được trong M* hai cặp giá trị này đều là (Trần, Nhi). Khi đó đối tượng cần xác định trong M* không duy nhất. Có nhiều cách tiếp cận khác nhau, chẳng hạn thuật toán Tane [7]mở rộng các phụ thuộc hàm bằng cách đưa ra một sai số chấp nhận được dựa vào tỷ lệ giữa các bộ (đối tượng) đúng với phụ thuộc hàm đó và tổng số bộ trong cơ sở dữ liệu. Ý tưởng này cũng được chúng tối mở rộng trên cả phụ thuộc đa trị xấp
