Tài liệu Về các phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 NGUYỄN NĂNG HƢNG VỀ CÁC PHỤ THUỘC HÀM XẤP XỈ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI LUẬN VĂN THẠC SĨ MÁY TÍNH HÀ NỘI, 2014 LỜI CẢM ƠN Tôi xin chân thành cảm ơn và tri ân sâu sắc đến PGS.TS. Trịnh Đình Thắng đã tận tình hướng dẫn, giúp đỡ tôi trong quá trình nghiên cứu, hoàn thành luận văn. Tôi xin chân thành cảm ơn Trường Đại học Sư phạm Hà Nội 2 quý Thầy Cô giáo Lãnh đạo và các giảng viên, cán bộ của trường đã tạo điều kiện thuận lợi cho tôi học tập, nghiên cứu và bảo vệ luận văn. Cảm ơn gia đình và những người thân đã ủng hộ, động viên, khích lệ, chia sẻ với tôi trong suốt quá trình học tập, nghiên cứu. TÁC GIẢ LUẬN VĂN NGUYỄN NĂNG HƢNG LỜI CAM ĐOAN Tôi xin cam đoan Luận văn: “Về các phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối” là công trình nghiên cứu của riêng bản thân. Các số liệu trong luận văn là trung thực, được trích dẫn và có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình đã nghiên cứu, ở trong nước và trên thế giới. Xây dựng chương trình tính toán phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối là chương trình do tôi tự viết. Không sử dụng một mã nguồn mở nào có sẵn. TÁC GIẢ NGUYỄN NĂNG HƢNG MỤC LỤC Trang phụ bìa Lời cảm ơn ........................................................................................................ i Lời cam đoan ................................................................................................... ii Mục lục ............................................................................................................ iii Danh mục các ký hiệu, các chữ viết tắt ........................................................ vi Danh mục các bảng ....................................................................................... vii Danh mục các hình vẽ, đồ thị ...................................................................... viii MỞ ĐẦU ........................................................................................................... i CHƢƠNG 1: MÔ HÌNH CƠ SỞ DỮ LIỆU QUAN HỆ........................... xiv 1.1 Thuộc tính, quan hệ, đại số quan hệ.................................................. xiv 1.1.1. Thuộc tính và miền thuộc tính............................................................. xiv 1.1.2. Quan hệ, lược đồ quan hệ ................................................................... xiv 1.2. Các phép toán đại số quan hệ ............................................................ xvi 1.2.1. Phép hợp ............................................................................................. xvi 1.2.2. Phép giao ............................................................................................ xvi 1.2.3. Phép trừ.............................................................................................. xvii 1.2.4. Tích Đề-các ........................................................................................ xvii 1.2.5. Phép chiếu ......................................................................................... xviii 1.2.6. Phép chọn............................................................................................ xix 1.2.7. Phép kết nối.......................................................................................... xx 1.2.8. Phép chia............................................................................................. xxi 1.3. Phụ thuộc hàm ..................................................................................... xxi 1.4. Bao đóng ............................................................................................. xxiii 1.4.1 Bao đóng của tập phụ thuộc hàm. ..................................................... xxiii 1.4.2 Bao đóng của tập thuộc tính đối với tập các phụ thuộc hàm ............ xxiii 1.5. Khoá của quan hệ .............................................................................. xxiii 1.6 Phụ thuộc hàm và lớp tƣơng đƣơng ................................................. xxiv 1.6.1 Sự phân hoạch.................................................................................... xxiv 1.6.2 Phân hoạch mịn hơn .......................................................................... xxvi 1.6.3 Một số tính chất của phụ thuộc hàm và lớp tương đương ................ xxvii 1.7 Phụ thuộc hàm xấp xỉ ...................................................................... xxviii 1.8 Bao đóng của tập phụ thuộc hàm xấp xỉ ........................................ xxxiii 1.9 Khoá xấp xỉ ....................................................................................... xxxiii 1.10 Một số Tính chất của phụ thuộc hàm xấp xỉ trên lƣợc đồ quan hệ [9] xxxv CHƢƠNG 2: MÔ HÌNH CƠ SỞ DỮ LIỆU DẠNG KHỐI ............... xxxviii 2.1. Khối, lƣợc đồ khối ......................................................................... xxxviii 2.2. Lát cắt ............................................................................................... xxxix 2.3. Đại số quan hệ trên khối ....................................................................... xl 2.3.1. Phép hợp ............................................................................................... xl 2.3.2. Phép giao ............................................................................................. xli 2.3.3. Phép trừ................................................................................................ xli 2.3.4. Tích Đề các .......................................................................................... xli 2.3.5. Tích Đề các theo tập chỉ số .................................................................. xli 2.3.6. Phép chiếu ........................................................................................... xlii 2.3.7. Phép chọn............................................................................................ xlii 2.3.8. Phép kết nối........................................................................................ xliii 2.3.9. Phép chia............................................................................................ xliv 2.4. Phụ thuộc hàm .................................................................................... xliv 2.5. Các tính chất của phụ thuộc hàm trên lƣợc đồ khối. ...................... xlv CHƢƠNG 3: PHỤ THUỘC HÀM XẤP XỈ TRONGMÔ HÌNH DỮ LIỆU DẠNG KHỐI ............................................................................................... xlix 3.1 Phụ thuộc hàm xấp xỉ trong mô hình dữ liệu khối .......................... xlix 3.2 Mối quan hệ giữa phụ thuộc hàm xấp xỉ trên khối và phụ thuộc hàm xấp xỉ trên lát cắt........................................................................................liii 3.4 Một số tính chất ..................................................................................... lvi 3.5 Cài đặt ..................................................................................................... lx KẾT LUẬN ................................................................................................... 54 TÀI LIỆU THAM KHẢO ............................................................................ 55 PHỤ LỤC ....................................................................................................... 58 DANH MỤC CÁC CHỮ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu FDs Functional Dependencies Các phụ thuộc hàm AFDs Approximate Functional Dependencies Các phụ thuộc hàm xấp xỉ DANH MỤC CÁC BẢNG STT Tên bảng Trang 1 Bảng 1.1:Biểu diễn quan hệ r 6 2 Bảng 1.2: Bảng dữ liệu sinh viên 6 3 Bảng 1.3: Biểu diễn các quan hệ r, s và quan hệ r× s 9 4 Bảng 1.4: Bảng dữ liệu quan hệ 16 5 Bảng 1.5: Bảng dữ liệu thuộc tính giá trị số 21 5 Bảng 3.1: Bảng biểu diễn khối dữ liệu 48 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ STT Tên hình vẽ Trang 1 Hình 2.1: Biểu diễn khối nhân viên NV(R). 30 2 3 HHình 3.1: Biểu diễn khối sinhviên1 Hình 3.2: Khối dữ liệu 41 48 MỞ ĐẦU 1. Lý do chọn đề tài Để xây dựng được một hệ thống cơ sở dữ liệu tốt, người ta thường sử dụng các mô hình dữ liệu thích hợp. Đã có một số mô hình được sử dụng trong các hệ thống cở sở dữ liệu như: mô hình thực thể - liên kết, mô hình mạng, mô hình phân cấp, mô hình hướng đối tượng, mô hình dữ liệu datalog và mô hình quan hệ. Trong số các mô hình này, có ba mô hình dữ liệu hay được sử dụng là mô hình phân cấp, mô hình mạng và mô hình quan hệ. Đối với ba mô hình này, mô hình quan hệ được quan tâm hơn cả, bởi vì nó được xây dựng trên cơ sở toán học chặt chẽ. Tuy nhiên, do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này chưa đủ đáp ứng đối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến tính. Trong những năm gần đây, việc nghiên cứu nhằm mở rộng mô hình dữ liệu quan hệ đã được nhiều nhà khoa học quan tâm. Theo hướng nghiên cứu này một mô hình được xem là mở rộng của mô hình dữ liệu quan hệ đã được đề xuất đó là mô hình dữ liệu dạng khối. Tuy nhiên mô hình này mới xây dựng nên chưa hoàn thiện và hiện đang được quan tâm nghiên cứu, xem [7], [8], [9], [12] và các tài liệu dẫn trong đó. Với mong muốn tìm hiểu sâu hơn về những kiến thức đã học, mối quan hệ và những ứng dụng của mô hình dữ liệu dạng khối, đặc biệt là các phụ thuộc hàm xấp xỉ, tôi chọn đề tài “Về các phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối” để nghiên cứu. 2. Mục đích nghiên cứu Nghiên cứu các tính chất của phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối nhằm góp phần hoàn chỉnh lý thuyết mô hình dữ liệu dạng khối. 3. Nhiệm vụ nghiên cứu Tìm hiểu về phụ thuộc hàm xấp xỉ, nghiên cứu các tính chất của phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối. Đồng thời nghiên cứu mối quan hệ giữa phụ thuộc xấp xỉ trên khối và trên lát cắt. 4. Đối tƣợng và phạm vi nghiên cứu Phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối. 5. Phƣơng pháp nghiên cứu - Tìm hiểu tài liệu: Các bài báo đã được đăng và sách đã in liên quan mật thiết đến phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối - Sử dụng các phương pháp phân tích tổng hợp các tài liệu và những thông tin liên quan đến đề tài, kết hợp các nghiên cứu đã có trước đây của tác giả trong nước cùng với sự chỉ bảo, góp ý của thầy hướng dẫn để hoàn thành nội dung nghiên cứu. 6. Những đóng góp mới của đề tài 7. Cấu trúc của luận văn Luận văn gồm: Lời mở đầu, ba chương nội dung, phần kết luận và tài liệu tham khảo. Chƣơng 1 Trình bày các khái niệm cơ bản nhất về mô hình quan hệ. Trình bày các phép toán đại số trên mô hình quan hệ. Phụ thuộc hàm xấp xỉ, một số tinh chất của phụ thuộc hàm xấp xỉ trên lược đồ quan hệ. Chƣơng 2 Giới thiệu tổng quan về mô hình khối: Phụ thuộc hàm trên khối, phụ thuộc hàm xấp xỉ trên khối. Chƣơng 3 Phát biểu và chứng minh các tính chất của phụ thuộc hàm, xấp xỉ trên khối. Mối quan hệ giữa phụ thuộc hàm xấp xỉ trên khối và trên lát cắt. Phụ thuộc hàm xấp xỉ trên khối và phụ thuộc hàm xấp xỉ trên quan hệ trong mô hình dữ liệu quan hệ (khi khối suy biến thành quan hệ) GIỚI THIỆU Cơ sở dữ liệu là một trong những lĩnh vực quan trọng của công nghệ thông tin. Cơ sở dữ liệu đã được nghiên cứu, ứng dụng thành công trong nhiều lĩnh vực và đem lại hiệu quả kinh tế cao cho đời sống và xã hội. Đã có rất nhiều bài báo nghiên cứu về cơ sở dữ liệu và mô hình cơ sở dữ liệu. Có 3 mô hình thường được sử dụng: mô hình phân cấp, mô hình mạng và mô hình quan hệ. Trong đó mô hình quan hệ được quan tâm hơn cả. Do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này chưa đủ đáp ứng đối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến,….Do đó việc mở rộng mô hình dữ liệu quan hệ thành mô hình dữ liệu dạng khối nhằm mở ra khả năng quản lý dữ liệu, đáp ứng nhu cầu thực tế tốt hơn [2]. Phụ thuộc hàm là một loại ràng buộc dữ liệu giữa các thuộc tính trong một cơ sở dữ liệu quan hệ, góp phần vào việc đảm bảo tính nhất quán của dữ liệu, loại bỏ bớt dữ liệu dư thừa. Phụ thuộc hàm cũng thể hiện tính chất ngữ nghĩa giữa các thuộc tính và có thể tồn tại trong một tập dữ liệu độc lập với mô hình quan hệ. Nghiên cứu về các phụ thuộc hàm là một hướng quan trọng trong thiết kế cơ sở dữ liệu quan hệ và đã đạt được nhiều thành tựu [11, 12, 13, 20] bên cạnh đó nghiên cứu về phụ thuộc hàm trong mô hình dữ liệu dạng khối [2] đã có những kết quả [2, 5] để tăng cường hơn nữa khả năng đảm bảo ngữ nghĩa, góp phần hoàn chỉnh thêm về mô hình dữ liệu dạng khối. Cho lược đồ khối R = (id; A1,A2,...,An), r(R) là một khối trên R, n X, Y   id (i ) , X  Y là kí hiệu một phụ thuộc hàm. Một khối r thoả X  Y i 1 nếu với mọi t1, t2 R sao cho t1(X) = t2(X) thì t1(Y) = t2(Y). Từ định nghĩa phụ thuộc hàm ở trên, ta nhận thấy: nếu tồn tại t1 , t2  r sao cho t1  X   t2  X  và t1 Y   t2 Y  thì có thể kết luận rằng r không thỏa phụ thuộc hàm X  Y (hay phụ thuộc hàm X  Y không đúng trên r). Trong thực hành, điều này tỏ ra quá chặt và cứng nhắc khi ta hình dung quan hệ r có hàng nghìn bộ, trong đó chỉ có một vài bộ vi phạm phụ thuộc hàm X  Y do có một số dữ liệu bị sai lệch hoặc ngoại lệ. Do đó việc mở rộng khái niệm phụ thuộc hàm (kinh điển) thành phụ thuộc hàm xấp xỉ (trong mô hình dữ liệu quan hệ, mô hình dữ liệu dạng khối) theo một cách thức, một nghĩa nào đó là nhu cầu tất yếu và tự nhiên. Các phụ thuộc hàm xấp xỉ khai phá được từ mô hình cơ sở dữ liệu quan hệ, mô hình dữ liệu dạng khối là các mẫu quan trọng, là những tri thức có giá trị về cấu trúc của các bộ dữ liệu. CHƢƠNG 1 MÔ HÌNH CƠ SỞ DỮ LIỆU QUAN HỆ 1.1 Thuộc tính, quan hệ, đại số quan hệ 1.1.1. Thuộc tính và miền thuộc tính Định nghĩa 1.1 [4], [6] - Thuộc tính là đặc trưng của đối tượng. - Tập tất cả các giá trị có thể có của thuộc tính Ai gọi là miền giá trị của thuộc tính đó, ký hiệu: Dom(Ai) hay viết tắt là DAi Ví dụ 1.1: Đối tượng Sinhviên có các thuộc tính như: MaSV, Hoten, NgSinh, Đchi, ... Miền giá trị của các thuộc tính của đối tượng Sinh viên : Dom(MaNV) = {char(4)} ={„SV01‟, „SV02‟, „SV03‟ ...}; Dom(Hoten) = {char(30)} ={„Nguyễn Văn A‟,„Nguyễn Văn B‟, ...} ; Dom(NgSinh) = {date} ={„30/03/78‟, „22/12/96‟, ...} ; Dom(Đchi) ={char(10)} = {„HN‟, „HP‟, „VP‟, …}. 1.1.2. Quan hệ, lược đồ quan hệ Định nghĩa 1.2 [4], [6] Cho U= {A1, A2, …, An} là một tập hữu hạn không rỗng các thuộc tính. Mỗi thuộc tính Ai (i=1,2, …, n) có miền giá trị là Dom(Ai). Khi đó r là một tập các bộ {h1, h2, …, hm} được gọi là quan hệ trên U với hj (j=1, 2, …, m) là một hàm: hj:U →  D sao cho hj(Ai) DAi(i=1, 2, ...,n). Ai U Ai Ta có thể xem một quan hệ như một bảng, trong đó mỗi hàng (phần tử) là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc tính. Biểu diễn quan hệ r thành bảng như sau: A1 A2 … An h1 h1(A1) h1(A2) … h1(An) h2 h2(A1) h2(A2) … h2(An) … … … … … hm hm(A1) hm(A2) … hm(An) Bảng 1.1: Biểu diễn quan hệ r Ví dụ 1.2: Sinhviên MaSV HOTEN NS DC KHOA SV01 A 24/01/92 HN TOAN SV02 B 3/05/92 VP LY SV03 B 3/05/92 VP TOAN Bảng 1.2 :Bảng dữ liệu sinh viên Trong đó các thuộc tính là MaSV: mã sinh viên; HOTEN: họ tên; NS: ngày sinh; DC: địa chỉ; KHOA: khoa. Bộ giá trị: (SV01, A, 24/01/92, HN, TOAN) là một bộ. Nếu có một bộ t = (d1, d2, d3, ..., dm)  r, r xác định trên U, X  U thì t(X) (hoặc t.X) được gọi là giá trị của tập thuộc tính X trên bộ t. Định nghĩa 1.3 [4], [6] Tập tất cả các thuộc tính trong một quan hệ cùng với mối liên hệ giữa chúng được gọi là lược đồ quan hệ. Lược đồ quan hệ R với tập thuộc tính U={A1, A2, .., An} được viết là R(U) hoặc R(A1, A2, .., An). 1.2. Các phép toán đại số quan hệ Định nghĩa 1.4 [3], [6] Hai quan hệ r và s được gọi là khả hợp nếu như hai quan hệ này xác định trên cùng tập thuộc tính và các thuộc tính cùng tên có cùng miền giá trị. 1.2.1. Phép hợp Phép hợp hai quan hệ khả hợp r và s, kí hiệu là r ∪ s, là tập tất cả các bộ thuộc r hoặc thuộc s. Ta có: r ∪ s = {t│ t ∈ r ∨ t ∈ s} Ví dụ 1.3: r (A B C) x1 y1 x2 ; s (A B C) z1 x1 y1 z1 y1 z2 x2 y2 z2 x2 y2 z1 r∪ s (A B C) x1 y1 z1 x2 y1 z2 x2 y2 z1 x2 y2 z2 1.2.2. Phép giao Phép giao của hai quan hệ khả hợp r và s, kí hiệu là r ∩ s, là tập tất cả các bộ thuộc cả hai quan hệ r và s. Ta có: r ∩ s = {t│ t ∈ r ∧ t ∈ s} Ví dụ 1.4: r (A B C) x1 y1 x2 x2 ; s (A B C) z1 x1 y1 z1 y1 z2 x2 y2 z2 y2 z1 r∩ s (A B C) x1 y1 z1 1.2.3. Phép trừ Phép trừ của hai quan hệ khả hợp r và s, kí hiệu: r - s là tập tất cả các bộ thuộc r nhưng không thuộc s. Ta có: r - s = {t│ t ∈ r ∧ t ∉ s} Ví dụ 1.5: r (A B C) x1 y1 x2 ; s (A B C) z1 x1 y1 z1 y1 z2 x2 y2 z2 x2 y2 z1 r - s = (A B C) s - r = (A B C) x2 y1 z2 x2 y2 z2 x2 y2 z1 1.2.4. Tích Đề-các Cho quan hệ r xác định trên tập thuộc tính {A1, A2, ..., An} và quan hệ s xác định trên tập thuộc tính {B1, B2, .., Bm}. Tích Đề-các của hai quan hệ r và s kí hiệu là r × s, là tập tất cả các (m+n) - bộ có n thành phần đầu tiên là một bộ thuộc r và m thành phần sau là một bộ thuộc s. Ta có: r×s A B C G H F x1 y1 z1 x1 y1 z1 x1 y1 z1 x2 y2 z2 x1 y1 z1 x1 y2 z2 x2 y1 z2 x1 y1 z1 x2 y1 z2 x2 y2 z2 x2 y1 z2 x1 y2 z2 x2 y2 z1 x1 y1 z1 x2 y2 z1 x2 y2 z2 x2 y2 z1 x1 y2 z2 r × s = {t=(a1, a2, .., an, b1, b2, .., bm)│(a1, a2, .., an) ∈r  (b1 b2, .., bm) ∈s} Ví dụ 1.6 : r A B C x1 y1 x2 x2 s G H F z1 x1 y1 z1 y1 z2 x2 y2 z2 y2 z1 x1 y2 z2 Bảng 1.3: Biểu diễn các quan hệ r, s và quan hệ r× s 1.2.5. Phép chiếu Cho r là một quan hệ n ngôi xác định trên tập thuộc tính U={A1, A2, .., An}, là tập con của U. Phép chiếu của quan hệ r trên tập thuộc tính X, kí hiệu là  x (r), là tập các bộ của r xác định trên tập thuộc tính X. Ta có:  x (r) = {t.X│ t ∈ r}. Phép chiếu thực chất là phép toán giữ lại một số thuộc tính cần thiết của quan hệ và loại bỏ những thuộc tính không cần thiết. Ví dụ 1.7: r (A B C D) x1 1 x 4 y1 5 y 2 z1 5 z 5 x1 8 x 5 y1 1 y 4  B (r) (B) 1 5 8 BD (r) (B D) 1 4 5 2 5 5 8 5 1.2.6. Phép chọn Phép chọn là phép toán lọc lấy ra một tập con các bộ của quan hệ đã cho thoả mãn một điều kiện xác định. Điều kiện đó được gọi là điều kiện chọn hay biểu thức chọn. Biểu thức chọn F được định nghĩa là một tổ hợp logic của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa một biến là một thuộc tính và một giá trị hằng. Biểu thức chọn F cho giá trị đúng hoặc sai đối với mỗi bộ đã cho của quan hệ khi kiểm tra riêng bộ đó. - Các phép toán so sánh trong biểu thức F: >, <, =, ≥, ≠, ≤. - Các phép toán logic trong biểu thức F: ∧ (và), ∨ (hoặc),  (phủ định). Cho r là một quan hệ và F là một biểu thức logic trên các thuộc tính của r. Phép chọn trên quan hệ r với biểu thức chọn F, kí hiệu là  F (r), là tập tất cả các bộ của r thoả mãn F. Ta có:  F (r) = {t│ t ∈ r  F(t)}. Ví dụ 1.8: r(A B C D) x1 1 x 4 y1 5 y 2 z1 5 z 5 x1 8 x 5 y1 1 y 4 B D (r)(A B C D) y1 5 y 2 z1 5 z 5 x1 8 x 5 1.2.7. Phép kết nối Cho hai quan hệ r(U) và s(V). Đặt M=U∩V. Phép kết nối (tự nhiên) hai quan hệ r(U) và s(V), ký hiệu r*s, cho ta quan hệ giữa các bộ được dán từ các bộ u của quan hệ R với mỗi bộ v của quan hệ S (sao cho các trị trên miền thuộc tính chung M của hai bộ này giống nhau). P(UV)= r*s= {u*v│u∈ r, v∈ s, u.M=v.M} . Nếu M= U∩V=Ф, r*s sẽ cho ta tích Đề- các, trong đó mỗi bộ của quan hệ r sẽ được ghép với mọi bộ của quan hệ s. Ví dụ 1.9: r (A B C) x1 x x2 x2 x3 y2 y2 y2 y3 x z2 y z1 ; s (G H)