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

5. 
   .
   

1. 
   ĐỊNH NGHĨA
   

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

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?

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’

2. 
   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  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 đủ

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 XY 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}

2. 
   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)
   

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.

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

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

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

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
   

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}

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

B  C  G⁺? với G = F_1tt - {B  C}={B  D;C  D}

B_G⁺=BD  B  C  G⁺  trong F_1tt B  C không dư thừa.

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

B  D  G⁺? với G = F_1tt - {B  D}={B  C;C  D}

B_G⁺=BCD  B  D  G⁺  trong F_1tt,B  D dư thừa.

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

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

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

F_tt = {MSCD  CD;

CD  MSCD;

CD,HG  MSSV;

MSCD,MSSV  HG}

3. 
   KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)
   
   1. 
      Định Nghĩa
      

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

1. 
   K⁺ = Q⁺ và
   
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).

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.

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:

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

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

Q(C,S,Z); F = {f₁:CS  Z; f₂: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

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.

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

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

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

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:

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 X_i là các tập con của tập TG:

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
   

2. 
   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?
   
3. 
   Cho lược đồ CSDL
   

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
   

4. 
   Cho lược đồ CSDL
   

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
   

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

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

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

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

7. 
   Cho quan hệ r
   

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

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

F={STOCK  DIVIDENT

INVESTOR  BROKER

INVESTOR,STOCK  QUANTITY

BROKER  OFFICE }

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

f={ f₁: C T; f₂: HR C; f₃: HT R;

f₄: CS G; f₅: HS R}

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

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

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

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

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

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

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

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

2. 
   Q(A,B,C)
   

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

1. 
   Q₁(ABCDEGH)
   

2. 
   Q₂(ABCSXYZ)
   

3. 
   Q₃(ABCDEGHIJ)
   

4. 
   Q₄(ABCDEGHIJ)
   

6. 
   .
   

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

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)