advertisement

Csdl Nangcao

50 %
50 %
advertisement
Information about Csdl Nangcao

Published on June 14, 2008

Author: hcdung18

Source: slideshare.net

advertisement

CƠ SỞ DỮ LIỆU NÂNG CAO LÝ THUYẾT PHỤ THUỘC HÀM Thầy giảng dạy: TS. Hoàng Quang

Tại sao phải nghiên cứu LTPTH? DƯ THỪA DL DỊ THƯỜNG DƯ THỪA DL DỊ THƯỜNG

MỘT SỐ CÁC ĐỊNH NGHĨA TRONG LÝ THUYẾT PHỤ THUỘC HÀM

Phụ thuộc hàm r thỏa A  C r thỏa B  C A B C r = a b c b d c a e c X  Y  t 1 , t 2  r : t 1 [X] = t 2 [X]  t 1 [Y] = t 2 [Y]

Lược đồ quan hệ thoả mãn phụ thuộc hàm KHÔNG THỎA MÃN X  Y Stop R= <U, SC> Or R= < U, F >

Bao đóng của tập phụ thuộc hàm R = <U, F>. F + là tập tất cả các phụ thuộc hàm hệ quả của F F + = {X  Y | F╞ X  Y} F  F +

R = <U, F>. F + là tập tất cả các phụ thuộc hàm hệ quả của F

F + = {X  Y | F╞ X  Y}

F  F +

Khoá của lược đồ quan hệ R = <U, F>, X  U. X là khoá của R nếu: 1.X  U ( siêu khoá ) 2. Không  X’  X : X’ là siêu khoá của R Ví dụ : R = <U, F> U = ABC; F = {A  B, B  C} {A} là khoá của R

R = <U, F>, X  U. X là khoá của R nếu:

1.X  U ( siêu khoá )

2. Không  X’  X : X’ là siêu khoá của R

Hệ tiên đề Amstrong Cho R = <U, F> -   (X, Y  U ) (X  Y) : Y  X  F + -   (X, Y, Z  U) (X  Y)  F +: XZ  YZ  F + -    (X, Y, Z  U) (X  Y  F + , Y  Z  F +): X  Z  F +

Cho R = <U, F>

-   (X, Y  U ) (X  Y) : Y  X  F +

-   (X, Y, Z  U) (X  Y)  F +: XZ  YZ  F +

-    (X, Y, Z  U) (X  Y  F + , Y  Z  F +): X  Z  F +

Hệ tiên đề Amstrong (2) Ví dụ : R =<U, F>, U =ABC, F = {A  B, A  C} Chứng minh: A  BC  F + A  B (1) A  C (2) Từ (1)  A  AB (3) (Luật gia tăng) Từ (2)  AB  BC (4) (Luật gia tăng) Từ (3) & (4)  A  BC (Luật bắc cầu)  đpcm

Ví dụ : R =<U, F>, U =ABC, F = {A  B, A  C}

Chứng minh: A  BC  F +

A  B (1)

A  C (2)

Từ (1)  A  AB (3) (Luật gia tăng)

Từ (2)  AB  BC (4) (Luật gia tăng)

Từ (3) & (4)  A  BC (Luật bắc cầu)

 đpcm

Bao đóng của tập thuộc tính (X + ) Ví dụ F = {A  B, B  C} A + F = ABC (AB) + = ABC R = <U, F> và X, Y  U. Khi đó: X  Y  F +  Y  X + F X + = {A | X  A  F + }=X + F

Ví dụ

F = {A  B, B  C}

A + F = ABC

(AB) + = ABC

R = <U, F> và X, Y  U. Khi đó: X  Y  F +  Y  X + F

Hai tập phụ thuộc hàm tđương Cho F & G. F  G nếu và chỉ nếu F + = G + Ý tưởng đề kiểm chứng F  G F+ G G+ F &

Cho F & G. F  G nếu và chỉ nếu F + = G +

Ý tưởng đề kiểm chứng F  G

Hai tập phụ thuộc hàm tđương (2) Ví dụ : Kiểm tra F và G có tđương hay ko F={A  BC}, G={A  B, A  C

  • {Kiểm tra F  G + } A  B :A + F = ABC B A  C: A + F = ABC C {Kiểm tra G  F + } A  BC: A + G = ABC BC Vậy F tđ với G

    Ví dụ : Kiểm tra F và G có tđương hay ko

    F={A  BC}, G={A  B, A  C
  • {Kiểm tra F  G + }

    A  B :A + F = ABC B

    A  C: A + F = ABC C

    {Kiểm tra G  F + }

    A  BC: A + G = ABC BC

    Vậy F tđ với G

    Phủ cực tiểu của một lược đồ quan hệ (1) Cho R = <U, F>, F được gọi là phủ cực tiểu của R khi và chỉ khi: Vế phải chỉ có 1 thuộc tính Không có thuộc tính dư thừa ở vế trái Không có phụ thuộc hàm dư thừa

    Cho R = <U, F>, F được gọi là phủ cực tiểu của R khi và chỉ khi:

    Vế phải chỉ có 1 thuộc tính

    Không có thuộc tính dư thừa ở vế trái

    Không có phụ thuộc hàm dư thừa

    Phủ cực tiểu của một lược đồ quan hệ (2) b)   X  A  F,  B  X  ((F {X  A} )  (X {B}  A)) +  F +   X  A  F,  B  X: X{B}  A  F +   X  A  F,  B  X: (X {B}) + A       c)   X  A  F: X  A  (F {X  A}) +   X  A  F, X + F{X  A} A

    b)   X  A  F,  B  X

     ((F {X  A} )  (X {B}  A)) +  F +

      X  A  F,  B  X: X{B}  A  F +

      X  A  F,  B  X: (X {B}) + A

         

    c)   X  A  F: X  A  (F {X  A}) +

      X  A  F, X + F{X  A} A

    Phủ cực tiểu của tập phụ thuộc hàm R = <U, F>. G đgl 1 phủ cực tiểu của F nếu thoả 2 điều kiện: G  F G là phủ cực tiểu của R’ = <U, G> Phủ cực tiểu của 1 phụ thuộc hàm là không duy nhất

    R = <U, F>. G đgl 1 phủ cực tiểu của F nếu thoả 2 điều kiện:

    G  F

    G là phủ cực tiểu của R’ = <U, G>

    Phủ cực tiểu của 1 phụ thuộc hàm là không duy nhất

    Giải thuật tìm phủ cực tiểu Bước 1 Bước 2 For (mỗi X  A  F) do For (mỗi B  X) do If ((X {B}) + F  A) then X := X {B};

    Giải thuật tìm phủ cực tiểu

    Bước 1

    Giải thuật (tt) Bước 3 For (mỗi X  A  F) do If (X + F{X  A}  A) then F := F {X  A}; Kết luận : G := F;

    Giải thuật (tt)

    Bước 3

    For (mỗi X  A  F) do

    If (X + F{X  A}  A) then

    F := F {X  A};

    Kết luận : G := F;

    Ví dụ Tìm phủ cực tiểu của tập PTH R = <U, F>,U = ABD, F ={B  A, D  A, AB  D} AB  D B + F = BAD  D  loại bỏ A F = {B  A, B  D, D  A} B  D B + F{B  D} = BA D B  A B + F{B  A} = BDA  A  loại bỏ B  A  F = {D  A, B  D} D  A D + F{D  A} = D A Kết luận: F = {D  A, B  D}

    AB  D

    B + F = BAD  D  loại bỏ A

    F = {B  A, B  D, D  A}

    B  D

    B + F{B  D} = BA D

    B  A

    B + F{B  A} = BDA  A  loại bỏ B  A

     F = {D  A, B  D}

    D  A

    D + F{D  A} = D A

    Khóa của lược đồ Định lý Hồ Thuần - Nguyễn Văn Bào (Điều kiện cần để X là khoá) (U P)  X  (U P)  (T  P)  Function Key(R) 1.       Xđịnh T 2.       Xác định P 3.        X := (U P)  (T  P) (X:= S) 4.        For <mỗi A  (T  P)> do (A  S  T  P ) 5.        If <(X A) F + = U> then X := X A; Return X .

    Định lý Hồ Thuần - Nguyễn Văn Bào (Điều kiện cần để X là khoá)

    (U P)  X  (U P)  (T  P)

     Function Key(R)

    1.       Xđịnh T

    2.       Xác định P

    3.        X := (U P)  (T  P) (X:= S)

    4.        For <mỗi A  (T  P)> do (A  S  T  P )

    5.        If <(X A) F + = U> then

    X := X A; Return X .

    Giải thuật xác định tất cả các khoá của 1 lược đồ quan hệ Định lý Lucchesi và Osborn: (Điều kiện cần và đủ để bổ sung khoá) R = <U, F>. K là 1 tập khác rỗng các khoá của lược đồ quan hệ R. Điều kiện cần và đủ để bổ sung khoá mới vào K là:  k  K  X  Y  F sao cho T = X  (K Y) không chứa phần tử nào của K.

    Định lý Lucchesi và Osborn: (Điều kiện cần và đủ để bổ sung khoá)

    R = <U, F>. K là 1 tập khác rỗng các khoá của lược đồ quan hệ R. Điều kiện cần và đủ để bổ sung khoá mới vào K là:

     k  K

     X  Y  F

    sao cho T = X  (K Y) không chứa phần tử nào của K.

    Giải thuật Tìm 1 khoá k  K ; K := {R}; For <mỗi k  K> For <mỗi X  Y  F> do T := X  (K Y) ; If < T không chứa phần tử nào của K > then Tìm khoá k ’ nhận T làm siêu khoá ; K + := K  {K ’ }

    Tìm 1 khoá k  K ;

    K := {R};

    For <mỗi k  K>

    For <mỗi X  Y  F> do

    T := X  (K Y) ;

    If < T không chứa phần tử nào của K > then

    Tìm khoá k ’ nhận T làm siêu khoá ;

    K + := K  {K ’ }

    Giải thuật (2) goto 3; EndIf; EndFor; EndFor; Return;

    goto 3;

    EndIf;

    EndFor;

    EndFor;

    Return;

    Xin chân thành cảm ơn thầy và các bạn đã tham gia thảo luận!

Add a comment

Related pages

CSDL NangCao - Google+

CSDL NangCao hasn't shared anything on this page with you.
Read more

HỌC VIỆN KỸ THUẬT QUÂN SỰ

CSDL đa phương tiện. CSDL hướng đối tượng. Đồ án môn học sẽ được giao cho sinh viên thực hiện trong quá trình học
Read more

BỘ MÔN DUYỆT

Chủ nhiệm Bộ môn. Ngô Thành Long ĐỀ CƯƠNG CHI TIẾT BÀI GIẢNG (Dùng cho 60 tiết giảng) Học phần: CƠ SỞ DỮ LIỆU NÂNG CAO
Read more

Bổ túc kiến thức Nhập Môn CSDL

Bổ túc kiến thức Nhập Môn CSDL Tuần1: Giớithiệuhệcơsởdữliệu–môhìnhdữ liệuquanhệ –SQL cănbản
Read more

Mở lớp học Excel Nâng Cao tại Hà Nội, Khai ...

Bluesofts mở lớp học Excel Nâng Cao tại Hà Nội, khai giảng: 18h30 ngày 1,3 tháng 3/2016 http://bluesofts.net/Products/daotao/excel/nangcao ...
Read more

Mở lớp học Excel NÂNG CAO - Hà Nội, khai giảng ...

MỞ LỚP EXCEL NÂNG CAO http://bluesofts.net/Products/daotao/excel/nangcao/pic/banner2.png Khóa học “Excel nâng cao”cung cấp các kiến ...
Read more

tin hoc chung chi quoc gia ABC

Tổ chức CSDL với Microsoft Access, xây dựng truy vấn, rút trích, ..., màn hình nhập liệu và tạo dựng báo biểu, biểu đồ, ...
Read more