Tìm khóa của lược đồ quan hệ trong cơ sở dữ liệu

Tìm tất cả các khóa trong lược đồ quan hệ
Trước khi đi vào chi tiết chúng ta tìm hiểu một số khái niệm:
- Tập thuộc tính nguồn (TN): bao gồm các thuộc tính chỉ xuất hiện ở vế trái, không xuất hiện ở vế phải của pth và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth.
- Tập thuộc tính đích (TĐ) : bao gồm các thuộc tính chỉ xuất hiện ở vế phải không xuất hiện ở vế trái của pth.
- Tập thuộc tính trung gian (TG): Chứa thuộc tính ở vế trái lẫn vế phải của pth.
Thuật toán:
Bước 1:  Tạo tập nguồn TN và tập trung gian TG
Bước 2:  Nếu TG=0(rỗng) thì K=TN, kết thúc. ngược lại qua bước 3.
Bước 3:  Tìm tất cả, tập con Xi của tập trung gian.
Bước 4: Tìm siêu khóa Si bằng cách với mọi Xi, nếu (TN U Xi)+=Q+ thì Si = TN U Xi
Bước 5: Tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu. Với mọi Si, Sj thuộc S
nếu Si chứa trong Sj thì loại bỏ tập Sj ra khỏi siêu khóa (VD: Si=AB, Sj=ABC thì loại bỏ Sj ra khỏi tập siêu khóa)
S còn lại chính là tập khóa cần tìm.
Ví dụ :
cho lược đồ quan hệ Q={CSZ} tập phụ thuộc hàm F={CS → Z; Z → C} tìm tất cả các khóa của lược đồ quan hệ trên.
Bước 1:
- TN={S}, TG={CZ}
Bước 2:
- TG khác rỗng nên qua bước 3
Bước 3:
- tập con Xi của tập trung gian X={0,C,Z,CZ} ghi chú 0: là rỗng
Bước 4:
- S+=S Khác Q có nghĩa không có siêu khóa.
- SC+=CZS bằng với Q nên siêu khóa SC.
- SZ+=CZ bằng với Q nên Siêu khóa là CZ
- SCZ+= bằng với Q nên Siêu khóa là CSZ
Bước 5:
- Vậy tập siêu khóa S={SC, CZ, CSZ} Vì SC chứa trong CSZ và CZ chứa trong CSZ nên loại bỏ siêu khóa CSZ khỏi tập siêu khóa.
- Kết quả khóa của lược đồ quan hệ trên là SC và CZ. K={SC, CZ}

Thuật toán tìm một khóa trên lược đồ quan hệ

Mục tiêu : cho một lược đồ U có các thuộc tính {A1,A2,...An} và tập Phụ thuộc hàm F. hãy tìm một khóa cho lược đồ đó.
Thuật toán:
Bước 1: + Gán K0=U+ (U+ là tập thuộc tính của U)
Bước 2 : Ta có A là thuộc tính của U.
+ Tính bao đóng của (Ki-1\A)+ nếu bằng U+ ((Ki-1\A)+ =U+) thì loại bỏ A ra khỏi K tức là Ki =(Ki-1\A). nếu (Ki-1\A)+ !=U+ thì Ki =Ki-1.
Lặp lại bước trên n lần
Bước n: kết quả K=Kn
Ví dụ : cho U={A,B,C,D,E} và F={AB->C, AC->B, BC->DE} tìm một khóa của lược đồ quan hệ r xác định trên U và F ?
Bước 1:
+ K=U tức là K=ABCDE
Bước 2:
+ Tính Bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy kết quả tính bao đóng không bằng U+ nên K=ABCDE
Bước 3:
+ Tính Bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K=ACDE
Bước 4:
+ Tính Bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy kết quả tính bao đóng Không bằng U+ nên không bỏ C ra tập K ta có K=ACDE
Bước 5:
+ Tính Bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K=ACE
Bước 6:
+ Tính Bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K=AC
=>>Kết quả Khóa là K=AC