Thuật Toán và Ví dụ tìm tất cả các khóa trong lược đồ quan hệ

Đầu tiên, chúng ta cần hiểu một vài khái niệm :

Ta gọi :

• Q là tập cơ sở dữ liệu
• F là tập phụ thuộc hàm
• L(left) : là các thuộc tính chỉ xuất hiện bên trái
• R(right) : là các thuộc tính chỉ xuất hiện ở vế phải
• S(supperkey) : là tập các siêu khóa
• K(key) : là tập các khóa

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 F( tập phụ thuộc hàm) và các thuộc tính không xuất hiện ở cả vế trái và vế phải của F.

Vậy TN = Q \ R

Nghĩa là ta lấy Q trừ cho R để tìm thuộc tính chỉ xuất hiện ở L và các thuộc tính không xuất hiện ở cả L và R

Ví dụ : Cho tập cơ sở dữ liệu Q = {A,B,C,D,E}    L = {A,B}    R = {B,C,E}

TN = Q \ R = {A,D}

Tập thuộc tính đích (TĐ) : Bao gồm các thuộc tính chỉ xuất hiện ở R, không xuất hiện ở L.

Vậy TĐ = R \ L

Ví dụ : Cho L = {A,B,C,D,E}     R = {E,F,G,H}

TĐ = {F,G,H}

Tập thuộc tính trung gian (TG) : Chứa các thuộc tính xuất hiện ở cả L và R

Vậy TG = L Giao R (Giao của 2 tập hợp để lấy thuộc tính chung của 2 Tập hợp đó)

Ví dụ : Cho L = {A,B,C,D,E}   R = {D,E,F,G}

Vậy TG = L /cap R = {D,E}

Thuật toán :

Bước 1 :

Tìm tập thuộc tính nguồn TN và Tập thuộc tính trung gian TG, bằng các ví dụ ở trên thì các bạn có thể dễ dàng tìm thấy 2 tập thuộc tính này.

Bước 2 :

Nếu TG = 0

Thì K(Key) = TN, và kết thúc thuật toán, xuất ra K của tập cơ sở dữ liệu <Q,F>

Ngược lại, nếu TG # 0

Thì qua bước 3

Bước 3 :

Tìm tất cả các tập con X_i  của TG

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)⁺ = Q thì khi đó S_i = TN U X_i

Bước 5 :

Tìm Khóa(K_i) 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ỏ S_j ra khỏi tập siêu khóa. Khi đó, tập S còn lại chính là tập khóa cần tìm

Ví dụ :

Ta có S = {AB, ABC, ED, EDF}

Ta thấy AB chứa trong ABC, ED chứa trong EDF vậy chúng ta cần phải loại bỏ ABC và EDF.

Vậy S = {AB,ED} chính là tập khóa cần tìm

Chúng ta có một ví dụ mẫu như sau :

Ví dụ : Cho một tập cơ sỡ dữ liệu R = <Q, F>

Với Q = {ABC}     F = {AB –> C, C -> A}. Tìm tất cả các khóa thuộc tập cơ sở dữ liệu trên.

Bài Làm :
L = {ABC}      R = {CA}

TN = {B}        TG = {AC} # 0 nên ta làm tiếp bước 3

Ta có tập con X_i của tập TG = {0, A,C,AC}

Ta lấy từng thuộc tính thuộc tập con X_i của tập TG hợp với TN ta có các thuộc tính sau :

S1 = TN U 0 = B Ta có B⁺ = B # Q nên S1 = A không là siêu khóa

S2 = TN U A = AB Ta có AB⁺ = ABC = Q nên S2 = AB là siêu khóa

S3 = TN U C = BC Ta có BC⁺ = ABC = Q nên S3 = BC là siêu khóa

S4 = TN U AC = ABC Ta có ABC⁺ = ABC = Q nên S4 = ABC  là siêu khóa

Vậy ta có tập siêu khóa S = {AB,BC,ABC}.

Tuy nhiên, vì AB chứa trong ABC và BC chứa trong ABC nên loại bỏ siêu khóa ABC ra khỏi tập siêu khóa

Vậy ta có, tập khóa K = {AB,BC} là khóa của lượt đồ quan hệ