TUYỂN SINH

THÔNG TIN TUYỂN SINH Thông tin tuyển sinh 2013

T.T ngoại ngữ Tin học

Trung tâm Ngoại ngữ - Tin học tuyển sinh 2013

Tài Nguyên

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • PHỦ CỦA TẬP PHỤ THUỘC HÀM

    Wait
    • Begin_button
    • Prev_button
    • Play_button
    • Stop_button
    • Next_button
    • End_button
    • 0 / 0
    • Loading_status
    Nhấn vào đây để tải về
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn: sưu tầm
    Người gửi: Võ Thị Kim Chi
    Ngày gửi: 09h:18' 16-07-2013
    Dung lượng: 74.0 KB
    Số lượt tải: 31
    Số lượt thích: 0 người
    THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ (Relational Database Designing)
    Phần V – PHỦ CỦA TẬP PHỤ THUỘC HÀM

    Một số định nghĩa
    Cho F, G là 2 tập phụ thuộc hàm,
    F và G gọi là tương đương nếu và chỉ nếu F+=G+
    Ký hiệu : F  G

    F gọi là phủ G nếu và chỉ nếu
    F+  G+
    2 tập Phụ thuộc hàm tương đương
    Thuật toán kiểm tra F  G
    Bước 1 : Tính F+, G+
    Bước 2 : Nếu F+ = G+, => F  G

    Thuật toán kiểm tra F  G
    Phủ tối thiểu (minimal cover) –Tập Phụ thuộc hàm không đầy đủ
    Cho lược đồ Q, tập PTH F, ZY  F.

    ZY gọi là có vế trái dư thừa hay Y phụ thuộc không đầy đủ vào Z hay ZY là phụ thuộc hàm không đầy đủ nếu và chỉ nếu :
    A  Z: F  (F {ZY})  {(Z-A)Y}
    Ngược lại, ZY gọi là phụ thuộc hàm đầy đủ hay không có vế trái dư thừa.
    F được gọi (tắt) là có vế trái không dư thừa, nếu F không chứa PTH có vế trái dư thừa.
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.1)
    Phụ thuộc hàm không đầy đủ - Ví dụ
    Cho Q(ABC), F={ABC, BC}
    Xét ABC :
    F’ = F – {ABC} = {BC}
    (AB-A)C = {BC}
    => F’ = (F – {ABC})  {(AB-A)C} = {BC}
    Tính (F’)+ , ta có (F’)+ = {ABC,BC}
    Tính F+ = F = {ABC, BC}
    => F+ = (F’)+
    => ABC là phụ thuộc hàm có vế trái dư thừa
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.2)
    Thuật toán loại khỏi F các PTH không đầy đủ
    Bước 1 : Tính F+
    Bước 2 : Duyệt tập F, với mọi d = XY F :
    Bước 2.1 : Duyệt các tập con X’ của X :
    Nếu X’Y  F+ : thay X = X’, lặp lại 2.1
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.3)
    Tập phụ thuộc hàm có vế phải 1 thuộc tính
    Định nghĩa : F được gọi là tập phụ thuộc hàm có vế phải 1 thuộc tính nếu và chỉ nếu mọi phụ thuộc hàm trong F đều có vế phải chỉ 1 thuộc tính.
    Ví dụ : F = {ABC,BC,ABD}, ta tách các phụ thuộc hàm trong F để F thỏa tiêu chuẩn là tập phụ thuộc hàm có vế phải 1 thuộc tính :
    F = {AB, AC, BC, ABD}
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.4)
    Tập phụ thuộc hàm không dư thừa
    Định nghĩa : F được gọi là tập phụ thuộc hàm không dư thừa 
    Không  F’  F, F’ F
    Ngược lại, F được gọi là tập phụ thuộc hàm dư thừa.
    Ví dụ : F = {ABC, BD, ABD}
    F dư thừa vì F  F’ = {ABC, BD}
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.5)
    Thuật toán loại khỏi F các PTH dư thừa
    Duyệt từng PTH XY thuộc F :
    Nếu (F-{XY}) |= XY thì F = F-{XY}

    Ví dụ : F = {ABC, BD, ABD}
    Xét ABC : {BD, ABD} không thể |= ABC
    Xét BD : {ABC, ABD} không thể |= BD
    Xét ABD : {ABC,BD} |= ABD vì :
    ABC => AB, do BD => AD => ABD
    Vậy ABD là dư thừa trong F, => F = {ABC,BD}
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.6)
    Tập PTH tối thiểu
    Định nghĩa : F được gọi là một tập PTH tối thiểu (hay F là 1 phủ tối thiểu) nếu và chỉ nếu F thỏa 3 điều kiện sau :
    F là tập PTH có vế trái không dư thừa.
    F là tập PTH có vế phải 1 thuộc tính.
    F là tập PTH không dư thừa.
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.7)
    Thuật toán tìm Phủ tối thiểu
    Bước 1 :
    Loại khỏi F các PTH có vế trái dư thừa.
    Bước 2 :
    Tách các PTH có vế phải nhiều hơn 1 thuộc tính thành các PTH có vế phải 1 thuộc tính.
    Bước 3 :
    Loại khỏi F các PTH dư thừa.
    Luôn tìm được ít nhất 1 PTH tối thiểu của 1 tập PTH bất kỳ.
    Có thể tìm được nhiều PTH tối thiểu của 1 tập PTH bất kỳ.
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.8)
    Thuật toán tìm PTT – Ví dụ
    Input : Q(ABCD), F = {ABCD, BC, CD}
    Output : Fm = PTT của F
    Bước 1 :
    ABCD là PTH không đầy đủ, vì A là dư thừa trong vế trái: BC, CD => BCD.
    => F = {BCD, BC, CD}
    Bước 2 :
    F = {BC, BD, BC, CD}
    Bước 3 :
    F = {BC, CD}
    Phủ tối thiểu của 1 tập phụ thuộc hàm (p.9)
    Khóa(Key) của lược đồ quan hệ
    Cho Q(A1,A2,…,An), tập PTH F, K là 1 tập con của Q+
    Định nghĩa : K là 1 siêu khóa của Q nếu
    KF+ = Q+
    Định nghĩa : K là 1 khóa của Q nếu
    KF+ = Q+
    Không tồn tại K’  K , K’F+ = Q+
    Khóa của lược đồ quan hệ (p.1)
    Thuật toán tìm khóa của LDQH
    Input : Lược đồ quan hệ Q, tập PTH F
    Output : K là 1 khóa của Q
    Bước 1 : gán K = Q+
    Bước 2 : Duyệt các thuộc tính A trong K,
    _ Tính K’+ với K’ = K-A
    _ Nếu K’+ = Q+, gán K = K’
     Khóa K tìm được có thể không là khóa duy nhất của Q
    Khóa của lược đồ quan hệ (p.2)
    Tính chất của khóa
    Ký hiệu :
    Tập nguồn (TN) : chứa tất cả các thuộc tính chỉ xuất hiện ở vế trái của các PTH trong F.
    Tập đích (TD) : chứa tất cả các thuộc tính chỉ xuất hiện ở vế phải của các PTH trong F.
    Tập trung gian (TG) = Q+ - TN – TD
    Tính chất : Nếu K là 1 khóa của Q, thì
    TN  K và TD  K = 
    Khóa của lược đồ quan hệ (p.3)
    Tính chất của khóa – Chứng minh
    Chứng minh TN  K :
    Giả sử TN không  K, => tồn tại 1 PTH XYF và X không  K và không tồn tại 1 PTH ZV F sao cho X  V
    Dựa trên thuật toán tìm bao đóng của tập thuộc tính K => X không xuất hiện trong Ki nào => XK+F => trái với giả thiết (K là khóa, nên XK+F)
    Khóa của lược đồ quan hệ (p.4)
    Tính chất của khóa – Chứng minh (t.t)
    Chứng minh TD  K =  :
    Giả sử TD  K   => A: A  TD  A  K
    A  TD => tồn tại 1 PTH XAF (1)
    AK => K+=(K-A)+A ;
    X K+X(K-A)+A ;
    AX vì XA không là PTH hiển nhiên (xem slide 4 chương 4) => X(K-A)+ => K-AX (2)
    (1) và (2) => K-AA => (K-A)+ = [(K-A)A]+=K+ => vô lý vì K là khóa.
    Khóa của lược đồ quan hệ (p.5)
    Thuật toán tìm tất cả các khóa
    Bước 1 : Tạo tập TN, TG
    Bước 2 : Nếu TG= => Q chỉ có 1 khóa K = TN, kết thúc thuật toán.
    Bước 3 : Tìm tất cả tập con Xi của TG, đặt Si=TNXi , tính Si+. Gọi L là tập tất cả các Si
    Bước 4 : Duyệt tập Si, nếu Si+<>Q+ thì bỏ Si khỏi L.
    Bước 5 : Với mọi Sk,Sl  L, nếu Sk Sl thì bỏ Sk khỏi L.
     Tập L còn lại chính là tập tất cả các khóa của Q.
    Khóa của lược đồ quan hệ (p.6)
     
    Gửi ý kiến

    Hình ảnh thiết bị phòng thực hành Điện dân dụng và công nghiệp