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Ụ THUỘC HÀM (CSDL)

    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: 109.0 KB
    Số lượt tải: 68
    Số lượt thích: 0 người
    THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ (Relational Database Designing)
    Phần IV – PHỤ THUỘC HÀM
    (Functional Dependency)
    Phụ thuộc hàm – Khái niệm
    Phụ thuộc hàm là công cụ để biểu diễn hình thức các RBTV phụ thuộc.
    Các lý thuyết về Phụ thuộc hàm ứng dụng nhiều trong bài toán Chuẩn Hóa CSDL.
    Ký hiệu :
    X  Y : Y phụ thuộc hàm vào X hay X xác định Y.
    với X, Y là các tập thuộc tính (trong 1 lược đồ quan hệ).
    Khái niệm về Phụ thuộc hàm
    Phụ thuộc hàm – Định nghĩa
    Cho Q(A1,A2,…,An); X, Y là 2 tập con của Q+; q là 1 quan hệ trên Q; t1, t2 là 2 bộ bất kỳ của q.
    Ta có X xác định Y , ký hiệu X  Y , nghĩa là
    (t1.X=t2.X => t1.Y=t2.Y)
    Nếu 2 bộ bất kỳ trong q giống nhau trên X thì phải giống nhau trên Y.
    X  Y là PTH của Q, khi X  Y đúng với mọi q là quan hệ trên Q
    Hệ quả : Q, X  Q+ , X  

    Định nghĩa về Phụ thuộc hàm
    Phụ thuộc hàm hiển nhiên (Trivial Dependencies)
    Nếu X  Y thì XY luôn đúng
    Trong trường hợp này (X  Y), XY được gọi là Phụ thuộc hàm hiển nhiên.
    Ví dụ : XX

    Khi chuẩn hóa CSDL, ta thường không quan tâm đến các PTH hiển nhiên.
    Phụ thuộc hàm hiển nhiên
    Thuật toán kiểm tra PTH : Satifies
    Input : _ Quan hệ q,
    _ Tập thuộc tính X, Y

    Output :
    _ True nếu XY, ngược lại, False
    Thuật toán kiểm tra Phụ thuộc hàm (p.1)
    Thuật toán kiểm tra PTH (t.t)
    Bước 1 :
    Sắp lại các bộ trong q sao cho các bộ giống nhau trên X nằm kề nhau.

    Bước 2 :
    Kiểm tra nếu tất cả các bộ giống nhau trên X cũng giống nhau trên Y thì trả về True, ngược lại, trả về False.
    Thuật toán kiểm tra Phụ thuộc hàm (p.2)
    Hệ luật dẫn Amstrong(Amstrong inference rule) - Một số định nghĩa
    Ký hiệu F là tập các phụ thuộc hàm của lược đồ quan hệ Q, F = {f1,f2,…,fn}, quy ước ta không quan tâm đến các phụ thuộc hàm hiển nhiên.
    Định nghĩa : Phụ thuộc hàm được suy diễn logic từ F.
    Phụ thuộc hàm d = XY được suy diễn logic từ F nếu với mọi q trên Q thỏa F thì cũng thỏa d, ký hiệu F |= XY , hay F|=d.
    Định nghĩa : Bao đóng của F(Closure), ký hiệu F+, là tập tất cả các phụ thuộc hàm được suy diễn logic từ F
    Hệ luật dẫn Amstrong (p.1)
    Các tính chất của Bao đóng F+
    Tính phản xạ
    Với mọi F+, ta luôn có F  F+
    Tính đơn điệu
    Nếu F  G thì F+  G+
    Tính lũy đẳng
    Với mọi F, ta luôn có (F+)+ = F+
    Định nghĩa : Phủ của F, ký hiệu F- = G - F+, với G là tập tất cả các phụ thuộc hàm có thể có của Q
    Hệ luật dẫn Amstrong (p.2)
    Hệ luật dẫn Amstrong
    Cho X,Y,Z,W là các tập con của Q+; q là 1 quan hệ bất kỳ trên Q.

    Luật phản xạ (Reflexive rule) : X  X
    Luật thêm vào (Augmentation rule) : X  Y => XZ  Y
    Luật hợp (Union rule) : X  Y, X  Z => X  YZ
    Luật phân rã (Decomposition rule) : X  YZ => X  Y, X  Z
    Luật bắt cầu (Transitive rule) : X  Y, Y  Z => X  Z
    Luật giả bắt cầu (Pseudo transitive rule) :
    X  Y, YZ  W => XZ  W
    Hệ luật dẫn Amstrong (p.3)
    Bao đóng của tập thuộc tính
    Cho lược đồ quan hệ Q(A1,A2,…,An) với quan hệ q; F là tập phụ thuộc hàm trên Q, X là 1 tập con của Q+.
    Định nghĩa : Bao đóng của X trên F, ký hiệu XF+, là tập các thuộc tính Ai :
    XF+= Ai với XAi được suy diễn từ F nhờ hệ luật dẫn Amstrong.

    Khi không có nhầm lẫn về F, ta viết X+ thay vì XF+
    Hệ luật dẫn Amstrong (p.4)
    Các tính chất của Bao đóng
    Hệ quả : Bao đóng của Q chính là Q+ : QF+ = Q+
    Tính phản xạ : X  X+
    Tính đơn điệu : X  Y => X+  Y+
    Tính lũy đẳng : (X+)+ = X+
    (XY)+  X+Y+
    (X+Y)+ = (XY+)+ = (X+Y+)+
    X  Y  Y+  X+
    X  X+, X+  X
    X+ = Y+  X  Y và Y  X

    Hệ luật dẫn Amstrong (p.5)
    Thuật toán tìm Bao đóng
    Input : lược đồ quan hệ Q, tập phụ thuộc hàm F, tập thuộc tính X.
    Output : X+
    Bước 1 : i = 0, Xi = X
    Bước 2 : Duyệt tập F,
    Nếu Fk = YZ có Y  Xi thì
    Xi+1 = Xi  Z và F = F Fk
    Bước 3 : Nếu Xi+1  Xi :
    i = i+1, trở lại bước 2
    Nếu Xi+1 = Xi : kết thúc
    Hệ luật dẫn Amstrong (p.6)
    Thuật toán tìm Bao đóng – Ví dụ
    Cho : Q(ABCDEGH), F = {
    f1: B  A
    f2: DA  CE
    f3: D  H
    f4: GH  C
    f5: AC  D
    }
    X = {AC} , tìm X+ ?
    Hệ luật dẫn Amstrong (p.7)
    Tìm Bao đóng - Ví dụ (t.t)
    Hệ luật dẫn Amstrong (p.8)
    Thuật toán Kiểm tra F|=d
    Cho d = XY, kiểm tra F|=d ?
    Bước 1 : Tính X+=XF+
    Bước 2 : Y  X+ <=> F|=d
    Hệ luật dẫn Amstrong (p.9)
    Tính chất của các PTH  F+
    Xét d = XY  F+ , => F |= d hay F+ |= d
    F |= d, => Y  XF+ (1)
    Gọi TN là tập các thuộc tính có xuất hiện ở vế trái của ít nhất 1 PTH trong F
    Từ thuật toán tìm bao đóng của tập thuộc tính, ta có kết luận rằng : Nếu X  TN => XF+ = X (2)
    Hệ luật dẫn Amstrong (p.10)
    Thuật toán tìm F+
    Input : Lược đồ Q, tập PTH F
    Output : Tập PTH F+
    Bước 1 : F+ = , Tìm tất cả các tập con của TN
    Bước 2 : Ứng với mỗi tập con X của TN:
    2.1 Tính XF+
    2.2 Tìm tất cả các tập con Y của XF+ và Y  X
    2.3 F+ = F+ + XY
    Hệ luật dẫn Amstrong (p.11)
     
    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