Báo cáo 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ệ

TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệp Đề tài: 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Ệ 1  LỜI CAM ĐOAN  Tôi xin cam đoan: 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ệ” là công trình  nghiên cứu riêng của tôi  Các kết quả nghiên cứu trong luận văn là trung thực. Nếu sai tôi xin hoàn  toàn chịu trách nhiệm.  Hà Nội, ngày 15 tháng 11 năm 2009  Học viên  Trần Thành Trung 2  LỜI CẢM ƠN  Tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Vũ Ngọc Loãn, người  đã  hướng dẫn,  truyền đạt những kinh nghiệm quý báu và  tận  tình giúp đỡ tác  giả hoàn thành  luận văn này.  Tác giả xin cảm ơn sự quan tâm giúp đỡ của các thầy, cô trong khoa Công  nghệ thông tin đã tận tình giảng dạy cũng như giúp đỡ trong quá trình học tập và  nghiên cứu tại Khoa; đồng thời xin cảm ơn sự ủng hộ của các anh chị học viên  lớp K13HTTT đã động viên và giúp đỡ tác giả trong quá trình  thực hiện đề tài  này.  Hà Nội, ngày 15 tháng 11 năm 2009  Học viên  Trần Thành Trung 3  TÓM TẮT  Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế  cơ sở dữ liệu thì 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. Ngày nay, việc mở rộng lớp phụ thuộc hàm này (mờ hoá) đang được  nghiên cứu và tiếp cận theo nhiều hướng khác nhau. Với mục tiêu nghiên cứu về  việc mở rộng này cũng như các khái niệm liên quan, trong đề tài nghiên cứu đã  tìm hiểu sâu về phụ thuộc dữ  liệu và  trình bày các nội dung  liên quan đến lớp  phụ  thuộc  hàm mờ  (fuzzy  functional  dependency), bao đóng  tập  thuộc  tính và  thuật toán tìm bao đóng tập thuộc tính mờ (fuzzy transitive closure),  khoá mờ  (fuzzy key) và thuật toán tìm khoá mờ, các dạng chuẩn mờ trong CSDL quan hệ.  Bên cạnh đó đề tài cũng đã nghiên cứu về việc mở rộng một trong những định lý  quan trọng nhất của việc nghiên cứu CSDL đó là định lý tương đương. 4  ABSTRACT  Data dependency plays a very  important role  in the process of designing  the  database  and  one  of  the  first  data  dependency  class  is  the  functional  dependency.  Today,  the  expansion  of  the  functional  dependency  (fuzzy  functional dependency) are being studied and approached in several ways. With  the  objective  of  researching  on  the  expansion  of  functional  dependency  and  related concepts, my  thesis  focus on researching about data dependency,  fuzzy  functional  dependency,  fuzzy  transitive  closure    and  the  algorithm  for  finding  fuzzy  transitive  closure  of  attributes  ,  fuzzy  key    and  the  algorithm  of  finding  fuzzy keys in relational database. Besides, my thesis also focuses on researching  about the expansion of one of the most important theorems of rational database  – the equivalence theorem. 5  MỤC LỤC  LỜI CAM ĐOAN .............................................................................................. 1  LỜI CẢM ƠN .................................................................................................... 2  TÓM TẮT.......................................................................................................... 3  ABSTRACT....................................................................................................... 4  DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... 7  DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................. 8  DANH MỤC CÁC BẢNG BIỂU....................................................................... 9  MỞ ĐẦU ..........................................................................................................10  I.  Mục tiêu nghiên cứu của đề tài ..............................................................10  II.  Một số kết quả đạt được.........................................................................10  III.  Bố cục của Luận văn .............................................................................11  CHƯƠNG 1. TỔNG QUAN .............................................................................12  1.1 Cơ sở dữ liệu ...........................................................................................12  1.1.1 Các khái niệm chung ........................................................................12  1.1.2 Định nghĩa ........................................................................................12  1.2 Phụ thuộc hàm.........................................................................................13  1.2.1 Định nghĩa ........................................................................................13  1.2.2 Tính chất của Phụ thuộc hàm (Hệ tiên đề Amstrong)........................14  1.2.3 Bao đóng tập thuộc tính ....................................................................15  1.2.4 Định lý tương đương.........................................................................18  1.3 Khoá........................................................................................................19  CHƯƠNG 2. LỚP PHỤ THUỘC HÀM MỜ TRONG CƠ SỞ DỮ LIỆU QUAN  HỆ.....................................................................................................................21  2.1 Dữ liệu mờ ..............................................................................................21  2.1.1 Tập rõ ...............................................................................................21  2.1.2 Tập mờ .............................................................................................21  2.1.3 Các phép toán cơ bản trên tập mờ .....................................................22  2.2 Phụ thuộc hàm mờ...................................................................................23  2.2.1 Định nghĩa ........................................................................................23  2.2.2 Tính chất...........................................................................................27  2.3 Xây dựng hệ tiên đề cho lớp Phụ thuộc hàm mờ ( Hệ tiên đề Amstrong  mở rộng)........................................................................................................29  CHƯƠNG 3. KHOÁ MỜ TRONG CƠ SỞ DỮ LIỆU QUAN HỆ ....................31  3.1  Khoá mờ.................................................................................................31  3.2  Bao đóng tập thuộc tính..........................................................................31  3.2.1. Tính chất của bao đóng tập thuộc tính (X + ) .....................................32  3.2.2  Bài toán thành viên ..........................................................................33  3.2.3 Thuật toán tìm bao đóng ...................................................................34  3.2.4 Tính đúng của thuật toán tìm bao đóng .............................................37  3.3  Định lý tương đương cho tập mờ ............................................................41  3.3.1 Định nghĩa ........................................................................................42 6  3.3.2 Định nghĩa ........................................................................................42  3.3.3  Định lý.............................................................................................42  3.4  Thuật toán tìm khoá mờ..........................................................................44  3.5  Các dạng chuẩn mờ ................................................................................45  3.5.1 Dạng chuẩn mờ F1NF.......................................................................45  3.5.2 Dạng chuẩn mờ F2NF.......................................................................46  3.5.2.1 Xác định dạng chuẩn mờ F2NF .....................................................47  3.5.2.2 Đưa quan hệ về dạng chuẩn mờ F2NF ...........................................48  3.5.3 Dạng chuẩn mờ F3NF.......................................................................50  3.5.4 Dạng chuẩn mờ Boyce Codd (FBCNF) ............................................51  KẾT LUẬN.......................................................................................................53  4.1  Ý nghĩa khoa học và thực tiễn của đề tài.................................................53  4.2  Kết luận và kiến nghị..............................................................................53  4.2.1  Kết luận ...........................................................................................53  4.2.2  Hướng phát triển đề tài ....................................................................54  TÀI LIỆU THAM KHẢO.................................................................................55  PHỤ LỤC .........................................................................................................57 7  DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT  TT  Từ viết tắt  Nghĩa đầy đủ  1  CNTT  Công nghệ thông tin  2  CSDL  Cơ sở dữ liệu  3  HTTT  Hệ thống thông tin  4  HĐH  Hệ điều hành  5  FTH  Phụ thuộc hàm  6  FFD  Fuzzy  Functional Dependency  ­  Phụ  thuộc  hàm  mờ  7  FK  Fuzzy Key – khoá mờ 8  DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ  Hình 1: Hệ thống thông tin ............................................................................... 12  Hình 2: Hệ thống Cơ sở dữ liệu........................................................................ 13  Hình 3: Tập mờ và tập rõ.................................................................................. 22  Hình 4: Tập Input ............................................................................................. 71  Hình 5: Giao diện cài đặt thuật toán ................................................................. 71  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 + ) 72  Hình 7: Kết quả bao đóng của tập thuộc tính {A,B,C} ..................................... 72 9  DANH MỤC CÁC BẢNG BIỂU  Bảng 1: Bảng quan hệ Học sinh ....................................................................... 14  Bảng 2: Bảng các mở rộng của Phụ thuộc hàm................................................. 26  Bảng 3: Bảng các khả năng kết hợp giữa các tập thuộc tính ............................. 27  Bảng 4: Bảng các khả năng kết hợp giữa các tập thuộc tính ............................. 28  Bảng 5: Bảng quan hệ Nhân viên ..................................................................... 46 10  MỞ ĐẦU  I.  Mục tiêu nghiên cứu của đề tài  Trong  những  năm gần đây,  việc  ứng  dụng  công  nghệ  thông  tin  trở  nên  rộng  rãi  và  vai  trò của công nghệ  thông  tin  ngày càng được khẳng định  trong  nhiều  lĩnh vực khác nhau như là: học tập, khoa học kỹ thuật, kinh doanh, quản  lý, ... dưới nhiều quy mô khác nhau. Cơ sở dữ liệu là một trong những lĩnh vực  nghiên cứu đóng vai  trò nền tảng  trong sự phát  triển của công nghệ  thông  tin.  Tuy nhiên sự phát triển của cơ sở dữ liệu cũng chỉ mới bắt đầu trong thời gian  gần  đây,  đặc  biệt  từ  khi  E.F.Codd  giới  thiệu mô  hình Cơ  sở  dữ  liệu  quan  hệ  (Relational Database Model). Ngày nay có rất nhiều hệ quản  trị Cơ sở dữ  liệu  được  xây  dựng  và  phát  triển  dựa  trên mô hình  này  như  là  : MS Access,  SQL  Server, Oracle,…  Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế  cơ sở dữ liệu thì 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ề  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 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.  Với mong muốn được đóng góp một phần công sức nhỏ bé của mình vào  việc nghiên cứu về lớp phụ thuộc dữ liệu và khai phá dữ liệu trong CSDL quan  hệ mục tiêu nghiên cứu của đề tài này chủ yếu chú trọng vào việc nghiên cứu về  sự phụ thuộc  dữ  liệu,  lớp  phụ thuộc  hàm mờ, bao đóng và  thuật  toán  tìm bao  đóng, khoá mờ và thuật toán tìm khoá mờ.  II. Một số kết quả đạt được  Với mong muốn nghiên cứu sâu về lĩnh vực CSDL và các ứng dụng mở rộng  CSDL đề  tài nghiên cứu của tác giả đã đạt được một số kết quả nhất định như  sau: ·  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  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. 11  III.  Bố cục của Luận văn  Bố cục của  luận văn được chia làm 3 chương chính theo trình tự nghiên  cứu  từ  CSDL  quan  hệ  truyền  thống  đến  việc  mở  rộng  các  khái  niệm  trong  CSDL này. Cụ thể luận văn bao gồm các vấn đề được trình bày theo thứ tự như  sau:  Chương 1: Tổng quan  Chương 1 trình bày lại những khái niệm cơ bản như là: dữ liệu, thông tin,  cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, khái niệm về Phụ thuộc hàm, Bao đóng  tập  thuộc  tính và Khóa. Bên cạnh đó trong chương này cũng  trình bày về một  trong những định lý quan trọng nhất của Cơ sở dữ liệu quan hệ ­ định lý tương  đương.  Chương 2: Lớp phụ thuộc hàm mờ trong Cơ sở dữ liệu quan hệ  Chương 2 trình bày các khái niệm cơ bản về tập mờ, các phép toán trên  tập mờ, phụ thuộc hàm mờ trong cơ sở dữ liệu quan hệ và một số mở rộng của  hệ tiên đề Amstrong trong ngữ cảnh mờ.  Chương 3: Khoá mờ trong Cơ sở dữ liệu quan hệ  Chương 3 trình bày các khái niệm cơ bản về khoá, khóa mờ, định nghĩa  về khoá mờ (fuzzy key), thuật toán tìm khóa mờ trong CSDL quan hệ; trình bày  khái niệm về bao đóng của tập thuộc tính đối với lớp phụ thuộc hàm mờ, thuật  toán tìm bao đóng; nêu và chứng minh định lý tương đương đối với hai kiểu suy  dẫn trong lớp phụ thuộc hàm mờ . Bên cạnh đó chương này cũng trình bày một  cách cơ bản về các dạng chuẩn mờ F1NF, F2NF, F3NF và FBCNF.  Trong quá trình thực hiện luận văn, mặc dù đã có nhiều cố gắng nhưng do  thời gian và kinh nghiệm nghiên cứu còn hạn chế nên những vấn đề  trình bày  trong luận văn, những kết quả đạt được vẫn còn những điều cần phải khắc phục  và bổ sung thêm. Tác giả rất mong nhận được những lời góp ý của các thầy cũng  như các anh, các chị quan tâm đến chủ đề này. 12  CHƯƠNG 1. TỔNG QUAN  1.1 Cơ sở dữ liệu  1.1.1 Các khái niệm chung  Dữ liệu:Dữ liệu là các sự kiện, văn bản, đồ họa, hình ảnh và đoạn phim video có  ý nghĩa trong môi trường người dùng.  Thông tin:Thông tin  (information)  là dữ  liệu được xử  lý để  tăng hiểu biết của  người dùng về dữ liệu này  Hệ thống thông tin: Hệ thống thông tin bao gồm bộ phận xử lý thông tin, các  thông tin vào ra (I/O information);  bộ phận xử lý thông tin được đặt trong môi  trường của hệ thống [2].  Hình 1: Hệ thống thông tin  1.1.2 Định nghĩa  Cơ sở dữ liệu (CSDL) là một hệ thống thông tin có cấu trúc được lưu trữ  trên các thiết bị lưu trữ thông tin thư cấp (như băng từ, đĩa từ…) để có thể thoả  mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều  chương trình ứng dụng với nhiều mục đích khác nhau. 13  Hình 2: Hệ thống Cơ sở dữ liệu  Việc tổ chức dữ liệu tốt sẽ cho ta một hệ thống CSDL tốt, giúp cho người  quản trị hệ thống dễ dàng trong việc  làm chủ hệ thống này. Một số hệ quản trị  CSDL phổ biến hiện nay như là: Oracle, SQL Server, DB2, My SQL, …  1.2 Phụ thuộc hàm  Khi xét đến mối quan hệ giữa dữ liệu trong CSDL quan hệ [2] một trong  những yếu tố quan trọng nhất được xét đến là sự phụ thuộc giữa các thuộc tính  này với thuộc tính khác. Từ  đó có thể xây dựng những ràng buộc cũng như loại  bỏ đi những dư thừa dữ liệu trong một CSDL.  Phụ thuộc hàm [3] là những mối quan hệ giữa các thuộc tính trong CSDL  quan hệ. Khái niệm về phụ thuộc hàm có một vai trò rất quan trọng trong việc  thiết kế mô hình dữ liệu. Một trạng thái phụ thuộc hàm chỉ ra  rằng  giá trị của  một  thuộc  tính  được  quyết  định một  cách  duy  nhất  bởi  giá  trị  của  thuộc  tính  khác. Ở đây sẽ trình bày khái niệm một cách hình thức.  1.2.1 Định nghĩa  Định nghĩa  : Cho tập  thuộc tính U = {A  n A ... 1  }, R  là một quan hệ trên U. Gọi  X,Y là hai tập con của U. Khi đó: X→Y (đọc là X xác định hàm Y hay Y phụ  thuộc hàm vào X  ) sao cho với hai bộ bất kỳ  t1,t2  R Π mà    t1[X] =  t2[X]    thì  t1[Y] = t2[Y] 14  Phụ thuộc hàm ký hiệu là FD.  Ví dụ: Cho  quan hệ R = HS :  HS  STT  Ten  Namsinh  Diachi  DT  Email  1  Trung  1983  Việt Trì  0989313797  Trungtt  2  Kiên  1987  Phú Thọ  045596045  kientt  3  Nam  1984  Hà Nội  045769823  namlt  Bảng 1: Bảng quan hệ Học sinh  Theo bảng trên ta thấy mỗi một trong số các thuộc tính  Namsinh, Diachi,  DT, Email đều phụ thuộc hàm (PTH) vào  thuộc tính Ten. Mỗi giá  trị của Ten  đều tồn tại đúng một giá trị tương ứng đối với từng thuộc tính còn lại. Khi đó có  thể viết: Ten → Nam sinh, Ten → Diachi, …  1.2.2 Tính chất của Phụ thuộc hàm (Hệ tiên đề Amstrong)  Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế  cơ sở dữ liệu thì 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.  Khi  nghiên  cứu  về  lớp  phụ  thuộc  hàm  trong  CSDL  quan  hệ  Amstrong đã đưa ra một số tính chất như sau:  1.2.2.1 Hệ tiên đề  Gọi  R  là  quan  hệ  trên    tập  thuộc  tính  U.  Khi  đó  với  các  thuộc  tính  , , ,W X Y Z U Í  ta có hệ tiên đề Amstrong [3] như sau :  A1) Phản xạ : Nếu Y X Í  thì  X Y ®  A2) Tăng trưởng: Nếu W  U Í  và  X Y ®  thì  W YW X ®  A3) Bắc cầu : Nếu  , X Y Y Z ® ®  thì  X Z ®  Chứng minh:  A1) Giả sử  1 2 , t t R Π và  1 2 [X]=t [X] t  cần chứng minh  1 2 [Y]=t [Y] t  Thật vậy do Y X Í  suy ra  1 2 [Y]=t [Y] t  (đúng )  □  A2) Giả sử  1 2 , t t R Π và  1 2 [XW]=t [XW] t  cần chứng minh  1 2 [YW]=t [YW] t  .  Phản  chứng:  Giả  sử  1 2 [YW] t [YW] t ¹  .  Do  1 2 [W]=t [W] t  nên  để  có  1 2 [YW] t [YW] t ¹  thì  1 2 [Y] t [Y] t ¹  . Nhưng  theo  giả  thiết  ta  có X→Y  nghĩa  là  1 2 [X]=t [X] t  thì  1 2 [Y]=t [Y] t Þmâu thuẫn.Vậy  1 2 [YW]=t [YW] t  □ 15  A3) Theo giả thiết ta có  , X Y Y Z ® ®  là hai PTH trên quan hệ R  Giả sử  1 2 , t t R Π và  1 2 [X]=t [X] t  cần chứng minh  1 2 [Z]=t [Z] t  Phản  chứng  :  Giả  sử  1 2 [Z]   t [Z] t ¹  .  Từ  X Y ®  suy  ra  1 2 [X]=t [X] t  thì  1 2 [Y]=t [Y] t  . Mặt khác ta lại có PTH Y Z ®  nghĩa là  1 2 [Y]=t [Y] t  thì  1 2 [Z]=t [Z] t  nhưng  theo  giả  thiết  phản  chứng  ta  có  1 2 [Z]   t [Z] t ¹  (mâu  thuẫn).  Vậy  1 2 [Z]=t [Z] t  □  Ví dụ :  , BC A A C ® ®  Cần chứng minh  AB ABC ®  Thật vậy từ:  1.  A C ®  (g/t)  2.  AB BC ®  (luật tăng trưởng của (1) thêm thuộc tính C )  3.  BC A ®  (g/t)  4.  BC ABC ®  (luật tăng trưởng của (3) thêm BC )  5.  AB ABC ®  (bắc cầu từ (2) và (4))  □  1.2.2.2 Hệ quả  Từ các tính chất trên chúng ta có các hệ quả sau đây:  1) Luật hợp :  Nếu  X Y ®  và  X Z ®  thì  X YZ ®  2) Luật tựa bắc cầu : Nếu  X Y ®  và WY Z ®  thì  W Z X ®  3) Luật tách :  Nếu  X Y ®  và  Z Y Í  thì  X Z ®  Chứng minh:  1) Từ  X Y ®  dùng  luật  tăng  trưởng  thêm X  có  X XY ®  (1). Từ  X Z ®  dùng luật tăng trưởng thêm Y có  XY YZ ®  (2)  Vậy từ (1) và (2) áp dụng luật bắc cầu suy ra  X YZ ®  □  2) Từ  X Y ®  dùng luật tăng trưởng, thêm W có  W WY X ®  (3). Mặt khác  theo giả thiết ta có WY Z ®  (4)  Vậy từ (3) và (4) áp dụng luật bắc cầu ta có  W Z X ®  □  3) Do  Z Y Í  suy ra  Y Z ®  (theo  luật phản xạ). Áp dụng  luật bắc cầu cho  X Y ®  và Y Z ®  suy ra  X Z ®  □  1.2.3 Bao đóng tập thuộc tính  Trong một quan hệ R có  thể tồn tại nhiều các phụ thuộc hàm khác nhau  giữa các thuộc tính (có thể nhiều thuộc tính phụ thuộc vào một thuộc tính hoặc  cũng có thể một thuộc tính phụ thuộc và nhiều thuộc  tính khác nhau). Để tổng 16  quát hoá các phụ thuộc hàm này người ta đưa ra khái niệm Bao đóng tập thuộc  tính [3].  Gọi F  là  tập  tất  cả các phụ thuộc hàm đối với quan hệ R  trên  tập  thuộc  tính U và X®Y là một phụ thuộc hàm ( X, YÍU). Ta nói rằng X®Y được suy  diễn ra  từ F  nếu quan hệ  r  trên R(U) đều  thoả mãn phụ thuộc  hàm F  thì cũng  thoả mãn X®Y. Chẳng hạn như F = { A®C, C®D} thì A®D  được suy ra từ  F. Gọi F +  là bao đóng (transitive closure) của F tức  là  tập tất cả các phụ thuộc  hàm được suy diễn logic từ F. Nếu F=F +  thì F là họ đầy đủ của các phụ thuộc  hàm.  1.2.3.1 Định nghĩa  Cho tập thuộc tính U, XÌU và F là tập các phụ thuộc hàm nào đó trên U.  Khi đó ta định nghĩa Bao đóng của tập thuộc tính X theo phụ thuộc hàm F được  ký hiệu là X F +  được xác định như sau:  X F +  = { A| AÌU , X®A ÎF + }  Ta viết gắn gọn X F +  là X + .  Nhận xét:  Khái niệm Bao đóng  tập  thuộc  tính có  ý nghĩa hết  sức quan  trọng  trong  việc  nghiên  cứu về  lớp  phụ  thuộc  dữ  liệu. Có  thể  nói  đây  là  một  trong  những khái niệm quan trọng nhất vì tất cả các kết quả quan trọng nhất trong lớp  phụ thuộc hàm đều liên quan đến khái niệm này.  1.2.3.2 Tính chất của Bao đóng  Dựa vào các tính chất của phụ thuộc hàm ta có các tính chất của Bao đóng  tập thuộc tính như sau:  1)  Tính phản xạ: XÍX +  2)  Tính đơn điệu: Nếu XÍY thì X + ÍY + .  3)  X  X + ®  4)  Tính luỹ đẳng: X ++ = X + .  5)  X + Y + Í (XY) + .  6)  (X + Y) + = (XY + ) = (XY) + .  7)  X®YÛYÍX + .  8)  X®Y và Y®X ÛX + =Y + .  Chứng minh:  1)  Lấy bất kỳ AÎX, ta cần chứng minh AÎX + .  Ta có AÎX Û {A}ÍX. Vậy theo Luật phản xạ suy ra X®A ÞAÎX + .  □  2)  Lấy AÎX + , ta cần chứng minh AÎY + .  Ta có AÎX + ÞX®A (1)  Mà XÍY ÞY®X     (2)   ( theo Luật phản xạ )  Vậy từ (1) và (2) và Luật bắc cầu ta có Y ®A ÞAÎY +  □  3)  Giả sử X + = A 1 A 2 …A k  Do A 1 ÎX  +  ta có  X®A 1 17  Tương tự:  X®A 2  ………  X®A k  Theo Luật hợp ta có X®A 1 A 2 …A k ÞX  X + ®  4)  Ta có X + ÍX ++  ( tính chất 1). Ta cần chứng minh  X ++ ÍX +  Lấy A ÎX ++ , ta cần chứng minh AÎX + .  Do A ÎX ++ ÞX + ®A (1)  Mặt khác theo tính chất 3 ta có : X  X + ®  (2)  Từ (1) và (2) ta có X®A ( tính chất bắc cầu) ÞAÎX +  □  5)  Ta có X ÍXY  Theo tính chất 2 ( tính đơn điệu ) ta có : X + Í (XY) + (1)  Tương tự ta cũng có: Y + Í (XY) + (2)  Từ (1) và (2) suy ra X + Y + Í (XY) + .  □  6)  Theo những phần trên ta có:  XÍX + Y (1)  X + Í (XY) +  (2)  YÍ (XY) +  (3)  Từ (1), (2) và (3) ta có X + YÍ (XY) + Þ (X + Y) + Í (XY) ++ = (XY) + ( theo tính luỹ  đẳng )  Vậy ta có Þ (X + Y) + Í  (XY) +  (4)  Mặt khác ta cũng có :  XÍX +  ( tính chất 1) ÞXYÍ X + Y Þ (XY) + Í  (X + Y) +  (5)       ( tính đơn điệu)  Từ (4) và (5) suy ra (X + Y) + = (XY) +  □  7)  Để chứng minh X®YÛYÍX +  ta có:  a)  Giả sử có X®Y ta cần chứng minh YÍX +  Lấy bất kỳ AÎY, ta cần chứng minh AÎX +  Ta có: AÎY Þ Y®A (1)  Theo giả thiết ta lại có: X®Y  (2)  Từ (1) và (2)  và luật bắc cầu ta có X®A ÞAÎX +  b)  Giả sử có YÍX +  ta cần chứng minh X®Y  Do YÍX + ÞX + ®Y ( luật phản xạ )  Mặt khác: X  X + ®  ( theo tính chất 3)  Suy ra: X®Y  ( luật bắc cầu)  8)  Để chứng minh X®Y và Y®X ÛX + =Y + ta có:  a)  Giả sử có X®Y và Y®X  ta cần chứng minh X + =Y +  Do X®Y Þ YÎX + Þ Y + ÎX ++ Þ Y + ÎX +  (theo tính chất luỹ đẳng) (1)  Do Y®X Þ XÎY + Þ X + ÎY ++ 18 Þ X + ÎY +  (theo tính chất luỹ đẳng) (2)  Từ (1) và (2) ta có X + =Y +  □  b)  Giả sử có X + =Y +  ta cần chứng minh X®Y và Y®X  Do X + =Y +  nên ta có  Y + ÍX +  (1’)  X + ÍY +  (2’)  Theo tính chất 1 ta có YÍY +  mà Y + ÍX + ÞYÍX + ÞX®Y ( theo tính chất 7)  Nhận xét:  Trong các tính chất trên thì tính chất 7 là quan trọng nhất. Thực tế ta  cần biết với một phụ thuộc hàm X®Y thì hỏi rằng phụ thuộc hàm đó có được  suy dẫn logic từ tập phụ thuộc hàm F hay không?  Khi đó đặt ra 2 vấn đề:  ­  Nếu biết YÍX +  thì X®Y ÎF +  ­  Nếu YËX +  thì X®Y ÏF +  Khi đó nếu ta xây dựng được một thuật toán tìm X + một cách dễ dàng như vậy  thì ta cũng có thể trả lời câu hỏi X®Y một cách dễ dàng.  1.2.4 Định lý tương đương  Định  nghĩa: Cho  tập  phụ  thuộc  hàm F  trên  tập  thuộc  tính U  và  f  là một  phụ  thuộc  hàm  trên U. Ta  nói PTH  f được  suy dẫn  theo quan hệ  từ  tập phụ  thuộc  hàm F và viết F = f nếu mọi quan hệ R(U) thoả F thì R cũng thoả f.  Định  nghĩa: Cho  tập  phụ  thuộc  hàm F  trên  tập  thuộc  tính U  và  f  là một  phụ  thuộc hàm trên U. Ta nói phụ thuộc hàm f được suy dẫn theo tiên đề ( hoặc suy  dẫn  logic)  từ  tập PTH F và viết F├  f nếu fÎF + . Nói cách khác  f được suy dẫn  theo các tiên đề từ tập PTH F nếu như áp dụng các luật A1, A2, A3 đối các PTH  trong F thì sau hữu hạn lần ta sẽ thu được f.  Định lý: Với mọi tập FPT F và PTH f trên tập thuộc tính U ta có F├ f  khi và  chỉ khi F = f . Hay, suy dẫn theo tiên đề và suy dần theo quan hệ là một.  Ký hiệu: F├ f Û F = f .  Chứng minh:  a)  Giả sử ta có F├ f  ta cần chứng F = f.  Giả sử sau k bước ứng dụng các luật của hệ tiên đề ta nhận được các phụ thuộc  hàm:  f 1 , F 1  = FÈ {f 1 }  f 2 , F 2  = F 1 È {f 2 }  ………………..  f k  , F k  = F  1 k- È {f k }  Vậy ta có R(F) Þ R(F 1 ) Þ R(F 2 )Þ …ÞR(F k  ) Þ R(f) hay F = f  □ 19  b)  Giả sử ta có F = f ta cần chứng minh F├ f .  Để chứng minh F = f ÞF├ f  ta sẽ chứng minh F├ f  thì F = f  Thật vậy, đặt f = X®Y. Khi đó có F, X ta sẽ tính được X +  Xây dựng quan hệ R như sau:  R  A 1  A 2  …  A k  A  1 k+  …  A n  u  a 1  a 2  …  a k  a  1 k+  …  a n  v  a 1  a 2  …  a k  b  1 k+  …  b n  Giả sử X + = A 1 A 2 …A k  Như vậy quan hệ R chỉ gồm 2 bộ u và v. Hai bộ này giống nhau trên tập X + và  với mọi thuộc tính B ¹X +  thì u.B ¹ v.B tức là a j ¹ b j  ( j = k+1,..n).  Ta sẽ chứng minh f vừa dẫn xuất được theo quan hệ R và f vừa không dẫn xuất  được theo quan hệ R.  Hay là ta chứng minh R(f) và ┐R(f)  1)  Ta chứng minh R thoả mãn mọi phụ thuộc hàm trong F + hay R(f).  Giả sử có PTH Z®W ÎF + và u.Z = v.Z. Ta cần chứng minh u.W = v.W.  Ta có: u.Z = v.Z Þ ZÍX + ÞX + ®Z ( theo tính phản xạ )  Mà ta lại có X®X +  (theo tính chất 3)  Áp dụng tính chất bắc cầu cho các phụ thuộc hàm X®X + , X + ®Z và Z®W ta  có X®W  Suy ra WÍX +  ( theo tính chất 7)  Vậy u.W = v.W  □  2)  Ta chứng minh R không thoả mãn PTH X®Y hay ta cần chứng minh có  u.X = v.X  nhưng u.Y ¹ v.Y .  Từ là X®Y ÏF Û  Y ËX +  (theo tính chất 7)  Suy ra: u.Y ¹ v.Y (1)  Mặt khác theo tính chất 1 ta có XÍX + Þu.X = v.X (2)  Từ (1) và (2) suy ra R không thoả mãn PTH X®Y hay ┐R(f)  □  1.3 Khoá  Trong một quan hệ có những thuộc tính đóng vai trò “chủ chốt”  và từ các  thuộc tính này có thể suy ra được các thuộc tính khác thông qua các phụ thuộc  dữ liệu. Khái niệm về khoá cũng là một trong những khái niệm quan trọng nhất  trong việc nghiên cứu và xây dựng CSDL. 20  Nói đến khoá (key) [3]  trong quan hệ R là nói đến một tập nhỏ nhất các  thuộc  tính  nhằm  phân  biệt  các  đối  tượng.  Việc  xác  định  khoá  cũng  xác  định  được  tính toàn vẹn dữ  liệu  trong CSDL quan hệ. Do đó việc  tìm khoá  trong 1  lược đồ mang ý nghĩa hết sức quan trọng.  Định nghĩa:  Cho lược đồ quan hệ a  = (U,F), trong đó F là tập các phụ thuộc  hàm trên quan hệ R  Tập KÍU. Khi đó K được gọi là một siêu khoá nếu K + =U  R được gọi là quan hệ của a  nếu như ta có R(F).  Nhận xét:  ­  Nếu K là siệu khoá của lược đồ a  thì hai bộ t1, t2 bất kỳ không thể giống  nhau trên K.  ­  Trong lược đồ quan hệ a có thể có một hoặc nhiều siêu khoá  ­  Hợp của một siêu khoá là một siêu khoá  ­  Giao của các hoá nói chung không là một siêu khoá.  Định nghĩa:  Cho lược đồ quan hệ a  = (U,F), trong đó F là tập các phụ thuộc  hàm trên quan hệ R  Tập KÍU  Khi đó K được gọi là khoá của lược đồ nếu K thoả mãn hai điều kiện sau:  1.  K là 1 siêu khoá  2. "K 1 ÍK thì K 1  không là siêu khoá.  Tức là: {  1 1 :  K U  K K K U + + = " Í ¹  Nhận xét:  ­  Trong lược đồ quan hệ a  có thể có một hoặc nhiều khoá  ­  Hợp của các khoá khác nhau không phải là một khoá. 21  CHƯƠNG 2. LỚP PHỤ THUỘC HÀM MỜ TRONG  CƠ SỞ DỮ LIỆU QUAN HỆ  2.1 Dữ liệu mờ  Cơ sở dữ liệu [2] là biểu hiện của thế giới thực, hầu hết các giá trị của nó  là rõ ràng nhưng đôi khi cũng không xác định, không rõ ràng hay còn gọi là mờ  (fuzzy). Việc thiết kế Cơ sở dữ liệu với các giá trị ra sao là do nhà thiết kế lựa  chọn và tuỳ vào mục đích sử dụng nhưng hầu hết các Cơ sở dữ liệu hiện nay đều  rõ. Tuy nhiên để nắm bắt những giá trị chưa rõ ràng của thế giới thực đặc biệt là  với những ứng dụng trong các ngành sinh học và gen, hệ thống thông tin địa lý,  hệ thống dự báo kinh tế và thời tiết,… người ta nghĩ đến việc mờ hoá dữ liệu và  xây dựng mô hình Cơ sở dữ liệu mờ.Việc xây dựng cũng như phát triển các mô  hình cơ sở dữ liệu mờ cũng như lớp phụ thuộc hàm mờ (FFDs) có thể theo nhiều  hướng khác nhau nhưng đều dựa trên các khái niệm cơ bản sau:  2.1.1 Tập rõ  Khái niệm tập  rõ  là khái  niệm được  sử dụng  trong CSDL  truyền thống.  Khi đó các thuộc tính được xét đến coi như thoả mãn các yêu cầu một cách tuyệt  đối. Ta có thể định nghĩa về tập rõ như sau:  Cho U là tập các đối tượng, A là tập con của U. A được gọi là tập rõ (crisp  set) [4] nếu A được định  nghĩa bởi hàm đặc trưng của nó sao cho:  1  nếu x thuộc A l (x) =  0         nếu x không thuộc A  2.1.2 Tập mờ  Cho U là tập các đối tượng xΠU. A là tập con của  U, A được gọi là tập  mờ (fuzzy set ) [4] nếu  các phần tử  x chỉ thuộc A với ngưỡng nào đó được xác  định bởi ánh xạ m  A : U → [ 0,1]  ( 0 1 A m £ £  ), m  A (x) là mức thoả của phần tử x  thuộc A, nếu m  A (x) = 0 thì  x  A Ï  còn nếu m  A (x) = 1 thì x hoàn toàn thuộc vào  A. Tập rõ là một trường hợp đặc biệt của tập mờ khi m  A (x) = 1.  Ký hiệu:  A = { , (x) x U} A x m Π với xΠU và m  A (x) là mức thỏa của x trong  tập mờ A. 22  Hình 3: Tập mờ và tập rõ  Như vậy ta có:  ( ) 0 x x U m ³ " Π x u  sup[ (x)]=1 A m Π Ví dụ : Cho các phần tử A,B,C thuộc vào tập X với các mức 0.4, 0.7, 0.8.  Khi đó tập mờ X sẽ được biểu diễn như sau:  X = {(A,0.4) , (B, 0.7), (C, 0.8)}  2.1.3 Các phép toán cơ bản trên tập mờ  Trong tập mờ có một số phép toán cơ bản sau:  §  Phép lấy phần bù  C =  ~ A(u) = 1 – A(u)  §  Phép hợp  C = ( A È  B )(u) = max [A (u), B(u)]  §  Phép giao  C =  (AÇ  B)(u)   = min [ A(u), B(u) ]  Ví dụ: Cho 2 tập mờ :  X = { (A,0.9), (B,0.8), (D,0.6)}  Y = { (A,0.7), (B,0.65), (G,0.6)}  Khi đó ta có:  Phép lấy phần bù: Z= ~ X(u) = 1–X(u) = {(A,0.1),(B,0.2),(D,0.4)}. 23  Phép  giao:  Z  =  (XÇY)(u)  =  min  [  A(u),  B(u)  ]  =  {(A,0.7),  (B,0.65), (D,0.6),(G,0.6)}.  Phép  hợp: Z=(XÈY)(u) = max  [ A(u), B(u)  ] = {(A,0.9),  (B,0.8),  (D,0.6),(G,0.6)}.  2.2 Phụ thuộc hàm mờ  Trong quá  trình xác định những  ràng buộc dữ  liệu, đặc biệt  là việc xác  định  lớp  các  thụ  thuộc  hàm đã  cho  thấy  vẫn  còn  những  vấn  đề  cần  được  giải  quyết. như là  trong cơ sở dữ liệu  lớn, các dữ liệu nhiễu thì những xung đột dữ  liệu và lỗi đều có thể xảy ra, cụ thể như sự thiếu chính xác trong việc nhập, thay  đổi cũng như cập nhật dữ liệu. Nói chung khó có thể tìm được phụ thuộc hàm  nếu ràng buộc giữa các thuộc tính chưa rõ ràng, chưa xác định hoặc mờ. Vì vậy  việc mở rộng phụ thuộc hàm mờ (fuzzy functional dependency) [12] sẽ giúp cho  việc thiết kế mô hình dữ liệu để xử lý được những vấn đề về phụ thuộc dữ liệu  với độ tin cậy a  (0<a <1) . Chúng ta sẽ xét đến phụ thuộc hàm (X → Y) a  nghĩa  là Y phụ thuộc hàm vào X  với mức a  nào đó.  2.2.1 Định nghĩa  Định nghĩa: Cho một tập U ={ A 1 , A 2 , …, A n } với mỗi phần tử A Πi  U là một  thuộc tính, ứng với mỗi thuộc tính A i ;  i =1,2,…,n sẽ có miền giá trị  là D i .Ký  hiệu Dom(A i ) = D i . Ta chỉ xét  i D ³  2. Khi đó:  Với R là một quan hệ trên U; X→Y là phụ thuộc hàm trên quan hệ R  Cặp bộ bất kỳ  t i , t j ΠR được gọi là thoả mãn phụ thuộc hàm X→Y nếu  t i (X) = t j (X) thì  t i (Y) =  t j (Y).  Đặt :  0   nếu  t i (X) = t j (X)  nhưng  t i (Y) ¹  t j (Y)  1   nếu ngược lại  Nếu  T (  ) ,  j i  t t  (X→ Y) = 1 ta nói rằng 2 cặp bộ t i , t j  thỏa mãn phụ thuộc  hàm X®Y.  Quan hệ R được gọi là thoả mãn phụ thuộc hàm X®Y với hai bộ bất kỳ  t i , t j ΠR nếu T (  ) ,  j i  t t  (X→ Y) = 1.  Nhận xét:  Nếu quan hệ R được gọi là thoả mãn phụ thuộc hàm X®Y thì  T R  (X→ Y) = 1  T (  ) ,  j i  t t  (X→Y)       = 24  Định nghĩa: Cho tập thuộc tính U ={ A 1 , A 2 , …, A n } và R là một quan hệ trên  U; X , YÍ U . Đặt  T R  (X→Y) =  N  Y X T  j i  j i  j i  t t  R t t  t t å ¹ Î " ®  ,  ) , (  ) (  trong đó: n là số bộ trong R:  N = C 2 n  = n(n–1)/2.  Nhận xét:  Ta thấy 0<T R  (X→Y)  1 £  .  ­  Nếu T R  (X→ Y) = 1 thì chính là định nghĩa phụ thuộc hàm trong CSDL  truyền thống.  ­  Nếu 0<T R  (X→Y)  1 £  . Xét hệ số a  nào đó (0<a £1). Khi đó quan hệ R  có  T R  (X→Y) ³ a  thì ta nói quan hệ R thoả mãn phụ thuộc hàm X→Y  với mức thoả a (0<a £1).  ­  Khi  giá  trị T R  (X→Y)  càng  gần  giá  trị 1  thì  quan  hệ R  thoả mãn phụ  thuộc hàm  X→Y càng có ý nghĩa và chặt chẽ. Nếu T R  (X→Y) càng gần  giá trị 0 thì quan hệ R thoả mãn mãn phụ thuộc hàm  X→Y  lỏng lẻo và  gần như không có ý nghĩa khi ta xét đến các ràng buộc dữ liệu trong quan  hệ R.  Ví dụ: Cho quan hệ R  :  Khi đó theo định nghĩa trên ta có  T R  (X→Y) =  85,7 % . Vậy R thỏa mãn  phụ thuộc hàm X→Y với mức thoả a ³0.875.  Định nghĩa: Cho tập thuộc tính U ={ A 1 , A 2 , …, A n } và R là một quan hệ trên  U; X, Y là  hai tập con của U.  R  STT  X  Y  1  2  3  4  5  6  7  A  A  A  B  B  C  C  E  E  G  H  K  D  D 25  Khi đó với giá trị a  (0<a £1) cho trước nếu T R  (X→Y) ³ a  thì X → Y  được gọi là phụ thuộc hàm trong R với mức thoả a  hay nói cách khác là R thỏa  mãn phụ thuộc hàm X → Y với mức thoả a .  Một số mở rộng định nghĩa Phụ thuộc hàm:  Theo  định  nghĩa  trên mới  xét  đến  phụ  thuộc  hàm mờ  với mức  thoả a  (0<a £1) còn dữ liệu là rõ (các thuộc tính X, Y). Do đó đôi khi trong một CSDL  có thể gây ra “lãng phí” dữ liệu. Chẳng hạn như xét một quan hệ HS sau đây:  Theo định nghĩa thì 2 bộ t 1 , t 2 ΠR được gọi là phụ thuộc hàm X→Y nếu  t 1 (X) =  t 2 (X)  thì    t 1 (Y) =    t 2 (Y). Trong  trường hợp “xấp xỉ”  nhau  thì  cũng coi  như khác biệt và không có sự phụ thuộc hàm gì ở đây. Chính điều này gây  ra  “lãng phí” dữ liệu và không thấy được sự phụ thuộc dữ liệu gì ở đây.  Theo một cách khác nếu xét ở chừng mực nào đó ta có thể đánh giá 2 bộ  vẫn phụ thuộc hàm vào nhau, chẳng hạn như ví dụ trên HS 1 có điểm các môn  gần như “tương đương” với HS 2. Theo định nghĩa trên thì sẽ không tồn tại  phụ  thuộc hàm giữa 2 bộ này. Tuy nhiên nếu đặt ra “tỷ lệ” khác biệt l nào đó thì ta  có thể coi 2 bộ này “giống nhau” và sẽ có phụ thuộc hàm:  {Toán, Lý, Hoá }®Trung bình  Chẳng hạn ta xét “tỷ lệ” khác biệt giữa 2 bộ 1 và 2 ở các thuộc tính lần lượt như  sau:  + Thuộc tính Toán: ta có  1 l = 0.96  + Thuộc tính Lý: ta có  2 l  = 0.97  + Thuộc tính Văn: ta có  3 l = 0.96  + Thuộc tính Trung bình: ta có  4 l  = 0.99  Ta có  thể coi “tỷ  lệ” khác biệt   giữa giữa hai bộ  thuộc  tính mức độ phụ  thuộc dữ liệu giữa hai bộ thuộc tính này.  Lấy min{  i l } với I = 1,4, ta có min{  i l } = min {0.96, 0.97, 0.96, 0.99} =  0.96  Ta có thể nói : ({Toán, Lý, Hoá }®Trung bình ) 0.96  HS  STT  Toán  Lý  Văn  Trung bình  1  2  8  8.3  6,8  7  9  8.7  7.93  8.0 26  Như vậy xét theo một khía cạnh nào đó ta có thể mở rộng thêm định nghĩa  về Phụ thuộc hàm mờ như sau:  Định nghĩa 1: Cho tập  thuộc  tính U ={ (A 1 ,  1 l ),  (A 2 ,  2 l  ),…, (A n ,  n l  )} và R  là  một quan hệ trên U; X, Y là  hai tập con của U.  Đặt l  = min{  i l } với  1, i n =  và (0<l £1)  Khi đó với nói rằng   2 bộ  t 1 ,  t 2  là  thoả mãn PTH X → Y mức l  nếu  t 1 (X) l =  t 2 (X) thì  t 1 (Y) l =  t 2 (Y) .  Định nghĩa 2: Cho tập  thuộc  tính U ={ (A 1 ,  1 l ),  (A 2 ,  2 l  ),…, (A n ,  n l  )} và R  là  một quan hệ trên U; X, Y là  hai tập con của U.  Đặt l  = min{  i l } với  1, i n =  và (0<l £1)  Khi đó R được  gọi  là  thoả mãn PTH X → Y với mức  thoả l  nếu T R  (X→Y) ³ l .  Nhận xét:  ­ Từ việc nghiên cứu về lớp phụ thuộc hàm trong CSDL quan hệ truyền thống ta  thấy rằng việc mở rộng các khái niệm (mờ hoá) sẽ càng ngày càng giúp cho việc  xây dựng các hệ thống dữ liệu sát với thực tế hơn. Đặc biệt việc mở rộng này có  ý nghĩa vô cùng quan trọng trong các hệ thống dự báo như là hệ thống về dự báo  thời tiết, dự báo tăng trưởng kinh tế,….  ­ Dưới đây là một số hướng mở rộng về phụ thuộc hàm trong CSDL quan hệ.  Dữ liệu  Độ bằng  Độ phụ thuộc  Kết quả  R  R  R  Quan  niệm  truyền  thống  R  R  (X → Y) a  Mở rộng 1  R  M  (X → Y) a  Mở rộng 2  M  M  (X → Y) a  Mở rộng 3  Ghi chú:  R: Rõ; M: Mờ  Bảng 2: Bảng các mở rộng của Phụ thuộc hàm  ­ Các định nghĩa mở rộng về phụ thuộc hàm mờ chỉ coi như là một mở rộng khi  xét đến các phụ thuộc dữ và đánh giá độ tin cậy của dữ liệu chứ không nên sử  dụng trong việc tìm Khoá của lược đồ quan hệ. 27  2.2.2 Tính chất  Cũng tương tự như trong khái niệm phụ thuộc hàm truyền thống, đối với  lớp phụ thuộc hàm mờ cũng có một số tính chất [12] như sau:  Tính chất 1( Tính phản xạ ): Cho R là một quan hệ trên tập thuộc tính U,  X và  Y  là các tập con của U. Khi đó nếu YÍ X thì  T R  (X →Y) = 1.  Chứng minh:  Vì YÍ X nên  với mỗi cặp (t i  , t j ) thuộc R ta có:  §  Nếu  t i (X) =  t j (X)  thì    t j (Y) =  t j (Y),  theo  định  nghĩa 1  ta  có  T  ) , (  j i  t t  (X→Y) = 1  (1)  §  Nếu t i (X) ¹  t j (X) thì trong cả hai trường hợp t j (Y) = t j (Y) hoặc t j (Y) ¹ t j (Y) ta đều có  T  ) , (  j i  t t  (X→Y) = 1  (2)  Vậy từ (1) và (2) ta có T R  (X →Y) = 1     □  Tính chất 2  (Tính  tăng  trưởng): Cho R  là một quan hệ  trên  tập  thuộc  tính U.  Với  X, Y và Z  là các tập con của U. Khi đó:  Nếu  T R (X →Y) ³ a  thì  T R (XZ →YZ) ³ a  ( 0£ £ a  1) [12]  Chứng minh:  Với 3  tập thuộc tính X, Y, Z ta có thể liệt kê tất cả các khả năng kết hợp  giữa các tập thuộc  thuộc tính. Do đó ta có bảng sau:  Bảng 3: Bảng các khả năng kết hợp giữa các tập thuộc tính  Trong đó :  1  biểu diễn t i (X) = t j (X)  0  biểu diễn t i (X) ¹  t j (X)  t i (X) = t j (X)  t i (Y) = t j (Y)  t i (Z)= t j (Z)  T  ) , (  j i  t t  (X→Y)  T  ) , (  j i  t t  (XZ→YZ)  0  0  0  0  1  1  1  1  0  0  1  1  0  0  1  1  0  1  0  1  0  1  0  1  1  1  1  1  0  0  1  1  1  1  1  1  1  0  1  1 28  Vậy  theo  bảng  trên  ta  thấy  với  mỗi  cặp  bộ  (t i ,t j )  thì  T  ) , (  j i  t t  (XZ→YZ)³T  ) , (  j i  t t  (X→Y).  Theo  giả  thiết    T R (X  →Y) ³ a  ta  có:    T R (XZ  →YZ)  = å ® YZ))/N (XZ (T  ) t , (t  j i ³ å ® Y))/N (X (T  ) t , (t  j i  = T R (X →Y).  Vậy T R (XZ →YZ) ³ a  □  Tính chất 3  (Tính   tựa bắc cầu): Cho R là một quan hệ trên tập thuộc tính U.  Với  X, Y và Z  là các tập con của U. Khi đó:  Nếu    T R (X →Y)  =a  ,    T R (Y →Z)  = b  thì    T R (X →Z)  = g  với g  =  min( b a ,  ).  Chứng minh:  Ta  có bảng sau:  Bảng 4: Bảng các khả năng kết hợp giữa các tập thuộc tính  Trong đó :  1  biểu diễn t i (X) = t j (X)  0  biểu diễn t i (X) ¹  t j (X)  Coi n là số bộ của quan hệ R . N = C 2 n  = n(n­1)/2.  Dựa vào bảng ta thấy T  ) , (  j i  t t  (X→Z) = 0 tại vị trí thứ 5 và thứ 7  Vậy định nghĩa ta có T R (X→Z) = g  =  N  Z X T  j i  j i  j i  t t  R t t  t t å ¹ Î " ®  ,  ) , (  ) (  = [ ]  N  n n  2  4 ) 1 ( - -  t i (X) = t j (X)  t i (Y) = t j (Y)  t i (Z)= t j (Z)  T  ) , (  j i  t t  (X→Y)  T  ) , (  j i  t t  (XZ→YZ)  0  0  0  0  1  1  1  1  0  0  1  1  0  0  1  1  0  1  0  1  0  1  0  1  1  1  1  1  0  0  1  1  1  1  1  1  1  0  1  1 29  Tương tự a  = [ ]  N  n n  2  4 ) 1 ( - -  ; b = [ ]  N  n n  2  4 ) 1 ( - -  Suy ra  ) , min( b a g =  □  2.3 Xây dựng hệ tiên đề cho lớp Phụ thuộc hàm mờ ( Hệ tiên đề Amstrong  mở rộng)  Để  đơn  giản  ta  ký  hiệu  phụ  thuộc  hàm X → Y với mức  thỏa T R (X →  Y)³ a  là  (X →  Y) a  .  Đây  cũng  là  sự  mở  rộng  rất  tự  nhiên  của  hệ  tiên  đề  Amstrong. Việc mở rộng này sẽ là cơ sở nền tảng cho phép xem xét các vấn đề  liên quan đến phụ thuộc hàm, bao đóng và khoá trong ngữ cảnh mờ.  Định  lý( Hệ  tiên đề Amstrong mở rộng[12]  ): Cho R  là một quan hệ  trên  tập  thuộc tính U và X, Y, Z  là 3 tập thuộc tính của U. Khi đó:  A1': Nếu YÍ X thì (X → Y) a  với  (0  1 £ £ a  ).  A2': Nếu  (X → Y) a  thì (X Z→ YZ) a  A3': Nếu  (X → Y) a  , (Y→ Z) b  thì (X → Z) f  với  ) , min( b a f =  .  A4': Nếu  (X → Y) a  thì (X→ Y) b  với mọi a b £  Chứng minh: Với A1' , A2' , A3' dễ dàng chứng minh dựa vào định nghĩa Phụ  thuộc hàm mờ nêu trên và các tính chất 1,2 và 3.  Với A4' ta có (X→ Y) a  tức là T R (X → Y) = a b ³  suy ra (X→ Y) b  □  Từ hệ tiên đề trên ta cũng có các hệ quả sau:  Hệ quả:  D1: Nếu (X→Y) a  và (X→Z) b  thì (X→ YZ) g  với  ) , min( b a g =  .  D2: Nếu  (X→Y) a  và  (WY→Z) b  thì (WX→Z) g  ) , min( b a g =  D3: Nếu (X→Y) a  và ZÍ Y thì (X→Z) a  .  D4: (X→Y 1 Y 2  … Y k ) a  khi và chỉ khi (X→ Y i ) a  với i = 1,2,…,k.  Chứng minh:  D1: Từ (X→Y) a  theo A2' ; thêm X ta có (X→XY) a  Từ   (X→Z) b  cũng  theo A2'  ;  thêm Y  ta có    (XY→YZ) b  . Và cuối cùng  theo A3' ta có (X→ YZ) g  với  ) , min( b a g =  .  D2: Từ (X→Y) a  theo A2' ; thêm W ta có (WX→WY) a  . Khi từ giả thiết  theo A3' ta có (WX→Z) g  với  ) , min( b a g =  .  D3: Vì ZÍ Y nên  (Y→Z) a  với (0  1 £ £ a  ) ( theo A1' ) 30  Khi đó từ giả thiết áp dụng A3' cho (X→Y) a và  (Y→Z) a  ta có  (X→Z) a  .  D4: Þ  Nếu (X→Y 1 Y 2  … Y k ) a  thì hiển nhiên ta có (X→ Y i ) a  với  i =  1,2,…,k. Ü Nếu (X→ Y i ) a  với i = 1,2,…,k  thì theo D1 ta có:  (X→Y 1 Y 2  … Y k ) a 31  CHƯƠNG 3. KHOÁ MỜ TRONG CƠ SỞ DỮ LIỆU  QUAN HỆ  3.1  Khoá mờ  Khoá chính [2] ( primary key) là trường hợp đặc biệt của phụ thuộc hàm  trong  mô  hình  CSDL  quan  hệ  cổ  điển.  Vai  trò  của  X  trong  phụ  thuộc  hàm  X àY thuộc về các thuộc tính trong một khoá và tập tất cả các thuộc tính còn  lại trong quan hệ đóng vai trò là Y. Do đó, khi nói  K, một tập con của tập thuộc  tính U,  trong quan hệ R  là một khoá có nghĩa  là các giá  trị của U được quyết  định  từ  các  giá  trị  của  K  cho  tất  cả  các  bộ  trong  quan  hệ R.  Trong  mô  hình  CSDL truyền thống, các giá trị K đồng nhất sẽ dẫn đến các giá trị U đồng nhất.  Sự quyết định được phản ánh bởi mối quan hệ giữa K và U. Để mở rộng mối  quan hệ này trong mô hình cơ sở dữ liệu quan hệ mờ thì khoá chính được “mở  rộng” và được gọi là khoá mờ [10] ( fuzzy key ) với ngưỡng α nào đó.  Định  nghĩa:  Phụ  thuộc  hàm  từng  phần  [10]  (partial  functional  dependency)  là phụ thuộc hàm có thuộc tính không phải  là khoá mà phụ thuộc  một phần vào khoá chính.  Nói cách khác với X, Y ΠU, F là tập các PTH trên U. Khi đó (X®Y) a được gọi  là  PTH  từng  phần  nếu  và  chỉ  nếu  (X®Y) a ÎF  và  tồn  tại  X’ÍX,  X’ ¹ Æ  mà  (X’®Y) b ÎF mà b a ³  .  Định nghĩa: Cho tập K, S ⊆ U, F là tập phụ thuộc hàm mờ trong quan hệ  R: K được gọi là khoá mờ của quan hệ R với ngưỡng α nếu và chỉ nếu K→  i a  U ÎF và K→  i a  U không phải là phụ thuộc hàm mờ một phần trong đó α = min  i a  và  α > 0.  Ví dụ:  Cho quan hệ R ( A, B, C, D ) và phụ thuộc hàm mờ: A  0.6 ®  B và A  0.85 ®  CD  Ta thấy A quyết định các giá trị của B với mức thoả 0.6; A quyết định các  giá trị của C, D với mức thoả 0.85  Như vậy ta có:  1 a  = 0.6 và  2 a  = 0.85 Þ  1 2 min( , ) min(0.6,0.85) a a a = =  = 0.6  Vậy A được gọi là khoá mờ với mức thoả a =0.6.  Một khoá mờ có thể chứa các giá trị là thuộc tính nguyên thuỷ, nó cũng có  thể chứa các  thuộc  tính đa  trị như  là { a, b}  trong đó a và b được xem như  là  giống nhau với mức thoả a  nào đó.  3.2  Bao đóng tập thuộc tính  Định nghĩa: Cho tập thuộc tính U ={ A 1 , A 2 , …, A n } và R là một quan  hệ trên U; X, Y là  hai tập con của U. Gọi F là tập các phụ thuộc hàm mờ trên R.  Khi đó bao đóng của tập thuộc tính (transitive closure) X theo Phụ thuộc  hàm mờ F  được ký hiệu là X F +  và: 32  X F +  = { (A, f  ) │AΠU, f = sup {b  │(X → A) b ΠF + }}.  Để đơn giản ta ký hiệu X F +  bằng X +  3.2.1. Tính chất của bao đóng tập thuộc tính (X + )  Tính chất 1 (Tính phản xạ): X + Í  X F  Chứng minh:  Lấy A  X Π cần chứng minh (A,a )  X Î + .  Thật  vậy,  từ  A  X Î { } A X Þ Í + Î ® Þ  F A X a ) (  (theo  A1’).  Theo  định  nghĩa của X +  suy ra  (A, + Î X ) a  . Vậy X + Í  X F  □  Tính chất 2 (Tính đơn điệu): Nếu  X  F Í  Y thì X  +  F Í  Y  +  .  Chứng minh: Lấy (A,a ) + Î X  cần  chứng minh (A,a ) + ÎY  .  Thật vậy, từ  (A,a ) + Î X + Î ® Þ  F A X a ) (  . Mặt khác do X  Y F Í  nên  (Y→X) b + Î F  (0  1 £ £ b  )  (theo A1’). Vậy  (Y + Î ®  F A g )  với  ) , min( b a g =  (theo  A3’)Þ  (A, g ) + ÎY  . Suy ra X +  F Í  Y  +  □  Tính chất 3: (X→X + ) a  và  (X + →X) a  (0  1 £ £ a  ).  Chứng minh: Theo tính chất 1 ta có X + Í  X F a ) (  X X ® Þ +  .  Giả sử X  } ) , {(A i  i a = +  với i =1,2… k. Ta có:  (A + Î X ) ,  1 1 a Þ  (X + Î ®  F A  1 1 ) a  Tương tự :                  (X + Î ®  F A  2 2 ) a  …………..........  (X + Î ®  F A  k k a )  Suy ra  ( X→A g ) ... 2 1  k A A + Î F  với  ) ..., , min(  2 1  k a a a g =  (Theo D1). Vậy theo  D4 suy ra  (X a ) + ® X  □  Tính chất 4: X + + Y + Í  ) (XY F  Chứng minh: Ta có X  XY F Í + + Í Þ  ) (XY X  F  (1 )   (theo tính chất 2)  Tương tự : Y + + Í  ) (XY F  (2)  Từ (1) và (2) suy ra X + + + + Í  ) (XY Y  F  □  Tính chất 5: (X→Y) a Û  Y + Í  X F  với (0  1 £ £ a  )  Chứng minh: Þ Giả sử có (X→Y) a  cần chứng minh Y + Í  X F 33  Lấy A  Y Π cần chỉ ra (A, + Î X ) b  . Thật vậy ta có:  A  Y Î { } A X Þ Í b ) (  A Y ® Þ  (1)   ( theo A1’)  Mặt khác theo giả thiết ta có (X a ) Y ®  (2)  Từ  (1) và  (2) suy  ra  (X g ) A ®  với  ) , min( b a g =  (theo A3’). Từ đó suy ra  (A,g ) + Î X  . Ü Giả sử có  Y + Í  X F  cần chứng minh  (X→Y) a  .  Do Y + Í  X F b ) (  Y X ® Þ +  (theo  A1’)  mà  (X→X + ) g  (tính chất 3) suy ra  (X→Y) a  với  ) , min( g b a =  .  Định  lý:  Cho  U  là  tập  thuộc  tính  ,A i  (i  =1,2…k)  là  các  thuộc  tính,  Y  =A 1 A 2 …A k Í U . Khi đó (X → Y) f ΠF +  khi và chỉ khi tồn tại một bộ thuộc  tính  (A i  ,  i f  ) (i = 1,2 …k) thuộc vào bao đóng của X tức là : $  (A 1  ,  1 f  ),…, (A k  ,  k f  ) ÎX +  trong đó  min (  1 f  ,  2 f  , … ,  k f  ) ³ f .  Chứng minh:  Điều kiện cần: Nếu (X → Y) f ΠF +  thì (X→ A i ) f ΠF +  với (i =1,2…k)  (theo D4). Do đó $  (A i ,  i f  ) ΠX +  và  i f ³ f  vì  i f = sup {f  │(X → Y) f ΠF + }  với (i =1,2…k) (theo định nghĩa X + ) . Suy ra  min (  1 f  ,  2 f  , … ,  k f  ) ³ f .  Điều kiện đủ: Nếu $  (A 1  ,  1 f  ),…, (A k  ,  k f  ) ÎX +  và min (  1 f  ,  2 f  , … ,  k f  ) ³ f  thì (X→ A i )  i f ΠF +  với (i =1,2…k) (theo định nghĩa X + )  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}