Đề 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ệ

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