Cách xác định khóa trong lược đồ quan hệ- CSDL

    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 Xi  của TG

    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ì khi đó Si = TN U Xi

    Bước 5 :

    Tìm Khóa(Ki) 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ỏ Sj 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 Xi của tập TG = {0, A,C,AC}

Ta lấy từng thuộc tính thuộc tập con Xi 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ệ