1. Trang Chủ
  2. Công nghệ thông tin
  3. Đề 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ệ

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

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. 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ên

Thể loại Tài liệu miễn phí Công nghệ thông tin

Số trang 73

Ngày tạo 8/30/2018 1:19:04 AM +00:00

Loại tệp PDF

Kích thước 1.17 M

Tên tệp

Tải Đề tài: Nghiên cứu một số vấn đề về phụ thuộc dữ l... (.pdf)

Xem mẫu

  1. 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Ệ
  2. 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
  3. 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
  4. 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.
  5. 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.  Wit h  the  objective  of  researching  on  the  expansion  of  functional  dependency  and  related  concepts,  my  thesis  focus  on  researching  about  data  dependency,  fuzz y  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 theore m.
  6. 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
  7. 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
  8. 7  DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT  Nghĩa đầy đủ  TT  Từ viết tắt  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ờ
  9. 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
  10. 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
  11. 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.
  12. 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.
  13. 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.
  14. 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 CSD L  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 ... An  },  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]
  15. 14  Phụ thuộc  hàm ký hiệu là FD.  Ví dụ: Cho  quan hệ R = HS :  STT  Ten  Namsinh  Diachi  DT  Email  HS  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  Te n  đề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à  t1[X]=t 2 [X]  cần chứng minh  t1[Y]=t 2 [Y]      Thật vậy do  Y Í  X suy ra  t1[Y]=t 2 [Y]  (đúng )    □  A2) Giả sử  t1 , t2  ΠR và  t1[XW]=t 2 [XW] cần chứng  minh  t1[YW]=t 2 [YW] .      Phản  chứng:  Giả  sử  t1[YW] ¹ t 2 [YW] .  Do  t1[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à  t1[X]=t 2 [X]  thì  t1[Y]=t 2 [Y] Þ mâu thuẫn.Vậy  t1[YW]=t 2 [YW]      □
  16. 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à  t1[X]=t 2 [X]  cần chứng minh  t1[Z]=t 2 [Z]      Phản  chứng  :  Giả  sử  t1[Z]  ¹  t 2 [Z] .  Từ  X ® Y suy  ra  t1[X]=t 2 [X]  thì    t1[Y]=t 2 [Y] . Mặt khác ta  lại có PTH  Y ® Z nghĩa  là  t1[Y]=t 2 [Y]  thì  t1[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  t1[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  nha u  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
  17. 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 +  được xác định như sau:  F X F = { A| A Ì U , X ® A Î F    }  + +  Ta viết gắn gọn X +  là X   .  + F 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 +
  18. 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 
  19. 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  □
  20. 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:  A k  A n  R  A 1  A 2  …  A k +1  …    a k  a n  u  a 1  a 2  …  a k +1  …    a k  b n  v  a 1  a 2  …  b k +1  …    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.
nguon tai.lieu . vn
Thạc sĩ - Tiến sĩ - Cao học Công nghệ thông tin Kinh tế - Thương mại Tài chính - Ngân hàng Kiến trúc - Xây dựng Điện-Điện tử-Viễn thông Cơ khí - Chế tạo máy Công nghệ - Môi trường Báo cáo khoa học Quản trị kinh doanh Khoa học xã hội Khoa học tự nhiên Nông - Lâm - Ngư Y khoa - Dược