Chuyển tới nội dung
Home » Khóa Tối Thiểu Là Gì | Re: Cách Tìm Khóa, Phủ Tối Thiểu, Tìm Bao Đóng

Khóa Tối Thiểu Là Gì | Re: Cách Tìm Khóa, Phủ Tối Thiểu, Tìm Bao Đóng

Tìm khóa tối thiểu của quan hệ - cơ sở dữ liệu #2

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

Thật là ngưỡng mộ Pác Tuấn Anh hết sức ah nha..!!Tks nhiều hen..!!

Tks nhiều hen..!!

nanaly
Cống hiến
Tổng số bài gửi : 376Join date : 18/09/2009Age : 40Đến từ : QNgai
NamThang
Khởi đầu
Tổng số bài gửi : 40Join date : 18/09/2009

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

ai giup minh voi timMột cơ sở dữ liệu cho một công ty đầu tư gồm các thuộc tính sau : B (người buôn cổ phiếu), O (văn phòng của người buôn cổ phiếu), I (người đầu tư), S (loại cổ phiếu), Q (số lượng của loại cổ phiếu mà người đầu tư có) và D (giá trị lãi của loại cổ phiếu đó). Như vậy có các phụ thuộc hàm sau :S D, I B, IS Q, B Oa) Tìm khoá tối tiểu của lược đồ quan hệ R(BOSQID)b) Tìm một phép tách R thành những lược đồ ở dạng chuẩn 3, phép tách này vừa là tách kết nối không mất thông tin vừa bảo toàn các phụ thuộc đã cho

Một cơ sở dữ liệu cho một công ty đầu tư gồm các thuộc tính sau : B (người buôn cổ phiếu), O (văn phòng của người buôn cổ phiếu), I (người đầu tư), S (loại cổ phiếu), Q (số lượng của loại cổ phiếu mà người đầu tư có) và D (giá trị lãi của loại cổ phiếu đó). Như vậy có các phụ thuộc hàm sau :

S D, I B, IS Q, B O

a) Tìm khoá tối tiểu của lược đồ quan hệ R(BOSQID)

b) Tìm một phép tách R thành những lược đồ ở dạng chuẩn 3, phép tách này vừa là tách kết nối không mất thông tin vừa bảo toàn các phụ thuộc đã cho

phuongtoan
Tổng số bài gửi : 3Join date : 25/12/2011
Tìm khóa tối thiểu của quan hệ - cơ sở dữ liệu #2
Tìm khóa tối thiểu của quan hệ – cơ sở dữ liệu #2

Bài tập áp dụng

Cho lược đồ R =

: 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 =

, 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 (TP)

    Ta có K = K (TP) = {ABDE}

  4. Thử xóa từng thuộc tính trong TP = {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

    Đế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 =

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

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

Cho lược đồ quan hệ R =

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

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

Cho lược đồ quan hệ R =

, Trong đó :

U = {ABC}

F = {A→B, B→A, C→B}

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

  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.

Tìm khóa tối thiểu của lược đồ quan hệ

Cho lược đồ R =

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

Cho lược đồ quan hệ R =

Hãy tìm một khoá (tối thiểu) của quan hệ R.

Bài tập áp dụng

Cho lược đồ R =

: 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 = UP = {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 =

, 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 = UP = {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 (TP)

    Ta có K = K (TP) = {ABDE}

  4. Thử xóa từng thuộc tính trong TP = {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

    Đế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 =

, 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 = UP = {}
  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}

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

Cho lược đồ quan hệ R =

, 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 = UP = {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}.

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

Cho lược đồ quan hệ R =

, Trong đó :

U = {ABC}

F = {A→B, B→A, C→B}

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

  1. Đặt

    T = {ABC}

    P = {AB}

    K = UP = {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.

Cơ sở dữ liệu - 5 - tìm khóa tối thiểu của quan hệ
Cơ sở dữ liệu – 5 – tìm khóa tối thiểu của quan hệ

Tìm khóa tối thiểu của lược đồ quan hệ

Science and Technology

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

Cho lược đồ R =

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

Phát biểu bài toán tìm khoá tối thiểu

Cho lược đồ quan hệ R =

Hãy tìm một khoá (tối thiểu) của quan hệ R.

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

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

2. Bỏ các thuộc tính dư thừa ở vế trái.

+ B->C, C->D Không xét vì vế trái chỉ có một thuộc tính.

+ xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

+ xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

3. Loại khỏi F các phụ thuộc hàm dư thừa.

+ xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C

+ xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D

+ B->C : tính B+=B không thể bỏ.

+ C->D : tính C+=C không thể bỏ.

Ở trên xét AB->C thì B+=BCD

Còn xét B->C thì B+=B

Mình không hiểu chỗ này lắm mong bạn có thể giải thích rõ được không

Còn nữa nếu như là các PTH mà có bao đóng của thuộc tính vế trái chứa thuộc tính vế phải thì là dư thừa thì PTH nào cũng dư thừa à, vì theo cách tính bao đóng thì sẽ đưa các thuộc tính của vế phải vào mà, mong bạn giải thích giùm luôn, thanks

linhtinh
Tổng số bài gửi : 1Join date : 03/12/2011
Cơ sở dữ liệu - Tìm phủ tối thiểu của tập phụ thuộc hàm
Cơ sở dữ liệu – Tìm phủ tối thiểu của tập phụ thuộc hàm

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

Một thư viện dùng một hệ cơ sở dữ liệu gồm 3 quan hệ sau đây để quản lý sách, mượn-trả và đọc giả : B (B#, TITLE, AUNAME, PNUM),BR (B#, R#, BDATE, RAL),R (R#, RNAME, YDATE, ADD) ,Trong đó R# là số thẻ đọc giả, B# là số hiệu sáchRNAME là tên đọc giả, TITLE là tên sáchYDATE và ADD là năm sinh và địa chỉ của đọc giảPNUM là số trang, BDATE là ngày mượn và RAL cho biết đã trả hay chưa (giả sử miền giá trị của RAL là {true, false})Hãy dùng các biểu thức đại số quan hệ (hoặc ngụn ngữ tõn từ) và ngôn ngữ SQL để biểu diễn các yêu cầu sau:a) Cho biết số hiệu của các quyển sách mà người có số thẻ “S3” đã từng mượnb) Tìm địa chỉ người mượn quyển sách “MARTIN” của tác giả có tên là “J. D. BERWILL”c) Tìm số hiệu những quyển sách đã từng có một người mượn hơn một lầnGiai giup minh bai nay voi

BR (B#, R#, BDATE, RAL),

R (R#, RNAME, YDATE, ADD) ,

Trong đó R# là số thẻ đọc giả, B# là số hiệu sách

RNAME là tên đọc giả, TITLE là tên sách

YDATE và ADD là năm sinh và địa chỉ của đọc giả

PNUM là số trang, BDATE là ngày mượn và RAL cho biết đã trả hay chưa (giả sử miền giá trị của RAL là {true, false})

Hãy dùng các biểu thức đại số quan hệ (hoặc ngụn ngữ tõn từ) và ngôn ngữ SQL để biểu diễn các yêu cầu sau:

a) Cho biết số hiệu của các quyển sách mà người có số thẻ “S3” đã từng mượn

b) Tìm địa chỉ người mượn quyển sách “MARTIN” của tác giả có tên là “J. D. BERWILL”

c) Tìm số hiệu những quyển sách đã từng có một người mượn hơn một lần

Giai giup minh bai nay voi

phuongtoan
Tổng số bài gửi : 3Join date : 25/12/2011

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

Mọi người dùng phần mềm này nhé. http://www.mediafire.com/?muynxnzcj1kphuongtoan đã viết:ai giup minh voi timMột cơ sở dữ liệu cho một công ty đầu tư gồm các thuộc tính sau : B (người buôn cổ phiếu), O (văn phòng của người buôn cổ phiếu), I (người đầu tư), S (loại cổ phiếu), Q (số lượng của loại cổ phiếu mà người đầu tư có) và D (giá trị lãi của loại cổ phiếu đó). Như vậy có các phụ thuộc hàm sau :S D, I B, IS Q, B Oa) Tìm khoá tối tiểu của lược đồ quan hệ R(BOSQID)b) Tìm một phép tách R thành những lược đồ ở dạng chuẩn 3, phép tách này vừa là tách kết nối không mất thông tin vừa bảo toàn các phụ thuộc đã cho

– Có thể tìm được khóa tối thiểu.

– Xác định chuẩn

……………….

VANTHUAN986
Tổng số bài gửi : 19Join date : 29/09/2009
CSDL : 3. Tìm khóa tối thiểu
CSDL : 3. Tìm khóa tối thiểu

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

bài viết thật ý nghĩa và thật hay… mình đang cần cái này quá… tự dưng như gặp được vàng,,, thanks bác nhé,,,,,,,,,,

trungthot
Tổng số bài gửi : 1Join date : 30/05/2012
Sponsored content

» Chăm sóc trẻ hóa da mặt một cách khoa học» Đồng hồ camera giá rẻ đa chức năng – Móc khóa camera siêu nhỏ Bảo hành 1 năm» Móc khóa camera giá rẻ 550K – Đồng hồ camera siêu nhỏ tích hợp nhiều tính năng» Móc khoá camera- moc khoa camera- Móc khoá camera HD- Móc khoá camera nguy trang-Kính camera HD giá siêu rẻ» Móc khóa camera – Móc khóa quay phim kèm ghi âm Giá rẻ nhất toàn quốc

» Đồng hồ camera giá rẻ đa chức năng – Móc khóa camera siêu nhỏ Bảo hành 1 năm

» Móc khóa camera giá rẻ 550K – Đồng hồ camera siêu nhỏ tích hợp nhiều tính năng

» Móc khoá camera- moc khoa camera- Móc khoá camera HD- Móc khoá camera nguy trang-Kính camera HD giá siêu rẻ

» Móc khóa camera – Móc khóa quay phim kèm ghi âm Giá rẻ nhất toàn quốc

:: Góc Học Tập :: Cơ Sở Dữ Liệu

Trang 1 trong tổng số 1 trang

Permissions in this forum:

Bạn không có quyền trả lời bài viết

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

thk tuấn anh , nếu bạn tìm được lý thuyết các phần: tiếp cận phân rã,tổng hợp, phân rã bảo toàn thông tin,bảo toàn phụ thuộc hàm thì post lên lun nhé, phần này khó,môn này lại là môn thi tốt nghiệp,hic

môn này lại là môn thi tốt nghiệp,hic

itlinh
Góp sức
Tổng số bài gửi : 84Join date : 27/09/2009Đến từ : HCM
Tìm Phủ Tối Thiểu Trong Cơ Sở Dữ Liệu
Tìm Phủ Tối Thiểu Trong Cơ Sở Dữ Liệu

Thông tin tài liệu

H-íng dÉn «n tËp CSDL quan hÖ Tµi liÖu tham kh¶o Trang 27 DẠNG 7: TÌM KHOÁ TỐI THIỂU CỦA QUAN HỆ Bài toán: Cho quan h R(U, F). Hãy tìm một khoá tối thiểu của R. Kiến thức liên quan: Cho quan hệ R(U, F), X ⊆ U. X được gọi là khoá của R nếu X + ≡ U. X được gọi là một khoá tối thiểu của R nếu: X là khoá của R và X tối thiểu (tức không tồn tại một tập con thực sự nào của X mà tập con đó cũng là khoá của R). Giải thuật tìm khoá tối thiểu của R: B1: Đặt K 0 = {U} B2: Tính K 1 = K 0 ∪ Z nếu ∃ Y → Z mà Y ∈ K 0 . Tính K i = K i-1 ∪ Z nếu ∃ Y → Z mà Y ∈ K i-1 Lặp cho tới khi K i ≡ K i-1 B3: Kết luận K i là một khoá tối thiểu của R. Ví dụ: Cho quan hệ R(U, F): U = {A, B, C, D, E, G, H} Và F = {AB →C, B → DE, C → EG, G → B, E → H} Tìm một khóa tối thiểu của quan hệ R. Đặt K 0 = {A,B,C,D,E,G,H} K 1 = {ABCDEG} vì E → H và E ∈ K 0 K 2 = {ABCD} vì C → EG và B ∈ K 1 K 3 = {ABC} vì B → D và B ∈ K 2 K 4 = {AB} vì AB → C và AB ∈ K 3 K 5 ≡ K 4 Vậy {AB} là một khóa tối thiểu của R. Chú ý: Với một quan hệ R(U, F) cho trước có thể tồn tại nhiều khóa tối thiểu khác nhau, tùy thuộc vào thứ tự loại bỏ các thuộc tính trong giải thuật. Chẳng hạn, với ví dụ trên, ta có thể thu được một khóa khác bằng cách loại B đi ngay từ đầu: Đặt K 0 = {A,B,C,D,E,G,H} K 1 = {ABCDEG} vì E → H và E ∈ K 0 K 2 = {ACDEG} vì G → B và G ∈ K 1 K 3 = {ACD} vì C → EG và C ∈ K 2 K 4 ≡ K 3 Vậy {ACD} là một khóa tối thiểu của R. Ta thấy {ACD} có nhiều thuộc tính hơn {AB} nhưng nó vẫn là khóa tối thiểu. Điều này cũng dễ hiểu do {ACD} + trùng với U nên nó là khóa của R. Mặt khác nó không chứa một tập con nào cũng là khóa của R nên nó tối thiểu. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. . tËp CSDL quan hÖ Tµi liÖu tham kh¶o Trang 27 DẠNG 7: TÌM KHOÁ TỐI THIỂU CỦA QUAN HỆ Bài toán: Cho quan h R(U, F). Hãy tìm một khoá tối thiểu của R. Kiến. là một khoá tối thiểu của R. Ví dụ: Cho quan hệ R(U, F): U = {A, B, C, D, E, G, H} Và F = {AB →C, B → DE, C → EG, G → B, E → H} Tìm một khóa tối thiểu của

Ngày đăng: 29/09/2013, 05:20

Xem thêm: Tìm khóa tối thiểu của một quan hệ, Tìm khóa tối thiểu của một quan hệ

Luyện Tập

Xác định khóa, Tìm phủ tối thiểu, Chuẩn hóa dữ liệu 3NF

ĐỀ SỐ 1:

Câu II:

Cho lược đồ quan hệ Q(A,B,C,D,E,G,H) và tập phụ thuộc hàm:

F = { E → C; H → E; A→ D; A,E → H; D,G → B; D,G → C }

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN:

Tìm khóa?

TN = {AG }

TG = { DEH }

TN+F = { AG }+F = AGDBC ≠ Q+

Xi

TN U Xi

(TN U Xi)+

Siêu khóa

Khóa

AG

AGDBC

AGD

AGDBC

AGE

AGEDBCH = Q+

AGE

AGE

AGH

AGHDEBC = Q+

AGH

AGH

DE

AGDE

AGDEBCH = Q+

AGDE

DH

AGDH

AGDHBCE = Q+

AGDH

EH

AGEH

AGEHDBC = Q+

AGEH

DEH

AGDEH

AGDEHBC = Q+

AGDEH

Vậy TK = { AGE, AGH }

3NF?

Xét pth: E → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Tìm phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Bước 3:

F’ = { E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

* Xét E → C: E+ – { E → C } = E, C ∉ E+ ⇔ E → C ∉ F+ ⇒ Không thể bỏ pht này.

* Các pth H → E; A→ D; A,E → H; D,G → B đều không bỏ được vì các thuộc tính E, D, H, B chỉ xuất hiện 1 lần bên vế phải.

* D,G → C: DG+ – { D,G → C } = DGB, C ∉ DG+ ⇔ D,G → C ∉ F+ ⇒ Không thể bỏ pht này.

Vậy F’ = { E → C;

H → E;

A→ D;

A,E → H;

D,G → B;

D,G → C }

Là phủ tối thiếu của F.

Phân rã?

Vậy TK = { AGE, AGH }

Bước 1, Bước 2: Không làm

Bước 3: Q1( EC ) với F1 = { E → C }

Q2( HE ) với F2 = { H → E }

Q3( AD ) với F3 = { A→ D }

Q4( AEH ) với F4 = { A,E → H }

Q5( DGB ) với F5 = { D,G → B }

Q6( DGC ) với F6 = { D,G → C }

Bước 4: Vì không có LĐQH con nào chứa 1 khóa của Q nên bổ sung 1 khóa của Q vào phân rã: Q7( AGE ), F7 = {ø}

===============================================

ĐỀ SỐ 2

Câu II

Cho lược đồ quan hệ Q(ABCDEG) và tập phụ thuộc hàm

F= {B → C; DEG → B; A → D; A → E; A → G}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

Tìm khóa?

TN = { A }

TG = { BDEG }

TN+F = { A }+F = ADEGBC = Q+

Vậy Q chỉ có 1 khóa duy nhất là A

3NF?

Xét pth: B → C, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Tìm phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { B → C;

DEG → B;

A → D;

A → E;

A → G }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { B → C;

DEG → B;

A → D;

A → E;

A → G }

Bước 3:

F’ = { B → C;

DEG → B;

A → D;

A → E;

A → G }

* Các pth B → C; DEG → B; A → D; A → E; A → G đều không bỏ được vì các thuộc tính C, B, D, E, G chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { B → C;

DEG → B;

A → D;

A → E;

A → G }

Là phủ tối thiếu của F.

Phân rã?

TK = {A}

Bước 1, Bước 2: Không làm

Bước 3: Q1( BC ) với F1 = { B → C }

Q2( DEGB ) với F2 = { DEG → B }

Q3( AD ) với F3 = { A→ D }

Q4( AE ) với F4 = { A → E }

Q5( AG ) với F5 = { A → G }

Bước 4: Vì có Q3, Q4, Q5 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 3

Câu II :

Cho lược đồ quan hệ Q(ABCDEG) và tập các phụ thuộc hàm

F = {AB→ C, AC→D, D→EG, G→B, A→D, CG→A}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN

Tìm khóa?

TN = {ø}

TG = { ABCDG }

Xi

TN U Xi

(TN U Xi)+

Siêu khóa

Khóa

ADEGBC = Q+

DEGB

GB

AB

AB

ADEGBC = Q+

AB

AC

AC

ADEGBC = Q+

AC

AD

AD

ADEGBC = Q+

AD

AG

AG

ADEGBC = Q+

AG

BC

BC

BC

BD

BD

BDEG

BG

BG

BG

CD

CD

CDEGBA = Q+

CD

CD

CG

CG

CGABDE = Q+

CG

CG

DG

DG

DGBE

ABC

ABC

ADEGBC = Q+

ABC

ABD

ABD

ADEGBC = Q+

ABD

ABG

ABG

ADEGBC = Q+

ABG

ACD

ACD

ADEGBC = Q+

ACD

ACG

ACG

ADEGBC = Q+

ACG

ADG

ADG

ADEGBC = Q+

ADG

BCD

BCD

CDEGBA = Q+

BCD

BCG

BCG

CGABDE = Q+

BCG

BDG

BDG

BDGE

CDG

CDG

CDEGBA = Q+

CDG

ABCD

ABCD

CDEGBA = Q+

ABCD

ABCG

ABCG

CDEGBA = Q+

ABCG

ABDG

ABDG

CDEGBA = Q+

ABDG

ACDG

ACDG

CDEGBA = Q+

ACDG

BCDG

BCDG

CDEGBA = Q+

BCDG

ABCDG

ABCDG

CDEGBA = Q+

ABCDG

Vậy TK = { A, CD, CG }

3NF?

Xét pth: G→B, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Tìm phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { AB→ C,

AC→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { AB→ C,

AC→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

AB→C: có B dư thừa vì A→D→G→B A→B ( B ẩn trong A)

A C→D: có C dư thừa vì A→D

Bước 3:

F’ = { A→ C,

A→D,

D→E,

D→G,

G→B,

A→D,

CG→A }

A→D: bỏ pth này vì trùng lắp

Các pth A→ C; D→E; D→G; G→B; A→D; CG→A đều không bỏ được vì các thuộc tính C, E, G, B, D, A chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { A→ C,

D→E,

D→G,

G→B,

A→D,

CG→A }

Là phủ tối thiếu của F.

Phân rã?

Dựa vào phủ tối thiểu F’

TK = { A, CD, CG }

Bước 1, Bước 2: Không làm

Bước 3: Q1( AC ) với F1 = { A → C }

Q2( DE ) với F2 = { D→E }

Q3( DG ) với F3 = { D→G }

Q4( GB ) với F4 = { G→B }

Q5( AD ) với F5 = { A→D }

Q6( CGA ) với F6 = { CG→A }

Bước 4: Vì có Q1 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 4

Câu II :

Cho quan hệQ(GHIKLM) và tập các phụ thuộc hàm

F = {GH→ L, I→M, L→K, HM→G, GK→I, H→L}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thông tin và phụ thuộc hàm.

HƯỚNG DẪN

Tìm khóa?

TN = { H }

TG = {GIKLM }

TN+F = { H }+F = HLK ≠ Q+

Xi

TN U Xi

(TN U Xi)+

Siêu khóa

Khóa

HLK

HG

HGLKIM = Q+

HG

HG

HI

HILMGK = Q+

HI

HI

HK

HKL

HL

HLK

HM

HMLKGI = Q+

HM

HM

GI

HGI

HGLKIM = Q+

HGI

GK

HGK

HGLKIM = Q+

HGK

GL

HGL

HGLKIM = Q+

HGL

GM

HGM

HGLKIM = Q+

HGM

IK

HIK

HGLKIM = Q+

HIK

IL

HIL

HGLKIM = Q+

HIL

IM

HIM

HGLKIM = Q+

HIM

KL

HKL

HKL

KM

HKM

HGLKIM = Q+

HKM

LM

HLM

HGLKIM = Q+

HLM

GIK

HGIK

HGLKIM = Q+

HGIK

GIL

HGIL

HGLKIM = Q+

HGIL

GIM

HGIM

HGLKIM = Q+

HGIM

GKL

HGKL

HGLKIM = Q+

HGKL

GKM

HGKM

HGLKIM = Q+

HGKM

GLM

HGLM

HGLKIM = Q+

HGLM

IKL

HIKL

HGLKIM = Q+

HIKL

IKM

HIKM

HGLKIM = Q+

HIKM

ILM

HILM

HGLKIM = Q+

HILM

KLM

HKLM

HGLKIM = Q+

HKLM

GIKL

HGIKL

HGLKIM = Q+

HGIKL

GIKM

HGIKM

HGLKIM = Q+

HGIKM

GILM

HGILM

HGLKIM = Q+

HGILM

GKLM

HGKLM

HGLKIM = Q+

HGKLM

IKLM

HIKLM

HGLKIM = Q+

HIKLM

GIKLM

HGIKLM

HGLKIM = Q+

HGIKLM

Vậy TK = { HG, HI, HM }

Cách 2: Tìm chu trình của Tập TG

Ta thấy G, I và M tạo thành 1 chu trình, vì vậy mỗi điểm trên chu trình này kết hợp với TN tạo thành khóa của Q.

Vậy TK = { HG, HI, HM }

3NF?

Xét pth: L→K, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Tìm phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { GH→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { GH→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

GH→L: có G dư thừa vì có H→L

Bước 3:

F’ = { H→ L,

I→M,

L→K,

HM→G,

GK→I,

H→L }

H→ L: bỏ pth này vì trùng lắp

Các pth I→M; L→K; HM→G; GK→I; H→L đều không bỏ được vì các thuộc tính M, K, G, I, L chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { I→M,

L→K,

HM→G,

GK→I,

H→L }

Là phủ tối thiếu của F.

Phân rã?

Dựa vào phủ tối thiểu F’

TK = { HG, HI, HM }

Bước 1, Bước 2: Không làm

Bước 3: Q1( IM ) với F1 = { I→M }

Q2( LK ) với F2 = { L→K }

Q3( HMG ) với F3 = { HM→G }

Q4( GKI ) với F4 = { GK→I }

Q5( HL ) với F5 = { H→L }

Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung.

===============================================

ĐỀ SỐ 5

Câu II :

Cho lược đồ quan hệ Q và tập phụ thuộc hàm F được cho như sau:

Q(A,B,C,D,E,G,H,K,L,M,N), F={ C → D,E; G → H,K; A,G → L; M → A,N; A → B,C}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

Tìm khóa?

TN = { GM }

TG = { AC }

TN+F = {GM }+F = GMANBCDEHKL = Q+

Vậy Q có 1 khóa duy nhất là GM

3NF?

Xét pth: C → D,E, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Bước 3:

F’ = { C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Các pth C → D; C → E; G → H; G → K; A,G → L; M → A; M → N; A → B; A → C đều không bỏ được vì các thuộc tính D, E, H, K, L, A, N, B, C chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { C → D;

C → E;

G → H;

G → K;

A,G → L;

M → A;

M → N;

A → B;

A → C }

Là phủ tối thiếu của F.

Phân rã?

Dựa vào phủ tối thiểu F’

TK = { GM }

Bước 1, Bước 2: Không làm

Bước 3: Q1( CD ) với F1 = { C → D }

Q2( CE ) với F2 = { C → E }

Q3( GH ) với F3 = { G → H }

Q4( GK ) với F4 = { G → K }

Q5( AGL ) với F5 = { A,G → L }

Q6( MA ) với F6 = { M → A }

Q7( MN ) với F7 = { M → N }

Q8( AB ) với F8 = { A → B }

Q9( AC ) với F9 = { A → C }

Bước 4: Vì không có LĐQH con nào chứa 1 khóa của Q nên bổ sung 1 khóa của Q vào phân rã: Q10( GM ), F10 = {ø}

===============================================

ĐỀ SỐ 6

BÀI 2:

Cho lược đồ quan hệ CCS và tập phụ thuộc hàm F được cho như sau như sau: CCS(MAHV,HOTEN,NGAYSINH,MALOP,TENLOP,NGAYKG,MAMH,TENMH,SOTIET, DIEMTHI, SOBL, SOTIEN)

F={ MAHV → HOTEN, NGAYSINH, MALOP,

MALOP → NGAYKG, TENLOP,

MAMH → TENMH,SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,SOTIEN}

1. Hãy xác đinh tất cả các khóa của Q

2. Hãy cho biết Q có đạt 3NF không ?

3. Tìm phủ tối thiểu của F.

4. Phân rã Q về dạng chuẩn 3, yêu cầu phân rã bảo toàn thong tin và phụ thuộc hàm.

HƯỚNG DẪN

Tìm khóa?

TN = { MAMH, SOBL }

TG = { MAHV, MALOP }

TN+F = { MAMH, SOBL }+F = { MAMH, SOBL, TENMH, SOTIET, MAHV, SO TIEN, DIEMTHI, HOTEN, NGAYSINH, MALOP, NGAYKG, TENLOP } = CSS+

Vậy CSS có 1 khóa duy nhất là { MAMH, SOBL }

3NF?

Xét pth: MAHV → HOTEN, NGAYSINH, MALOP, ta thấy vế trái không chứa khóa và vế phải không là thuộc tính khóa => Q không đạt 3NF

Tìm phủ tối thiểu?

Bước 1: F’ = F, tách F’ thành một tập phụ thuộc hàm mà vế phải chí có một thuộc tính

F’ = { MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Bước 2: Loại bỏ những thuộc tính dư thừa

F’ = { MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Bước 3:

F’ = { MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Các pth MAHV → HOTEN, MAHV → NGAYSINH, MAHV → MALOP, MALOP → NGAYKG, MALOP → TENLOP, MAMH → TENMH, MAMH → SOTIET, MAHV,MAMH → DIEMTHI, SOBL → MAHV, SOBL → SOTIEN đều không bỏ được vì các thuộc tính HOTEN, NGAYSINH, MALOP, NGAYKG, TENLOP, TENMH, SOTIET, DIEMTHI, MAHV, SOTIEN chỉ xuất hiện 1 lần bên vế phải.

Vậy F’ = { MAHV → HOTEN,

MAHV → NGAYSINH,

MAHV → MALOP,

MALOP → NGAYKG,

MALOP → TENLOP,

MAMH → TENMH,

MAMH → SOTIET,

MAHV,MAMH → DIEMTHI,

SOBL → MAHV,

SOBL → SOTIEN }

Là phủ tối thiếu của F.

Phân rã?

Dựa vào phủ tối thiểu F’

TK = { MAMH, SOBL }

Bước 1, Bước 2: Không làm

Bước 3: Q1(MAHV, HOTEN ) với F1 = { MAHV → HOTEN }

Q2(MAHV, NGAYSINH ) với F2 = { MAHV → NGAYSINH }

Q3(MAHV, MALOP ) với F3 = { MAHV → MALOP }

Q4(MALOP, NGAYKG ) với F4 = { MALOP → NGAYKG }

Q5(MALOP, TENLOP ) với F5 = { MALOP → TENLOP }

Q6(MAMH, TENMH ) với F6 = { MAMH → TENMH }

Q7(MAMH, SOTIET ) với F7 = { MAMH → SOTIET }

Q8(MAHV,MAMH, DIEMTHI ) với F8 = { MAHV,MAMH → DIEMTHI }

Q9(SOBL, MAHV ) với F9 = { SOBL → MAHV }

Q10(SOBL, SOTIEN ) với F10 = { SOBL → SOTIEN }

Bước 4: Vì không có LĐQH con nào chứa 1 khóa của CSS nên bổ sung 1 khóa của CSS vào phân rã: Q11( MAMH, SOBL ), F11 = {ø}

===============================================

ĐỀ SỐ 8

CÂU II :

Cho lược đồ quan hệ HoaDon và tập các phụ thuộc hàm F như sau: HoaDon(SOHD, KHACH, NGAYLAP, MATHANG, DONGIA, SOLUONG) F={SOHD →KHACH, NGAYLAP,

SOHD,MATHANG →DONGIA,SOLUONG}

1. Tìm khóa cho Hoadon

2. Hãy cho biết lược đồ quan hệ HoaDon có đạt dạng chuẩn nào ? Tại sao?

3. Nếu lược đồ chưa đạt dạng chuẩn 3 hãy phân rã thành các lược đồ con đạt dạng chuẩn 3, xác định khóa chính cho các lược đồ con này.)

HƯỚNG DẪN

Tìm khóa?

TN = { SOHD, MATHANG }

TG = { ø }

Vậy HoaDon có 1 khóa duy nhất là { SOHD, MATHANG }

Tìm dạng chuẩn?

2NF:

Tập thuộc tính không khóa: N = {KHACH, NGAYLAP, DONGIA, SOLUONG}

Xét pht SOHD, MATHANG →KHACH Є F:

có MATHANG dư thừa vì có SOHD→KHACH

SOHD, MATHANG →KHACH là phụ thuộc hàm không đầy đủ.

Vậy HoaDon không đạt 2NF.

Dạng chuẩn của LĐQH HoaDon là 1NF

Phân rã?

F={ SOHD →KHACH,

SOHD → NGAYLAP,

SOHD,MATHANG →DONGIA,

SOHD,MATHANG → SOLUONG}

Phân rã thành các lược đồ con đạt dạng chuẩn 3:

Bước 1, Bước 2: Không làm

Bước 3:

Q1(SOHD, KHACH) với F1 = { SOHD →KHACH }, có K1 = {SOHD}

Q2(SOHD, NGAYLAP) với F2 = { SOHD → NGAYLAP }, có K2 = {SOHD}

Q3(SOHD,MATHANG, DONGIA) với F3 = {SOHD,MATHANG →DONGIA}, có K3 = {SOHD, MATHANG}

Q4(SOHD,MATHANG, SOLUONG) với F4 = {SOHD,MATHANG → SOLUONG}, có K4 = {SOHD, MATHANG}

Bước 4: Vì có Q3 chứa khóa của Q nên không bổ sung.

Đăng nhập/Đăng ký
Ranking
Cộng đồng
|
Kiến thức
26 tháng 03, 2022
Admin
04:29 26/03/2022
Khóa trong hệ quản trị cơ sở dữ liệu – DBMS Keys
Cùng tác giả
Không có dữ liệu
0
0
0
Admin
2995 người theo dõi
1283
184
Có liên quan
Không có dữ liệu
Chia sẻ kiến thức – Kết nối tương lai
Về chúng tôi
Về chúng tôi
Giới thiệu
Chính sách bảo mật
Điều khoản dịch vụ
Học miễn phí
Học miễn phí
Khóa học
Luyện tập
Cộng đồng
Cộng đồng
Kiến thức
Tin tức
Hỏi đáp
CÔNG TY CỔ PHẦN CÔNG NGHỆ GIÁO DỤC VÀ DỊCH VỤ BRONTOBYTE
The Manor Central Park, đường Nguyễn Xiển, phường Đại Kim, quận Hoàng Mai, TP. Hà Nội
THÔNG TIN LIÊN HỆ
[email protected]
©2024 TEK4.VN
Copyright © 2024
TEK4.VN

Cách tìm khóa, phủ tối thiểu, tìm bao đóng

+12

thanhhue163

Lamborghini_MU

Virus

quocanh

angel_hb

ThuyLinh

ThuHang

NamThang

nanaly

itlinh

nguyenduc

phamtuananh

16 posters

:: Góc Học Tập :: Cơ Sở Dữ Liệu

Trang 1 trong tổng số 1 trang

Cách tìm khóa, phủ tối thiểu, tìm bao đóng

Tìm tất cả các khóa trong lược đồ quan hệTrước khi đi vào chi tiết chúng ta tìm hiểu một số khái niệm:- 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 pth và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth.- 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 pth.- Tập thuộc tính trung gian (TG): Chứa thuộc tính ở vế trái lẫn vế phải của pth.Thuật toán:Bước 1:- Tạo tập nguồn TN và tập trung gian TGBước 2:- Nếu TG=0(rỗng) thì K=TN, kết thúc. 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 Si bằng cách với mọi Xi,nếu (TN U Xi)+=Q+ thì Si = TN U XiBướ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 Si, Sj thuộc Snếu Si chứa trong Sj thì loại bỏ tập Sj ra khỏi siêu khóa (VD: Si=AB, Sj=ABC thì loại bỏ Sj 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ệ Q={CSZ} 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.Bước 1:- TN={S}, TG={CZ}Bước 2:- TG khác rỗng nên qua bước 3Bước 3:- tập con Xi của tập trung gian X={0,C,Z,CZ} ghi chú 0: là rỗngBước 4:- S+=S Khác Q có nghĩa không có siêu khóa.- SC+=CZS bằng với Q nên siêu khóa SC.- SZ+=CZ bằng với Q nên Siêu khóa là CZ- SCZ+= bằng với Q nên Siêu khóa là CSZBướ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}Thuật toán tìm một khóa trên lược đồ quan hệSUNDAY, 31. MAY 2009, 17:05:46COSODULIEUMục tiêu : cho một lược đồ U có các thuộc tính {A1,A2,…An} và tập Phụ thuộc hàm F. hãy tìm một khóa cho lược đồ đó.Thuật toán:Bước 1 :+ Gán K0=U+ (U+ là tập thuộc tính của U)Bước 2 : ta có A là thuộc tính của U.+ Tính bao đóng của (Ki-1\A)+ nếu bằng U+ ((Ki-1\A)+ =U+) thì loại bỏ A ra khỏi K tức là Ki =(Ki-1\A). nếu (Ki-1\A)+ !=U+ thì Ki =Ki-1.Lặp lại bước trên n lầnBước n: kết quả K=KnVí dụ : cho U={A,B,C,D,E} và F={AB->C, AC->B, BC->DE} tìm một khóa của lược đồ quan hệ r xác định trên U và F ?Bước 1:+ K=U tức là K=ABCDEBước 2:+ Tính Bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy kết quả tính bao đóng không bằng U+ nên K=ABCDEBước 3:+ Tính Bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K=ACDEBước 4:+ Tính Bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy kết quả tính bao đóng Không bằng U+ nên không bỏ C ra tập K ta có K=ACDEBước 5:+ Tính Bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K=ACEBước 6:+ Tính Bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K=AC=>>Kết quả Khóa là K=ACThuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. (ví dụ: A->BC thành A->B và A->C)2. Bỏ các thuộc tính dư thừa ở vế trái. (ví dụ: cho F = {A → B, B → C, AB → D} các phụ thuộc hàm có vế trái 1 thuộc tính là đầy đủ nên ta không xét, xét AB → D có B dư thừa(bỏ B) vì bao đóng của A có chứa B. A+=ABC) (dễ hiểu là chúng ta bỏ thuộc tính bên vế trái, khi và chỉ khi bao đóng của các thuộc tính còn lại có chứa thuộc tính đó)3. Loại khỏi F các phụ thuộc hàm dư thừa. (Các thuộc tính ở vế phải của PTH chỉ xuất hiện di nhất 1 lần thì không thể loại bỏ. Còn lại tính bao đóng của tập thuộc tính vế trái nếu có xuất hiện thuộc tính vế phải thì có thể loại bỏ thuộc tính đó và đó là PTH dư thừa.)Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={AB->CD, B->C, C->D} Tìm phủ tối thiểu?1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.+ ta có F={AB->C, AB->D, B->C, C->D}2. Bỏ các thuộc tính dư thừa ở vế trái.+ B->C, C->D Không xét vì vế trái chỉ có một thuộc tính.+ xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.+ xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.3. Loại khỏi F các phụ thuộc hàm dư thừa.+ xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C+ xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D+ B->C : tính B+=B không thể bỏ.+ C->D : tính C+=C không thể bỏ.Phủ tối thiểu là Ftt = {B->C, C->D}Tìm bao đóngVí dụ: Cho lược đồ quan hệ R(U, F)Với U = ABCDE và F = { AB –>CD, E –> C, D –>CE, A –>E}. Tìm A+- Đầu tiên gán A+=A- Tiếp theo xét xem có PTH nào A->X không? nếu có bỏ X vào A+, ở đây ta có A->E nên A+=AE- Ta thấy E->C nên A+=ACE- Cuối cùng ta có A+=ACE

Trước khi đi vào chi tiết chúng ta tìm hiểu một số khái niệm:

– 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 pth và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth.

– 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 pth.

– Tập thuộc tính trung gian (TG): Chứa thuộc tính ở vế trái lẫn vế phải của pth.

Thuật toán:

Bước 1:

– Tạo tập nguồn TN và tập trung gian TG

Bước 2:

– Nếu TG=0(rỗng) thì K=TN, kết thúc. 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 Si bằng cách với mọi Xi,

nếu (TN U Xi)+=Q+ thì Si = TN U Xi

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 Si, Sj thuộc S

nếu Si chứa trong Sj thì loại bỏ tập Sj ra khỏi siêu khóa (VD: Si=AB, Sj=ABC thì loại bỏ Sj 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ệ Q={CSZ} 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.

Bước 1:

– TN={S}, TG={CZ}

Bước 2:

– TG khác rỗng nên qua bước 3

Bước 3:

– tập con Xi của tập trung gian X={0,C,Z,CZ} ghi chú 0: là rỗng

Bước 4:

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

– SC+=CZS bằng với Q nên siêu khóa SC.

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

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

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

SUNDAY, 31. MAY 2009, 17:05:46

COSODULIEU

Mục tiêu : cho một lược đồ U có các thuộc tính {A1,A2,…An} và tập Phụ thuộc hàm F. hãy tìm một khóa cho lược đồ đó.

Thuật toán:

Bước 1 :

+ Gán K0=U+ (U+ là tập thuộc tính của U)

Bước 2 : ta có A là thuộc tính của U.

+ Tính bao đóng của (Ki-1\A)+ nếu bằng U+ ((Ki-1\A)+ =U+) thì loại bỏ A ra khỏi K tức là Ki =(Ki-1\A). nếu (Ki-1\A)+ !=U+ thì Ki =Ki-1.

Lặp lại bước trên n lần

Bước n: kết quả K=Kn

Ví dụ : cho U={A,B,C,D,E} và F={AB->C, AC->B, BC->DE} tìm một khóa của lược đồ quan hệ r xác định trên U và F ?

Bước 1:

+ K=U tức là K=ABCDE

Bước 2:

+ Tính Bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy kết quả tính bao đóng không bằng U+ nên K=ABCDE

Bước 3:

+ Tính Bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K=ACDE

Bước 4:

+ Tính Bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy kết quả tính bao đóng Không bằng U+ nên không bỏ C ra tập K ta có K=ACDE

Bước 5:

+ Tính Bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K=ACE

Bước 6:

+ Tính Bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K=AC

=>>Kết quả Khóa là K=AC

Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm

1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. (ví dụ: A->BC thành A->B và A->C)

2. Bỏ các thuộc tính dư thừa ở vế trái. (ví dụ: cho F = {A → B, B → C, AB → D} các phụ thuộc hàm có vế trái 1 thuộc tính là đầy đủ nên ta không xét, xét AB → D có B dư thừa(bỏ B) vì bao đóng của A có chứa B. A+=ABC) (dễ hiểu là chúng ta bỏ thuộc tính bên vế trái, khi và chỉ khi bao đóng của các thuộc tính còn lại có chứa thuộc tính đó)

3. Loại khỏi F các phụ thuộc hàm dư thừa. (Các thuộc tính ở vế phải của PTH chỉ xuất hiện di nhất 1 lần thì không thể loại bỏ. Còn lại tính bao đóng của tập thuộc tính vế trái nếu có xuất hiện thuộc tính vế phải thì có thể loại bỏ thuộc tính đó và đó là PTH dư thừa.)

Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={AB->CD, B->C, C->D} Tìm phủ tối thiểu?

1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.

+ ta có F={AB->C, AB->D, B->C, C->D}

2. Bỏ các thuộc tính dư thừa ở vế trái.

+ B->C, C->D Không xét vì vế trái chỉ có một thuộc tính.

+ xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

+ xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

3. Loại khỏi F các phụ thuộc hàm dư thừa.

+ xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C

+ xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D

+ B->C : tính B+=B không thể bỏ.

+ C->D : tính C+=C không thể bỏ.

Phủ tối thiểu là Ftt = {B->C, C->D}

Tìm bao đóng

Ví dụ: Cho lược đồ quan hệ R(U, F)

Với U = ABCDE và F = { AB –>CD, E –> C, D –>CE, A –>E}. Tìm A+

– Đầu tiên gán A+=A

– Tiếp theo xét xem có PTH nào A->X không? nếu có bỏ X vào A+, ở đây ta có A->E nên A+=AE

– Ta thấy E->C nên A+=ACE

– Cuối cùng ta có A+=ACE

phamtuananh
Cống hiến
Tổng số bài gửi : 165Join date : 16/09/2009
Tìm khóa tối thiểu trong môn cơ sở dữ liệu
Tìm khóa tối thiểu trong môn cơ sở dữ liệu

Re: Cách tìm khóa, phủ tối thiểu, tìm bao đóng

Em co mot bai nhu the nay cac bac giai dum em voi:Cho lược đồ quan hệ R { ABCDEGH} và tập phụ thuộc hàmF={ AECGH, AC G, CDABC, AHCE, BGA}• Tìm phủ tối thiểu• Tìm mọi khóa (theo thuật toán tìm mọi khóa)Thanks!

Cho lược đồ quan hệ R { ABCDEGH} và tập phụ thuộc hàm

F={ AECGH, AC G, CDABC, AHCE, BGA}

• Tìm phủ tối thiểu

• Tìm mọi khóa (theo thuật toán tìm mọi khóa)

Thanks!

Lamborghini_MU
Tổng số bài gửi : 1Join date : 13/12/2010

Keywords searched by users: khóa tối thiểu là gì

Csdl : 4.Tìm Tất Cả Các Khóa - Youtube
Csdl : 4.Tìm Tất Cả Các Khóa – Youtube
Tìm Khóa Tối Thiểu Của Một Quan Hệ
Tìm Khóa Tối Thiểu Của Một Quan Hệ
Cơ Sở Dữ Liệu - 5 - Tìm Khóa Tối Thiểu Của Quan Hệ - Youtube
Cơ Sở Dữ Liệu – 5 – Tìm Khóa Tối Thiểu Của Quan Hệ – Youtube
Phương Pháp Bình Phương Tối Thiểu (Least Squares Method) Là Gì? Đặc Điểm Và  Ví Dụ
Phương Pháp Bình Phương Tối Thiểu (Least Squares Method) Là Gì? Đặc Điểm Và Ví Dụ
Bài Tập Tính Khóa Của Lược Đồ Quan Hệ
Bài Tập Tính Khóa Của Lược Đồ Quan Hệ
Lương Tối Thiểu Là Gì? Vai Trò Của Lương Tối Thiểu Như Thế Nào?
Lương Tối Thiểu Là Gì? Vai Trò Của Lương Tối Thiểu Như Thế Nào?
Icsi: Lựa Chọn Tối Ưu Cho Trường Hợp Thiểu Tinh Nặng – Cryptozoospermia -  Family Hospital
Icsi: Lựa Chọn Tối Ưu Cho Trường Hợp Thiểu Tinh Nặng – Cryptozoospermia – Family Hospital
Bộ Phận Chống Đau Của Khoa Gây Mê Hồi Sức Phải Có Tối Thiểu Bao Nhiêu Bác  Sĩ? Nhiệm Vụ Của Bác Sĩ Và Điều Dưỡng Tại Bộ Phận Chống Đau Là
Bộ Phận Chống Đau Của Khoa Gây Mê Hồi Sức Phải Có Tối Thiểu Bao Nhiêu Bác Sĩ? Nhiệm Vụ Của Bác Sĩ Và Điều Dưỡng Tại Bộ Phận Chống Đau Là
Tổng Hợp Mức Lương Tối Thiểu Vùng Qua Các Năm
Tổng Hợp Mức Lương Tối Thiểu Vùng Qua Các Năm
Seo Là Gì? Tổng Quan Về Search Engine Optimization Từ A-Z
Seo Là Gì? Tổng Quan Về Search Engine Optimization Từ A-Z
Khóa Điện Tử Kassler Kl-655 Copper | Thế Giới Khoá Thông Minh
Khóa Điện Tử Kassler Kl-655 Copper | Thế Giới Khoá Thông Minh
Số Tiền Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? | Vib
Số Tiền Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? | Vib
Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? Tìm Hiểu Các Quy Định Liên Quan |  Techcombank
Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? Tìm Hiểu Các Quy Định Liên Quan | Techcombank
Lương Tối Thiểu Vùng Là Gì Và 05 Điều Cần Lưu Ý?
Lương Tối Thiểu Vùng Là Gì Và 05 Điều Cần Lưu Ý?
Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? Vì Sao Phải Trả Đúng Hạn
Thanh Toán Tối Thiểu Thẻ Tín Dụng Là Gì? Vì Sao Phải Trả Đúng Hạn

See more here: kientrucannam.vn

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *