Tài liệu Nghiên cứu phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ

i .. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ----------------------------- PHẠM XUÂN HÀ NGHIÊN CỨU CÁC PHƯƠNG PHÁP TRÍCH CHỌN SỰ KIỆN VÀ ỨNG DỤNG VÀO BÀI TOÁN TRÍCH CHỌN SỰ KIỆN DỊCH BỆNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2016 ii ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ----------------------------- PHẠM XUÂN HÀ NGHIÊN CỨU CÁC PHƯƠNG PHÁP TRÍCH CHỌN SỰ KIỆN VÀ ỨNG DỤNG VÀO BÀI TOÁN TRÍCH CHỌN SỰ KIỆN DỊCH BỆNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC GS. TS VŨ ĐỨC THI Thái Nguyên - 2016 iii LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu thực sự của cá nhân mình, thực hiện dưới sự hướng dẫn tận tình của thầy giáo TS. Lê Văn Phùng. Các số liệu, kết quả do bản thân nghiên cứu và tìm hiểu được trình bày trong luận văn này trung thực và chưa từng được công bố dưới bất cứ hình thức nào. Tôi xin chịu hoàn toàn trách nhiệm về nghiên cứu của mình. Học viên Lê Long Giang iv LỜI CẢM ƠN Lời đầu tiên, tôi xin được gửi lời cảm ơn sâu sắc nhất tới thầy giáo TS. Lê Văn Phùng, người thầy đã trực tiếp dành nhiều thời gian tận tình hướng dẫn, cung cấp những thông tin, tài liệu quý báu giúp đỡ tôi hoàn thành bản luận văn này. Tôi cũng xin gửi lời cảm ơn đến các giảng viên trường Đại Học Công nghệ Thông Tin và Truyền Thông - Đại học Thái Nguyên, các thầy Viện Công nghệ thông tin - Viện Hàn lâm Khoa học Công nghệ Việt Nam đã giảng dạy, truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá trình học tập của mình. Tôi cũng xin gửi lời cảm ơn tới Ban Giám đốc - Sở Khoa học và Công nghệ tỉnh Lào Cai, Phòng Quản lý Công nghệ và Thị trường công nghệ đã tạo mọi điều kiện thuận lợi cho em tham gia khóa học và trong suốt quá trình hoàn thành luận văn. Cuối cùng, tôi xin cảm ơn những người thân, bạn bè và gia đình đã luôn cổ vũ động viên tôi hoàn thành luận văn tốt nghiệp này. Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân, nhưng luận văn không tránh khỏi những thiếu sót. Kính mong nhận được những ý kiến đóng góp của quý thầy cô và bạn bè, đồng nghiệp. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 20 tháng 04 năm 2016 Học viên Lê Long Giang v MỤC LỤC LỜI CAM ĐOAN ................................................................................................... i LỜI CẢM ƠN ....................................................................................................... iv MỤC LỤC .............................................................................................................. v CÁC KÍ HIỆU VIẾT TẮT DÙNG TRONG LUẬN VĂN ................................. viii MỘT SỐ QUI ƯỚC VỀ KÍ HIỆU THƯỜNG ĐƯỢC ......................................... ix SỬ DỤNG TRONG LUẬN VĂN: ....................................................................... ix BẢNG CÁC HÌNH VẼ .......................................................................................... x DANH MỤC CÁC ĐỊNH NGHĨA, ĐỊNH LÝ, BỔ ĐỀ, THUẬT TOÁN ............ x MỞ ĐẦU ................................................................................................................ 1 CHƯƠNG 1: PHỤ THUỘC HÀM MẠNH VÀ PHẦN TỬ NGOẠI LAI ............ 3 1.1. Khái niệm về phụ thuộc mạnh .................................................................. 3 1.2. Phương pháp xác định phụ thuộc mạnh trong CSDL ............................... 5 1.3. Phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu ....... 13 1.3.1. Khái niệm về phần tử ngoại lai ....................................................... 13 1.3.2. Các phương pháp xác định phần tử ngoại lai .................................. 14 1.3.3. Mối quan hệ giữa phần tử ngoại lai và khai phá dữ liệu ................. 15 1.4. Mô hình phát hiện phần tử ngoại lai trong dữ liệu và trong cơ sở dữ liệu quan hệ ........................................................................................................... 16 1.4.1. Định nghĩa mô tả ............................................................................. 17 1.4.2. Phân loại các phần tử ngoại lai trong CSDL quan hệ ..................... 18 1.4.3. Mô hình phát hiện phần tử ngoại lai dựa theo luật đối với CSDL quan hệ ............................................................................................................... 18 1.5. Ứng dụng của các phần tử ngoại lai ....................................................... 22 KẾT LUẬN CHƯƠNG 1..................................................................................... 23 CHƯƠNG 2: PHÁT HIỆN PHẦN TỬ NGOẠI LAI ĐỐI VỚI PHỤ THUỘC HÀM MẠNH TRONG CƠ SỞ DỮ LIỆU QUAN HỆ ........................................ 24 2.1. Phần tử ngoại lai đối với các dạng phụ thuộc hàm đặc biệt ................... 24 2.1.1. Phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau .............. 24 vi 2.1.2. Phần tử ngoại lai đối với phụ thuộc hàm dạng tỉ lệ......................... 26 2.2. Phần tử ngoại lai đối với hệ ràng buộc dạng phụ thuộc hàm ................. 28 2.3. Thuật toán phát hiện các phần tử ngoại lai đối với các dạng chuẩn ....... 32 2.3.1. Thuật toán phát hiện phần tử ngoại lai đối với dạng chuẩn 2NF .... 33 2.3.2. Thuật toán phát hiện phần tử ngoại lai đối với dạng chuẩn 3NF .... 34 2.3.3. Thuật toán phát hiện phần tử ngoại lai đối với dạng chuẩn BCNF . 36 2.4. Phần tử ngoại lai đối với phụ thuộc mạnh .............................................. 37 2.4.1. Thuật toán tìm các phụ thuộc hàm mạnh trong quan hệ và SĐQH 38 2.4.2. Xác định phụ thuộc hàm mạnh cực đại đối với một tập thuộc tính 39 2.4.3. Thuật toán tìm phần tử ngoại lai đối với phụ thuộc mạnh trong CSDL quan hệ ...................................................................................................... 42 KẾT LUẬN CHƯƠNG 2..................................................................................... 43 CHƯƠNG 3: ỨNG DỤNG TÌM PHẦN TỬ NGOẠI LAI ................................. 45 3.1. Lựa chọn bài toán để cài đặt ................................................................... 45 3.2. Cài đặt chương trình ............................................................................... 48 3.2.1. Yêu cầu hệ thống ............................................................................. 48 3.2.2. Cấu trúc của chương trình ............................................................... 48 3.3.Chương trình minh họa:........................................................................... 48 3.3.1. Demo 01: ......................................................................................... 48 3.3.2. Demo 02: ......................................................................................... 52 3.3.3. Một số đoạn mã lệnh sử dụng trong chương trình ......................... 56 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................................... 65 TÀI LIỆU THAM KHẢO .................................................................................... 66 vii DANH MỤC HÌNH ẢNH Hình 1.3.1 Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp ...................................... 13 Hình 1.4.3 Sơ đồ phát hiện phần tử ngoại lai dựa theo luật trong CSDL quan hệ ... 21 viii CÁC KÍ HIỆU VIẾT TẮT DÙNG TRONG LUẬN VĂN Kí hiệu Nghĩa CNTT Công nghệ thông tin CSDL Cơ sở dữ liệu PTH Phụ thuộc hàm PTM Phụ thuộc mạnh SĐQH Sơ đồ quan hệ SĐM Sơ đồ mạnh ix MỘT SỐ QUI ƯỚC VỀ KÍ HIỆU THƯỜNG ĐƯỢC SỬ DỤNG TRONG LUẬN VĂN: - Các thuộc tính được kí hiệu bằng các chữ Latin hoa đầu bảng chữ A, B, C,... - Tập thuộc tính được ký hiệu bằng các chữ Latin hoa cuối bảng chữ X, Y, Z,... - XY hoặc X ∪ Y biểu diễn hợp của hai tập X và Y. Phép trừ hai tập X và Y được ký hiệu là X\Y, hoặc X - Y. - Một phân hoạch của tập M (thành các tập con rời nhau và có hợp là M), X1, X2, ..., Xm được ký hiệu là M = X1| X2| ...| Xm Với ý nghĩa M = X1∪ X2∪ ... ∪ Xm và Xi ∩ Xj = ∅, 1≤ i, j≤ m, i ≠ j. - Kí hiệu R, U... để chỉ tập toàn bộ các thuộc tính trong một sơ đồ quan hệ - Các quan hệ (hoặc bảng dữ liệu) được kí hiệu bằng các chữ cái thường: r, p, q,... - Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số t, u, v, t1,... - Với mỗi bộ t trong quan hệ r và mỗi tập con các thuộc tính X ⊆ R ta kí hiệu t[X] hoặc t.X là hạn chế của bộ (ánh xạ) t trên tập thuộc tính X. - Kí hiệu | r | là lực lượng (số bộ) của quan hệ r. - Kí hiệu X ⟶ Y để chị phụ thuộc hàm giữa X và Y  Y để chỉ phụ thuộc mạnh giữa X và Y; hoặc có thể sử - Kí hiệu X  s dụng kí hiệu X ⟶ Y để chỉ phụ thuộc mạnh với lời chú dẫn đi trước. - Kí hiệu X ⟶ 𝜎 Y để chỉ phụ thuộc hàm xấp xỉ mức 𝜎 giữa X và Y - Kí hiệu ⇒ để chỉ sự kéo theo trong mệnh đề logic x BẢNG CÁC HÌNH VẼ DANH MỤC CÁC ĐỊNH NGHĨA, ĐỊNH LÝ, BỔ ĐỀ, THUẬT TOÁN Định nghĩa 1.4.1 Định nghĩa mô tả.................................................................................17 Định nghĩa 2.1.1.1 Phụ thuộc hàm dạng bằng nhau ....................................................... 24 Định nghĩa 2.1.1.2 Phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau ............... 24 Định nghĩa 2.1.2.1 Phụ thuộc hàm dạng tỉ lệ .................................................................. 26 Định nghĩa 2.1.2.2 Phần tử ngoại lai đổi với phụ thuộc hàm dạng tỉ lệ ......................... 27 Định nghĩa 2.1.3.1 Phần tử ngoại lai đối với hệ ràng buộc dạng PTH ........................... 29 Định nghĩa 2.2.1 Phần tử ngoại lai đối với dạng chuẩn .................................................. 32 Định nghĩa 2.2.3 Phụ thuộc mạnh cực đại ...................................................................... 39 Định lý 1.2.1 Tính đúng và đầy đủ của hệ T1-T3. ............................................................ 6 Định lý 1.2.2 Sự tồn tại họ phụ thuộc hàm sinh ra họ phụ thuộc mạnh............................ 9 Định lý 1.2.3 Họ phụ thuộc mạnh. .................................................................................. 12 Bổ đề 1.2.1 Tính bắc cầu hỗn hợp .................................................................................... 8 Bổ đề 1.2.2: ..................................................................................................................... 11 Bổ đề 2.1.3.1 ................................................................................................................... 29 Mệnh đề 1.2.2 Phụ thuộc mạnh của các tập phụ thuộc hàm tương đương. .................... 11 Mệnh đề 2.2.3 Sự tồn tại của phụ thuộc mạnh................................................................ 39 Thuật toán 2.1.1 (phát hiện phần tử ngoại lai đối với PTH dạng bằng nhau) ....... 25 Thuật toán 2.1.2 (phát hiện phần tử ngoại lai đối với phụ thuộc hàm dạng tỉ lệ)......... 27 Thuật toán 2.1.3 (Thuật toán xác định phần tử ngoại lai đối với hệ ràng buộc dạng PTH) . 31 Thuật toán 2.2.1.1 (Thuật toán NL_ 2NF) ........................................................................ 33 Thuật toán 2.2.1.2 (Thuật toán NL_ 3NF) ........................................................................ 34 Thuật toán 2.2.1.3 (Thuật toán NL_ BCNF) .................................................................... 36 Thuật toán 2.2.2 (Tìm các PTM trong SĐQH) ................................................................. 38 Thuật toán 2.2.3.1 (Tìm phụ thuộc mạnh cực đại).......................................................... 40 Thuật toán 2.3.1.2 (Tìm các phụ thuộc mạnh trong quan hệ r) ...................................... 40 1 MỞ ĐẦU Thế kỉ XXI được xem là một kỷ nguyên của công nghệ thông tin. Các công nghệ khám phá trí thức được áp dụng rộng rãi trong nhiều lĩnh vực và đem lại những thành tựu to lớn. Nhưng các công nghệ khám phá tri thức thường nhằm mục đích tìm kiếm, khám phá các dạng và mẫu thường gặp. Chủ yếu tập trung vào các hướng: Tìm kiếm các luật kết hợp, nhận dạng và phân lớp mẫu… Còn lĩnh vực khám phá phần tử ngoại lai chưa có được sự quan tâm, đầu tư và phát triển ở trong nước cũng như ở nước ngoài. Người ta nhận thấy rằng có rất nhiều tri thức còn tiềm ẩn trong dữ liệu, vấn đề đặt ra là làm thế nào để khai thác được thông tin và khai thác một cách có hiệu quả. Còn trong lĩnh vực khám phá phần tử ngoại lai mới bước đầu được sự quan tâm nghiên cứu. Mặc dù nó được ứng dụng trong nhiều lĩnh vực cuộc sống như: Phát hiện những thẻ bất thường trong hệ thống ngân hàng, những tuyến đường bất ổn không hợp lý tong giao thông, ứng dụng trong hệ thống an ninh, dự báo thời tiết, trong thị trường chứng khoán, trong lĩnh vực thể thao,… Tuy nhiên, với số lượng dữ liệu được tập trung và lưu trữ trong cơ sở dữ liệu ngày càng lớn thì việc tìm kiếm các ngoại lai hoặc các phần tử ngoại lai trở nên cấp thiết hơn rất nhiều. Do tính hấp dẫn và tính thời sự của khai phá dữ liệu, đặc biệt là phát hiện phần tử ngoại lai trong cơ sở dữ liệu quan hệ, tôi chọn đề tài: “Nghiên cứu phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ” là luận văn cao học của mình. Trong đó nghiên cứu vận dụng kiến thức nghiên cứu này vào giải quyết bài toán tìm phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ. Đề tài đi sâu nghiên cứu một mảng kỹ thuật khai thác dữ liệu nhằm hỗ trợ cho mục đích sử dụng khác nhau. Có mục đích tìm các nhân tố tích cực, có mục đích tìm các lỗi lưu trữ trong tập dữ liệu, có mục đích tìm kiếm nhận dạng tội phạm, gian lận tài chính hoặc cũng có thể làm dự báo, phân tích thị trường,… Trong phạm vi, ứng dụng rộng rãi em đã nêu ở trên, việc nghiên cứu phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ đã mang ý nghĩa khoa học rất lớn. Luận văn sẽ thực hiện với hi vọng sẽ đóng góp một phần 2 nghiên cứu khoa học nhất định trong việc tổng hợp, đánh giá một nhiệm vụ khai phá dữ liệu quan trọng nhằm phát hiện những tri thức có ý nghĩa lớn, đảo bảo cơ sở toán học trong chuyên ngành khoa học máy tính. Trọng tâm của Luận văn là giải quyết bài toán phát hiện phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ, song bên cạnh đó Luận văn cũng tiến hành nghiên cứu và đề xuất những vấn đề lý thuyết mới về phụ thuộc hàm, các dạng chuẩn của quan hệ cũng như một số thuật toán tìm luật kết hợp, xây dựng cây quyết định dựa trên phụ thuộc hàm. Một số mục tiêu cụ thể của Luận văn được đặt ra là: 1. Xây dựng mô hình phát hiện phần tử ngoại lai dựa theoluật trong CSDL quan hệ, bao gồm: - Xây dựng phương pháp xác định phần tử ngoại lai đối với phụ thuộc hàm và khóa. - Xây dựng phương pháp xác định phần tử ngoại lai đối với hệ ràng buộc dạng phụ thuộc hàm. - Xây dựng phương pháp xác định phần tử ngoại lai đối với các dạng chuẩn. 2. Xây dựng phương pháp xác định phụ thuộc mạnh trong cơ sở dữ liệu quan hệ và xác định phương pháp xác định phần tử ngoại lai đối với phụ thuộc mạnh. 3. Ứng dụng kết quả nghiên cứu vào giải quyết bài toán. Với việc hoàn thành các mục tiêu đã đặt ra, luận văn đã đạt được mộ số kết quả đóng góp một phần trong việc phát triển lý thuyết về phát hiện phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ. Luận văn được bố cục như sau Ngoài phần mở đầu và kết luận luận văn được chia làm 3 chương: + Chương 1: Phụ thuộc mạnh và phần tử ngoại lai. + Chương 2: Phát hiện phần tử ngoại lai đối với phụ thuộc hàm mạnh trong cơ sở dữ liệu quan hệ. + Chương 3: Ứng dụng tìm phần tử ngoại lai đối với phụ thuộc mạnh trong mô hình dữ liệu quan hệ. 3 CHƯƠNG 1 PHỤ THUỘC HÀM MẠNH VÀ PHẦN TỬ NGOẠI LAI Trong nội dung của chương nay trình bày một số lý thuyết và công trình nghiên cứu của các tác giả đi trước làm cơ sở cho nghiên cứu bao gồm: Khái niệm phụ thuộc mạnh, hệ tính chất xác định phụ thuộc mạnh, phương pháp xác định phụ thuộc mạnh trong Cơ sở dữ liệu, phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu. Đồng thời trình bày mô hình phát hiện phần tử ngoại lai trong dữ liệu,trong cơ sở dữ liệu quan hệ và ứng dụng của các phần tử ngoại lai. 1.1. Khái niệm về phụ thuộc mạnh Phụ thuộc mạnh (StrongDependencies) là khái niệm mới được một số tác giả đề xuất và nghiên cứu [2], [11], [17], nó có nhiều ứng dụng quan trọng trong thực tiễn, đặc biệt khi chúng ta cần phân tích mối quan hệ giữa những yếu tố có ảnh hưởng mạnh mang tính quyết định đến nhau. Phụ thuộc mạnh (PTM) liên quan nhiều đến phụ thuộc hàm (PTH) thông thường, và các PTM trên R cũng là các phụ thuộc hàm theo nghĩa thông thường trên R. Tuy nhiên các kết quả về PTM của các tác giả đi trước mới chỉ được đề xuất trong phạm vi họ các PTM trên một tập thuộc tính R. Nội dung dưới đây em trình bày một số kết quả nghiên cứu về mối quan hệ giữa họ S+các PTM và họ F+ các PTH trên R; phương pháp để xác định các họ phụ thuộc mạnh S+ trên một sơ đồ quan hệ cũng như phương pháp xác định các PTM trên một quan hệ, đồng thời em cũng trình bày phương pháp xác định phần tử ngoại lai đối với các phụ thuộc mạnh. Các khái niệm về phụ thuộc mạnh và các kết quả sau có thể tìm thấy trong [2], [11], [17]: Cho R là một tập hữu hạn không rỗng các thuộc tính, r = (t1, t2,...,tm) là một quan hệ trên R và A, B ⊆ R. Ta nói rằng B phụ thuộc mạnh vào A trên r, kí hiệu  B nếu: là A  s r  t1, t2 ∈ r : nếu với mỗi a ∈ A mà t1(a) = t2(a) thì với mọi b ∈ B: t1(b) = t2(b).  B}. Sr được gọi là một họ đầy đủ các phụ thuộc Đặt Sr= {(A,B): A  s r 4  B, với A,B mạnh của r. Một phụ thuộc mạnh trên R là một mệnh đề dạng A  s r ⊆ R.  B đúng trên một quan hệ r nếu A   B. Một phụ thuộc mạnh A  s s  B. Cho R là một tập không Chúng ta cũng nói rằng r thoả phụ thuộc mạnh A  s rỗng hữu hạn các thuộc tính và P(R) là các tập con của R. Cho Y ⊆ P(R) x P(R). Chúng ta nói rằng Y là một họ s trên R nếu và chỉ nếu với mọi A, B, C, D ⊆ R v à a ∈ R, ta có: (S1) ({a}, {a}) ∈ Y, (S2) (A, B) ∈ Y, (B, C) ∈ Y ; B ≠  ⇒ (A, C) ∈ Y, (S3) (A, B) ∈ Y, C ⊆ A , D ⊆ B ⇒ (C, D) ∈ Y, (S4) (A, B) ∈ Y, (C, D) ∈ Y ⇒ (A ∪ C, B ∩ D) ∈ Y, (S5) (A, B) ∈ Y, (C, D) ∈ Y ⇒ (A ∩ C, B ∪ D) ∈ Y. Dễ thấy rằng Sr là một họ s trên R. Nếu Y là một họ s trên R thì sẽ có một quan hệ r để sao cho Y = Sr. Đặt S+ là họ tất cả các PTM mà có thể suy dẫn logic từ s theo các qui tắc ( S 1 ) - (S5). Gọi S+ là bao đóng của S. Gọi cặp (R, S) với R là tập không rỗng các thuộc tính và S là tập các PTM trên R là một sơ đồ mạnh (SĐM) (StrongScheme). Giả sử: G = (R, S) là một SĐM trên R và X ⊆ R khi đó đặt:  a ∈ S+} Xs+ ={a ∈ R | X  s Gọi Xs+ là bao đóng của X trên G.  B ∈ S+ khi và chỉ khi Y ⊆ Xs+ Với X, Y ⊆ R rõ ràng A  s Để thuận tiện ta sẽ kí hiệu X⟶Y để chỉ phụ thuộc hàm thông thường và ký  Y là phụ thuộc mạnh (hoặc có thể viết X⟶Y ∈ S+). hiệu: X  s Trong [2], [11], [17], các tác giả mới chỉ nghiên cứu các tính chất của các PTM trên một sơ đồ mạnh (SĐM) g = (R, S) mà chưa đề cập đến mối quan hệ giữa một tập các phụ thuộc mạnh trên R với tập các phụ thuộc hàm F trên R. Trong nội 5 dung dưới đây, tôi trình bày một số kết quả nghiên cứu về mối quan hệ giữa tập PTM và tập các PTH thông thường trên một tập thuộc tính R. Đồng thời cũng trình bày phương pháp xác định các PTM trên một sơ đồ quan hệ cũng như trên một quan hệ cho trước. 1.2. Phương pháp xác định phụ thuộc mạnh trong CSDL Vì rằng các PTM được sinh ra từ họ các phụ thuộc hàm nào đó trên tập thuộc tính R. Vì vậy trong kết quả nghiên cứu của tôi dưới đây, tôi xét mối quan hệ giữa họ các PTM và họ các PTH thông thường trên một SĐQH.  Y ∈ S+ hoặc kí Ta kí hiệu một phụ thuộc mạnh giữa X, Y ⊆ R là X  s hiệu: X ⟶Y ∈ S+ (với S+ là một tập các phụ thuộc mạnh) là tương đương [1], [2]. * Hệ tính chất xác định phụ thuộc mạnh Giả sử cho (R, F) là một sơ đồ quan hệ. Ta kí hiệu F+ là bao đóng của F, S+ là tập các phụ thuộc mạnh được sinh ra từ F+ theo hệ tính chất sau: T1. Với a ∈ R, Y ⊆ R nếu {a}⟶Y ∈ F+ khi và chỉ khi {a}⟶Y ∈ S+;  C ∈ S+ khi và chi khi A   C và B T2.  A, B, C ⊆ R ta có AB  s s s   C ∈ S+;  C D ∈ S+ khi và chỉ khi A   C ∈ S+ và T3.  A, C, D ⊆ R ta có A  s s  D ∈ S+; A s Tính đúng đắn và đầy đủ của hệ tính chất trên sẽ được chứng minh ở Định lý 1.2.1 dưới đây. Từ hệ các tính chất trên ta cũng sẽ dễ chứng minh các hệ quả sau của họ các phụ thuộc mạnh S+ được sinh ra từ F+ .  Y ∈ S+ khi và chỉ khi  a ∈ X ta có {a}⟶ Y ∈ H1.  X, Y ⊆ R khi đó X  s F H2. S+ ∈ F. Ta chứng minh H1 : Nếu  X, Y ⊆ R, giả sử X= x1x2...xk mà ta có {xi} ⟶ Y ∈ F+ với i =1...k thì theo T1 ta có: {xi} ⟶ Y ∈ S+. Áp dụng k lần T2 đối với các PTM: 6 {xi} ⟶ Y ∈ S+, xi ∈ X, ta có: X⟶ Y ∈ S+. Ngược lại:  X, Y ⊆ R ta có X⟶ Y ∈ S+ giả sử với bất kỳ a ∈ X ta có: X = {a} ∪ X - {a} như vậy {a} ∪ (X - {a}) ⟶ Y ∈ S+ . Theo T2 ta có: {a} ⟶ Y ∈ S+. Theo T1 thì ta có {a} ⟶ Y ∈ F+. Điều phải chứng minh. Chứng minh H2: Giả sử X ⟶ Y ∈ S+. Ta sẽ chứng minh X ⟶ Y ∈ F+. Thật vậy theo Hệ quả H1 đã được chứng minh ở trên thì  a ∈ X ta có {a} ⟶ Y ∈ F+. Do F+ là một họ f trên R do vậy áp dụng nhiều lần tính cộng tính của họ f ta có X ⟶ Y ∈ F+. Suy ra S+ ⊂ F+[1], [2]. Điều phải chứng minh. Định lý 1.2.1 (Tính đúng và đầy đủ của hệ T1-T3). Cho (R, F) là một SĐQH, F+ là bao đóng của F. Tập các phụ thuộc mạnh S+ được sinh ra từ tập F+ theo các tính chất T1-T3 là đúng và đầy đủ. Chứng minh +Ta sẽ chứng minh tính đúng đắn của hệ tính chất T1-T3 Có nghĩa là S+ được sinh ra theo T1 - T3 là một họ s trên R. Tức là nó sẽ thoả mãn các tính chất (S1) - (S5) của một họ s trên R[2]. - Tính chất (S1):  {a} ∈ S+. Điều phải Với mọi a ∈ R ta có {a} ⟶ {a} ∈ F+. Do vậy {a}  s chứng minh. - Tính chất (S2):  B ∈ S+, B   C ∈ S+; B #  ta sẽ chứng minh Giả sử: A  s s A s   C ∈ S+.  B ∈ S+ suy ra  a ∈ A ta có {a}⟶ B ∈ F+ (Theo Thật vậy: từ A  s  C ∈ S+suy ra  b ∈ B ta có {b}⟶ C ∈ F+. H1). Cũng vậy từ B  s Theo tính chất của họ các phụ thuộc hàm thì ta có: {a} ⟶ {b} ∈ F+,  a ∈ A và  b ∈ B {b} ⟶ {b} ∈ F+,  b ∈ B và  c ∈ C 7 Suy ra {a}⟶ {c} ∈ F+ suy ra {a}⟶ C ∈ F+  a ∈ A và  c ∈ C. Theo tính  C ∈ S+. Áp dụng tính chất T2 nhiều lần ta sẽ thu được A chất T1 ta có {a}  s s   C ∈ S+. Điều phải chứng minh. - Tính chất (S3):  B ∈ S+ và C ⊆ A, D ⊆ B, ta sẽ chứng minh C   D ∈ Giả sử từ A  s s S+  B ∈ S+, theo Thật vậy, ta có A = C ∪ (A - C); B = D ∪ (B - D); A  s  B ∈ S+. Theo tính chất T3 ta có A   B ∈ S+. tính chất T2 ta có: C  s s Điều phải chứng minh. - Tính chất (S4):  B ∈ S+, C   D ∈ S+ ta sẽ chứng minh: AC   B ∩ D ∈ Giả sử A  s s s S+  B ∈ S+ suy ra Thật vậy: đặt E = B ∩ D do B = (B - E) ∪ E. Từ A  s  E ∈ S+ (theo T3). A s  D ∈ S+ suy ra C   E ∈ S+ Tương tự do D = (D - E) ∪ E. Từ C  s s  E ∈ S+ hay là: AC   B ∩ D ∈ S+. (theo T3). Theo tính chất T2 ta có: C  s s Điều phải chứng minh. - Tính chất (S5):  B ∈ S+, C   D ∈ S+ ta chứng minh: A ∩ C   BD ∈ Giả sử A  s s s  B ∈ S+ và theo S+. Thật vậy, đặt Q = A ∩ C. Ta có: A = Q ∪ (A - Q) từ A  s  B ∈ S+. Tương tự vì C = Q ∪ (C - Q) và C   D ∈ tính chất T2 suy ra Q  s s  D ∈ S+. Theo tính chất T3 ta có: Q   BD ∈ S+ hay là: A ∩ S+ ta có: Q  s s  BD ∈ S+. C s Như vậy tập S+ thoả mãn các tính chất (S1) - (S5). Do vậy nó là một họ s trên R. 8 + Ta chứng minh tính đầy đủ của S+, có nghĩa là với một phụ thuộc mạnh  Y ∈ F+ ta sẽ chứng minh X   Y ∈ S+. bất kỳ X  s s  Y ∈ F+ là phụ thuộc mạnh nên dễ dàng suy Giả sử X = x1x2...xk. Vì X  s ra các phụ thuộc hàm {Xi}⟶ Y ∈ S+ với i = l…k.  Y ∈ F+ với i = l…k. Vì các phụ thuộc mạnh này Theo T1 ta có (xi}  s  Y ∈ S+. Điều thuộc S+ nên ta có thể áp dụng k lần tính chất T2 và suy ra X  s phải chứng minh. Định lý dưới đây sẽ chỉ ra rằng với một họ các phụ thuộc mạnh cho trước có thể xác định một họ các phụ thuộc hàm sinh ra nó. Trước hết ta xét một bổ đề sau: Bổ đề 1.2.1(Tính bắc cầu hỗn hợp): Giả sử (R, F) là một SĐQH. F+ là bao đóng của F (theo hệ tiên đề Amstrong). S+ là họ các phụ thuộc mạnh sinh ra từ F+ theo hệ tính chất T1 - T3.  Y ∈ S+ và Y   Z ∈ F+ thì ta có X   Z ∈ S+. Khi đó nếu X  s s s Chứng minh Trước hết với một quan hệ r bất kỳ trên (R, F). Chúng ta chứng minh  Z là một phụ thuộc mạnh đúng trên r. Thật vậy, do X   Y là phụ thuộc X s s mạnh nên ta có:  t1 t2 ∈ r: nếu với mỗi a ∈ X mà t1(a) = t2(a) thì  b ∈ Y: t1(b) = t2(b). Do Y ⟶ Z là một phụ thuộc hàm nên ta có:  t1 t2 ∈ r: nếu  b ∈ Y: t1(b) = t2(b) thì suy ra  z ∈ Z: t1(z) = t2(z). Từ đây ta suy ra:  t1 t2 ∈ r: nếu với mỗi a ∈ X mà t1(a) = t2(a) thì  z ∈ Z: t1(z) = t2(z).  Z là một phụ thuộc mạnh Theo định nghĩa phụ thuộc mạnh ta có X  s đúng trên r.  Y ∈ F+,Y   Z ∈ F+. Theo tính chất bắc cầu suy ra: X   Vì X  s Z ∈ F+. s s 9  Z là một phụ thuộc mạnh thuộc F+ nên theo Định lý 1.2.1 suy Do X  s  Z ∈ S+. Bổ đề được chứng minh. ra: X  s Định lý 1.2.2 (Sự tồn tại họ phụ thuộc hàm sinh ra họ phụ thuộc mạnh) Cho R là một tập các thuộc tính, S+là một họ s các phụ thuộc mạnh trên R. Có thể tìm được một họ F+ các phụ thuộc hàm trên R mà S+ sẽ được sinh ra từ F+ theo các tính chất T1-T3. Chứng minh Ta xây dựng một họ các phụ thuộc hàm F+ từ họ S+ theo các qui tắc như sau: Quy tắc 1:  X ⊆ R, A ⊆ X thì X ⟶ A ∈ F+; Quy tắc 2:  ∈ R, Y ⊆ R, nếu {a} ⟶Y ∈ S+ thì {a} ⟶ Y ∈ F+. Quy tắc 3:  X ⟶Y ∈ F+,  Z ⊆ R thì XZ ⟶ YZ ∈ F+; Quy tắc 4:  X, Y, Z ⊆ R mà có X ⟶ Y ∈ F+, và Y ⟶ Z ∈ F+ thì X ⟶ Z ∈ F+. Họ S+ sẽ đóng vai trò như tập phụ thuộc hàm F ban đầu để xây dựng F+. Trước hết ta chứng minh rằng họ F+ được sinh ra từ họ phụ thuộc mạnh S+ theo các qui tắc 1, quy tắc 4 như trên là một họ f trên R. (Khái niệm về họ f trên R được trình bày trong [1], [2], [5], [6]). Thật vậy: Với mọi A, B, C, D ⊆ R ta có: - Do A ⊆ A nên A⟶A ∈ F+ theo Qui tắc 1 - Giả sử có A⟶ B ∈ F+, và C⟶ D ∈ F+ thì A ⟶ C ∈ F+ theo Qui tắc 4 - Giả sử có A⟶B ∈ F+, A ⊆ C, D ⊆ B ta có do A ⊆ C nên C⟶ A ∈ F+ (Qui tắc 1). Theo Qui tắc 4 (bắc cầu) thì C⟶ B ∈ F+. Do D ⊆ B nên B⟶D ∈ F+. (Qui tắc 1), kết hợp với C⟶B ∈ F+ ta có G⟶D ∈ F+. (Qui tắc 4). - Giả sử A⟶ B ∈ F+, C⟶D ∈ F+. Áp dụng Qui tắc 3 với A⟶C ∈ F+ ta có AC⟶ BC ∈ F+; với C⟶ D ∈ F+ ta có BC⟶ BD ∈ F+. Theo Qui tắc 4 (bắc cầu), suy ra AC⟶ BD ∈ F+. 10 Như vậy F+ là một họ f trên R (Theo [2], [5]). Bây giờ chúng ta sẽ chứng minh rằng S+ cũng thoả các tính chất T1 - T3 với F+ được xây dựng như trên. - Tính chất T1 : Giả sử với a ∈ R, Y ⊆ R à {a}⟶Y ∈ S+ khi đó theo qui tắc 2 thì {a}⟶Y ∈ F+. Ngược lại, giả sử a ∈ R, Y ⊆ R nếu {a}⟶Y ∈ F+ (giả sử Y ≠ {a} vì nếu Y = {a) thì hiển nhiên (a)⟶Y ∈ S+ theo tính chất của họ s). Ta sẽ chứng minh rằng (a)⟶ Y ∈ S+. Thật vậy, F+ là một họ f trên R nên suy ra  y ∈ Y ta có {a}⟶{y} ∈ F+. Do mọi phụ thuộc hàm thuộc F+ được suy dẫn theo các qui tắc 1, 2, 3, 4 theo cách xây dựng trên {a}⟶{y} ∈ F+ chỉ có thể được suy dẫn từ qui tắc 2 hoặc qui tắc 4. + Nếu nó được suy dẫn từ Qui tắc 2 thì hiển nhiên {a}⟶{y} ∈ S+ . + Nếu nó được suy dẫn từ Qui tắc 4, thì sẽ phải có một phụ thuộc mạnh dạng{a}⟶{z} ∈ S+ (cũng đồng thời thuộc F+) và một phụ thuộc hàm {z}⟶{y} ∈ F+ để {a}⟶{y} ∈ F+ với z là một thuộc tính nào đó thuộc R. Theo Bổ đề 2.1 thì {a}⟶{y} ∈ S+. Từ đó  y ∈ Y ta có{a}⟶{y} ∈ S+. Theo tính chất (S5) của họ s, ta dễ dàng suy ra {a}⟶Y ∈ S+. Điều phải chứng minh. - Tính chất T2: Giả sử có A, B, C ⊆ R mà AB⟶C ∈ S+. do A ⊆ AB, theo tính chất S3 của họ PTM ta có: A ⟶ C ∈ S+. Tương tự ta có B ⟶ C ∈ S+. Ngược lại, nếu có A ⟶ C ∈ S+ và B ⟶ C ∈ S+ thì theo tính chất S4 của họ PTM ta có AB ⟶ C ∈ S+. Điều phải chứng minh. - Tính chất T3: Giả sử với A, C, D ⊆ R mà A⟶ CD ∈ S+. Do C ⊆ CD, theo tính chất S3 của họ PTM ta có A⟶ C ∈ S+. Tương tự A⟶ D ∈ S+. Ngược lại nếu A⟶ C ∈ S+ và A⟶ D ∈ S+ thì theo tính chất S5 của họ PTM ta có A⟶ CD ∈ S+. Ta được điều phải chứng minh.