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.