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

Bài viết Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu thuộc chủ đề về Giải Đáp thời gian này đang được rất nhiều bạn quan tâm đúng không nào !! Hôm nay, Hãy cùng Khoa Lịch Sử tìm hiểu Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu trong bài viết hôm nay nhé ! Các bạn đang xem nội dung : “Khóa tối thiểu là gì?Thuật toán tìm khoá tối thiểu”Xem thêm:

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

Xem nhanh
Tìm khóa tối thiểu của phụ thuộc hàm - cơ sở dữ liệu #2

Định nghĩa khoá tối thiểu

Cho lược đồ R = <U,F>, trong đó U là tập thuộc tính, F là tập phụ thuộc hàm. K được gọi là khoá tối thiểu của R nếu như số thuộc tính trong K là ít nhất nhưng vẫn thoả mãn K+ =U .

Thuật toán tìm khoá tối thiểu

từ nay nếu không có sự nhầm lẫn thì ta gọi tắt khoá tối thiểu là Khoá
Mọi Người Xem :   Ấn rồng

Bài tập áp dụng

Cho lược đồ R = <UF> : U = {ABCDE} , F = {A→B, B→C, B→DE, A→E, A→D}

Hãy tìm một khoá tối thiểu K của lược đồ R ?

  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.

Cho lược đồ quan hệ R = <UF>, Trong đó : U = {ABCDE} , F = {AB→DE, E→AD, D→C}

Hãy tìm một khoá tối thiểu K của lược đồ 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

Xem thêm:

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

Cho lược đồ quan hệ R = <U, F>, Trong đó :

U = {ABCDEG}

F = {AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD, CE→AG}

Hãy tìm một khoá tối thiểu K của lược đồ R.

  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}

Mọi Người Xem :   Ngọc Trâm - Ý nghĩa của tên Ngọc Trâm

Cho lược đồ quan hệ R = <U, F>, Trong đó :

U = {ABCDEGH}

F = {A→C, AB→C, C→DG, CD→G, EC→ABEG,C, H→C}

Hãy tìm một khoá tối thiểu K của lược đồ R

  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}.

Xem thêm:

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

Các câu hỏi về khóa tối thiểu là gì

Nếu có bắt kỳ câu hỏi thắc mắt nào vê khóa tối thiểu là gì hãy cho chúng mình biết nhé, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình cải thiện hơn trong các bài sau nhétìm khóa tối thiểu khóa tối thiểu là gì khóa tối thiểu bài tập tìm khóa của lược đồ quan hệ lược đồ quan hệ tìm khóa tìm khóa của lược đồ quan hệ xác định khóa của lược đồ quan hệ lược đồ quan hệ là gì khóa của lược đồ quan hệ là gì tìm khóa của lược đồ tìm khóa của phụ thuộc hàm luoc do quan he cho lược đồ quan hệ r(u) với u= a b c d e f= a→bc c→de d→a . tập thuộc tính không khóa của r(u) là tìm phủ tối thiểu g của f được cho như sau f = a → c ab → c b → eg be → d c → h a → h tìm khoá của lược đồ quan hệ tìm phủ tối thiểu cách tìm tất cả các khóa của lược đồ

Loading

Related Posts

About The Author