Tài liệu 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ệ

®¹i häc quèc gia hµ néi Tr−êng ®¹i häc C¤NG NGHÖ  ­­­˜&™­­­ TrÇn Thμnh Trung 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Ö LUËN V¡N TH¹C SÜ  Hà Nội – 2009 ®¹i häc quèc gia hµ néi Tr−êng ®¹i häc C¤NG NGHÖ  ­­­˜&™­­­ TrÇn Thμnh Trung 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Ö Ngµnh: C«ng nghÖ th«ng tin Chuyªn ngµnh: HÖ thèng th«ng tin M∙ sè: 60 48 05 LUËN V¡N TH¹C SÜ NG−êi h−íng dÉn khoa häc: pgs. ts vò ngäc lo∙n  Hà Nội – 2009 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  1  2  3  4  5  6  Từ viết tắt  CNTT  CSDL  HTTT  HĐH  FTH  FFD  7  FK  Nghĩa đầy đủ  Công nghệ thông tin  Cơ sở dữ liệu  Hệ thống thông tin  Hệ điều hành  Phụ thuộc hàm  Fuzzy  Functional  Dependency  ­  Phụ  thuộc  hàm  mờ  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 1 ... A n  }, 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  2  Kiên  1987  Phú Thọ  045596045  kientt  3  Nam  1984  Hà Nội  045769823  namlt  Trungtt  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  X , Y , Z , W Í 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ì  XW ® YW  A3) Bắc cầu : Nếu  X ® Y , Y ® Z thì  X ® Z Chứng minh:  A1) Giả sử  t1 , t2  ΠR và  t 1[X]=t 2 [X]  cần chứng minh  t 1[Y]=t 2 [Y]  Thật vậy do  Y Í  X suy ra  t 1[Y]=t 2 [Y]  (đúng )  □  A2) Giả sử  t1 , t2  ΠR và  t 1[XW]=t 2 [XW] cần chứng minh  t 1[YW]=t 2 [YW] .  Phản  chứng:  Giả  sử  t1[YW] ¹ t 2 [YW] .  Do  t 1[W]=t 2 [W]  nên  để  có  t1[YW] ¹ t 2 [YW]  thì  t1[Y] ¹ t 2 [Y] .  Nhưng  theo  giả  thiết  ta  có  X→Y  nghĩa  là  t 1[X]=t 2 [X]  thì  t1[Y]=t 2 [Y] Þ mâu thuẫn.Vậy  t 1[YW]=t 2 [YW]  □ 15  A3) Theo giả thiết ta có  X ® Y , Y ® Z là hai PTH trên quan hệ R  Giả sử  t1 , t2  ΠR và  t 1[X]=t 2 [X]  cần chứng minh  t 1[Z]=t 2 [Z]  Phản  chứng  :  Giả  sử  t1[Z]  ¹  t 2 [Z] .  Từ  X ® Y suy  ra  t 1[X]=t 2 [X]  thì  t 1[Y]=t 2 [Y] . Mặt khác ta lại có PTH  Y ® Z nghĩa là  t 1[Y]=t 2 [Y]  thì  t 1[Z]=t 2 [Z]  nhưng  theo  giả  thiết  phản  chứng  ta  có  t1[Z]  ¹  t 2 [Z] (mâu  thuẫn).  Vậy  t 1[Z]=t 2 [Z]  □  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ì  XW ® Z  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ó  XW ® WY (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ó  XW ® Z  □  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 k -1  È {f k  }  Vậy ta có R(F) Þ  R(F 1 ) Þ  R(F 2  ) Þ  … Þ R(F k  ) Þ  R(f) hay F = f  □