Khóa của lược đồ quan hệ

Định nghĩa:

• Cho R(A1, …,An) là lược đồ quan hệ;
• Tập các thuộc tính U = { A1, A2, .. , An}
• Tập các phụ thuộc hàm F= { f1, f2, .. ,fn} xác định trên R.
• K Í U là khoá của R nếu thoả mãn hai điều kiện sau :

(1):  K ® U

(2):  Không tồn tại K’ Ì K mà K’ ® U

Tập thuộc tính S được gọi là siêu khóa nếu S ⊇ K

Thuộc tính A được gọi là thuộc tính khóa nếu A ∈ K với K là khóa bất kì của lược đồ R, ngược lại A là thuộc tính không khóa.

Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa có thể là rỗng.

Khi thiết kế một hệ thống thông tin thì việc tạo được một lược đồ quan hệ đạt một tiêu chuẩn nào đó là rất quan trọng và việc xác định chuẩn của một lược đồ quan hệ liên quan mật thiết với thuật toán tìm khóa.

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

Input:

• Lược đồ quan hệ R(A1,A2,…An)
• Tập thuộc tính U {A1,A2,…An}
• Tập PTH F

Output: Khóa K của quan hệ R

Ý tưởng: Bắt đầu từ tập U vì U⁺ = U. Ta bớt dần các phần tử của U để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U.

Các bước:

Bước 1: Gán K = U

Bước 2: Loại khỏi K lần lượt từng thuộc tính A mà ( K\A)⁺ =U

Lặp lại bước 2 đến khi không loại khỏi K được nữa

Nhận xét: Thuật toán trên chỉ tìm được một khoá trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta thay đổi trật tự loại bỏ các phần tử của K.

Ví dụ:

Cho R(ABCD) và tập phụ thuộc hàm F = { AB ® C; D ® B; C ® ABD}

Giải:

Bước 1: K=ABCD

Bước 2: Lần lượt loại các thuộc tính của K

Loại A ta có (BCD)+ = {BCDA} = U nên K= BCD

Loại B ta có (CD)+ = {CDAB} = U nên K = CD

Loại C ta có D+ = {DB} ≠ U nên không thể loại C

Loại D ta có C+ = {CABD} = U nên K = C

Kết luận: C là  một khóa của lược đồ R đã cho.

Nhận xét: Ta có thể cải thiện tốc độ thực hiện thuật toán trên bằng cách trong bước 1 ta thay K= U bởi K=Left(U) U (U\(Left U Right)) – tập các thuộc tính xuất hiện ở vế trái và không xuất hiện ở cả hai vế của phụ thuộc hàm.

Thuật toán tìm khóa cải tiến

• Bước 1: Gán K = Left(U) U (U\(Left U Right))
• Bước 2: Loại khỏi K lần lượt từng thuộc tính A mà ( K\A)⁺ =U
• Lặp lại bước 2 đến khi không loại khỏi K được nữa

Ví dụ:

Cho R(ABCD) và tập F = {AB → C, B → D, D → B}

Giải:

• K=ABD
• Loại A ta có BD+ = {BD} ≠ U nên không loại được A
• Loại B ta có AB+ = {ABCD}= U nên K= AD
• Loại D ta có A+ = {A} ≠ U nên không loại được D

Kết luận khóa của lược đồ đã cho là AD.

Thuật toán tìm tất cả các khóa

Một số khái niệm cơ bản:

• 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 phụ thuộc hàm và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của phụ thuộc hàm
• 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 phụ thuộc hàm
• Tập thuộc tính trung gian (TG): Chứa thuộc tính xuất hiện ở cả vế trái lẫn vế phải của phụ thuộc hàm.

Input: Lược đồ R(U) và tập phụ thuộc hàm F

Output: Tất cả các khóa của phụ thuộc hàm

Các bước:

• Bước 1: Tạo tập nguồn TN và tập trung gian TG
• Bước 2: Tính TN⁺_, nếu TN⁺ = U, kết luận chỉ có một khóa duy nhất là TN. 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 S_i bằng cách với mọi X_i, nếu (TN U X_i)⁺=R⁺ thì S_i = TN U {X_i}
• 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 S_i, S_j thuộc S nếu S_i chứa trong S_j thì loại bỏ tập S_j ra khỏi siêu khóa (VD: S_i=AB, S_j=ABC thì loại bỏ S_j 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ệ R(CSZ) và 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.

Giải:

Bước 1: TN={S}, TG={CZ}

Bước 2: TN⁺ ≠ U nên qua bước 3

Bước 3: Tập con Xi của tập trung gian X={∅,C,Z,CZ}

Bước 4:

S+=S Khác R có nghĩa không có siêu khóa.

SC+=SCZ bằng với R nên siêu khóa SC.

SZ+=SZC bằng với R nên Siêu khóa là CZ

SCZ+= bằng với R 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}

Ta có thể lập bảng để thực hiện bước 4 và 5 như sau:

Xi	TN U Xi	(TN U Xi)+	Siêu khóa	Khóa
∅	S	S
C	SC	SCZ = U	SC	SC
Z	SZ	SZC = U	SZ	SZ
CZ	SCZ	SCZ=U	SCZ

 

Quan hệ đã cho có 2 khóa là SC và SZ.