Luận văn Nghiên cứu một số vấn đề về phụ thuộc dữ liệu và khai phá dữ liệu trong cơ sở dữ liệu quan hệ

Do min (  1 f  ,  2 f  , … ,  k f  ) ³ f  ta có  i f ³ f  suy ra (X → A i ) f ΠF +  (theo  A4') và (X→A 1 A 2  … A k ) f  (theo D4). Vì vậy ta có (X → Y) f ΠF +  □  3.2.2  Bài toán thành viên  Một  trong  những ứng dụng  quan  trọng  nhất  của  tính  chất  bao  đóng  tập  thuộc  tính  là  sử  dụng  trong bài  toán  thành  viên. Bài  toán  thành  viên  được  áp  dụng nhiều trong việc tìm kiếm và trích trọn dữ liệu.  Định nghĩa: Cho R là một quan hệ trên tập thuộc tính U. Gọi F là tập các  Phụ thuộc hàm trên U. Tập  tất cả các phụ thuộc hàm được suy ra từ F dựa vào  các tiên đề trên được ký hiệu là F a +  và :  F + a = { (X→ Y) a  │ (X→ Y) a  nhận được từ F thông qua các tiên đề A1',  A2', A3', A4'  và a >0}.  Để đơn giản ta ký hiệu F + a  là F + 34  Bài  toán  đặt  ra  là  liệu  phụ  thuộc  hàm  (X→ Y) f  có  thuộc  vào  F +  hay  không?  Để trả lời câu hỏi này thì từ tập Phụ thuộc hàm F, dựa vào các hệ tiên đề  A1', A2', A3', A4' để tính F +  và kiểm tra yêu cầu của bài toán. Tuy nhiên việc  tính F +  không phải  lúc nào cũng dễ dàng vì F +  là một tập không xác định. Do  đó ta cần xác định một cách tính đơn giản hơn.  Ký hiệu (F  * ) +  = {(X→ Y) f  │(X→ Y) f ΠF +  và f  = sup {a  │(X→ Y) a ΠF + }} nghĩa là (F  * ) +  là tập tất cả các Phụ thuộc hàm có mức tin cậy cao nhất.  Do đó để kiểm tra Phụ thuộc hàm (X→ Y) f  có thuộc vào F +  hay không  thì thay vì tính F +  ta sẽ tính  (F  * ) +  .  Hiển nhiên ta thấy nếu tồn tại Phụ thuộc hàm mờ (X→ Y) a Π (F  * ) +  thì ta  sẽ chỉ ra ngay được phụ thuộc hàm mờ (X → Y) f ΠF +  với a  > f .  Tuy nhiên viêc  tính trực  tiếp  (F  * ) +  nghĩa  là phải xét mọi  thuộc tính của  quan hệ không phải  lúc nào cũng hiệu quả vì sẽ phải  tìm  tất cả các Phụ thuộc  hàm kể cả những thuộc tính không dẫn đến các Phụ thuộc hàm cần tìm.  Ví dụ: U = {A,B,C,D,E,H,G}  F = {(A→ B) a  , (B→ C) b  , (E→ H) f  , (ED→ G) j  }  Hỏi (A → C) h  có thuộc F +  hay không ?  Khi đó nếu tính trực tiếp (F  * ) +  thì ta sẽ phải tính tất cả các Phụ thuộc hàm  của các thuộc tính D, E, G, H mặc dù chúng không hề dẫn đến Phụ thuộc hàm (A→  C) h .  Để việc tính toán hiệu quả hơn ta sẽ  dựa vào việc tính toán bao đóng của  một tập thuộc tính theo phụ thuộc hàm mờ với mức tin cậy a  nào đó ( 0  1 a £ £  ).  Theo đó thay vì  tính trực  tiếp F +  ta sẽ tính X +  nghĩa  là sẽ tìm mọi thuộc tính  phụ thuộc hàm vào X với mức a  nào đó (0  1 £ £ a  ). Khi đó bài toán sẽ được giải  quyết một cách dễ dàng.  3.2.3 Thuật toán tìm bao đóng  Input:  X Í U ,  X = {A 1 , A 2 ,  … A k }  F  là tập các Phụ thuộc hàm mờ trên U  Output: X +  Thuật toán:  1. Khởi trị X 0  ={(A 1 ,1), (A 2 ,1)  … (A k  ,1)} , i=0. 35  2.Blist i ={(A,f )│(  F V W V Î ® $ $ a ) W ( ) )(  ,VÍdom(X  i ),  A  ) , min( , b a f = ÎW  với g b g  min  ) , (  V G  X G  i Î Î =  }  { Nghĩa là với mỗi Phụ thuộc hàm (V→W) a  thì:  Nếu VÍ  Dom(X i ) ={A│(A  ,f )  i X Π }: –  Tìm min của các ngưỡng của  tất cả các thuộc tính thuộc tập thuộc tính V  –  Đặt  ) , min( b a f =  .  Với  mỗi  tập  thuộc tính AÎW thỏa mãn (V→W) a  thì sẽ add (A,f ) vào Blist i  ( Blist i  là tập  bao đóng trung gian) }  3. X  1 + i  = X i ÈBlist i  Ở đây phép hợp là phép hợp mờ.  4. Nếu X  1 + i  = X i  thì dừng lại và X + = X  1 + i  . Nếu không thì quay lại bước 2.  Ở đây X i  được xét như là tập mờ trong đó (A ,f ) chỉ ra rằng A Phụ thuộc  hàm vào X với mức f . [6]  Ví dụ  : U ={A,B,C,D,E,F,G,H}, F = {(B→C)  6 , 0  ,  (B→E)  8 , 0  ,  (E→F)  85 , 0  ¸  (F→G)  9 , 0  , (G→H)  9 , 0  , (H→A)  75 , 0  , (A→C)  7 , 0  }  Tính B +  = ?  Giải: Áp dụng thuật toán trên ta có:  Khởi trị : B 0  = {(B,1)}  Khi đó với Phụ thuộc hàm (B→C)  6 , 0  thì f  = min( 1, 0.6) = 0.6  Vậy (C,0.6) được thêm vào tập bao đóng tạm thời Blist 0  Tương tự với Phụ thuộc hàm (B→E) 0,8  ta cũng có a  = (1,0.8) = 0.8. Suy  ra (E,0.8 ) cũng được thêm vào Blist 0  Vậy sau bước 1 tập bao đóng tạm thời là:  Blist 0  = {(C, 0.6), (E, 0.8)}  Suy ra:  B 1  =  B 0 È  F  Blist  0  = {(B,1),(C, 0.6),(E, 0.8) }  Tiếp  tục  như  trên  với  B 1 =  {(B,1),(C,  0.6),(E,  0.8)  }  và  Dom(B 1 )  =  {B,C,E}. Ta lần lượt có:  Blist 1  = {(C, 0.6), (E, 0.8),(F, 0.8)}  B 2  = B 1  F È  Blist  1  = { (B,1),(C, 0.6), (E, 0.8),(F, 0.8)} 36  Blist 2  = {(C, 0.6),(E, 0.8), (F, 0.8), (G, 0.8)}  B 3 = B 2  F È  Blist  2  ={(B,1), (C, 0.6),(E, 0.8), (F, 0.8), (G, 0.8)}.  Blist 3 = { (C, 0.6), (E, 0.8), (F, 0.8), (G, 0.8), (H, 0.8)}  B 4 = B 3  F È  Blist  3  ={(B,1), (C, 0.6), (E, 0.8), (F, 0.8), (G,0.8), (H,0.8)}.  Blist 4 = { (C, 0.6),(E, 0.8), (F, 0.8), (G, 0.8), (H, 0.8), (A, 0.75)}  B 5  = B 4  F È  Blist  4  ={(A, 0.75),  (B,1),(C, 0.6),  (E, 0.8),  (F, 0.8),  (G, 0.8),  (H, 0.8), }.  Blist 5 = {(C, 0.6), (E, 0.8),(F, 0.8), (G, 0.8), (H, 0.8), (A, 0.75), (C, 0.7)}  B 6  = B 5  F È  Blist  5  ={(A, 0.75),  (B,1),(C, 0.7),  (E, 0.8),  (F, 0.8),  (G, 0.8),  (H, 0.8)}.  Blist 6 = {(C, 0.6), (E, 0.8),(F, 0.8), (G, 0.8), (H, 0.8), (A, 0.75), (C, 0.7)}  B 7  = B 6  F È  Blist  6  ={(A, 0.75),  (B,1),(C, 0.7),  (E, 0.8),  (F, 0.8),  (G, 0.8),  (H, 0.8)} = B 6 Þ B + ={(A, 0.75), (B,1),(C, 0.7), (E, 0.8), (F, 0.8), (G, 0.8), (H, 0.8)}  Ví dụ 2: Cho tập thuộc tính U = {A,B,C,D,E,F};  F= { } 0.7 0.85 0.9 0.85 0.75 0.9 ( ) , ( ) , ( ) , ( ) , ( ) , ( ) AB C AB D D C B E CE F F D ® ® ® ® ® ®  Tính (AB) + ?  Giải: Áp dụng thuật toán trên ta có:  Khởi trị : AB 0  = {(A,1), (B,1)}  Khi đó với Phụ thuộc hàm (AB→C) 0,7  thì f  = min( 1, 0.7) = 0.7  Vậy (C,0.7) được thêm vào tập bao đóng tạm thời Blist 0  Tương tự với Phụ thuộc hàm (AB→D) 0,85  ta cũng có a  = (1,0.85) = 0.85.  Suy ra (D,0.85 ) cũng được thêm vào Blist 0  Vậy sau bước 1 tập bao đóng tạm thời là:  Blist 0  = {(C, 0.7), (D, 0.85)}  Suy ra:  AB 1  =  AB 0 È  F  Blist  0  = {(A,1), (B,1), (C, 0.7), (D, 0.85)}  Tiếp  tục  như  trên  với  AB 1 =  {(A,1),  (B,1),  (C,  0.7),  (D,  0.85)}  và  Dom(AB 1 ) = {A,B,C,D}. Ta lần lượt có:  Blist 1  = {(C, 0.7), (D, 0.85),(C, 0.85), (E, 0.85)}  AB 2  = AB 1  F È  Blist  1  = { (A,1), (B,1), (C, 0.85), (D, 0.85), (E, 0.85)}  Blist 2  = {(C, 0.7), (D, 0.85),(C, 0.85), (E, 0.85), (F, 0.75) } 37  AB 3  = AB 2  F È  Blist  2  ={(A,1),  (B,1),  (C, 0.85),  (D, 0.85),  (E, 0.85),  (F,  0.75)}.  Blist 3 = { (C, 0.7), (D, 0.85),(C, 0.85), (E, 0.85), (F, 0.75), (D, 0.75)}  AB 4  = AB 3  F È  Blist  3  ={(A,1),  (B,1),  (C, 0.85),  (D, 0.85),  (E, 0.85),  (F,  0.75)}=  (AB) + Þ AB + ={(A,1), (B,1), (C, 0.85), (D, 0.85), (E, 0.85), (F, 0.75)}  3.2.4 Tính đúng của thuật toán tìm bao đóng  Định lý: Thuật toán trên là hoàn toàn đúng đắn. Nghĩa là X t  = X +  với t là i thoả  mãn điều kiện dừng của thuật toán (X  1 + i  = X i  ) [6].  Chứng minh:  Để chứng minh thuật toán trên  là đúng đắn ta sẽ phát biểu một số bổ đề  sau:  Bổ  đề  1:Cho  R  là  một  quan  hệ  trên  tập  thuộc  tính  U  .Với  X,  Y  } 0 U, A ) , (A { > Î Í a a  , F là một tập các  _ q  Phụ thuộc hàm mờ  trên R;  X i , Y i  nhận được khi sử dụng thuật toán trên với  i bất kỳ. Với X  X = 0  và Y  Y = 0  . Khi  đó:  1) Nếu X  Y Í  thì X i Í Y i  2) X k  i X Í  với mọi k  i £  .  Chứng minh:  1) Ta sẽ chứng minh quy nạp theo i  +) Với i = 0 ta có X  0 0  Y Y X = Í =  (đúng)  +) Giả sử (1) đúng với i = j–1  Ta  cần  chứng  minh  (1)  cũng  đúng  với  i  =  j.  Do  X j  =  X  1 1 - - Í  j X  j  B  và  1 1 - - Í =  j Y  j j  B Y Y  trong đó:  B  1 - j X  = {(A ,f )│(  F V W V Î ® $ $ a ) W ( ) )(  ,VÍdom(X  1 - j  ), A  ) , min( , b a f = ÎW  với g b g  min  1 ) , (  V G  X G  j Î Î - =  }  B  1 - j Y  =  {(A  ,f ')│(  F V W V Î ® $ $ a ) W ( ) )(  ,VÍdom(Y  1 - j  ),  A  ) ' , min( ' , b a f = ÎW  với g b g  min  1 ) , (  '  V G  Y G  j Î Î - =  } 38  Theo giả thiết quy nạp ta có X  1 1 - - Í  j j  Y  suy ra B  1 - j X Í B  1 - j  Y  do với mỗi A Π W ta có b b ³ '  nên f f ³ '  . Từ đó theo định nghĩa của phép hợp mờ ta có X  1 - j È  B  1 - j X Í Y È -1 j  B  1 - j Y  . Suy ra X  j Í Y j  □  2) Từ X  1 1 - - È =  i X  i i  B X  suy ra X  i i  X Í -1  . Lấy k = i – m với m>0 ta có:  X  i i m i m i  X X X Í Í Í Í - - - -  1 1  ...  □  Bổ đề 2: Cho U là tập thuộc tính, XÍU, X= X 1  X 2 …X k  . Giả sử X  j  là giá trị  đạt được ở bước thứ j sau khi sử dụng thuật toán trên với giá trị ban đầu là X 0  =  {(X 1 , 1),(X 2  , 1), …(X k  , 1)}. Khi đó:  (1)  a, Nếu (Y,a )  j X Π thì a > 0.  b, Nếu (Y,h ) ΠBlist j  thì h  > 0.  (2)  Nếu  (Y,a )  j X Π và a ³ b  (0< b  <  1)  thì  với  mọi j  nào  đó  (  (A,j )  p X Π (p<j) và nếu không có j  sẽ dẫn đến (Y,a )  j X Π )  ta đều có b j ³  .  Chứng minh:  (1).  a)  Theo  giả  thiết  ta  có  (Y,a )  j X Π suy  ra Î a  M= {g │(X i  , g )  0 X Π ,  I  =1,2,…,k}È {t │(V→W)t + Î F  với  0 > t  }.  Mà  ta  có  X 0  =  {(X 1  ,  1),(X 2 ,  1)…(X k  , 1)} . Do đó a >0.  b) Tương tự như phần a) theo định nghĩa Blist i  ta cũng suy ra  0 > h  (2) Ta sẽ chứng minh bằng quy nạp theo j  +) Với j = 0 ta có (Y, a )ÎX 0  = {(X i ,1), i=1…k} suy ra a =1 ³ b  + Giả thiết quy nạp: Giả sử (2) đúng với j­1  Ta cần chứng minh (2) đúng với j.; Theo giả thiết ta có  (Y,a )  j X Π và b a ³  (0 b £  <1) mà  X  1 1 - - È =  j j j  B X  suy ra: ê ë é Î Î - -  ) ' 2 ( ) , (  ) ' 1 ( ) , (  1  1  j  j  B Y  X Y a a  (1’) đúng theo gải thiết quy nạp  Xét  (2’) theo định nghĩa B  1 - j  ta có a = min( g t ,  ) trong đó  B  1 - j  =  {(Y,a )│(  F V W V Î ® $ $ t ) W ( ) )(  ,VÍdom(X  1 - j  ),A  ) , min( , g t a = ÎW  với c g c  min  1 ) , (  V G  X G  j Î Î - =  } 39  Vì b a ³  suy ra b t ³  và b g ³ Þ c c  min  1 ) , (  V G  X G  j Î Î - ³ b . Do đó j  chỉ có thể là t  hoặc một trong những giá trị c  hoặc là một giá trị nào đó ký hiệu là  ' j  ­ có  liên quan đến tập các giá trị c . Do (G, c )  1 - Π j X  và b a ³  nên ta có  ' j b ³  (theo  giả thiết quy nạp). Vậy b j ³  □  Bổ đề 3: Cho X j  và Blist j  là các tập thu được khi sử dụng thuật toán trên sau j  bước với X 0  ={(X  1 ,1  )(X 2 ,1),…(X k  ,1)}. Gọi X g j  và Blist g j  cũng là các giá trị  đạt  được  khi  sử  dụng  thuật  toán  trên  sau  j  bước  nhưng  với  X g 0  ={(X g ,1  )(X 2 ,g ),…(X k  ,g )} với 0  1 £ £ < g b  . Khi đó  (1).  X g j Í X j  (2). Nếu (Y,a )  j X Π và a ³ b  thì {(Y, b )} g j X Í  Chứng minh:  (1). Vì X g 0 Í X 0  nên ta có X g j Í X j (theo Bổ đề 1).  (2). Để chứng minh  (2)  ta sẽ chứng minh nếu  (Y,a )  j X Π và a ³ b  thì  tồn tại {(Y,  ' a  )} g j X Í  thỏa mãn  ' a ³ b .Theo bổ đề 2  ta có nếu (Y,a )  j X Π và a ³ b  (0< b  < 1) thì với mọi j  nào đó liên quan đến việc tính a  ( Nghĩa là tồn  tại (A,j )  p X Π (p<j) và nếu không có j  sẽ dẫn đến (Y,a )  j X Ï  ) ta đều có b j ³  .  Và j  này  cũng  liên quan đến việc tính a ’ thỏa mãn (Y,a ’)  X Î g j  .  Bây giờ  ta sẽ chứng minh b a ³ '  bằng Phương pháp phản chứng: Giả sử b a < '  . Do X g g g  1 1 - - È =  j j j  Blist X  suy ra: ê ë é Î Î - - g a g a  1  1  ) ' , (  ) ' , (  j  j  Blist Y  X Y  Theo  định  nghĩa    X g j  và  Blist g j  suy  ra g l  1 1 ) , ( - - Î $  j j  X G  thỏa  mãn  1 - j l b <  .  Tương  tự g l  2 2 ) , ( - - Î $  j j  X G  thỏa  mãn b l < -2 j  … g l  0 0 ) , (  X G Î $  thỏa  mãn b l < 0  . Mâu thuẫn với giả thiết ban đầu b a l ³ = 0  . Vậy b a ³ '  □  Bây giờ ta sẽ chứng minh thuật toán trên là hoàn toàn đúng đắn  Để chứng minh  X t  = X +  ta cần chứng minh X t Í  X + và  X + Í X t  1) X t Í  X +  .Ta sẽ chứng minh nếu (A,a )  t X Π thì (X→A) a + Î F  Chứng minh bằng Phương pháp quy nạp toán học:  +) Với t = 0, nếu (A,  1)} , ...(X ,1), {(X )  k 1  0 = Î X a  ta có A ÎX ,  1 = a  suy ra  (X  ) A ® + Î F  . 40  +) Giả sử 1) đúng với t = j­1  Ta sẽ chứng minh 1) đúng với t=j. Ta có (A,  1 1 ) - - È = Π j j j  Blist X X a  suy ra ê ê ë é Î Î - -  ) 2 ( ) , (  ) 1 ( ) , (  1  1  j  j  Blist X  X X a a  (1)  Đúng theo giả thiết quy nạp  (2)  Theo định nghĩa Blist j  ta có  Blist  1 - j  ={(X,a )│(  F V W V Î ® $ $ h ) W ( ) )(  ,VÍdom(X  1 - j  ),A  ) , min( , g h a = ÎW  với q g q  min  1 ) , (  V G  X G  j Î Î - =  }  Từ  (G,q ) Í  X  1 - j  theo  giả  thiết  quy  nạp  ta  có  (X  ) G ® q + Î F  . Do G  V Í  suy  ra  (X→V) g + Î F  (theo  A4’,  D4).  Từ  đó  theo  tính  bắc  cầu  (A3’)  suy  ra  (X→W) a + Î F  với  ) , min( g h a =  . Vì A  W Π nên (X→A) a  F Π + (D4).  Bây giờ ta sẽ chứng minh với mọi  (A,a )  t X Π sẽ luôn tồn tại  (A, + Î X ) ' a  với a a ³ '  . Thật vậy, do (A,a )  t X Π nên (X→A) + Î F a  từ đó theo định nghĩa của  X +  suy ra + Î $  X A  ) ' , ( a  mà a a ³ '  . Vậy X t Í  X + . (1)  2) X + Í  X t  Trước tiên ta sẽ chứng minh rằng nếu    (X→A) + Î F a  , A  U Π thì tồn  tại  i  nào đó thỏa mãn {(A,a )}  i X Í  . Giả sử (X→A) a  là Phụ thuộc hàm thứ j trong  tập F +  ta sẽ chứng minh quy nạp theo j.  +) j = 1 (Chỉ có 1 PTH ) Khi đó (X→A) a  F Π thì theo định định nghĩa  0 Blist  ta  có (A,a )  0 Blist Π và {(A,a )}  1 X Í  +) Giả  thiết  quy  nạp: Giả  sử điều  trên đúng với  j =  p­1  nghĩa  là  với các Phụ  thuộc hàm (X→A) a  thứ j<p trong tập F  +  thì luôn tồn tại i nào đó thỏa mãn  {(A,a )}  i X Í  . Ta cần chứng minh điều đó cũng đúng với j = p.  +)  Thật  vậy,  Nếu    (X→A) a + Î F  thu  được  thông  qua  tiên  đề  (A1’)  thì  ta  có  (A,a )ΠX 0  hay (A,a )ΠX 1  Nếu (X→A) a + Î F  thu được thông qua tiên đề (A2’) thì khi đó tồn tại Phụ  thuộc hàm (V→W) + Î F a  thứ j<p nào đó và  U Z Í $  sao cho VZ = X  và WZ =  A. Vì AÍU nên A =W  U Í  .Vậy theo giả  thiết quy nạp suy ra  (A,a )  i V Í  . Mặt  khác  vì  V  X VZ = Í  với  V  =  V 1 V 2 …V l  ,  X  =  X  k X X  ... 2 1  và  V  0  =  {(V 1 ,1), 41  (V 2 ,1), …, (V l ,1)} X  0  = {(X 1 ,1), (X 2 ,1), …, (X k  ,1)}. Vì V  0 ÍX 0  nên V i  i X Í  ( Theo bổ đề 1 ). Suy ra {(A,a )}  i X Í  .  Nếu (X→A) a + Î F  thu được  thông qua  tiên đề bắc cầu (A3’)  từ hai Phụ  thuộc hàm thứ j,k < p nào đó. Gọi hai Phụ thuộc hàm đó lần lượt là (X→Z) f  và  (Z→A) j  với a j a f ³ ³  ,  và Z = Z  k Z Z  ... 2 1  U Í  . Theo giả thiết quy nạp suy ra  {(Z i ,f )}  i X Í  (i=1… k). Mặt khác  ta  có  (Z→A) j  nên cũng  theo  giả  thiết quy  nạp  suy  ra $ l  nào  đó  thỏa  mãn  {(A,j )}  l Z Í  ,  mà a j ³  l Z )} {(A, Í Þ a  .  Đặt  Z  )} , ),...(Z , {(Z  k 1  0 f f f =  , vì a f ³ Þ  {(A,a )} f l Z Í  ( theo bổ đề 3 ) với Z f l  được  tính  theo  thuật  toán  trên.  Do  Z  i X Í f 0 Þ  Z  l i l  X + Í f  (  theo  bổ  đề  1  ).  Vậy  {(A,a )}  l i X + Í  .  Nếu  (X→A) a + Î F  thu  được dựa  trên  tiên  đề  (A4’)  khi  đó a a ³ $  '  thỏa  mãn (X→A)  ' a + Î F  . Vì (X→A) a  là   Phụ thuộc hàm thứ j= p nên   (X→A)  ' a  là  Phụ thuộc hàm thứ j = (p­1). Vậy theo giả thiết quy nạp ta có {(A,  ' a  )}  i X Í  . Mà a a ³ '  suy ra {(A,a )}  i X Í  ( theo bổ đề 3).  Vậy  nếu      (X→A) + Î F a  ,  A  U Π thì  luôn  tồn  tại  i  nào  đó  thỏa  mãn  {(A,a )}  i X Í  Bây  giờ  ta  sẽ  chứng  minh  X  t X Í +  .  Tức  là  nếu  {(A,a )} + Í X  thì  {(A,a )}  i X Í  .  Thật  vậy,  do  {(A,a )} + Í X Þ  F A X Î ® a ) ( +  mà  theo  chứng  minh  trên  ta  có  nếu  F A X Î ® a ) ( +  thì  luôn  tồn  tại  số  i  nào  đó  thoả  mãn  {(A,a )}  i X Í  .  +) Nếu i£  t  thì  {(A,a )}  i X Í  t X Í  +) Nếu  i ³  t  thì X  t i  X =  Vì X  1 + =  t t  X  = X  2 + t  …..=   X i (do  t  là điều kiện dừng  của thuật toán).  Vậy  X  t X Í +  (2)  Từ  (1) và (2) ta có X  t X = +  . Nghĩa là thuật toán trên hoàn toàn đúng đắn           □  3.3  Định lý tương đương cho tập mờ  Trong quá trình nghiên cứu CSDL truyền thống người ta đã chứng minh  được rằng việc các phụ thuộc hàm được dẫn xuất theo quan hệ và theo các tiên  đề  (  suy  dẫn  logic)  là  tương đương  với  nhau.  Trong  quá  trình  nghiên  cứu  về  CSDL quan hệ,  tác  giả  đánh giá  việc mở  rộng  (mờ hoá) định  lý  tương đương  (the fuzzy equivalence theory) này là hoàn toàn tự nhiên. Đó cũng là cơ sở cho  việc xét các mối quan hệ trong ngữ cảnh mờ. Dưới đây ta xét một số khái niệm  sau: 42  3.3.1 Định nghĩa: Cho tập PTH mờ F trên tập thuộc tính mờ U và { } f a  là một  PTH mờ với  mức  (0 1) a a < £  trên U. Ta nói PTH { } f a  được suy dẫn theo quan  hệ  từ  tập PTH mờ   F   và  viết  ( ) F f a =  nếu mọi quan hệ R(U)  thoả F  thì  cũng  thỏa { } f a  3.3.2 Định nghĩa: Cho tập PTH mờ F trên tập thuộc tính mờ U và { } f a  là một  PTH mờ với  mức  (0 1) a a < £  trên U. Ta nói PTH { } f a  được suy dẫn theo tiên đề  (hay suy dẫn logic ) từ tập PTH mờ F và viết  ( ) F f a -  nếu { } f F a + Π 3.3.3  Định lý:  Gọi F là tập các PTH mờ trên tập thuộc tính U  (X  ) Y a ®  là một PTH mờ với mức a  trên  U  Khi đó:  F ├ (X→Y) a  ­ suy dẫn theo hệ tiên đề Û  F =  (X→Y) a  ­ suy dẫn theo quan hệ R  Hay nói cách khác suy dẫn theo quan hệ và suy dẫn theo  tiên đề  là như  nhau.  Chứng minh: Þ Nếu  F ├ (X®Y) a  thì  F = (X®Y) a  Giả sử sau k bước sử dụng các luật của hệ tiên đề ta thu được tập các PTH  {F k }  và  R{F k }.  Ta  cần  chứng  minh  với  PTH    thứ  (k+1)  (X  ) Y a ®  nếu { } k F ( ) X Y a - ®  thì { }  ( ) k F X Y a = ®  , hay nói cách khác  {(X Y) } R a ® o  Nếu { } k F ( ) X Y a - ®  theo  (A1’)  nghĩa  là { } F  ( )  k Y X X Y F a Í Þ ® Π .  Mà { } { } ( ) k R F R X Y a Þ ® o  Nếu { } k F ( ) X Y a - ®  theo (A2’) nghĩa tồn tại ZW = X và VW = Y thỏa  mãn { } { } { } ( W VW) ( ) k R F R Z R X Y a a Þ ® Þ ® o  Nếu { } k F ( ) X Y a - ®  theo  (A3’)  nghĩa  là  tồn  tại  hai  PTH { } 1 1 k ( ) , ( ) F X Z Z Y b j ® ® Π thỏa  mãn  ( ) X Y a ®  với  min( , ) a b j =  suy  ra { } { } k ( ) F ( ) X Y R X Y a a ® Î Þ ® o  Nếu { } k F ( ) X Y a - ®  theo  (A4’)  thì  tồn  tại  ' a a ³  thỏa  mãn { } { } ' ( ) ( ) k k X Y F X Y F a a ® Î Þ ® Π . Suy ra { } ( ) R X Y a ®  Vậy theo tất cả các tiên đề ta đều có { } ( ) R X Y a ®  hay   F = (X  ) Y a ® 43 Ü  Giả  sử  có F = (X®Y) a  ,  cần  chứng minh F├  (X®Y) a Û  chứng minh  F├ (X®Y) a ÞF ¹ (X®Y) a  (*)  Nói một cách khác giả sử có PTH { } f a  và { } f F a + Ï  ta cần chứng minh  (1)  R không thoả { } f a  (2)  R thỏa mọi PTH trong  F +  Thật vậy :  Giả sử có PTH mờ { } f a  = (X  ) Y a ®  và (X  ) Y a ®  F + Ï  Từ (X  ) Y a ® Þ  tính X +  Xây dựng quan hệ R thoả F nhưng không thoả (X  ) Y a ®  như sau:  R  (A1,  1 b  )    (A2,  2 b  ) … (A k  ,  ) k b  (A  1 k+  ,  1 k b +  ) ...   (A  , n n b  )  u  ( a1,  1 a  )  (a2,  2 a  )  … (a k  ,  k a  )    (a  1 1 , k k g + +  )  …    (a  , n n g  )  v  ( a1,  1 a  )  (a2,  2 a  )  … (a k  ,  k a  )     (b  1 1 , k k l + +  ) …    (b  , n n l  )  Giả sử X +  = {(A1,  1 b  )    (A2,  2 b  ) … (A k  ,  ) k b  }. Quan hệ R gồm hai bộ u,v.  Hai  bộ  này  giống  nhau  trên  tập  X +  và  với  mọi  thuộc  tính  (B  ,i i b  )  X + Ï  (i  =  k+1,… ,n ) thì u.(B,  i b  ) ¹ v.(B,  i b  ) tức là (a  , ) i i g  ( , ) i i b l ¹  (1)  Trước hết ta chứng minh R không thoả  ( ) X Y a ®  Ta có F├ (X  ) Y a ® ÞY  F  X + Ë  (t/c 5) Þu.(Y,a ) ¹ v.(Y,a )  (*)  (X,  ) a  X + Í  ( , ) ( , ) u X v X a a Þ =  (**)  Từ (*) và (**) Þ  ┐R{(X→Y) a }  (2)  R thoả mãn mọi PTH trong tập  F +  Giả sử (W→Z) j  F + Π và có u.(W,j ) = v.(W,  ) j  ta cần chứng minh  u.(Z,  ) j  = v.(Z,j )  Từ   u.(W,j ) = v.(W,  ) j ÞW  F  X + Í  ( ) X W j + Þ ®  (t/c 5)  (1’). Mặt khác  ta có (X  ) X f + ®  (t/c 4)  (2’)  Theo giả thiết ta có : F├ (W→Z) j  (3’)  Từ (1’), (2’) và (3’) áp dụng tiên đề bắc cầu:  (X→Z) q  với  min( , ) q f j =  F Z X + Þ Í  Suy ra  u.(Z,  ) q  = v.(Z,  ) q Þ  R{ (W Z) j ®  } 44  Từ (1) và (2) suy ra  F ¹ (X  ) Y a ®  □  3.4  Thuật toán tìm khoá mờ  Thông  thường,  việc  tìm  khoá  mờ  (fuzzy  key)  trong  CSDL  quan  hệ  thì  khái  niệm bao đóng  tập  thuộc  tính sẽ được áp dụng. Cách cơ bản  nhất để  tìm  khoá mờ là phân tích bao đóng tập thuộc tính của tất cả các bộ kết hợp giữa các  thuộc tính trong quan hệ và kiểm tra xem bao đóng tập thuộc tính được tìm thấy  có bao gồm toàn bộ thuộc tính của quan hệ hay không. Điều đó có nghĩa  là sự  kết hợp thuộc tính sẽ quyết định tất cả các thuộc tính trong quan hệ với mức thoả a  nào đó và giá trị min  i a  của mức thoả này sẽ thể hiện là khoá mờ ở mức thoả  đó. Nếu sử dụng cách này rất mất thời gian và thường không được áp dụng.  Một phương án khác để tìm khoá mờ là sẽ không quan tâm đến bao đóng  tập thuộc tính của tất cả các thuộc tính trong quan hệ mà chỉ quan tâm đến một  số thuộc tính cần thiết. Như ta đã biết mỗi thuộc tính là một phần của khoá mờ  sẽ nằm ở phía bên trái (left­hand) của bất kỳ một phụ thuộc hàm mờ nào hoặc nó  sẽ không nằm trong bất kỳ một phụ thuộc hàm mờ nào của quan hệ. Điều đó có  nghĩa rằng khi ta tìm khoá mờ thì các thuộc tính xuất hiện ở phía bên phải (right  –side)  của  bất  kỳ một  phụ  thuộc  hàm mờ nào  đó  cũng  sẽ  không được  xét  tới  trong quá trình tìm bao đóng tập thuộc tính.  Thuật toán tìm kiếm khoá mờ trong đó F là tập các phụ thuộc hàm mờ của  quan hệ R [10]  (1)Tìm tất cả các thuộc tính bên phía trái ( left­hand side) của phụ thuộc  hàm mờ (ffds) của tập F  (2)Tìm tất cả các thuộc tính không nằm trong bất kỳ một phụ thuộc hàm  mờ nào của tập F  (3)Hợp 2 tập thuộc tính đã tìm được ở bước (1) và bước (2) thành danh  sách thuộc tính ( Attribute List)  (4)Bắt đầu bằng sự kết hợp các thuộc tính đơn ( single attribute) sau đó  tăng dần lên sự kiết hợp của tất cả các thuộc tính trong Attribute List  §  Nếu  sự kết hợp  thuộc  tính chứa một khoá được  tìm  thấy  trước  thì tiếp tục với sự kết hợp thuộc tính khác  §  Tìm bao đóng của sự kết hợp thuộc tính trên  §  Nếu bao đóng tìm được có chứa tất cả các thuộc tính của quan  hệ R khi đó ta có a  = min {mức thoả trong bao đóng}. Add sự  kết  hợp  trên  và  danh  sách  khoá mờ  (  fuzzy  key  List)  với mức  thoả a  Ví dụ 1:  Cho  quan  hệ  R  (  A,  B,  C,  D  )  và  phụ  thuộc  hàm  mờ:  (A®B) 0.6  và  (A®CD) 0.85  Áp dụng thuật toán trên ta có:  ­ Tập Left­hand side của các thuộc tính trong quan hệ R là: {A} 45  ­ Quan hệ R không chứa bất kỳ một thuộc tính nào không có mặt trong tập các  phụ thuộc hàm mờ  ­ Attribute List: ={A}  ­ Do trong Attribute List chỉ có 1 thuộc tính nên chỉ có một tập bao đóng là của  thuộc tính A.  Ta có A + = { (A,1), (B,0.6), (C,0.85), (D, 0.85)}  Do A +  bao gồm  tất cả các  thuộc  tính của quan hệ R nên “A”  là khoá mờ chấp  nhận được .  Ta có a =min (1, 0.6, 0.85) = 0.6  Vậy A là khoá mờ chấp nhận được của quan hệ R với mức thoả  0.6 a =  Ví dụ 2:  Cho  quan  hệ  R  trên  tập  thuộc  tính  U  ={A,B,C,D,E,F,G,H},  F  =  {(B→C)  6 , 0  ,  (B→E)  8 , 0  , (E→F)  85 , 0  ¸ (F→G)  9 , 0  , (G→H)  9 , 0  , (H→A)  75 , 0  , (A→C)  7 , 0  }  Tìm khoá mờ của quan hệ R?  Áp dụng thuật toán trên ta có:  ­ Left­ hand side = {A,B,E,F,G,H}  ­ Thuộc tính  không có mặt trong tập các phụ thuộc hàm mờ của quan hệ R là:  {D} Þ Attribute List= {A,B,D,E,F,G,H}  Xét các thuộc tính đơn ta có, chẳng hạn:  A + = {(A,1), (C,0.7)}  B + = {(A, 0.75), (B,1),(C, 0.7), (E, 0.8), (F, 0.8), (G, 0.8), (H, 0.8)} ( theo ví dụ  trên)  Như vậy ta có thể dễ dàng nhận thấy ngay (BD) + bao gồm toàn bộ các thuộc tính  của quan hệ R.  Ta xét a = min (1;0.75;0.7;0.8) = 0.7  Vậy (BD, 0.7) là khoá mờ chấp nhận được của quan hệ R.  3.5  Các dạng chuẩn mờ  Khái niệm phụ thuộc hàm là điển hình trong lý thuyết chuẩn hoá [2]. Phụ  thuộc hàm là khái niệm ngữ nghĩa, liên quan đến quan hệ ngữ nghĩa cụ thể giữa  các thuộc tính của một quan hệ.  Việc xác định các dạng chuẩn mờ ( fuzzy normal form ) sẽ  là cơ sở cho  việc thiết kế CSDL tránh việc dư thừa dữ liệu cũng như tạo ra các ràng buộc dữ  liệu chặt chẽ hơn. Một số dạng chuẩn mờ dữ liệu được mô tả như sau:  3.5.1 Dạng chuẩn mờ F1NF  Dạng chuẩn mờ F1NF [10] (Fuzzy First Normal Form) được mở rộng từ  khái niệm dạng chuẩn 1NF trong CSDL quan hệ truyền thống.  Định nghĩa: Cho D k  là miền xác định của thuộc tính A k  , khi đó lược đồ quan hệ  R được gọi là dạng chuẩn mờ  F1NF nếu và chỉ nếu với bất kỳ quan hệ r Í R thì  không chứa bất kỳ một thuộc tính đa giá trị nào. 46  Thuật toán: Thuật toán đưa về dạng chuẩn mờ  F1NF  Khi quan hệ R không ở dạng chuẩn mờ F1NF thì  ta  loại  bỏ các bộ mà  thuộc tính của nó vi phạm dạng chuẩn mờ F1NF  Sắp xếp các thuộc tính này với các thuộc tính khác thành các bộ riêng rẽ  thoả mãn dạng chuẩn mờ F1NF.  Ví dụ:  Cho bảng Nhanvien  như sau  Nhanvien  Hoten  Tuoi  Ngoai ngu  Trần Văn Hòa  45  Anh  Lê Thị Hoa  Hơi trẻ  {Anh, Pháp}  Bùi Thị Huệ  Trung niên  Ả rập  Bùi Văn Trường  50  Đức  Bảng 5: Bảng quan hệ Nhân viên  Trong quan hệ trên ta có các bộ:  t 1 =(Trần Văn Hoà, 45, Anh}  t 2 =(Lê Thị Hoa, hơi trẻ, [Anh, Pháp]}  t 3 =(Bùi Thị Huệ, trung niên, Ả rập}  t 4 =(Bùi Văn Trường, 50, Đức}  Lược đồ trên không thoả mãn dạng chuẩn mờ F1NF vì ở bộ thứ 2 Lê Thị  Hoa nói 2 ngôn ngữ và thuộc tính này là đa giá trị. Chúng ta áp dụng thuật toán  trên để đưa lược đồ trên về dạng chuẩn mờ F1NF. Ta có như sau:  t 1 =(Trần Văn Hoà, 45, Anh}  t 2 =(Lê Thị Hoa, hơi trẻ, [Anh, Pháp]} Þ  t 5 =(Lê Thị Hoa, hơi trẻ, Anh}  t 6 =(Lê Thị Hoa, hơi trẻ, Pháp}  t 3 =(Bùi Thị Huệ, trung niên, Ả rập}  t 4 =(Bùi Văn Trường, 50, Đức}  Khi đó lược đồ R đã ở dạng chuẩn mờ F1NF  3.5.2 Dạng chuẩn mờ F2NF  Cũng tương tự như trong CSDL quan hệ truyền thống, khi xét đến CSDL  quan  hệ mờ  thì  dạng  chuẩn mờ  F2NF  [10]  được  xây  dựng dựa  trên  các  khái  niệm liên quan đến phụ thuộc hàm mờ hoàn toàn ( full FFD) và phụ thuộc hàm  từng phần. 47  Định nghĩa: Cho F là tập các phụ thuộc hàm mờ của lược đồ R và K là khoá mờ  của R với mức thoả a . R được gọi là dạng chuẩn mờ F2NF nếu và chỉ nếu các  thuộc tính không khoá mờ phụ thuộc hoàn toàn vào khoá chính. Nói cách khác  là không có thuộc tính không khoá nào phụ thuộc hàm từng  phần trên khoá mờ  K. Ví dụ:  Cho  quan  hệ  R  (  A,  B,  C,  D  )  và  phụ  thuộc  hàm  mờ:  (AB®D) 0.6  và  (A®C) 0.85  Ta thấy (AB) + 0.6  = { A, B, C, D} ÞAB là khoá mờ với mức thoả 0.6  Khoá  này  không  phải  là  khoá  chính do  thuộc  tính  không  phải  là  khoá C  phụ  thuộc một phần vào khoá chính AB của quan hệ R. Do đó quan hệ  R không  phải là ở dạng chuẩn mờ F2NF.  Khi lược đồ chưa ở dạng chuẩn mờ F2NF thì ta cần có thuật toán để đưa  lược  đồ  này  về  dạng  chuẩn  nêu  trên. Dưới  đây  là  các  bước  chi  tiết  của  thuật  toán.  3.5.2.1 Xác định dạng chuẩn mờ F2NF  Thuật toán:  Thuật toán xác định phụ thuộc hàm một phần:  Giả sử xét phụ thuộc hàm một phần (X®Y) a  If  ­  Tập Left­hand side  X  của tập các phụ thuộc hàm chứa thuộc tính đơn thì  thuật toán dừng lại  o  Phụ thuộc hàm không phải là phụ thuộc hàm một phần  Else  ­  Bắt đầu với sự kết hợp các  thuộc  tính đơn. Sau đó  xét  tất cả các bộ kết  hợp giữa các thuộc tính của X trừ sự kết hợp có chứa toàn bộ các thuộc  tính của quan hệ R.  o  Tìm bao đóng của các sự kết hợp thuộc tính  o  Nếu bao đóng chứa tất cả các thuộc tính bên phải (right­hand side) ­  Y của phụ thuộc hàm với mức  thoả b ³ ¶ thì đó  là Phụ thuộc hàm  một phần  ­  Lặp lại quá trình trên.  Để xác định xem quan hệ đã cho có phải ở dạng chuẩn mờ F2NF hay không  thì ta cần kiểm tra toàn bộ các thuộc tính không khoá để xem có phụ thuộc hàm  một phần trên các khoá mờ của quan hệ R.  Thuật toán:  Thuật toán xác định dạng chuẩn  mờ  F2NF. Xét K là tập các khoá mờ của  quan hệ R  For  K i ÍR  ­  Nếu khoá mờ  có  chứa  thuộc  tính đơn Þ  không  có  phụ  thuộc  hàm một  phần. Lặp lại và tiếp tục với các cơ hội khác. 48  ­  Với các thuộc tính không khoá A j  R Î o  Lấy phụ thuộc hàm mờ  K i ®A j  với mức thoả ¶ o  Áp dụng thuật toán xác định Phụ thuộc hàm mờ một phần nêu trên  để  tìm  ra  liệu một  phụ thuộc  hàm có  là phụ  thuộc  hàm một phần  hay không. Nếu có thì quan hệ trên không ở dạng chuẩn mờ F2NF  3.5.2.2 Đưa quan hệ về dạng chuẩn mờ F2NF  Trong trường hợp quan hệ R không ở dạng chuẩn mờ F2NF  ta có thể đưa  quan hệ R về dạng chuẩn mờ F2NF bằng thuật toán sau:  Thuật toán:  Thuật toán chuẩn hoá về dạng chuẩn  mờ  F2NF.  R  không  ở  dạng  chuẩn  mờ  F2NF,  sử  dụng  thuật  toán  xác  định  dạng  chuẩn  F2NF, tìm các khoá mờ chấp nhận được và các thuộc tính không khoá mờ.  ­  Sắp  xếp  lại  và  thiết  lập một  quan  hệ   mới  cho mỗi  khoá mờ một  phần  (partial fuzzy keys) và các thuộc tính không khoá phụ thuộc vào nó  ­  Phân rã các thuộc tính không khoá mờ mà nó là phụ thuộc hàm mờ một  phần vào các khoá mờ của quan hệ gốc và thiết lập quan hệ mới với các  thuộc tính còn lại.  Ví dụ 1:  Cho  quan  hệ  R  (  A,  B,  C,  D  )  và  phụ  thuộc  hàm  mờ:  (AB®D) 0.6  và  (A®C) 0.85  Ta thấy (AB) + 0.6  = { A, B, C, D} ÞAB là khoá mờ với mức thoả 0.6  Phụ thuộc hàm mờ (A®C) 0.85  ( A là thuộc tính của khoá mờ) ÞCần sắp  xếp lại quan hệ R  Áp dụng thuật toán trên ta có 2 quan hệ mới:  R1 = ( A, C)  trong đó A là khoá mờ với mức thoả 0.85  R2 = ( A, B, D) trong đó AB là khoá mờ với mức thoả 0.6  Khi đó các quan hệ R1, R2 đã ở dạng chuẩn F2NF.  Ví dụ 2:  Ta xét ứng dụng Quản lý rủi ro. Xây dựng một hệ thống đánh giá kết quả.  §  Các khách hàng: cá nhân, doanh nghiệp và liên danh  Các thuộc tính của khách hàng cá nhân (tuổi, tình trạng hôn nhân, địa chỉ)  trong  khi  đó  thuộc  tính  của  khách  hàng  doanh  nghiệp  sẽ  phức  tạp  hơn  và  có  chứa các dữ liệu mờ. Các thuộc tính của quan hệ Đánh giá rủi do như sau:  §  Vốn (Vốn điều lệ)  §  Doanh thu (Doanh thu hằng năm)  §  Nhân sự (Số lượng nhân sự)  §  Kinh nghiệm (Số năm kinh nghiệm)  §  ĐKKD (Đăng ký kinh doanh)  §  Tài sản (Đánh giá nền tảng tài chính)  §  Công ty (Đánh giá cơ cấu tổ chức doanh nghiệp) 49  §  Phát mại  tài  sản  (Đánh  giá  giá  trị  tài  sản  của  doanh  nghiệp  trong  trường hợp rủi do cần phát mại tài sản)  §  Tín chấp (Đánh giá mức độ tín nhiệm của doanh nghiệp)  Các Phụ thuộc hàm mờ bao gồm:  FFD1: Vốn điều lệ và doanh thu hằng năm quyết định năng lực tài chính  của doanh nghiệp đó  {Vốn, Doanh thu}  0.75 ®  Tài sản  FFD2: Số  lượng nhận sự,  số  năm kinh  nghiệm và  số ĐKKD của  doanh  nghiệp có thể sẽ quyết định tăng hay giảm giá trị công ty khi phát mại tài  sản  { Nhân sự, Kinh nghiệm, ĐKKD}  0.65 ®  Công ty  FFD3: Nền tảng tài chính và cơ cấu tổ chức doanh nghiệp sẽ quyết định  chủ yếu đến giá trị của doanh nghiệp trong trường hợp rủi ro cần phát mại  tài sản  { Tài sản, Công ty}  0.85 ®  Phát mại tài sản  FFD4: Đánh giá mức độ rủi do của công ty khi phải phát mại tài sản có  thể sẽ quyết định tăng hay giảm tín nhiệm của doanh nghiệp  Phát mại tài sản  0.8 ®  Tín chấp  Trong qua hệ trên thì thuộc tính ( Vốn, Doanh thu, Kinh nghiệm, ĐKKD)  là khoá mờ với mức thoả  0.65 a =  . FFD1 có chứa thuộc tính của khoá mờ  (Vốn,  Doanh thu) do đó  thuộc  tính Tài sản  là  thuộc  tính không khoá phụ thuộc hàm  vào một phần  của khoá mờ trên.  Tương tự như vậy đối với FFD2 ta thấy thuộc tính Công ty cũng là thuộc  tính không khoá phụ thuộc hàm vào một phần của khoá mờ.  Do đó, quan  hệ  trên không phải ở dạng chuẩn mờ F2NF. Để chuẩn hoá  quan hệ trên về dạng chuẩn F2NF ta phân rã thành 2 quan hệ như sau:  R1 = ( Vốn, Doanh thu, Tài sản)  Trong đó  thuộc  tính  {Vốn, Doanh  thu}  là  khoá mờ  với mức  thoả  0.75  và  phụ  thuộc hàm là:  {Vốn, Doanh thu}  0.75 ®  Tài sản  R2 = ( Nhân sự, Kinh nghiệm, ĐKKD, Công ty)  Trong đó thuộc tính {Nhân sự, Kinh nghiệm}, ĐKKD là khoá mờ với mức thoả b = 0.65 và phụ thuộc hàm là:  { Nhân sự, Kinh nghiệm, ĐKKD}  0.65 ®  Công ty  Khi đó  trong quan hệ cũ vẫn còn những thuộc  tính còn  lại,  loại các  thuộc  tính  Tài  sản  và Công  ty  (  các  thuộc  tính không khoá mà  phụ  thuộc một  phần vào  khoá chính) khỏi quan hệ ban đầu. Khi đó quan hệ bao gồm các thuộc tính còn  lại là:  R3= ( Vốn, Doanh thu,  Nhân sự, Kinh nghiệm, ĐKKD, Phát mại tài sản,  Tín chấp)  Trong đó {Vốn, Doanh thu,  Nhân sự, Kinh nghiệm, ĐKKD}  là khoá mờ  với mức thoả d =0.65 và các phụ thuộc hàm mờ là: 50  { Nhân sự, Kinh nghiệm, ĐKKD}  0.65 ®  Công ty  {Vốn, Doanh thu}  0.75 ®  Tài sản  Như vậy các quan hệ đã không còn các thuộc tính không khoá mờ phụ thuộc vào  một  phần  của  khoá  chính.  Khi  đó  các  quan  hệ  R1,  R2,  R3  đã  ở  dạng  chuẩn  F2NF.  3.5.3 Dạng chuẩn mờ F3NF  Định nghĩa: Cho F là tập của các phụ thuộc hàm của quan hệ R. K là khoá mờ  của quan hệ R với mức thoả a . R được gọi là dạng chuẩn mờ F3NF nếu và chỉ  nếu R ở dạng chuẩn F2NF và Phụ thuộc hàm X a ®  A  F Π , A ËX, hoặc X chứa  khoá mờ hoặc A là khoá chính mờ ( không tồn tại phụ thuộc bắc cầu).  Ta có thể sử dụng trực tiếp định nghĩa dạng chuẩn F3NF để xác định xem  quan hệ R có ở dạng chuẩn F3NF hay không. Tất cả các phụ thuộc hàm được  kiểm tra lại với các điều kiện:  ­  Nếu các  thuộc  tính bên  trái phụ thuộc  hàm chứa  toàn bộ  thuộc  tính của  phía bên phải phụ thuộc hàm thì phụ thuộc hàm đó không vi phạm dạng  chuẩn F3NF  ­  Nếu các thuộc tính bên trái phụ thuộc hàm có chứa khoá mờ của quan hệ  thì dạng chuẩn F3NF không bị vi phạm  ­  Nếu các thuộc tính bên phải của phụ thuộc hàm đều là các khoá chính mờ  thì dạng chuẩn F3NF cũng không bị vi phạm  Với các điều kiện trên ta xây dựng thuật toán xác định dạng chuẩn F3NF như  sau:  Thuật toán:  Thuật toán xác định dạng chuẩn  mờ  F3NF. Xét K là tập các khoá mờ  của quan hệ R.  (1) For all  FDDs  X a ®  Y trong R  §  If XÊY , R ở dạng F3NF , else  §  If XÊK i  trong đó K i  K Ì  , R ở dạng F3NF, else  §  Đặt P  là  tập các khoá chính mờ của quan hệ R.  If  Y ÍP, R ở  dạng F3NF  (2) If có ít nhất một phụ thuộc hàm trong quan hệ R không thoả mãn các  điều kiện trên thì R không ở dạng chuẩn F3NF.  Ví dụ:  Cho  quan  hệ  R  (A,  B,  C,  D,  E)  và  phụ  thuộc  hàm  mờ:  AB  0.85 ®  C,  AC  0.8 ®  D và C  0.7 ®  E  Ta thấy phụ thuộc hàm đầu tiên AB  0.85 ®  C có khoá mờ, và các thuộc tính  A, B của vế trái phụ thuộc hàm không vi phạm dạng chuẩn F3NF  Ở phụ thuộc hàm AC  0.8 ®  D và C  0.7 ®  E đã vi phạm dạng chuẩn F3NF vì  A, C không là một phần của khoá mờ {A,B} và D, E không phải là khoá chính.  Do đó R không ở dạng chuẩn F3NF. Cần sắp xếp lại quan hệ R 51  Áp dụng thuật toán trên ta có 2 quan hệ mới:  R1 = ( A, B,C)  trong đó {A,B} là khoá mờ với mức thoả 0.85  R2 = ( C,D, E) trong đó C là khoá mờ với mức thoả 0.7  Khi đó các quan hệ R1, R2 đã ở dạng chuẩn F3NF.  3.5.4 Dạng chuẩn mờ Boyce Codd (FBCNF)  Tương tự như trong CSDL quan hệ  truyền thống, dạng chuẩn mờ Boyce  Codd ( FBCNF) chặt chẽ hơn dạng chuẩn F3NF. Dạng chuẩn FBCNF sẽ tránh  được việc dư thừa dữ liệu trong thiết kế CSDL.  Định nghĩa: Cho F là tập của các phụ thuộc hàm của quan hệ R. K là khoá mờ  của quan hệ R với mức  thoả a . R được gọi  là dạng chuẩn mờ FBCNF nếu và  chỉ nếu R ở dạng chuẩn F3NF và với bất kỳ phụ thuộc hàm X a ®  A  F Π , A ÌX  hoặc X  là siêu khoá mờ (fuzzy superkey) của R thì X  K Ê  .  Để kiểm tra xem quan hệ R có ở dạng chuẩn FBCNF hay không thì tất cả  các phụ thuộc hàm mờ của quan hệ R phải thoả mãn hai điều kiện:  ­  Các thuộc tính phía bên trái của phụ thuộc hàm mờ có chứa toàn bộ các  thuộc tính bên phải.  ­  Các thuộc tính phía bên trái của phụ thuộc hàm mờ có chứa bất kỳ khoá  mờ nào của quan hệ R  thì phụ thuộc hàm mờ đó không vi phạm dạng chuẩn FBCNF. Thuật  toán xác  định xem quan hệ R có ở dạng chuẩn FBCNF hay không được  xây dựng như  sau:  Thuật toán:  Thuật toán xác định dạng chuẩn  mờ  FBCNF.  Giả sử có phụ thuộc hàm vi phạm chuẩn FBCNF là X b ®  A với mức thoả b  nào đó, trong đó A, X ÌR và A là thuộc tính đơn trị. Phân rã quan hệ R thành  hai quan hệ R­A và XA  Lặp lại cho tất cả các phụ thuộc hàm vi phạm chuẩn FBCNF cho đến khi  trong quan hệ R không còn phụ thuộc hàm nào vi phạm chuẩn FBCNF. Khi đó  các quan hệ mới được hình thành sẽ ở dạng chuẩn FBCNF.  Ví dụ:  Cho quan hệ R = ( A, B, C, D, E, F, G ), các phụ thuộc hàm mờ với các  mức thoả tương ứng:  (CE® A) 0.8 , (BD ®  E) 0.7  và (C ®B) 0.9  và A là khoá mờ của R với mức  thoả 0.85, tức là: (A®BCDEFG) 0.85 .  Xét quan hệ trên ta thấy R đã ở dạng chuẩn F2NF vì không có phụ thuộc  hàm từng phần do A là khóa đơn trị.  Xét R có ở dạng chuẩn F3NF?  ­ Ta  thấy A  là  khoá  của  quan  hệ mà  phụ  thuộc  hàm BD  0.7 ®  E  là  phụ  thuộc hàm giữa các  thuộc  tính không khoá. Do đó quan hệ R không thoả mãn  điều kiện của dạng chuẩn F3NF.  Ta phân ra quan hệ R thành hai quan hệ: 52  R1 = ( B, D, E ) với các phụ thuộc hàm là (BD ®  E) 0.7 , BD là khoá mờ  của quan hệ R1 với mức thoả 0.7  R2 = ( A,B,C,D,F,G ) với các phụ thuộc hàm (C ®B) 0.9 , A là khoá mờ  với mức thoả 0.85  Sau khi phân rã, R1 đã ở dạng chuẩn F3NF do không còn phụ thuộc hàm  bắc cầu  Xét quan hệ R2 ta  thấy vẫn còn phụ thuộc hàm (C ®B) 0.9  là phụ thuộc  hàm bắc cầu nên R2 chưa ở dạng chuẩn F3NF. Tiếp tục tách quan hệ R2 thành 2  quan hệ mới:  R3 = ( A,C,D,F,G ) và A là khoá mờ với mức thoả 0.85  R4 = ( B,C ) với các phụ thuộc hàm (C ®B) 0.9 , C là khoá mờ với mức  thoả 0.9  Khi đó R3, R4 đã ở dạng chuẩn F3NF.  Sau khi phân rã xong thì các quan hệ R1, R3, R4 đã ở dạng chuẩn FBCNF. 53  KẾT LUẬN  4.1  Ý nghĩa khoa học và thực tiễn của đề tài  Trong thiết kế cơ sở dữ liệu thì lớp phụ thuộc dữ liệu đóng vai trò rất quan  trọng  và một trong những lớp phụ thuộc dữ liệu đầu tiên là lớp phụ thuộc hàm.  Việc khai phá lớp phụ thuộc hàm có yếu tố quyết định trong việc thiết kế Lược  đồ khái niệm, bước đầu của quá trình xây dựng Cơ sở dữ liệu. Một trong những  đặc điểm quan trọng của phụ thuộc dữ liệu là việc nghiên cứu về lớp phụ thuộc  hàm và khoá  (một khái niệm quan trọng trong việc xác định quan hệ phụ thuộc  dữ liệu). Việc phát triển nghiên cứu về dữ liệu mờ (fuzzy data) đòi hỏi việc mở  rộng  khái  niệm  liên  quan  đến  lớp  phụ  thuộc  hàm  mờ  (fuzzy  functional  dependency) và nghiên cứu về khái niệm khoá mờ (fuzzy key) trong CSDL quan  hệ. Đây cũng là sự mở rộng hết sức tự nhiên của quá trình phát triển Cơ sở dữ  liệu.  Đề tài nghiên cứu đã thể hiện một cách nhìn nhận khác về phụ thuộc hàm  mờ, có  thể gợi mở những hướng tiếp cận mới về  lớp phụ thuộc hàm này. Bên  cạnh đó việc tìm hiểu về các khái niệm liên quan đến việc mở rộng bao đóng tập  thuộc tính, mở rộng định lý tương đương có một ý nghĩa quan trọng trong việc  thiết kế và xây dựng CSDL sát với thực tế hơn. Việc nghiên cứu về dữ liệu mờ  này cũng cho phép xử lý và tìm kiếm thông tin trong CSDL mờ một cách hiệu  quả hơn.  4.2  Kết luận và kiến nghị  4.2.1  Kết luận  Có thể nói Cơ sở dữ  liệu  là một  lĩnh vực nghiên cứu rất  rộng  lớn,  trong  phạm vi luận văn này chưa và cũng không thể nêu hết toàn bộ các vấn đề về Cơ  sở dữ liệu mà chỉ đề cập đến một khía cạnh nào đó về lớp phụ thuộc dữ liệu là  lớp phụ thuộc hàm. Ngoài việc trình bày lại một số khái niệm, thuật toán cơ bản  luận văn đã đạt được một số kết quả mở rộng nhất định:  ­  Tổng hợp lại khái niệm trong CSDL quan hệ truyền thống  ­  Nghiên cứu về lớp Phụ thuộc hàm mờ:  o  Đưa  ra  một  số  quan  điểm  về  lớp  phụ  thuộc  hàm  mờ  trong  CSDL quan hệ.  o  Hệ tiên đề cho lớp Phụ thuộc hàm mờ  o  Khái niệm và thuật toán tìm bao đóng trong ngữ cảnh mờ  o  Khoá mờ (fuzzy key) và thuật toán tìm khoá  o  Định lý tương đương trong lớp phụ thuộc hàm mờ  ­  Tìm hiểu mở rộng khái niệm các dạng chuẩn thành dạng chuẩn mờ ( fuzzy  normal form) F1NF, F2NF, F3NF, FBCNF. 54  Tuy vẫn còn những hạn chế nhưng những kết quả đạt được cũng góp phần  quan trọng cho việc nghiên cứu về lớp phụ thuộc hàm mờ, xây dựng CSDL mờ  với các dữ liệu mô tả những mối quan hệ giữa các đối tượng trong thế giới thực  một cách cụ thể hơn, chính xác hơn, góp phần vào sự phát triển CSDL nói chung  và CSDL mờ nói riêng.  4.2.2  Hướng phát triển đề tài  Nghiên  cứu về  lớp  phụ  thuộc  hàm mờ  trong CSDL  là một  trong  những  vấn đề khó và bao gồm rất nhiều các vấn đề nhỏ bên trong. Trong phạm vi luận  văn này cũng đã  đạt được một số kết quả nhất định trong việc nghiên cứu về lớp  phụ thuộc hàm mờ trong CSDL quan hệ. Với mong muốn được nghiên cứu sâu  hơn về lĩnh vực CSDL nói chung cũng như tập trung vào lớp phụ thuộc hàm mờ,  khoá mờ hướng nghiên cứu tiếp theo của tác giả trong vấn đề này bao gồm:  ­  Tìm kiếm các thuật toán tìm Phụ thuộc hàm mờ.  ­  Tìm kiếm các thuật toán tốt hơn cho việc tìm khoá mờ.  ­  Nghiên cứu về mối liên hệ giữa các dạng chuẩn mờ.  ­  Khai phá dữ liệu mờ (fuzzy data mining). 55  TÀI LIỆU THAM KHẢO  Tiếng Việt  1.  Ngô Thanh Thảo (2002) , Giáo trình Cơ sở dữ liệu,  ĐH Cần Thơ, tr.  2­13.  2.  Đỗ Trung Tuấn (2004), Cơ sở dữ liệu, NXB Đại học Quốc gia Hà nội,  tr. 7­13, 24­25, 81­87, 114­123.  3.  Lê Tiến Vương (1996), Nhập môn CSDL quan hệ, NXB Khoa học kỹ  thuật, tr. 9­15, 80­90.  Tiếng Anh  4.  Brian  Hartlieb,  Functional  Dependencies  in  Fuzzy  Databases,  21st  Computer Science Seminar, pp. 1­3.  5.  J.C.Cubero & M.A.Vila  (1994),  A  new  definition  of  fuzzy  functional  dependency  in  fuzzy  realtional  databases,  International  journal  of  intelligent systems, pp. 441­443.  6.  Guoqing  Chen,  Etienne  Kerre  &  Jacques  Vandenbulcke  (1994),  A  computational algorithm for the FFD transitive closure and complete  axiomatization  of  fuzzy  functional  dependencies  (FFD),  International  journal of intelligent systems, pp. 422­436.  7.  Nedzad  Dukic,  Zikrija  Avdagic  (2004),  Formalization  of  provenes  fuzzy  functional  dependency  in  fuzzy  database,  Mathware  &  Soft  computing 11, pp. 32­34.  8.  Nauman A.Chaudhry, James R.Moyne, Elke A.Rundensteiner (2004),  A  design  methodology  for  databases  with  uncertain  data,  The  university  of  Michigan,  Dept.  of  electrical  engineering  &  computer  science, pp. 1­4.  9.  Õgũn  Bahar,  Adnal  Yazci  (2004),  Normalization  and  lossless  join  decomposition  of  similarity  –  Based  fuzzy  relational  databases,  International journal of intelligent systems, pp. 894­ 906.  10.P.  C.  Saxena,  and  D.  K.  Tayal  (2007),  Fuzzy  Join  Dependency  in  Fuzzy Relational Databases,  International  journal  of  information  and  communication technology, pp. 37­39  11.Qiang Wei & Guoqing Chen (2004), Efficient discovery of  functional  dependencies  with  degrees  of  satisfaction,  International  journal  of  intelligent systems, pp. 1091­1096.  12.Sadeq  Al  Hamouz  and  Ranjit  Biswas  (2006),  Fuzzy  Functional  dependencies  in  relational  database,  International  journal  of  computational cognition, pp. 39­41. 56  13.Stephanne  Lopes,  Jean­Marc  Petit,  Lotfi  Lakhal  (2000),  Efficient  discovery  of  functional  dependencies  and  Amstrong  relations,  Speringer – Verlag Berlin Heidelberg, pp. 351­353.  14. T.C.Ling, Mashakuri Hj.Yaacob, K.K.Phang  (1997),  Fuzzy  database  framework­relation  versus  object  –  oriented  model,  IEEE,  pp.  246­  247.  15. Z.M.MA + ,  Li  Yan  (2008),  A  literature  of  fuzzy  database  models,  Journal of information science and engineering 24, pp.191­193.  16. Y.Dhanalakshmi,  Dr.I.  Ramesh  Babu  (2008),  Intrusion  Detection  Using  Data  Mining  Along  Fuzzy  Logic  and  Genetic  Algorithms,  IJCSNS  International  Journal  of  Computer  Science  and  Network  Security, VOL.8 No.2, pp. 27­29.  Website  17.   18.   19.  57  PHỤ LỤC  Thuật toán tìm bao đóng tập thuộc tính X +  Input: Tập thuộc tính, tập các PTH ban đầu  Output: Bao đóng của thuộc tính mờ với mức thoả q  nào đó1  (0 £ q £1)  Ngôn ngữ sử dụng: Pascal  {Chuong trinh mo phong thuat toan tim bao dong cua thuoc tinh mờ trong  CSDL quan he}  Program Tinh_bao_dong;  uses crt;  type contro= ^baodong;  baodong= record  thuoc_tinh: char;  muc_thoa:real;  next: contro; {tro sang phan tu tiep theo}  end;  mang= array[1..50] of char;  {*********Khai bao bien*******************************}  var  i: byte;  n,m:integer; 58  c,Y: char;  f: TEXT;  s: String;  muc_thoa,chi_so:array [1..50] of real;  vt,thuoc_tinh:array[1..50]of char;  vp: array[1..50]of string;  code: integer;  Blist, X, last: contro;   {Blist la bao dong tam thoi}  MXD: mang;  {Mien xac dinh cua tap thuoc tinh}  {**********Thu tuc doc du lieu tu File *******}  Procedure Doc_du_lieu;  Begin  Assign(f, 'Input.txt');  Reset(f);  readln(f);  readln(f,n);  readln(f,m);  for i:=4 to (3+n) do  begin  while not EOLN(f) do  begin 59  read(f,thuoc_tinh[i]);  read(f,c);  read(f,s);  val(s,chi_so[i],Code);  end;  readln(f);  end;  readln(f);  readln(f);  i:=14;  While not EOF(F) do  begin While not EOLN(f) do  begin  read(f,vt[i]);  read(f,c); read(f,c);  read(f,c);  s:='';  while c' ' do  begin  s:=s+c;  read(f,c); 60  end;  vp[i]:=s;  read(f,c);  read(f,s);  val(s,muc_thoa[i], Code);  end;  readln(f);  i:=i+1;  end;  End;  {Ham kiem tra xem thuoc tinh Y da nam trong MXD hay chua?}  Function Kiemtra(Y:char;MXD: mang):Boolean;  var i:byte;  kt:Boolean;  Begin  kt:= false;  for i:=1 to 50 do  begin  if (Y=MXD[i]) then  begin  kt:=true;  end; 61  end;  Kiemtra:=kt;  End;  {***********Ham kiem tra xem phan tu co thuoc danh sach hay  khong*************}  function kiem_tra_thuoc(c: char; p: contro): boolean;  var q: contro;  kt: boolean;  begin  q:= p;  kt:= false;  if p= nil then kt:= false  else  begin  while q nil do begin  if (q^.thuoc_tinh = c) then  begin  kt:= true;  break;  end;  q:=q^.next;  end; 62  end;  kiem_tra_thuoc:= kt;  end;  {******************************************************}  function min(a,b: real): real;  begin  if a>b then min:= b  else min:= a;  end;  {******************************************************}  function max(a,b: real):real;  begin  if a>b then max:=a  else max:= b;  end;  {************Ham so sanh 2 bao dong tam thoi*********}  Function Sosanh(var X:contro; var Y:contro): Boolean;  var tg:contro;  kt: boolean;  Begin  tg:=X;  While tgnil do 63  begin  if not(kiem_tra_thuoc(tg^.thuoc_tinh, Y)) then  begin  sosanh:= true;  exit;  end;  tg:= tg^.next;  end;  tg:=Y;  While tgnil do  begin  if not(kiem_tra_thuoc(tg^.thuoc_tinh, X)) then  begin  sosanh:= true;  exit;  end;  tg:= tg^.next;  end;  sosanh:= false;  End;  {****Thu tuc them phan tu vao tap bao dong tam thoi***}  procedure Them(c: char; r: real;var p: contro); 64  var phan_tu_moi: contro;  begin  if p= nil then  begin  new(phan_tu_moi);  phan_tu_moi^.thuoc_tinh:= c;  phan_tu_moi^.muc_thoa:= r;  phan_tu_moi^.next:=nil;  p:= phan_tu_moi;  end  else  begin  new(phan_tu_moi);  phan_tu_moi^.thuoc_tinh:= c;  phan_tu_moi^.muc_thoa:= r;  phan_tu_moi^.next:=p;  p:= phan_tu_moi;  end;  end;  {***Ham tim vi tri cua mot thuoc tinh trong bao dong***}  Function vi_tri(c: char; p: contro): contro; 65  var q: contro;  begin  q:= p;  while q^.thuoc_tinh c do q:= q^.next;  vi_tri:= q;  end;  {*******Ham hop mo 2 bao dong tam thoi******}  Function hop(X,Blist: contro): contro;  var p,q,tg: contro;  Begin  tg:=nil;  p:= X;  while pnil do  begin  if not(kiem_tra_thuoc(p^.thuoc_tinh,tg)) then  Them(p^.thuoc_tinh,p^.muc_thoa, tg)  else  begin q:= vi_tri(p^.thuoc_tinh,tg);  q^.muc_thoa:=max(q^.muc_thoa,p^.muc_thoa);  end; 66  p:= p^.next;  end;  p:= Blist;  while pnil do  begin  if not(kiem_tra_thuoc(p^.thuoc_tinh, tg)) then  Them(p^.thuoc_tinh,p^.muc_thoa, tg)  else  begin  q:= vi_tri(p^.thuoc_tinh,tg);  q^.muc_thoa:= max(q^.muc_thoa,p^.muc_thoa);  end;  p:= p^.next;  end;  hop:= tg;  End;  {******************************************************}  Procedure Inbaodong( X:contro);  var p: contro;  Begin  p:=X; 67  writeln;  writeln('Bao dong cua tap thuoc tinh ', p^.thuoc_tinh ,' la:');  While pNil do  begin  write('(',p^.thuoc_tinh,',',p^.muc_thoa:2:2,')');  write(' ');  p:=p^.next;  end;  End;  {**********Thu tuc tim bao dong cua thuoc tinh ********}  Procedure thuchien(B: char);  var i,j:byte;  p,q,tg:contro;  r: real;  Begin  {Khoi tri bao dong cua thuoc tinh B}  new(X);  X^.thuoc_tinh:=B;  X^.muc_thoa:=1;  X^.next:=nil;  {Khoi tri mien xac dinh} 68  for i:= 1 to 50 do  MXD[i]:='@';  {***************************************************}  MXD[2]:= B;  n:= 1;{n la so thuoc tinh trong MDX}  while (1>0) do  begin  for i:=14 to (13+m) do  begin  if Kiemtra(vt[i],MXD) then  begin  for j:= 1 to length(vp[i]) do  begin  if not(Kiemtra(vp[i][j],MXD)) then  begin  MXD[n+1]:=vp[i][j];  n:= n+1;  end;  end;  Them(vp[i][2],muc_thoa[i],Blist);  for j:= 2 to length(vp[i]) do  begin 69  if kiem_tra_thuoc(vp[i][j],Blist) then  begin  p:= vi_tri(vp[i][j],Blist);  P^.muc_thoa:= min(p^.muc_thoa,muc_thoa[i]);  end  else  Them(vp[i][j],muc_thoa[i], Blist);  end;  end;  end;  tg:= hop(X,Blist);  if sosanh(X,tg) then X:=tg  else exit;  end;  End;  BEGIN  clrscr;  Doc_du_lieu;  writeln('Tap thuoc tinh');  writeln('********************************************'); 70  for i:= 4 to (3+n) do  begin  writeln(thuoc_tinh[i], '  ', chi_so[i]:2:2);  end;  writeln;  writeln('Tap cac PTH');  writeln('********************************************');  for i:= 14 to (13+m) do  begin  writeln(vt[i], '­>',vp[i],'   ', muc_thoa[i]:2:2);  end;  Repeat  clrscr;  write('Nhap thuoc tinh de tinh bao dong: '); readln(Y);  thuchien(Y);  Inbaodong(X);  writeln;  writeln('Ban co muon tiep tuc chuong trinh khong? (C/K)');  write('Cau tra loi la: '); readln(c);  until (c='k') or (c='K');  clrscr;  readln; 71  END.  Một số giao diện của việc cài đặt Thuật toán tìm bao đóng tập thuộc tính X +  Hình 4: Tập Input  Hình 5: Giao diện cài đặt thuật toán 72  Hình 6: Giao diện chạy thuật toán (Nhập tập thuộc tính cần tính bao đóng X + )  Hình 7: Kết quả bao đóng của tập thuộc tính {A,B,C}