Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu

1. Đặt

   T = {AB} (T là tập các thuộc tính xuất hiện phía trái)

   P = {BCDE} (P là tập các thuộc tính xuất hiện phía phải)

   K = U\P = {A}

2. Tính thử K+

   Ta có K+ = {ABCDE}

   Vì K+ = U, nên K = {A} là một khoá của R.

1. Đặt:

   T = {ABED}

   P = {DEAC}

   K = U\P = {B}

2. Tính thử K ⁺

   Ta có K⁺ = {B}

    U, nên tiếp tục Bước 3

3. Tính K = K
   (T P)

   Ta có K = K

    (T P) = {ABDE}

4. Thử xóa từng thuộc tính trong T
   P = {AED} khỏi K

   Thử loại bỏ A khỏi K, ta có :

   K = {BED} và K ⁺ = {BEDAC} vẫn bằng U nên ta loại được A

   Thử loại bỏ {E} khỏi K, Ta có:

   K = {BD} và K⁺ = {BDC}

   Do K⁺

   U nên không thể loại được {E}. K vẫn là {BDE}

   Thử loại bỏ {D} khỏi K ta có

   K = {BE} và K⁺ = {BEADC}= U

• Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu
• Ngành cơ sở dữ liệu: Học gì, học ở đâu và cơ hội nghề nghiệp
• Thuật Toán và Ví dụ tìm tất cả các khóa trong lược đồ quan hệ – Đạt Tea’s Blog

Đến đây ta đã thử hết. Vậy khóa tối thiểu tìm được là : K = {BE}

1. Đặt
   • T = {ABCDEG}
   • P = {ABCDEG} (P là tập các thuộc tính xuất hiện phía phải)
   • K = U\P = {}
2. Tính thử K ⁺

   Ta có K⁺ = { } ≠ U, nên tiếp tục bước 3

3. Tính K = K
   (T  P)

   Ta có K = K

    (T  P) = {ABCDEG}

4. Thử xoá từng thuộc tính trong T
   P = {ABCDEG} khỏi K
   • Thử loại bỏ {A} khỏi K, Ta có:

     K = {BCDEG} và K⁺ = {BCDEGA} vẫn bằng U, nên ta loại được A

   • Thử loại bỏ {B} khỏi K, Ta có:

     K = {CDEG} và K⁺ = {CDEGAB} vẫn bằng U, nên ta loại được B

   • Thử loại bỏ {C} khỏi K, Ta có:

     K = {DEG} và K⁺ = {DEG}

     Do K⁺ ≠ U nên không loại được {C}. K vẫn là {DEGC}

   • Thử loại bỏ {D} khỏi K, Ta có:

     K = {EGC} và K⁺ = {EGCABD} vẫn bằng U, nên ta loại được D

   • Thử loại bỏ {E} khỏi K, Ta có:

     K = {GC} và K⁺ = {GCABDE} vẫn bằng U, nên ta loại được E

   • Thử loại bỏ {G} khỏi K, Ta có:

     K = {C} và K⁺ = {CA}

     Do K⁺ = ≠ U nên không loại được {G}. K vẫn là {CG} → Đã thử hết !

   Đến đây ta đã thử hết. Vậy khoá tối thiểu tìm được là : K = {CG}

1. Đặt

   T = {ABCDEH}

   P = {ABCDEG}

   K = U\P = {H}

2. Tính thử K ⁺

   Ta có K⁺ = {HCDG} ≠ U, nên tiếp tục bước 3

3. Tính K = K
   (T  P)

   Ta có K = K

    (T  P) = {HABCDE}

4. Thử xoá từng thuộc tính trong T
   P= {ABCDE} khỏi K

   Thử loại bỏ {A} khỏi K, Ta có:

   K = {HBCDE} và K⁺ = {HBCDEGA}

   Do K⁺ ≠ U nên không loại được {A}. K vẫn là {HBCDEA}

   Thử loại bỏ {B} khỏi K, Ta có:

   K = {HCDEA} và K⁺ = {HCDEAGB}

   Do K⁺ ≠ U nên không loại được {B}. K vẫn là {HCDEAB}

   Thử loại bỏ {C} khỏi K, Ta có:

   K = {HDEAB} và K⁺ = {HDEABCG}

   Do K⁺ ≠ U nên không loại được {C}. K vẫn là {HDEABC}

   Thử loại bỏ {D} khỏi K, Ta có:

   K = {HEABC} và K⁺ = {HEABCDG}

   Do K⁺ ≠ U nên không loại được {D}. K vẫn là {HEABCD}

   Thử loại bỏ {E} khỏi K, Ta có:

   K = {HABCD} và K⁺ = {HABCDG}

   Do K⁺ ≠ U nên không loại được {E}. K vẫn là {HABCDE}.

• Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu
• Ngành cơ sở dữ liệu: Học gì, học ở đâu và cơ hội nghề nghiệp
• Thuật Toán và Ví dụ tìm tất cả các khóa trong lược đồ quan hệ – Đạt Tea’s Blog

Đến đây ta đã thử hết. Vậy khoá tối thiểu tìm được là : K = {HABCDE}

1. Đặt

   T = {ABC}

   P = {AB}

   K = U\P = {C}

2. Tính thử K ⁺

   Ta có K⁺ = {CBA} = U

   Vì K⁺ = U, nên K = {C} là một khoá của R.