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

F₂⁺=_Q2(F)={SID,SISD,SIDI,SISDI}{SID}= F₂

Q₁ và Q₂ đều đạt dạng chuẩn BC vì trong Q_i chỉ có phụ thuộc hàm có vế trái là khóa. F₁ được tạo thành bằng cách lấy các phụ thuộc hàm của _Q1(F)có vế phải một thuộc tính. Tương tự cho F₂

Ví dụ 17: cho Q(CTHRSG), F={CT;HRC;HTR;CSG;HSR} hãy phân rã Q thành các lược đồ con đạt chuẩn BC bảo toàn thông tin. (giải như ví dụ trên)



Tính chất: Theo thuật toán trên, khi phân rã Q thành Q₁(XY)với XY và Q₂ thì tập khóa S_Q của Q luôn luôn bằng với tập khóa S_Q2 của Q₂.

Chứng minh

Thật vậy, K là một khóa của Q  K là một siêu khóa của Q₂. Giả sử có K’ K và K’ là khóa của Q₂  K’(Q⁺-Y) mà XY  K’Q⁺. Điều này mâu thuẫn với K là khóa của Q  K là khóa của Q₂. Ngược lại cũng đúng.

Dựa vào tính chất trên, ta cải tiến thuật toán phân rã nhằm giảm bớt khối lượng tính các phụ thuộc hàm của tập F⁺

Thuật toán phân rã Q,F thành dạng chuẩn BC (hay chuẩn 3) bảo toàn thông tin

Bước 1: Tìm tập tất cả khóa S_K của Q

Bước 2: Tìm phụ thuộc hàm X  Y  F có X không là siêu khóa và Y không chứa thuộc tính khóa. Nếu tìm thấy thì tách Q thành Q₁ và Q₂ theo quy tắc sau:

Q₁=Q[XY]; Tính F₁ bằng cách tính bao đóng tất cả tập con của XY

Q₂=Q[Q⁺ -Y] S_K cũng là tập khóa của Q₂

thực hiện bước 1 cho Q₁

thực hiện bước 2 cho Q₂

Ngược lại nếu không tìm thấy thì có hai trường hợp:

Trường hợp 1: mọi phụ thuộc hàm trong F_i đều cóvế trái là siêu khóa thì Q_i đạt chuẩn BC

Trường hợp 2: nếu có phụ thuộc hàm có vế trái không là siêu khóa và vế phải là thuộc tính khóa thì Q_i đạt chuẩn 3.

Chú ý: Thuật toán này chỉ tiện trong trường hợp khối lượng tính toán trong việc tìm tất cả khóa của lược đồ quan hệ Q không lớn. Nói cách khác tập trung gian TG có ít thuộc tính. Ngược lại ta phải dùng thuật toán của phần tiếp theo.

Ví dụ 18: phân rã lược đồ ở ví dụ trên thành các lược đồ con ở dạng chuẩn BC bảo toàn thông tin.

Trong F có 4 phụ thuộc hàm CT,HRC,HTR,CSG làm Q không đạt dạng chuẩn 3 hay BC và phép phân rã trên đã chọn ngẫu nhiên phụ thuộc hàm CT để phân rã thành Q₁ và tập thuộc tính của Q₁₂ chính là tập thuộc tính của Q bỏ thuộc tính T.Tập phụ thuộc hàm F₁₂ sẽ chứa các phụ thuộc hàm của F bỏ đi các phụ thuộc hàm có vế trái hay vế phải chứa thuộc tính T. Như vậy tùy theo cách chọn phụ thuộc hàm để phân rã thành Q₁ mà số lượng phụ thuộc hàm mang xuống Q₁₂ khác nhau và chất lượng phân rã cũng khác nhau. Kết quả của phép phân rã trên chính là Q₁, Q₂, Q₃ của hình trên. Phép phân rã bảo toàn thông tin, và các lược đồ con đạt chuẩn BC nhưng phép phân rã không bảo toàn phụ thuộc hàm vì G = F₁  F₂  F₃ = {CT; HRC; CHR; HSRG} không tương đương với F (HTR  G⁺ và CSG  G⁺). Ta hãy xem phép phân rã sau sẽ cho kết quả tốt hơn.

Phép phân rã cũng cho kết quả phép phân rã bảo toàn thông tin, các lược đồ con Q₁,Q₂,Q₃,Q₄ đạt chuẩn BC và phép phân rã không bảo toàn phụ thuộc hàm vì G = F₁  F₂  F₃  F₄ ={CSG;HRC;CHR;CT;HSC} không tương đương với F (HTR  G⁺).Phép phân rã này tốt hơn vì chỉ có một phụ thuộc hàm HTR không thuộc G⁺ trong khi phép phân rã trên có tới 2 phụ thuộc hàm HTR và CSG không thuộc G⁺.Sở dĩ phép phân rã thứ 2 tốt hơn vì ở bước chọn phụ thuộc hàm để phân rã thành Q₁ phép phân rã đã chọn phụ thuộc hàm sao cho khi chiếu F xuống Q₁₂ số phụ thuộc hàm mang xuống càng nhiều càng tốt.

Nếu Q được phân rã thành:

(Q₁(BDG), Q₂(A,B,C,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn 3

(Q₁(BDG), Q₂(A,C,E), Q₃(A,B,D,E)) lược đồ cơ sở dữ liệu đạt chuẩn BC

2. 
   Bổ đề:
   

Q không ở dạng chuẩn BC  có XA sao cho X không là siêu khóa  có thuộc tính B  XA (vì nếu không có B  XA thì X phải là siêu khóa)  (Q⁺-AB)  X  (Q⁺-AB)A

• 
  Một lược đồ Q ở dạng chuẩn BC vẫn có thể có AB sao cho (Q⁺-AB)A
  
• 
  Một lược đồ Q không có AB sao cho (Q⁺-AB)A thì Q ở dạng chuẩn BC
  

3. 
   Thuật toán
   

Ở mỗi bước 2 của thuật toán phân rã Q,F ta thu được 2 lược đồ Q_i⁺=Z’-A,Q₁⁺=XA với Q_i⁺Q₁⁺ = (Z’-A)XA = X và XQ₁⁺ và Q₁ là lược đồ ở dạng chuẩn BC. Thuật toán lại tiếp tục phân rã Q_i theo đúng cách đã làm  thuật toán phân rã bảo toàn thông tin và các lược đồ con Q_i đạt dạng chuẩn BC.

F = {S  D,

I  B

IS  Q

Hãy phân rã Q thành các lược đồ con đạt dạng chuẩn BC và bảo toàn thông tin.

***Đặt Z’= Q⁺= BOSQID

Thực hiện thuật toán chi tiết

Y’= BOSQID

Chọn 2 thuộc tính . Tìm bao đóng của tập hợp thuộc tính còn lại. Nếu bao đóng chứa 1 trong 2 thuộc tính chọn chẳng hạn A, nghĩa là ta đã tìm được 2 thuộc tính AB sao cho (Y’-AB)A

Chọn BO:(SQID)⁺  B

Giảm O trong Y’ ta được Y’= BSQID

Chọn BS:(QID)⁺  B

Giảm S trong Y’ ta được Y’= BQID

Chọn BQ:(ID)⁺  B

Giảm Q trong Y’ ta được Y’= BID

Chọn BD: I⁺  B

Giảm D trong Y’ ta được Y’= BI  Q₁=(BI) và F₁={IB}

Để tính F₁ ta phải tính bao đóng của tất cả tập con của {BI}F₁

***Giảm B trong Z’ ta được Z’= OSQID

Đặt Y’=OSQID

Chọn OD: (SQI)⁺  D;

Giảm O trong Y’ ta được Y’= SQID

chọn QD: (SI)⁺  D

giảm Q trong Y’ ta được Y’= SID

chọn ID: S⁺  D;

giảm I trong Y’ ta được Y’= SD  Q₂=(SD) và F₂={SD}

Để tính F₂ ta phải tính bao đóng của tất cả tập con của {SD}  F₂

*** Giảm D trong Z’ ta được Z’= OSQI

Đặt Y’=OSQI

chọn OQ: (SI)⁺  Q

giảm O trong Y’ ta được Y’= SQI  Q₃=(SQI) và F₃={SIQ}

Ở bước trên không chọn AB để bao đóng tập hợp thuộc tính còn lại chứa A hay B

Để tính F₃ ta phải tính bao đóng của tất cả tập con của {SQI}  F₃

*** Giảm Q trong Z’ ta được Z’= OSI

Đặt Y’=OSI

Chọn OS: I⁺=IBO  O

giảm S trong Y’ ta được Y’= OI  Q₄=(OI) và F₄={IO}
*** Giảm O trong Z’ ta được Z’= SI  Q₅=(SI)và F₅={PTHHN}

Ta có thể hiểu Q₃(SQI)là tổ hợp của 2 lược đồ con Q₅(SI) và Q₃(SQI)

1:Q₁(BI) F₁={IB}

2:Q₂(SD) F₂={SD}

3:Q₃(SQI) F₃={SIQ}

4:Q₄(OI) F₄={IO}

1. 
   Chú ý
   

• 
  Nên tránh phân rã nếu lược đồ đã ở dạng chuẩn mong muốn.
  
• 
  Nên xem xét tổ hợp các lược đồ quan hệ con thành lược đồ lớn hơn nếu lược đồ lớn hơn vẫn đạt dạng chuẩn mong muốn.
  
• 
  Một kết quả phân rã bảo toàn phụ thuộc hàm sẽ có giá trị hơn kết quả phân rã không bảo toàn phụ thuộc hàm. Giữa hai kết quả phân rã đều không bảo toàn phụ thuộc hàm thì kết quả phân rã thỏa nhiều phụ thuộc hàm trong F sẽ có giá trị hơn .
  
• 
  Không có thuật toán phân rã lược đồ Q thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.
  
• 
  Vẫn có lược đồ Q được phân rã thành các lược đồ con ở dạng chuẩn BC vừa bảo toàn thông tin vưa bảo toàn phụ thuộc hàm.
  

TN={S} TG={CZ}

2. 
   Phân rã thành dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm
   

• 
  F=F_tt={CT,HRC,THR,CSG,HSR} là phủ tối thiểu.
  
• 
  Áp dụng thuật toán trên Q được phân rã thành các lược đồ con
  

• 
  Khóa của Q
  

  Xi	TNXi	(TNXi)+	siêu khóa	khóa
  	HS	CTHRSG	HS	HS
  C	HSC	CTHRSG	HSC
  T	HST	CTHRSG	HST
  CT	HSCT	CTHRSG	HSCT
  R	HSR	CTHRSG	HSR
  CR	HSCR	CTHRSG	HSCR
  TR	HSTR	CTHRSG	HSTR
  CTR	HSCTR	CTHRSG	HSCTR

• 
  Q₅ chứa khóa của Q nên Q₁,Q₂,Q₃,Q₄,Q₅ là kết quả của phân rã.
  

1. 
   Nếu F_tt có phụ thuộc hàm f_i liên quan đến tất cả thuộc tính thì Q đạt chuẩn 3. Thật vậy:
   

2. 
   Nếu lược đồ Q’(W) gồm các thuộc tính không xuất hiện trong F_tt thì Q đạt chuẩn 3. Thật vậy:
   

3. 
   Ta chứng minh mỗi lược đồ con ở dạng chuẩn 3. Thật vậy:
   

4. 
   Ta chứng minh phép phân rã bảo toàn phụ thuộc hàm. Thật vậy:
   

Hơn nữa F_tt⁺  G = _Qi(F_tt) F_tt⁺⁺  G⁺  F_tt⁺  G⁺ (2)

5. 
   Ta chứng minh phép phân rã bảo toàn thông tin. Thật vậy:
   

	C	T	H	R	S	G
Q1(CT)	a1	a2
Q2(HRC)	a1		a3	a4
Q3(THR)		a2	a3	a4
Q4(CSG)	a1				a5	a6
Q5(HSR)			a3	a4	a5

Каталог: 2013
2013 -> 1. Most doctors and nurses have to work on a once or twice a week at the hospital
2013 -> TrầnTrang EnglishTheory Phonetics
2013 -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
2013 -> TRƯỜng đẠi học cần thơ
2013 -> DÂn số HỌc tài liệu dùng cho Chương trình bồi dưỡng nghiệp vụ
2013 -> VẬn dụng lực axit,LỰc oxy hóA, LỰc khử CỦa dãy axit hnX; HnXOm ĐỂ SỬ DỤng dạy họC
2013 -> TRƯỜng thpt chuyên bn ttđh lần II (Đề thi có 5 trang) ĐỀ thi thử ĐẠi họC

tải về 1.86 Mb.

Chia sẻ với bạn bè của bạn: