MÔ HÌnh quan hệ nguyên nhân ra đỜi của mô HÌnh quan hệ



tải về 1.86 Mb.
trang9/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   ...   5   6   7   8   9   10   11   12   ...   17

----oOo----

  1. .

PHỦ CỦA TẬP PHỤ THUỘC HÀM

    1. ĐỊNH NGHĨA

Nói rằng hai tập phụ thuộc hàm F và G là tương đương (Equivalent) nếu F = G+ ký hiệu F  G.

Ta nói F phủ G nếu F+  G+



Thuật toán xác định F và G có tương đương không

Bước 1: Với mỗi phụ thuộc hàm XY của F ta xác định xem XY có là thành viên của G không

Bước 2: Với mỗi phụ thuộc hàm XY của G ta xác định xem XY có là thành viên của F không

Nếu cả hai bước trên đều đúng thì F  G

Ví dụ 1: Cho lược đồ quan hệ Q(ABCDE) hai tập phụ thuộc hàm:

F={ABC,AD,CDE} và G = {ABCE,AABD,CDE}

a) F có tương đương với G không?

b) F có tương đương với G’={ABCDE} không?



Giải:

a) Ta có =ABCDE  trong G+ có ABC và AD  F  G+  F+  G+ (1). =ABCDE  trong F+ có ABCE và AABD  F+  G  F+  G+ (2) (1) và(2)  F+ = G+  F  G.

b) Do = CD  G’+ không chứa phụ thuộc hàm CDE  F không tương đương với G’


    1. PHỦ TỐI THIỂU CỦA MỘT TẬP PHỤ THUỘC HÀM (minimal cover)

      1. Phụ thuộc hàm có vế trái dư thừa

F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, Z là tập thuộc tính, ZYF. Nói rằng phụ thuộc hàm Z Y có vế trái dư thừa (phụ thuộc không đầy đủ) nếu có một AZ sao cho:

F  F-{Z  Y}{(Z-A)  Y}

Ngược lại Z  Y là phụ thuộc hàm có vế trái không dư thừa hay Y phụ thuộc hàm đầy đủ vào Z hay phụ thuộc hàm đầy đủ.

Ví dụ 2: Q(A,B,C) F={ABC; BC}

F  F-{ABC}{(AB-A)C}={BC}

AB  C là phụ thuộc hàm không đầy đủ

B  C là phụ thuộc hàm đầy đủ



Chú ý: phụ thuộc hàm có vế trái chứa một thuộc tính là phụ thuộc hàm đầy đủ.
Ví dụ 3: cho tập phụ thuộc hàm F = {A  BC,B  C,AB  D} thì phụ thuộc hàm ABD có vế trái dư thừa B vì:

F  F – {AB  D}{A  D}

 {A  BC,B  C,A  D}

Ta nói F là tập phụ thuộc hàm có vế trái không dư thừa nếu F không chứa phụ thuộc hàm có vế trái dư thừa.

Thuật toán loại khỏi F các phụ thuộc hàm có vế trái dư thừa.

Bước 1: lần lượt thực hiện bước 2 cho các phụ thuộc hàm XY của F

Bước 2:Với mọi tập con thật sự X’ của X.

Nếu X'Y F+ thì thay XY trong F bằng X'Y thực hiện lại bước 2

Ví dụ: Ở ví dụ 3 phụ thuộc hàm ABD có A+=ABCD  ADF+. Trong F ta thay ABD bằng AD  F  {A  BC,B  C,A  D}


      1. Tập phụ thuộc hàm có vế phải một thuộc tính (the right sides of dependencies has a single attribute)

Mỗi tập phụ thuộc hàm F đều tương đương với một tập phụ thuộc hàm G mà vế phải của các phụ thuộc hàm trong G chỉ gồm một thuộc tính.

Ví dụ 4: cho F = {A  BC,B  C,AB  D} ta suy ra

F  {A  B, A  C ,B  C,AB  D} = G

G được gọi là tập phụ thuộc hàm có vế phải một thuộc tính.


      1. Tập phụ thuộc hàm không dư thừa

Nói rằng F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’ F sao cho F’ F. Ngược lại F là tập phụ thuộc hàm dư thừa.

Ví du: cho F = {ABC, BD, ABD} thì F dư thừa vì

F  F’= {ABC, BD}


Thuật toán loại khỏi F các phụ thuộc hàm dư thừa:

Bước 1: Lần lượt xét các phụ thuộc hàm X  Y của F

Bước 2: nếu X  Y là thành viên của F - {X  Y} thì loại X  Y khỏi F

Bước 3: thực hiện bước 2 cho các phụ thuộc hàm tiếp theo của F

      1. Tập phụ thuộc hàm tối thiểu (minimal cover)

F được gọi là một tập phụ thuộc hàm tối thiểu (hay phủ tối thiểu) nếu F thỏa đồng thời ba điều kiện sau:

  1. F là tập phụ thuộc hàm có vế trái không dư thừa

  2. F là tập phụ thuộc hàm có vế phải một thuộc tính.

  3. F là tập phụ thuộc hàm không dư thừa


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

Bước 1: loại khỏi F các phụ thuộc hàm có vế trái dư thừa.

Bước 2: Tách các phụ thuộc hàm có vế phải trên một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính.

Bước 3: loại khỏi F các phụ thuộc hàm dư thừa.
Chú ý: Theo thuật toán trên, từ một tập phụ thuộc hàm F luôn tìm được ít nhất một phủ tối thiểu Ftt để FFtt và nếu thứ tự loại các phụ thuộc hàm trong tập F là khác nhau thì có thể sẽ thu được những phủ tối thiểu khác nhau.

Ví dụ 5: Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc F như sau:

F={AB  CD,B  C,C  D}

Hãy tính phủ tối thiểu của F.

Giải:

Bước 1: ABCD là phụ thuộc hàm có vế trái dư thừa?

B  CD  F+? trả lời: B+=BCD  B  CD  F+

Vậy AB  CD là phụ thuộc hàm có vế trái dư thừa A  kết quả của bước 1 là:

F{B  CD;B  C;C  D}



Bước 2: kết quả của bước 2 là:

F{B  D; B  C;C  D}=F1tt



Bước 3: trong F1tt, B  C là phụ thuộc hàm dư thừa?

B  C  G+? với G = F1tt - {B  C}={B  D;C  D}

BG+=BD  B  C  G+  trong F1tt B  C không dư thừa.

trong F1tt,B  D là phụ thuộc hàm dư thừa?

B  D  G+? với G = F1tt - {B  D}={B  C;C  D}

BG+=BCD  B  D  G+  trong F1tt,B  D dư thừa.

kết quả của bước 3 cho phủ tối thiểu:

F{B  C;C  D}=Ftt



Ví dụ 6: Cho lược đồ quan hệ Q(MSCD,MSSV,CD,HG) và tập phụ thuộc F như sau:

F = {MSCD  CD;

CD  MSCD;

CD,MSSV  HG;

MSCD,HG  MSSV;

CD,HG  MSSV;

MSCD,MSSV  HG}

Hãy tìm phủ tối thiểu của F



kết quả:

Ftt = {MSCD  CD;

CD  MSCD;

CD,HG  MSSV;

MSCD,MSSV  HG}


    1. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

      1. Định Nghĩa

Q(A1,A2,…,An)là lược đồ quan hệ.

Q+ là tập thuộc tính của Q.

F là tập phụ thuộc hàm trên Q.

K là tập con của Q+.



Nói rằng K là một khóa của Q nếu:

  1. K+ = Q+

  2. Không tồn tại K'  K sao cho K’+= Q+

Tập thuộc tính S được gọi là siêu khóa nếu S  K

Thuộc tính A được gọi là thuộc tính khóa nếu AK với K là khóa bất kỳ của Q. Ngược lại A được gọi là thuộc tính không khóa.
Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa cũng có thể bằng rỗng.

(Khi thiết kế một hệ thống thông tin, thì việc lập lược đồ cơ sở dữ liệu đạt đến một tiêu chuẩn nào đó là một việc làm quan trọng. Việc xác định chuẩn cho một lược đồ quan hệ có liên quan mật thiết với thuật toán tìm khóa).



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

Bước 1: gán K = Q+

Bước 2: A là một thuộc tính của K, đặt K’ = K  A. Nếu K’+= Q+ thì gán K = K' thực hiện lại bước 2

Nếu muốn tìm các khóa khác (nếu có) của lược đồ quan hệ, ta có thể thay đổi thứ tự loại bỏ các phần tử của K.



Ví dụ 7:

Q(A,B,C,D,E,G,H,I)F={AC B;BI  ACD;ABCD;HI;ACEBCG;CGAE}

Tìm K

Lần lượt loại các thuộc tính trong K theo thứ tự sau:



A, B, D, E, I

Ta được một khóa là của lược đồ quan hệ là {C,G,H}

(Lưu ý là thuật toán này chỉ nên sử dụng trong trường hợp chỉ cần tìm một khóa).


      1. Thuật toán tìm tất cả khóa

        1. Thuật toán cơ bản

Bước 1: Xác định tất cả các tập con khác rỗng của Q+. Kết quả tìm được giả sử là các tập thuộc tính X1, X2, …,X2n-1

Bước 2: Tìm bao đóng của các Xi

Bước 3: Siêu khóa là các Xi có bao đóng đúng bằng Q+. Giả sử ta đã có các siêu khóa là S = {S1,S2,…,Sm}

Bước 4: Xây dựng tập chứa tất cả các khóa của Q từ tập S bằng cách xét mọi Si, Sj con của S (i  j), nếu Si  Sj thì ta loại Sj (i,j=1..n), kết quả còn lại của S chính là tập tất cả các khóa cần tìm.

Ví dụ 8: Tìm tất cả các khóa của lược đồ quan hệ và tập phụ thuộc hàm như sau:

Q(C,S,Z); F = {f1:CS  Z; f2:Z  C}




Xi



Siêu khóa

khóa

C

C







S

S







CS

CSZ

CS

CS

Z

ZC







CZ

CZ







SZ

SZC

SZ

SZ

CSZ

CSZ

CSZ




Vậy lược đồ quan hệ Q có hai khóa là: {C,S} và {S,Z}

Thuật toán trên thì dễ hiểu, dễ cài đặt, tuy nhiên nếu với n khá lớn thì phép duyệt để tìm ra tập tất cả các tập con của tập Q+ là không hiệu quả. Do vậy cần thu hẹp không gian duyệt. Chúng ta sẽ nghiên cứu thuật toán cải tiến theo hướng giảm số thuộc tính của tập cần duyệt tất cả các tập con.



        1. Thuật toán cải tiến

Trước khi đi vào thuật toán cải tiến, ta cần quan tâm một số khái niệm sau:

  • Tập thuộc tính nguồn (TN) chứa tất cả các thuộc tính có xuất hiện ở vế trái và không xuất hiện ở vế phải của các phụ thuộc hàm và các thuộc tính không xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm.

  • Tập thuộc tính đích (TD) chứa tất cả các thuộc tính có xuất hiện ở vế phải và không xuất hiện ở vế trái của các phụ thuộc hàm.

  • Tập thuộc tính trung gian (TG) chứa tất cả các thuộc tính xuất hiện ở cả vế trái lẫn vế phải của các phụ thuộc hàm.

Hệ quả: Nếu K là khóa của Q thì TN  K và TD  K = 

Chứng minh TN  K

Theo hệ quả 2 của thuật toán tìm bao đóng ta có K+  KTDTG

Ta chứng minh A  TN  A  K. Thật vậy:

Nếu A  K  K+  KTDTG  Q+-A  K không là khóa  mâu thuẫn



Chứng minh TD  K = 

Giả sử có thuộc tính A  TD  K ta sẽ dẫn đến điều mâu thuẫn. Thật vậy:

Theo hệ quả 1 của thuật toán tìm bao đóng thì K+ = (K-A)+  A

A  TD  có X là vế trái của một phụ thuộc hàm trong F sao cho X  A (1) và A  X  X  K+ = (K-A)+  A vì A  X  X  (K-A)+  (K-A)  X (2)

(1) và (2) cho (K-A)  A  A(K-A)+  (K-A)+  A = (K-A)+  K+ = (K-A)+ mâu thuẫn với điều K là khóa.

Dựa vào hệ quả trên ta có thuật toán tìm tất cả khóa sau:



Dữ liệu vào: Lược đồ quan hệ Q và tập phụ thuộc hàm F

Dữ liệu ra: Tất cả các khóa của quan hệ

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

Bước 1: tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG

Bước 2: if TG =  then lược đồ quan hệ chỉ có một khóa K

K  TN

kết thúc

Ngược lại

Qua bước 3

Bước 3: tìm tất cả các tập con Xi của tập trung gian TG

Bước 4: tìm các siêu khóa Si bằng cách Xi

if (TN  Xi)+ = Q+ then

Si = TN  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 tiểu

 Si, Sj  S

if Si  Sj then Loại Sj ra khỏi Tập siêu khóa S

S còn lại chính là tập khóa cần tìm.
Ví dụ 9: Giải lại bài tập ví dụ 8

Ap dụng thuật toán cải tiến ta có lời giải như sau:

TN = {S}; TG = {C,Z}

Gọi Xi là các tập con của tập TG:



Xi

(TN  Xi)

(TN Xi)+

Siêu khóa

khóa



S

S







C

SC

Q+

SC

SC

Z

SZ

Q+

SZ

SZ

CZ

SCZ

Q+

SCZ




Kết quả quan hệ trên có hai khóa là : {S,C} và {S,Z}

    1. BÀI TẬP

  1. Chứng minh các tính chất sau:

  1. Tính cộng đầy đủ X  Y và Z  W  XZ  YW

  2. Tính tích lũy X  Y và Y  ZW  X  YZW

  1. Cho G={ABC,AB,BC,AC}. F={ABC,AB,BC} có tương đương với G không?

  2. Cho lược đồ CSDL

Kehoach(NGAY,GIO,PHONG,MONHOC,GIAOVIEN)

F={NGAY,GIO,PHONG  MONHOC

MONHOC,NGAY  GIAOVIEN

NGAY,GIO,PHONG  GIAOVIEN

MONHOC  GIAOVIEN}


  1. Tính {NGAY,GIO,PHONG}+ ; {MONHOC}+

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

  3. Tìm tất cả các khóa của Kehoach

  1. Cho lược đồ CSDL

Q(TENTAU,LOAITAU,MACHUYEN,LUONGHANG,BENCANG,NGAY)

F={TENTAU  LOAITAU

MACHUYEN  TENTAU, LUONGHANG

TENTAU,NGAY  BENCANG, MACHUYEN}



  1. Hãy tìm tập phủ tối thiểu của F

  2. Tìm tất cả các khóa của Q

  1. Q(A,B,C,D,E,G)

Cho F={ABC;CA;BCD;ACDB;DEG;BEC;CGBD;CE  AG}

X={B,D}, X+=?

Y={C,G}, Y+=?


  1. cho lược đồ quan hệ Q và tập phụ thuộc hàm F

  1. F={ABE;AGI;BEI;EG;GI H} chứng minh rằng AB  GH.

  2. F={ABC;BD;CDE;CEGH;GA}chứng minh rằng AB  E; AB  G

  1. Cho quan hệ r

A

B

C

D

x

u

x

Y

y

x

z

x

z

y

y

y

y

z

w

z

Trong các phụ thuộc hàm sau đây, PTH nào không thỏa

A  B; A  C; B  A; C  D; D  C; D  A



  1. Hãy tìm tất cả các khóa cho lược đồ quan hệ sau:

Q(BROKER,OFFICE,STOCK,QUANTITY,INVESTOR,DIVIDENT)

F={STOCK  DIVIDENT

INVESTOR  BROKER

INVESTOR,STOCK  QUANTITY

BROKER  OFFICE }


  1. Xét lược đồ quan hệ và tập phụ thuộc dữ liệu:

Q(C,T,H,R,S,G)

f={ f1: C T; f2: HR C; f3: HT R;

f4: CS G; f5: HS R}

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




  1. Q(A,B,C,D,E,H)

F={A  E; C  D; E  DH}

Chứng minh K={A,B,C} là khóa duy nhất của Q



  1. Q(A,B,C,D)

F={ABC; DB; CABD}

Hãy tìm tất cả các khóa của Q



  1. Q(A,B,C,D,E,G)

F={ABC;C A;BCD;ACDB;DEG;BEC;CGBD;CEG}

Hãy tìm tất cả các khóa của Q.



  1. Xác định phủ tối thiểu của tập phụ thuộc hàm sau:

  1. Q(A,B,C,D,E,G),

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

  1. Q(A,B,C)

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

  1. Xác định phủ tối thiểu của các tập phụ thuộc hàm sau:

  1. Q1(ABCDEGH)

F1={A H,ABC,BCD;GB}

  1. Q2(ABCSXYZ)

F2={SA;AXB;SB;BYC;CZX}

  1. Q3(ABCDEGHIJ)

F3={BGD;GJ;AIC;CEH;BDG;JHA; DI }

  1. Q4(ABCDEGHIJ)

F4={BHI;GCA;IJ;AEG;DB;IH}

----oOo----

  1. .

CHUẨN HÓA CƠ SỞ DỮ LIỆU


    1. DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ (normal forms for relation schemes)

Trong thực tế, một ứng dụng cụ thể có thể được thiết kế thành nhiều lược đồ cơ sở dữ liệu khác nhau, và tất nhiên chất lượng thiết kế của các lược đồ CSDL này cũng khác nhau. Chất lượng thiết kế của một lược đồ CSDL có thể được đánh giá dựa trên nhiều tiêu chuẩn trong đó sự trùng lắp thông tin và chi phí kiểm tra các ràng buộc toàn vẹn là hai tiêu chuẩn quan trọng.

Sau đây là một số tiêu chuẩn để đánh giá độ tốt/xấu của một lược đồ quan hệ. Trước tiên ta tìm hiểu một số khái niệm liên quan:



      1. Định nghĩa các dạng chuẩn

        1. Dạng Chuẩn Một (First Normal Form)

Một lược đồ quan hệ Q ở dạng chuẩn 1 nếu toàn bộ các thuộc tính của mọi bộ đều mang giá trị đơn.

Ví dụ 1: Xét quan hệ

MASV

HOVATEN

KHOA

TENMONHOC

DIEMTHI

99023

NGUYENTHITHU

CONG NGHE THONG TIN

KY THUAT LAP TRINH

6










TOAN ROI RAC

8










CO SO DU LIEU

4

99030

LE VAN THANH

DIEN TU

VI XULY

4
1   ...   5   6   7   8   9   10   11   12   ...   17


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương