Bài viết sưu tầm

Thuậttoán cải tiến

Trướckhi đi vào thuật toán cải tiến, ta cần quan tâm một số khái niệm sau:

+         Tậpthuộctínhnguồn(TN)chứatấtcảcácthuộctínhcóxuấthiệnởvếtráivàkhôngxuất hiệnởvếphảicủacácphụthuộchàmvàcácthuộctínhkhôngxuấthiệnởcảvếtráilẫnvế phải của các phụ thuộc hàm.

+         Tậpthuộctínhđích(TD)chứatấtcảcácthuộctínhcóxuấthiệnởvếphảivàkhôngxuất hiện ở vế trái của các phụ thuộc hàm.

+         Tậpthuộctínhtrunggian(TG)chứatấtcảcácthuộctínhxuấthiệnởcảvếtráilẫnvếphải của các phụ thuộc hàm.

Hệ quả: Nếu K là khóa của Qthì TNÎKvà TDÇK =Ø

Thuậttoántìmtấtcảkhóacủamộtlượcđồquanhệ

Bước1:         tạo tập thuộctính nguồn TN, tập thuộc tính trung gian TG

Bước2:    if TG= Ø  then lược đồ quan hệ chỉ có một khóa K

K=TN

kết thúc

Ngược lại

Quabước 3

Bước3:         tìm tất cả các tập con Xicủa tập trung gian TG

Bước4:         tìmcác siêu khóa Sibằng cách "Xi

if (TNÈXi)+ =  Q+ then

Si= TNÈXi

Bước5:         tìm khóa bằngcách loại bỏ các siêu khóa không tối tiểu

"Si, Sj ÎS

if Si ÌSj then Loại Sj  rakhỏiTậpsiêukhóaS S còn lại chính là tập khóa cần tìm.