Luận văn Ứng dụng phép dịch chuyển lược đồ quan hệ trong cơ sở dữ liệu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ___________________________________ VŨ TR Í DŨNG ỨNG DỤNG PHÉP DỊCH CHUYỂN LƯỢC ĐỒ QUAN HỆ TRONG CƠ SỞ DỮ LIỆU LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ____________________________ VŨ TRÍ DŨNG ỨNG DỤNG PHÉP DỊCH CHUYỂN LƯỢC ĐỒ QUAN HỆ TRONG CƠ SỞ DỮ LIỆU CHUYÊN NGÀNH : KHOA HỌC MÁY TÍNH MÃ SỐ : 60 48 35 01 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học PGS. TSKH. NGUYỄN XUÂN HUY T hái Nguyê n - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC LỜI NÓI ĐẦU 1 CHƢƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI VÀ CÁC KHÁI NIỆM CƠ SỞ 4 1.1. TỔNG QUAN VỀ ĐỀ TÀI 4 1.1.1. Giới thiệu đề tài. 4 1.1.2. Nội dung của đề tài, các vấn đề cần giải quyết. 4 1.1.3. Phƣơng pháp nghiên cứu. 5 1.1.4. Phạm vi ứng dụng. 5 1.1.5. Kết quả đạt đƣợc. 5 1.2. CÁC KHÁI NIỆM CƠ SỞ 6 1.2.1. Quan hệ, thuộc tính, bộ. 7 1.2.2. Đại số quan hệ. 10 1.2.3. Phụ thuộc hàm, Hệ tiên đề Armstrong, Lƣợc đồ quan hệ. 13 1.2.4. Bao đóng của tập thuộc tính. 18 1.2.5. Phủ của tập phụ thuộc hàm 21 1.2.6. Khóa của lƣợc đồ quan hệ. 27 1.2.7. Chuẩn hoá LĐQH trên cơ sở phụ thuộc hàm. 31 CHƢƠNG 2. PHÉP DỊCH CHUYỂN LƢỢC ĐỒ QUAN HỆ 36 2.1. Phép dịch chuyển LĐQH. 37 2.2. Thuật toán dịch chuyển LĐQH. 38 2.3. Định lý cơ bản của phép dịch chuyển LĐQH. 39 2.4. Dạng biểu diễn thứ nhất của khóa 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.5. Dạng biểu diễn thứ hai của khóa 45 2.6. Kết luận 50 CHƢƠNG 3. CÀI ĐẶT CHƢƠNG TRÌNH 51 3.1. Giới thiệu. 51 3.2. Các chức năng của chƣơng trình. 51 3.3. Một số giao diện của chƣơng trình. 52 3.4. Các thí dụ. 54 DANH MỤC BÀI BÁO, CÔNG TRÌNH NCKH 57 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 58 TÀI LIỆU THAM KHẢO 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT 1NF 1 st normal form - dạng chuẩn 1 2NF 2 nd normal form - dạng chuẩn 2 3NF 3 rd normal form - dạng chuẩn 3 CSDL Cơ sở dữ liệu LĐQH Lƣợc đồ quan hệ PTH phụ thuộc hàm FD phụ thuộc hàm ╞ suy dẫn theo tiên đề (theo logic) ├ suy dẫn theo quan hệ  khác  với mọi  thuộc  là con  chứa  giao (của 2 tập thuộc tính)  hợp (của 2 tập thuộc tính) X + bao đóng của tập thuộc tính X  tƣơng đƣơng ≢ không tƣơng đƣơng \ phép trừ logic Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 1 LỜI NÓI ĐẦU Trong quản lý các cơ sở dữ liệu (CSDL), phụ thuộc dữ liệu được hiểu là những mệnh đề mô tả các ràng buộc mà dữ liệu phải đáp ứng trong thực tế. Nhờ có những mô tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu có thể quản lý tốt được chất lượng dữ liệu. Lý thuyết về các phụ thuộc dữ liệu đóng vai trò quan trọng trong việc mô tả thế giới thực, phản ánh ngữ nghĩa dữ liệu trong cơ sở dữ liệu. Phụ thuộc dữ liệu được Codd, tác giả của mô hình dữ liệu quan hệ đặt nền móng từ những năm 70 với khái niệm phụ thuộc hàm. Sau đó một loạt tác giả khác tiếp tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ cũng như xây dựng các hệ tiên đề cho các lớp phụ thuộc - tức là đặt cơ sở lý thuyết về phụ thuộc dữ liệu. Một điều khá tự nhiên là ngay từ những ngày đầu phát triển lý thuyết thiết kế cơ sở dữ liệu, logic đã được chọn như một ngôn ngữ hữu hiệu để đặc tả phụ thuộc dữ liệu, do đó, trong số các loại hình phụ thuộc dữ liệu rất đa dạng được đề xuất và phát triển sau này, các phụ thuộc logic luôn luôn là trọng tâm chú ý của các nhóm nghiên cứu. Đề tài này tập trung vào tìm hiểu và nghiên cứu khái niệm chuyển dịch lược đồ quan hệ, đưa chúng về dạng thu gọn và nhận được các biểu diễn quan trọng cho bao đóng, khóa và phản khoá. Các kết quả thu được sử dụng trong quá trình thiết kế các cơ sở dữ liệu. Nội dung đề tài được cấu trúc như sau: Chương 1 giới thiệu về đề tài và các khái niệm chung về mô hình quan hệ với trọng tâm là các khái niệm hình thức của mô hình quan hệ, trong đó vận dụng chủ yếu các cấu trúc rời rạc. Phụ thuộc hàm (PTH) là lớp phụ thuộc đầu tiên của phụ thuộc logic và đồng thời cũng là lớp phụ thuộc kinh điển theo nghĩa, được Codd, tác giả của mô hình dữ liệu quan hệ, đề xuất sớm nhất và được sử dụng như một công cụ thiết kế các cơ sở dữ liệu chuẩn hóa. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 2 Chương 2 trình bày một kỹ thuật thu gọn lược đồ quan hệ (LĐQH) được gọi là phép dịch chuyển lược đồ quan hệ. Bản chất của kỹ thuật này là loại bỏ khỏi LĐQH ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm ảnh hưởng đến kết quả tính toán các đối tượng đang được quan tâm như bao đóng, khóa, phản khóa... Mặc dù LĐQH thu được qua phép dịch chuyển không tương đương với LĐQH ban đầu, nhưng ta có thể thu được các đối tượng cần tìm bằng những phép toán đơn giản như loại bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi loại bỏ một số thuộc tính thì một số PTH sẽ được loại bỏ theo vì chúng trở thành các PTH tầm thường (có vế trái chứa về phải) hoặc mang thông tin tiền định (đó là các PTH dạng   X). Các phép dịch chuyển LĐQH được phát triển cho lớp các phụ thuộc logic đầu tiên là phụ thuộc hàm cho ta một số kết quả lý thú về biểu diễn bao đóng, khóa, phản khóa cùng một số dấu hiệu cần và đủ để nhận biết các đặc trưng tương quan giữa các đối tượng nói trên. Chương 3 cài đặt chương trình mô phỏng ứng dụng phép dịch chuyển lược đồ quan hệ vào thiết kế cơ sở dữ liệu cùng với một số thí dụ. Phần cuối của luận văn là kết luận và hướng phát triển và các tài liệu tham khảo. Em xin bày tỏ lòng chân thành cảm ơn PGS TSKH Nguyễn Xuân Huy - người Thầy đã tận tình hướng dẫn, giúp đỡ em hoàn thành luận văn này. Em xin chân thành cảm ơn Khoa Công nghệ thông tin - Đại học Thái Ngyên đã tạo điều kiện về tinh thần cũng như cơ sở vật chất để em được học tập, nâng cao kiến thức và thực hiện luận văn tốt nghiệp. Em xin chân thành cảm ơn các Thầy, Cô giáo ở Viện Công nghệ thông tin - Viện Khoa học và Công nghệ Việt Nam, các Thầy, Cô giáo ở Khoa Công nghệ thông tin - Đại học Thái Nguyên đã nhiệt tình giảng dạy, hướng dẫn và cung cấp cho em những kiến thức vô cùng quí báu, để em có điều kiện nâng cao kiến thức và hiểu biết của mình trong lĩnh vực công nghệ thông tin. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 3 Em cũng xin chân thành cảm ơn Ban lãnh đạo Liên đoàn Lao động tỉnh Hà Nam, Ban giám hiệu Trường trung cấp nghề Kinh tế - Kỹ thuật Hà Nam, gia đình, người thân và bạn bè đã tạo điều kiện thuận lợi, động viên và giúp đỡ em trong suốt thời gian học tập, nghiên cứu và làm luận văn tốt nghiệp. Học viên Vũ Trí Dũng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 4 CHƯƠNG 1 TỔNG QUAN VỀ ĐỀ TÀI VÀ CÁC KHÁI NIỆM CƠ SỞ 1.1. TỔNG QUAN VỀ ĐỀ TÀI 1.1.1. Giới thiệu đề tài Trong quản lý các cơ sở dữ liệu lớn và phức tạp đòi hỏi nhiều thuật toán hữu hiệu để tính toán các đối tượng như bao đóng, khóa, phủ... Một số thuật toán tốt theo nghĩa độ phức tạp tính toán giới hạn ở các hàm tuyến tính hoặc đa thức theo chiều dài dữ liệu vào đã được công bố như thuật toán tính bao đóng của tập thuộc tính, thuật toán tìm một khóa, thuật toán xác định thành viên hay thuật toán xác định phụ thuộc hàm suy dẫn, thuật toán tìm giao các khóa, thuật toán xác định một lược đồ quan hệ có một khóa duy nhất… [1, 2, 8]. Một nhận xét tự nhiên là nếu kích thước của lược đồ quan hệ càng nhỏ thì các thuật toán càng phát huy hiệu quả hơn. Một số hướng nghiên cứu tinh giản các lược đồ cơ sở dữ liệu được thực hiện thông qua các phép biến đổi tương đương, chẳng hạn đưa tập phụ thuộc hàm về dạng thu gọn hoặc thu gọn tự nhiên, dạng không dư, dạng tối ưu (chứa ít ký hiệu nhất)… đã được công bố [3, 5, 6, 7]. Trong phép dịch chuyển lược đồ quan hệ. Bản chất của kỹ thuật này là loại bỏ khỏi lược đồ quan hệ ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm ảnh hưởng đến kết quả tính toán các đối tượng đang quan tâm như bao đóng, khóa,... Mặc dù lược đồ quan hệ thu được qua phép thu gọn không tương đương với lược đồ quan hệ ban đầu, nhưng ta có thể thu được các đối tượng cần tìm bằng những phép toán đơn giản như loại bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi loại bỏ một số thuộc tính thì một số phụ thuộc hàm sẽ được loại bỏ theo, vì chúng trở thành các phụ thuộc hàm tầm thường (có vế trái chứa về phải) hoặc mang thông tin tiền định (đó là các phụ thuộc hàm dạng   X). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 5 1.1.2. Nội dung của đề tài, các vấn đề cần giải quyết Luận văn tập trung tìm hiểu và cải tiến các kỹ thuật và thuật toán thu gọn lược đồ quan hệ p thông qua phép dịch chuyển lược đồ quan hệ theo một tập thuộc tính X. Khảo sát sự phụ thuộc của phép dịch chuyển thông qua các tính chất của tập thuộc tính X. Khảo sát hai dạng biểu diễn khóa của lược đồ quan hệ qua phép dịch chuyển. Xây dựng một hệ trình minh họa và đánh giá các kết quả lý thuyết. 1.1.3. Phương pháp nghiên cứu 1. Tiếp cận chủ yếu để giải quyết các vấn đề đặt ra trong phạm vi đề tài là tiên đề hóa. Các hệ tiên đề được xây dựng trên cơ sở một hệ suy dẫn hình thức với các tính chất cơ bản về các đối tượng cơ sở và các mối liên hệ giữa chúng. Cơ sở toán học của các hệ tiên đề là định lý về tính xác đáng và đầy đủ cùng với các định lý về điều kiện cần và đủ cho các hệ tiên đề tương đương. 2. Tiếp cận hình thức vận dụng chủ yếu các phương pháp và các cấu trúc của toán học rời rạc (bao gồm cả logic hình thức), kết hợp với các phương pháp đối sánh, mô hình hóa, tối ưu và quy hoạch rời rạc. 3. Kết hợp chặt chẽ giữa lý thuyết và thực hành, sử dụng và phát triển các phần mềm nói chung và các phần mềm toán học nói riêng để kiểm định và thể hiện các kết quả lý thuyết. 1.1.4. Phạm vi ứng dụng Các kết quả thu được có thể vận dụng cho các quy trình thiết kế các cơ sở dữ liệu quan hệ dùng trong các hệ thống thông tin, cụ thể là: - Tính bao đóng của các tập thuộc tính, - Tìm khóa của các lược đồ quan hệ. - Chuẩn hoá LĐQH Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 6 1.1.5. Kết quả đạt được Về lý thuyết, luận văn tập trung vào các kết quả sau đây: - Khái niệm về phép dịch chuyển lược đồ quan hệ, - Phát biểu và chứng minh công thức tính bao đóng qua phép dịch chuyển lược đồ quan hệ, - Phát biểu và chứng minh kết quả về dạng biểu diễn khóa thứ nhất, - Phát biểu và chứng minh kết quả về dạng biểu diễn khóa thứ hai, - Phân tích thuật toán tìm khóa, phát triển thuật toán tìm tất cả các khoá Về thực hành luận văn sẽ cài đặt các kết quả lý thuyết dưới dạng chương trình bao gồm các chức năng sau:  Nạp và cập nhật dữ liệu: thuộc tính và các phụ thuộc hàm.  Tính bao đóng  Tìm các khóa của lược đồ quan hệ.  Chuẩn hoá LĐQH 1.2. CÁC KHÁI NIỆM CƠ SỞ Trong các mô hình dữ liệu thì mô hình dữ liệu quan hệ được sử dụng rộng rãi hơn cả do tính trực quan, kiến trúc đơn giản và có cơ sở toán học chặt chẽ. Ngoài ra, người ta đã chứng minh được sự tương đương và cung cấp các phép chuyển đổi giữa mô hình dữ liệu quan hệ với mô hình mạng và phân cấp. Một cách giải thích rất trực quan cho mô hình dữ liệu quan hệ là các dữ liệu của bài toán quản lý được tổ chức theo hàng và cột, cột biểu thị thuộc tính thông tin cần quản lý của một đối tượng, thuộc tính này còn gọi là tiêu đề cột và các giá trị trong cột đó có cùng một kiểu. Tập hợp tất cả các giá trị thuộc tính trên một hàng (gọi là bộ) là dữ liệu về một đối tượng đang quản lý. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 7 Mục này trình bày một số khái niệm mở đầu về mô hình quan hệ. Trọng tâm được tập trung vào các khái niệm hình thức của mô hình quan hệ, trong đó vận dụng chủ yếu các cấu trúc rời rạc. Phần đầu tiên của mục này giới thiệu định nghĩa về quan hệ, thuộc tính và bộ. Phần thứ hai giới thiệu về đại số quan hệ như một ngôn ngữ truy nhập dữ liệu trong các cơ sở dữ liệu quan hệ. Phần thứ ba mô tả phụ thuộc hàm như một công cụ toán học trợ giúp cho việc biểu đạt ngữ nghĩa dữ liệu và đảm bảo tính nhất quán của dữ liệu trong cơ sở dữ liệu, phụ thuộc hàm là lớp phụ thuộc đầu tiên của phụ thuộc logic và đồng thời cũng là lớp phụ thuộc kinh điển theo nghĩa, được Codd, tác giả của mô hình dữ liệu quan hệ đề xuất sớm nhất và được sử dụng như một công cụ thiết kế các cơ sở dữ liệu chuẩn hóa. Các tính chất của phụ thuộc hàm và các hệ tiên đề cho phụ thuộc hàm được mô tả đầy đủ, trong đó hệ tiên đề Armstrong được sử dụng nhiều hơn cả. Một trong những khái niệm quan trọng của phụ thuộc hàm là bao đóng của tập thuộc tính và các tính chất cơ bản của phép toán lấy bao đóng được trình bày trong phần thứ tư của mục này. Phần thứ năm giới thiệu các loại phủ quan trọng nhất, đóng vai trò thu gọn các tập phụ thuộc hàm, tạo thuận tiện cho tối ưu hóa các thao tác ngữ nghĩa. Hai khái niệm chủ chốt liên quan đến phụ thuộc hàm là khóa và các dạng chuẩn của lược đồ quan hệ được trình bày trong hai phần cuối, phần thứ sáu và thứ bảy của mục. 1.2.1. Quan hệ, thuộc tính, bộ Địn h n g h ĩ a Cho tập hữu hạn U = {A1, A2 , ... , An} khác rỗng (n 1). Các phần tử của U được gọi là thuộc tính. Ứng với mỗi thuộc tính AiU, i = 1,2,...,n có một tập chứa ít nhất hai phần tử dom(Ai) được gọi là miền trị của thuộc tính Ai. Gọi D là hợp của các dom(Ai), i = 1,2,...,n. Một quan hệ R với các thuộc tính U, ký hiệu là R(U), là một tập các ánh xạ t: UD sao cho với mỗi AiU ta có t(Ai)dom(Ai). Mỗi ánh xạ được gọi là một bộ của quan hệ R. Mỗi quan hệ R(U) có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính, mỗi dòng là một bộ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 8 Ta ký hiệu t(U) là một bộ trên tập thuộc tính U. Một quan hệ rỗng, ký hiệu , là quan hệ không chứa bộ nào. Vì mỗi quan hệ là một tập các bộ nên trong quan hệ không có hai bộ trùng lặp. Các ký hiệu và một số quy ước Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các quy định sau đây: 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,... Các phần tử trong một tập thường được liệt kê như một xâu ký tự, không có các ký hiệu biểu diễn tập, chẳng hạn ta viết X = ABC thay vì viết X = A, B, C. XY biểu diễn hợp của hai tập X và Y, X 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. Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số, thí dụ t, u, v, t1 ... Với mỗi bộ t trong quan hệ R(U) và mỗi tập con các thuộc tính X  U 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. Ta chấp nhận quy ước tự nhiên là miền trị của mọi thuộc tính chứa ít nhất hai phần tử. Trong trường hợp một miền trị của thuộc tính chỉ chứa một giá trị duy nhất thì ta có thể loại bỏ cột tương ứng của thuộc tính đó trong quan hệ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 9 Ta chấp nhận quy ước sau đây: Mọi cặp bộ t và v trong mọi quan hệ giống nhau trên miền rỗng các thuộc tính, t. = v..  Hàm Attr(R) cho tập thuộc tính của quan hệ R.  Hàm Card(R) cho lực lượng (số bộ) của quan hệ R. Trong trường hợp tập thuộc tính U đã cho trước ta có thể viết đơn giản R thay cho R(U). Ký hiệu REL(U) là tập toàn thể các quan hệ trên tập thuộc tính U, REL_p(U) là tập toàn thể các quan hệ có không qúa p bộ trên tập thuộc tính U, p  1. Hai quan hệ R và S được gọi là tương thích nếu chúng có cùng một tập thuộc tính, tức là nếu Attr(R) = Attr(S). Với mỗi bộ t trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký hiệu tv là phép dán hai bộ t và v. tv cho ta bộ r trên tập thuộc tính UV thoả điều kiện: r.U = t và r.V = v. Với mỗi bộ t trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu tS là phép dán bộ t với quan hệ S. tS cho ta quan hệ P(UV) = { tv | vS }. Th í d ụ Cho U = ABC, V = BD, t(U) = (a,b,c), v(V) = (b,d). Ta có r(UV) = t * v = (a,b,c,d) là một bộ trên tập thuộc tính UV = ABCD. Cho thêm quan hệ S(BD) Khi đó t*S cho ta quan hệ P(ABCD) sau đây S (B D) b d x d b e P (A B C D) a b c d a b c e Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 10 1.2.2. Đại số quan hệ Đại số quan hệ được xây dựng trên tập các quan hệ với các phép toán cơ sở là chọn, chiếu, kết nối tự nhiên, chia, hợp, giao và trừ. Mục này sử dụng các ký pháp theo tài liệu [7]. Phép chọn (phép lọc) Địn h n g h ĩ a Cho quan hệ R(U) và biểu thức điều kiện (còn gọi là biểu thức lọc hay biểu thức chọn) e. Phép chọn trên quan hệ R theo điều kiện e, ký hiệu R(e) cho ta quan hệ: P(U) = R(e) = { t  R | Sat(t, e) } trong đó hàm logic Sat(t, e) kiểm tra bộ t thoả điều kiện e được xác định theo hai bước sau: 1) Thay mọi xuất hiện của mỗi thuộc tính A trong biểu thức chọn e bằng trị tương ứng của A trong bộ t, t.A, ta thu được một mệnh đề logic b. 2) Tính trị của b. Nếu là đúng (True) thì bộ t thoả điều kiện e; ngược lại, nếu trị của b là sai (False) thì bộ t không thoả điều kiện e. Trong các biểu thức chọn ta sử dụng ký hiệu cho các phép toán logic như sau: Hội: Tuyển: Phủ định: ¬, Kéo theo:  Phép chiếu Địn h n g h ĩ a Phép chiếu quan hệ R(U) trên tập con thuộc tính X  U, ký hiệu R[X], cho ta quan hệ P(X) = R[X] = { t.X | tR } R[X] được tính theo 2 bước như sau: (i) Xoá các cột không thuộc X của bảng R, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 11 (ii) Lược bớt các dòng giống nhau trong bảng kết quả: chỉ giữ lại một dòng trong số các dòng giống nhau. Phép kết nối tự nhiên Địn h n g h ĩ a 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ệ chứ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 Descartes, trong đó mỗi bộ của quan hệ R sẽ được ghép với mọi bộ của quan hệ S. Phép cộng (hợp) Địn h n g h ĩ a Phép hợp (theo lý thuyết tập hợp hoặc nối dọc) hai quan hệ tương thích R(U) và S(U), ký hiệu RS, hoặc R+S, cho ta quan hệ chứa các bộ của mỗi quan hệ thành phần, P(U) = R S = { t | tR  tS } Phép trừ Địn h n g h ĩ a Phép trừ (theo lý thuyết tập hợp hoặc lấy phần riêng) hai quan hệ tương thích R(U) và S(U), ký hiệu R\S, hoặc R-S, cho ta quan hệ chứa các bộ của quan hệ R không có trong quan hệ S, P(U) = R \ S = { t | tR, t S } Phép giao Địn h n g h ĩ a Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 12 Phép giao (theo lý thuyết tập hợp hoặc lấy phần chung) hai quan hệ tương thích R(U) và S(U), ký hiệu RS, hoặc R&S cho ta quan hệ chứa các bộ xuất hiện đồng thời trong cả hai quan hệ thành phần, P(U) = R S ={ t | tR, tS } Các phép toán hợp, trừ và giao đựơc gọi là các phép toán tập hợp trên các quan hệ (tương thích). Phép chia Địn h n g h ĩ a Cho hai quan hệ R(U) và S(V) thỏa V  U. Đặt M = U\V. Phép chia quan hệ R cho quan hệ S, ký hiệu R:S, cho ta quan hệ P(M) = R : S = { t.M | t R, (t.M)*S R } Thứ tự thực hiện các phép toán quan hệ Trong một biểu thức quan hệ các phép toán một ngôi có độ ưu tiên cao hơn (do đó được thực hiện sớm hơn) các phép toán hai ngôi. Tiếp đến là nhóm các phép toán kết nối, giao và chia, cuối cùng là nhóm các phép toán cộng và trừ. Thứ tự ưu tiên từ cao đến thấp của các phép toán quan hệ được liệt kê như sau: ( ) , [ ]  ,  , :  , \ Dãy các phép toán cùng thứ tự ưu tiên được thực hiện lần lượt từ trái qua phải. Nếu biểu thức quan hệ có chứa các cặp ngoặc (*) thì các biểu thức con trong các cặp ngoặc được thực hiện trước. Một số hàm tiện ích SumR, A: cho tổng các giá trị số trong thuộc tính cột A của quan hệ R. AvgR, A: cho trung bình cộng các giá trị trong thuộc tính cột A của quan hệ R. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 13 MaxR, A: cho giá trị lớn nhất trong thuộc tính cột A của quan hệ R. MinR, A: cho giá trị nhỏ nhất trong thuộc tính cột A của quan hệ R. Nếu trong biểu thức quan hệ có chứa các hàm tiện ích thì các hàm này được thực hiện sớm nhất trong ngữ cảnh cho phép. Th í d ụ Biểu thức quan hệ P = SR(A > Avg(S,A))[AB] sẽ được thực hiện theo trật tự sau đây: 1. Tính hàm c = Avg(S,A) 2. Thực hiện phép chọn P1 = R(A > c) 3. Thực hiện phép chiếu P2 = P1[AB] 4. Thực hiện phép kết nối P = S*P2. 1.2.3. Phụ thuộc hàm, hệ tiên đề Armstrong, lược đồ quan hệ Phụ thuộc hàm Địn h n g h ĩ a Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là biểu thức dạng f: XY ; X,Y  U Nếu f: XY là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y. X là vế trái và Y là vế phải của PTH f. Ta cũng dùng hai toán tử LS(f) và RS(f) để xác định vế trái và vế phải của PTH f, cụ thể là nếu f:XY thì LS(f) = X, RS(f)=Y. Cho quan hệ R(U) và một PTH f: XY trên U. Ta nói quan hệ R thoả PTH f và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống nhau trên Y, R(XY)  (u,v  R): (u.X = v.X)  (u.Y = v.Y) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 14 Ta dùng ký hiệu X ↛ Y với ý nghĩa tập thuộc tính Y không phụ thuộc hàm vào tập thuộc tính X. Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH F, và viết R(F), nếu R thoả mọi PTH trong F, R(F)  ( f  F): R(f) Nếu quan hệ R thỏa PTH f ta cũng nói PTH f đúng trong quan hệ R. Th í d ụ Cho quan hệ R(A, B, C, D) như sau và các PTH f1: AA, f2: AB, f3: ACC, f4: AD, f5: DA, f6: AC. Khi đó các PTH f1 - f5 đúng trong R, mặt khác, R không thỏa PTH f6. Cho trước tập PTH F trên tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ trên U thoả tập PTH F, SAT_p(F), p  1 là tập toàn thể các quan hệ có không quá p bộ trên U và thoả tập PTH F , cụ thể là SAT(F) = { R | RREL(U), R(F) } SAT_p(F) = { R | RREL_p(U), R(F) } Cho tập  các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng trong mọi quan hệ của . Hệ tiên đề Armstrong Bao đóng của tập PTH Địn h n g h ĩ a R(A B C D) a 1 x 2 a 1 y 2 b 2 x 1 b 2 y 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 15 Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F+ là tập nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1-F3 của hệ tiên đề Armstrong A o sau đây: X, Y, Z  U: F1. Tính phản xạ: Nếu X  Y thì XY  F + F2. Tính gia tăng: Nếu XY  F + thì XZYZ  F + F3. Tính bắc cầu: Nếu XY  F + và YZ  F + thì XZ  F + C h ú ý Các PTH có vế trái chứa vế phải như mô tả trong F1 được gọi là tầm thường. Các PTH tầm thường đúng trong mọi quan hệ. Ngoài ra, các quan hệ trên tập thuộc tính U có không quá một bộ thỏa mọi PTH trên U. Suy dẫn theo tiên đề (suy dẫn logic) Địn h n g h ĩ a Ta nói PTH f được suy dẫn theo tiên đề (hoặc suy dẫn logic) từ tập PTH F và ký hiệu là F╞ f, nếu f  F +. F╞ f  f  F + Nói cách khác PTH f được suy dẫn theo tiên đề từ tập PTH F nếu xuất phát từ F, áp dụng các luật F1, F2 và F3 của hệ tiên đề Armstrong Ao sau hữu hạn lần ta sẽ thu được PTH f. Suy dẫn theo quan hệ Địn h n g h ĩ a Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH f được suy dẫn theo quan hệ từ tập PTH F và viết F├ f, nếu mọi quan hệ R(U) thoả F thì R cũng thoả f. F├ f  SAT(F)  SAT(f) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 16 Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F* là tập các PTH f trên U được suy dẫn theo quan hệ từ tập PTH F F * = { f: XY | X,Y  U, F├ f } Địn h l ý (Tính đủ và xác đáng của hệ tiên đề Armstrong) F + = F * Nói cách khác, suy dẫn theo quan hệ và suy dẫn theo logic là một, tức là F╞ f  F├ f Suy dẫn theo quan hệ có không quá p bộ Địn h n g h ĩ a Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH f được suy dẫn theo quan hệ có không quá p bộ từ tập PTH F và viết F ├p f, nếu mọi quan hệ R trong REL_p(U) thoả F thì R cũng thoả f. F├p f  SAT_p(F)  SAT_p(f) Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F' là tập các PTH f trên U được suy dẫn theo quan hệ có không quá hai bộ từ tập PTH F F' = { f: XY | X,Y  U, F├2 f } Địn h l ý (Định lý tương đương) F + = F * = F' Nói cách khác, đối với phụ thuộc hàm, ba loại suy dẫn sau là tương đương (i) Suy dẫn logic: F╞ f , (ii) Suy dẫn theo quan hệ: F├ f , và (iii) Suy dẫn theo quan hệ có không quá hai bộ: F├2 f. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 17 Một số tính chất của PTH Cho tập thuộc tính U và các tập phụ thuộc hàm F, G trên U, tập một số quan hệ  trên U, các quan hệ R và S trên U. Dễ dàng chứng minh các tính chất sau đây: 1. Nếu F  G thì SAT(F)  SAT(G) 2. SAT(FG) = SAT(F)  SAT(G) 3. FD(RS)  FD(R)  FD(S) 4. R  S  FD(R)  FD(S) 5. F  FD(SAT(F)) 6.   SAT(FD()) 7. SAT(FD(SAT(F))) = SAT(F) 8. FD(SAT(FD())) = FD() Th í d ụ Chứng tỏ FD(RS)  FD(R )  FD(S). Ta chọn U = AB; quan hệ R(U) chứa một bộ duy nhất u = (a,x); quan hệ S(U) chứa một bộ duy nhất v = (a,y), x y. R và S thỏa mọi PTH trên U. Quan hệ P = R S chứa 2 bộ u và v. P không thỏa PTH AB. Một số tính chất mở rộng của PTH Sử dụng ba tiên đề Armstrong ta dễ dàng chứng minh các tính chất F4 -F11 sau đây. Một số tính chất được chia nhỏ nhằm mục đích mô tả các hệ tiên đề khác cho PTH trong các mục tiếp theo.  X, Y, Z, V  U,  A  U: F4. Tính tựa bắc cầu: XY, YZV  XZV F5. Tính phản xạ chặt: X X F6. Mở rộng vế trái và thu hẹp vế phải: XY  XZY\V F7. Cộng tính đầy đủ: XY, ZV  XZYV F8. Mở rộng vế trái: XY  XZY Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 18 F9. Cộng tính ở vế phải: XY, XZ  XYZ F10. Bộ phận ở vế phải: XYZ  XY F11.Tính tích luỹ: XYZ, ZAV  XYZA Lược đồ quan hệ Địn h n g h ĩ a Lược đồ quan hệ (LĐQH) là một cặp a = (U,F), trong đó U là tập hữu hạn các thuộc tính, F là tập các ràng buộc trên các miền trị (dữ liệu) của các thuộc tính trong U. Trong chương này chúng ta chỉ xét một loại ràng buộc là PTH và một số biến thể của PTH. Theo quy ước trên, trong chương này, chúng ta hiểu lược đồ quan hệ (LĐQH) là một cặp a = (U,F), trong đó U là tập hữu hạn các thuộc tính, F là tập các PTH trên U. Quy ước Trong trường hợp không chỉ rõ tập F, ta xem LĐQH chỉ là một tập hữu hạn các thuộc tính U. Các hệ tiên đề khác cho PTH Các hệ tiên đề cho PTH sau đây tương đương với hệ tiên đề Armstrong Ao [7] B o = {F5, F10, F11} S o = {F1, F4} D o = {F3, F5, F6, F7} M o = {F4, F5, F8} 1.2.4. Bao đóng của tập thuộc tính Địn h n g h ĩ a Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 19 X + = {A U | X  AF+} Thuật toán tìm bao đóng của một tập thuộc tính Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Để xác định bao đóng X+ của tập thuộc tính X ta xây dựng dãy bao nhau X (0)  X(1)  …  X(i) như sau  Xuất phát: Đặt X(0)=X,  Với i > 0, ta đặt  )( )()1( iXL FRL ii RXX      Nếu X(i+1) = X(i) thì dừng thuật toán và cho kết quả X + = X(i) . Algorithm Closure Format: Closure(X,F) Input: - Tập PTH F trên U - Tập con thuộc tính X của U Output: - Y = X+ = {A U | XA F+} Method Y:=X; repeat Z:=Y; for each FD LR in F do if L  Y then Y:=YR; endif; endfor; until Y=Z; return Y; end Closure. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 20 Thuật toán trên có độ phức tạp O(mn2 ), trong đó n là số lượng thuộc tính trong U, m là số lượng PTH trong tập F. Quy ước giản lược Ta thường viết XY thay vì viết XYF+ hoặc F╞ XY. Bài toán thành viên Cho tập thuộc tính U, một tập các PTH F trên U và một PTH f: XY trên U. Hỏi rằng f F+ (f có phải là thành viên của F+) hay không ? Địn h l ý (Định lý thành viên) XY  F + khi và chỉ khi Y  X + Thuật toán cho bài toán thành viên Algorithm IsMember Format: IsMember(f,F) Input: - Tập PTH F trên U - PTH f trên U Output: - True, nếu f F+; - False, trong trường hợp phủ định. Method IsMember := (RS(f)  Closure(LS(f),F)); end IsMember. Một số tính chất của bao đóng Cho LĐQH a = (U,F). Khi đó  X, Y  U ta có (C1) Tính phản xạ: X  X + (C2) Tính đồng biến: X  Y X + Y + (C3) Tính lũy đẳng: (X +)+ = X + Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 21 Ngoài ra, sử dụng ba tính chất (C1), (C2) và (C3) nói trên ta dễ dàng chứng minh các tính chất (C4)-(C8) sau đây: (C4) (XY) +  X +Y + (C5) (X + Y) + = (XY + ) + = ( XY) + (C6) XY khi và chỉ khi Y+ X+ (C7) XX+ và X+X (C8) X + = Y + khi và chỉ khi XY và YX 1.2.5. Phủ của tập PTH Địn h n g h ĩ a Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn ra được G, ký hiệu F╞ G, nếu gG: F╞ g. Ta nói F tương đương với G, ký hiệu F  G, nếu F╞ G và G╞ F. Nếu F  G ta nói G là một phủ của F. Ký hiệu F ≢ G có nghĩa F và G không tương đương. Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký hiệu XF + trong trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập PTH F. Phủ thu gọn tự nhiên Địn h n g h ĩ a Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ thu gọn tự nhiên của F nếu 1. G là một phủ của F, và 2. G có dạng thu gọn tự nhiên theo nghĩa sau: 2a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau.) f  G: LS(f)  RS(f) =  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 22 2b. Các vế trái của mọi PTH trong G khác nhau đôi một. f, g  G: f  g  LS(f)  LS(g) Thuật toán tìm phủ thu gọn tự nhiên Algorithm Natural_Reduced Format: Natural_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn tự nhiên G của F (i) G  F     (ii)LR  G: L R =      (iii)LiRi,LjRjG: ij  LiLj Method G:=; for each FD LR in F do Z:=R\L; if Z then if there is an FD LY in G then replace LY in G by LYZ else add LZ to G; endif; endif; endfor; return G; end Natural_Reduced. Nếu dùng kỹ thuật chỉ dẫn để tổ chức truy nhập trực tiếp tới các thuộc tính và PTH thì thuật toán thu gọn tự nhiên Natural_Reduced đòi hỏi độ phức tạp tính toán là O(mn) trong đó m là số lượng PTH trong tập F, n là số lượng thuộc tính trong U. Để ý rằng mn là chiều dài dữ liệu vào của thuật toán, do đó O(mn) chính là độ phức tạp tuyến tính theo chiều dài dữ liệu vào. Ta dễ dàng chứng minh tính đúng của mệnh đề sau, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 23 Mệnh đ ề Nếu F và G là hai tập PTH trên cùng một tập thuộc tính U thì F  G khi và chỉ khi X  U: XF + = XG + Phủ không dư Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ không dư của F nếu (i) G là một phủ của F, và (ii) G có dạng không dư theo nghĩa sau: gG: G \{g} ≢ G Thuật toán tìm phủ không dư của tập PTH Algorithm Nonredundant Format: Nonredundant(F) Input: - Tập PTH F Output: - Một phủ không dư G của F (i) G  F (ii) g  G: G\{g} ≢ G Method G:=F; for each FD g in F do if IsMember(g,G\{g})then G:=G\{g}; endif; endfor; return G; end Nonredundant. Phủ thu gọn Phủ thu gọn trái Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 24 Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn trái của F nếu (i) G là một phủ của F, và (ii) (LRG,AL): G\{LR}{L\AR} ≢ G Thuật toán tìm phủ thu gọn trái của tập PTH Để ý rằng AL ta có L\A L, nên g: LRG,AL): G\{g}{L\AR}╞ LR, do đó ta chỉ cần kiểm tra G ╞ L\AR ? Algorithm Left_Reduced Format: Left_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn trái G của F (i) G  F (ii) g:LR G,AL: G\{g}{L\AR}≢G Method G:= F; for each FD g:L  R in F do X:=L; for each attribute A in X do if IsMember(L\AR,G)then delete A from L in G; endif; endfor; endfor; return G; end Left_Reduced. Phủ thu gọn phải Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 25 Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn phải của F nếu (i) G là một phủ của F, và (ii) (LRG, AR): G\{LR}{LR\A} ≢ G Thuật toán tìm phủ thu gọn phải của tập PTH Để ý rằng, AR: R\A R, nên (g: LRG,AR): G╞ LR\A do đó ta chỉ cần kiểm tra G\{LR}{LR\A}╞ LA. Algorithm Right_Reduced Format: Right_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn phải G của F (i) G  F (ii)(g:LR G,AR): G\{g}{LR\A}≢G Method G:= F; for each FD g:L  R in F do H:=G\{LR}; X:=R; for each attribute A in X do if A in Closure(L,H{LR\A})then delete A from R in G; endif; endfor; endfor; return G; end Right_Reduced. Phủ thu gọn Địn h n g h ĩ a Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 26 Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ thu gọn của F nếu G đồng thời là phủ thu gọn trái và thu gọn phải của F. Thuật toán tìm phủ thu gọn của tập PTH Algorithm Reduced Format: Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method return Right_Reduced(Left_Reduced(F)); end Reduced. Phủ tối tiểu Địn h n g h ĩ a Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ tối tiểu của F nếu (i) G là một phủ thu gọn của F, (ii) Vế phải của mọi PTH trong G chỉ chứa một thuộc tính. Thuật toán tìm phủ tối tiểu của tập PTH Algorithm MinCover Format: MinCover(F) Input: - Tập PTH F Output: - Một phủ tối tiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH có // vế phải chỉ chứa một thuộc tính LA, A  R G:=; for each FD LR in F do for each attribute A in R\L do if LA not_in G then Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 27 add LA to G; endif; endfor; endfor; G:=Nonredundant(Left_Reduced(G)); return G; end MinCover. 1.2.6. Khóa của lược đồ quan hệ Khóa của lược đồ quan hệ Địn h n g h ĩ a Cho LĐQH a = (U, F). Tập thuộc tính K  U được gọi là khoá của LĐQH a nếu (i) K + = U (ii) A K: (K \A)+ U Hai điều kiện trên tương đương với (i') KU (ii') A K: K\A ↛ U Nếu K thoả điều kiện (i) (hoặc (i')) thì K được gọi là một siêu khoá. Thuộc tính A  U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở) nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH a = (U, F). Ta ký hiệu UK là tập các thuộc tính khóa của a và U0 là tập các thuộc tính không khóa của a. Dễ thấy UK |Uo là một phân hoạch của U. C h ú ý Trong một số tàì liệu thuật ngữ khoá được dùng theo nghĩa siêu khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 28 Thuật toán tìm một khóa của LĐQH Tư tưởng: Xuất phát từ một siêu khóa K tùy ý của LĐQH, duyệt lần lượt các thuộc tính A của K, nếu bất biến (K\A)+ = U được bảo toàn thì loại A khỏi K. Có thể thay kiểm tra (K\A)+ = U bằng kiểm tra A (K\A)+. Algorithm Key Format: Key(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Khóa K  U thỏa (i) K+ = U     (ii)AK: (K\A)+ U Method K:= U; for each attribute A in U do if A in Closure(K\A,F) then K:=K\A endif; endfor; return K; end Key. Thuật toán duyệt n thuộc tính, với mỗi thuộc tính thực hiện phép lấy bao đóng với độ phức tạp n2m. Tổng hợp lại, độ phức tạp tính toán của thuật toán là O(n3m). Một số tính chất của khóa Các tính chất đơn giản Cho LĐQH (U,F). Khi đó 1. K  U là một khoá khi và chỉ khi U phụ thuộc đầy đủ vào K. 2. Hai khoá khác nhau của một LĐQH không bao nhau. 3. Mọi LĐQH đều có ít nhất một khoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 29 Địn h l ý ( Đặc trưng của các thuộc tính khóa [7]) Cho K là một khóa của LĐQH a = (U,F). Khi đó với mọi tập con X của K ta có: X + K=X. Chứn g m i n h Vì X  X+ và X  K nên X  X+K. Ta cần chứng minh X+K  X. Giả sử AX+K và AX. Ta xét tập M = K\A. Dễ thấy X  M. Ta có, theo tính chất đồng biến của bao đóng, AX+  M+. Từ đây suy ra K  M+, do đó, theo tính chất lũy đẳng của bao đóng và tính chất khóa của K ta có, U = K+  M++ = M+, tức là M là bộ phận thực sự của khóa K lại đồng thời là siêu khóa, trái với định nghĩa khóa. Vậy A X ■ Địn h l ý (Công thức tính giao các khóa) Cho LĐQH a = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi UI là giao các khóa của a. Khi đó có thể xác định giao các khóa bằng một thuật toán tuyến tính theo mn qua công thức  FRL I LRUU   )\(\ Chứn g m i n h Trước hết để ý rằng các PTH LR và L(R\L) là tương đương, do đó ta có thể giả thiết rằng mọi PTH trong F đều có dạng LR, LR = , tức là giả thiết rằng tập PTH F được cho dưới dạng thu gọn tự nhiên. Do giả thiết này ta có R\L=R. Dễ nhận thấy, theo công thức tính UI trong định lý, UI là tập các thuộc tính không có mặt trong vế phải của mọi PTH trong F, do đó chúng phải có mặt trong mọi khóa. Giả sử A là một thuộc tính có trong vế phải của PTH LAR' nào đó của F. Ta chứng minh A sẽ không xuất hiện trong một khóa K nào đấy của a. Thật vậy, xét tập X = U\A. Dễ thấy X  L và X+ = XAR' = U và do đó X là siêu khóa. Từ siêu khóa X không chứa A ta lấy ra được một khóa K không chứa A ■ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 30 Thuật toán xác định giao các khóa trong LĐQH Algorithm KeyIntersec Format: KeyIntersec(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Giao các khóa  FRL LRUM   )\(\ Method M:=U; for each FD LR in F do M:= M\(R\L); endfor; return M; end KeyIntersec. Theo thuật toán trên, để tính giao các khóa ta cần thực hiện m lần lặp ứng với số lượng PTH trong tập F. Trong mỗi lần lặp, phép toán trên tập hợp n phần tử có độ phức tạp O(n) do đó độ phức tạp của thuật toán tính giao các khóa, KeyIntersec là O(mn). Tích mn chính là chiều dài của biểu diễn LĐQH a = (U,F) tức là chiều dài của dữ liệu vào trong thuật toán. Địn h l ý (Định lý về khóa duy nhất, Hồ Thuần, Lê Văn Bào) Cho LĐQH a = (U,F). Gọi UI là giao của các khóa trong a. Khi đó a có một khóa duy nhất khi và chỉ khi UI + = U. Chứn g m i n h Nếu UI + = U thì UI là siêu khóa. Vì UI là giao của các khóa đồng thời lại là siêu khóa nên a không thể còn khóa nào khác ngoài UI. Ngược lại, nếu a chỉ có một khóa duy nhất K thì giao của các khóa đương nhiên là UI = K, và do đó, theo tính chất của khóa UI + = K + = U ■ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 31 Th í d ụ Cho LĐQH a = (U, F), U = ABCDE, F = {ABC, ADB, BD}. Ta có, giao của các khóa là UI = ABCDE\BCD = AE. UI + = (AE) + = AE  U nên a có hơn một khóa. Vì UI là giao các khóa nên ta có thể bổ sung cho UI một số thuộc tính để thu được các khóa. Dễ xác định được a có hai khóa là K1 = ABE và K2= ADE. Ta còn có, tập các thuộc tính khóa là UK = ABDE, tập các thuộc tính không khóa là Uo = C. 1.2.7. Chuẩn hóa LĐQH trên cơ sở PTH Phép tách Địn h n g h ĩ a Cho lược đồ quan hệ a = (U,F). Một phép tách lược đồ a là một họ các tập con của U,  = (X1, X2,...,Xk) thỏa tính chất UX i k i  1  Phép tách  = (X1, X2,...,Xk) trên lược đồ a được gọi là không tổn thất (hoặc không mất thông tin) đối với tập PTH F nếu  R(U)  SAT(F): R[X1]  R[X2]  ...  R[Xk] = R Ngược lại, nếu không tồn tại đẳng thức thì ta gọi  là phép tách tổn thất. Kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng Algorithm Lossless_Join_Testing Input - LĐQH p = (U,F) - Phép tách  = (X1, X2,...,Xk) Output  True, nếu  là một phép tách không tổn thất  False, ngoài ra. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 32 Method 1. Khởi trị: Lập bảng T với các cột là các thuộc tính trong U và k dòng, mỗi dòng ứng với một thành phần của Xi trong : Dòng i chứa các ký hiệu phân biệt (KHPB) aj ứng với các thuộc tính Aj trong Xi và các ký hiệu không phân biệt (KHKPB) bij ứng với các thuộc tính Aj trong U-Xi . Chú ý rằng mọi KHPB trong cột j của T là giống nhau và bằng aj còn mọi KHKPB trong bảng T lúc đầu là khác nhau. 2. Sửa bảng: Lặp đến khi bảng T không còn thay đổi: Vận dụng các F-luật để biến đổi bảng như sau: Với mỗi PTH L  R trong F, nếu trong bảng T có chứa hai dòng u và v giống nhau trên L thì sửa các ký hiệu của chúng cho giống nhau trên mọi cột A R trong bảng T như sau: a. nếu u.A = v.A: không sửa, b. nếu một trong hai ký hiệu u.A hoặc v.A là KHPB thì sửa mọi xuất hiện trong bảng của KHKPB thành KHPB đó, c. nếu cả hai ký hiệu u.A và v.A đều là KHKPB thì sửa mọi xuất hiện trong bảng của ký hiệu có chỉ số thứ nhất lớn hơn thành ký hiệu thứ hai. 3. Kết luận: Gọi bảng kết quả là T*. Nếu T* chứa một dòng toàn KHPB thì return True nếu không return False. end Lossless_Join_Testing. Th í d ụ a) Dùng kỹ thuật bảng để kiểm tra tính kết nối không tổn thất của phép tách trong LĐQH p = (U,F), U = ABCD, F = { A  B, AC  D },  = (AB, ACD). T  T* 1. A 2. B 3. C 4. D 1. AB a1 a2 b13 b14 2. ACD a1 b22 / a2 a3 a4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 33 Vì T* chứa dòng thứ hai gồm toàn ký hiệu phân biệt nên phép tách đã cho là không tổn thất. b) Dùng kỹ thuật bảng để kiểm tra tính kết nối không tổn thất của phép tách trong LĐQH p = (U,F), U = ABCDE, F = { A  C, B  C, C  D, DE  C, CE  A },  = (AD, AB, BE, CDE). T  T* 1. A 2. B 3. C 4. D 5. E 1. AD a1 b12 b13 / a3 a4 b15 2. AB a1 a2 b23 / b13 / a3 b24 / a4 b25 3. BE b31 a2 b33 / b13 / a3 b34 / a4 a5 4. CDE b41 / b31 b42 a3 a4 a5 Vì T* không chứa dòng nào gồm toàn ký hiệu phân biệt nên phép tách đã cho là tổn thất. Tính chất của phép tách Mệnh đ ề Cho LĐQH a = (U, F). Nếu X  Y thì phép tách (XY, U\(Y\X)) là không tổn thất. Các dạng chuẩn Địn h n g h ĩ a LĐQH p = (U,F) được gọi là lược đồ a) dạng chuẩn 1 (1NF) nếu mọi thuộc tính trong U đều không phải là thuộc tính phức hợp, b) dạng chuẩn 2 (2NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều phụ thuộc đầy đủ vào mọi khoá,  A  Uo ,  K  Key(p) : K + A c) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều phụ thuộc trực tiếp vào mọi khoá, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 34  A  Uo ,  K  Key(p) : K * A d) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi PTH không tầm thường XA, A là thuộc tính không khóa đều cho ta X là một siêu khoá,  (X  A, A  Uo – X )  X + = U e) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi thuộc tính đều phụ thuộc trực tiếp vào mọi khoá,  A  U ,  K  Key(p) : K * A f) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi PTH không tầm thường XY đều cho ta X là một siêu khóa.  (X  Y, Y – X   )  X + = U Sơ đồ tương quan giữa các dạng chuẩn BCNF  3NF  2NF Thuật toán chuẩn hoá 3NF không tổn thất và bảo toàn PTH Algorithm 3NF Function: Chuẩn hóa 3NF không tổn thất và bảo toàn PTH. Input: LĐQH p = (U,F) Output: Các LĐQH 3NF (U1,K1),(U2,K2),...,(Us ,Ks) thoả RREL(U): R[U1]R[U2]...R[Us] = R K1, K2,..., Ks - khoá của các lược đồ tương ứng F  i=1..s(F+[Ui]) Method 1. Tìm một phủ tối tiểu của F: G = {K1  A1,K2  A2,..., Km  Am} 2. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1  X1, K2  X2,..., Ks  Xs}. 3. // Xét phép tách  = (K1X1,...,KsXs). Nếu  // chứa một siêu khóa nào đó // của p thì return {(K1X1,K1),...,( KsXs,Ks)} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 35 // nếu không return {(K1X1,K1),...,(KsXs,Ks), // (K,K)} với K là một khóa của p. construct  = (K1X1,K2X2,...,KsXs); for each component V = KiXi in  do if V+ = U then // V = KiXi là siêu khóa return {(K1X1,K1),...,(KsXs,Ks)}; endif; endfor; K = Key(U,F); return {(K1X1,K1),...,(KsXs,Ks),(K,K)}; End 3NF. Th í d ụ Xác định và giải thích dạng chuẩn cao nhất của LĐQH sau: a = (U, F), U = ABCD, F = { A  C, D  B, C  ABD } LĐQH a có 2 khoá là A và C vì A+ = C+ = ABCD = U. Tập thuộc tính khoá là Uk = AC, tập thuộc tính không khoá là Uo = BD. Ta có, DB, B là thuộc tính không khóa và D không phải là một siêu khóa do đó a không ở 3NF và đương nhiên không ở BCNF. Vì hai khoá A và C đều chỉ có một thuộc tính nên các thuộc tính không khoá khác là B và D đều phụ thuộc đầy đủ vào hai khoá này. Vậy a ở 2NF. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 36 CHƯƠNG 2 PHÉP DỊCH CHUYỂN LƯỢC ĐỒ QUAN HỆ Quản lý các cơ sở dữ liệu lớn và phức tạp đòi hỏi nhiều thuật toán hữu hiệu để tính toán các đối tượng như bao đóng, khóa, phủ... Một số thuật toán tốt theo nghĩa độ phức tạp tính toán giới hạn ở các hàm tuyến tính hoặc đa thức theo chiều dài dữ liệu vào đã được công bố như thuật toán tính bao đóng của tập thuộc tính, thuật toán tìm một khóa, thuật toán xác định thành viên hay thuật toán xác định phụ thuộc hàm suy dẫn, thuật toán tìm giao các khóa, thuật toán xác định một lược đồ quan hệ có một khóa duy nhất.... [1, 2, 8]. Một nhận xét tự nhiên là nếu kích thước của LĐQH càng nhỏ thì các thuật toán càng phát huy hiệu quả hơn. Một số hướng nghiên cứu tinh giản các lược đồ cơ sở dữ liệu được thực hiện thông qua các phép biến đổi tương đương, chẳng hạn đưa tập PTH về dạng thu gọn hoặc thu gọn tự nhiên, dạng không dư, dạng tối ưu (chứa ít ký hiệu nhất)... đã được công bố [3, 5, 6, 7]. Trong phép dịch chuyển lược đồ quan hệ [7]. Bản chất của kỹ thuật này là loại bỏ khỏi LĐQH ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm ảnh hưởng đến kết quả tính toán các đối tượng đang quan tâm như bao đóng, khóa, phản khóa... Mặc dù LĐQH thu được qua phép dịch chuyển không tương đương với LĐQH ban đầu, nhưng ta có thể thu được các đối tượng cần tìm bằng những phép toán đơn giản như loại bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi loại bỏ một số thuộc tính thì một số PTH sẽ được loại bỏ theo, vì chúng trở thành các PTH tầm thường (có vế trái chứa về phải) hoặc mang thông tin tiền định (đó là các phụ thuộc hàm dạng   X). Th í d ụ Cho LĐQH a = (U,F) với tập thuộc tính U = ABCDEH và tập PTH F = {AE  D, BC E, E  BC}. Để tìm tập khóa Key(a) của lược đồ a chúng ta xây dựng một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 37 lược đồ b bằng cách xóa khỏi lược đồ a các thuộc tính A, D và H. Ta thu được lược đồ b = (V,G) trong đó V= U\ADH = BCE, G = {E  Ø, BC  E, E  BC}. Tiếp đến ta loại PTH tầm thường E  Ø khỏi G. Ta thu được G = {BC  E, E  BC}. Ta dễ dàng tìm được hai khóa của lược đồ b, Key(b) = {BC, E}. Để thu được Key(a) ta chỉ việc thêm tập thuộc tính AH (không thêm D) vào mỗi khóa của lược đồ b. Vậy Key(a) = {AHBC, AHE}. Dù F đã là tập PTH tối ưu [7] nhưng G còn chứa ít ký hiệu hơn F. 2.1. Phép dịch chuyển LĐQH Địn h n g h ĩ a Cho hai LĐQH a = (U,F), b = (V,G) và tập thuộc tính M  U. Ta nói LĐQH b nhận được từ LĐQH a qua phép dịch chuyển theo tập thuộc tính M, nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính của M trong lược đồ a thì thu được lược đồ b. Nếu sau khi thực hiện phép dịch chuyển theo M cho LĐQH a ta thu được LĐQH b thì ta viết b = a\M Thao tác loại bỏ M được thực hiện trên lược đồ a = (U,F) để thu được lược đồ b=(V,G) như sau: 1. Tính V = U\M có độ phức tạp O(n) với n là số lượng thuộc tính trong U. 2. Với mỗi PTH X  Y trong F ta tạo một PTH X\M  Y\M cho G. Thủ tục này được ký hiệu là G = F\M. Tính F\M đòi hỏi độ phức tạp O(mn) với m là số lượng PTH trong F. Như vậy b = a\M = (U\M,F\M) được thực hiện với độ phức tạp O(mn), tức là tuyến tính theo chiều dài dữ liệu vào (LĐQH a). Sau khi thực hiện thủ tục G = F\M nếu  G chứa các PTH tầm thường (dạng X  Y, X  Y) thì ta loại các PTH này khỏi G, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 38  G chứa các PTH trùng lặp thì ta lược bớt các PTH này. Th í d ụ Cho LĐQH a = (U,F), U = ABCDEH, F = {AE  D, A  DH, BC  E, E  BC}. Với M = ADH, hãy xác định b = (V,G) = a\M. Ta có V= U\ADH = ABCDEH\ADH=BCE, G = {E  Ø (loại),    (loại), BC  E, E  BC} ≡ {BC  E, E  BC}. Ta cũng dễ nhận thấy phép dịch chuyển thỏa tính hợp thành, cụ thể là nếu a là LĐQH trên tập thuộc tính U và X, Y là hai tập con của U thì a\(XY) = (a\X)\Y Trong trường hợp X và Y là hai tập con rời nhau của U ta có a\XY = (a\X)\Y = (a\Y)\X 2.2. Thuật toán dịch chuyển LĐQH Thuật toán Translation dưới đây mô tả phép dịch chuyển một LĐQH với độ phức tạp O(mn). Algorithm Translation Format: Translation(a,M) Input: - LĐQH a = (U,F) - Tập thuộc tính M  U Output: - LĐQH b = (V,G) = a\M, V = U\M, G = F\M. Method V := U\M; G := ; for each FD L  R in F do G := G  {L\M  R\M}; endfor; G := Natural_Reduced(G); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 39 return (V,G); end Translation. Thủ tục Natural_Reduced(G) đưa tập PTH G về dạng thu gọn tự nhiên bằng cách loại khỏi G những PTH tầm thường (có vế trái chứa vế phải), chuyển đổi mỗi PTH về dạng PTH có hai vế trái và phải rời nhau và gộp các PTH có cùng vế trái. Định lý sau đây thiết lập công thức biểu diễn bao đóng của tập thuộc tính theo phép dịch chuyển LĐQH. 2.3. Định lý cơ bản của phép dịch chuyển LĐQH Địn h l ý (Công thức biểu diễn bao đóng theo phép dịch chuyển LĐQH [7]) Cho LĐQH a = (U,F) và hai tập con không giao nhau X và Y trong U. Khi đó (XY) + F = XY + F\X Chứn g m i n h Đặt V = U\X và G = F\X và để ý rằng do X  Y = Ø và X không xuất hiện trong V và G nên theo định nghĩa bao đóng của tập thuộc tính ta có X  Y+G = Ø. Ta chứng minh bằng quy nạp theo số bước xây dựng các dãy (XY)(h) và Y(h), h = 0,1,… theo thuật toán tính bao đóng của các tập thuộc tính XY và Y tương ứng với các tập PTH F và G. Cụ thể là ta chứng minh bất biến (XY) (h) = XY (h) , h = 0,1,… Cơ sở: h = 0. Ta có (XY)(0) = XY và Y(0) = Y, do đó (XY)(0) = XY(0) = XY. Quy nạp: Giả sử với h ≥ 0 ta có (XY)(h) = XY(h). Ta cần chứng minh (XY) (h+1) = XY (h+1) . Ta sẽ chỉ ra rằng khi chuyển từ bước h sang bước h+1 hai tập (XY)(h) và XY(h) sẽ được bổ sung thêm cùng một số thuộc tính. Trước hết để ý rằng do X  Y =  và X không có mặt trong LĐQH b = a \ X = (V, G) nên với mọi h = 0,1,2,... ta luôn có X  Y(h) = . Ngoài ra, do dãy (XY)(h) đơn điệu không giảm và (XY)(0) = XY  X nên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 40 với mọi h = 0,1,2,... ta luôn có (XY)(h)  X. Từ các nhận xét này và từ giả thiết quy nạp (XY)(h) = XY(h) ta suy ra L  U: L  (XY)(h) = XY(h)  L\X  Y(h) và Z  U\X: Z  Y(h)  XZ  XY(h) = (XY)(h) Giả sử PTH L  R  F thỏa tính chất L  (XY)(h). Khi đó L\X  R\X  G và L\X  Y(h). Từ (XY)(h) = XY(h) ta suy ra R(XY)(h) = RXY(h) = (R\X) XY(h). Ngược lại, giả sử Z  P  G và Z  Y(h). Theo định nghĩa của phép dịch chuyển theo X, trong F, tồn tại một PTH L  R để Z = L\X và P = R\X. Khi đó ta có L  XZ  XY(h) = (XY)(h) và do đó R(XY)(h) = RXY(h) = (R\X)XY(h) = PXY(h) ■ Để ý rằng với mọi tập X, ta có X = X và X   = . Từ nhận xét này ta suy ra hệ quả sau, Hệ q ủ a (Công thức tính bao đóng cho một tập thuộc tính) Cho LĐQH a = (U,F) và tập X  U. Khi đó X+F = X() + F\X. Th í d ụ Cho LĐQH a = (U,F), U = ABCDEH, F = {AE  D, BC  E, E  BC}. Tính 1. (AHE) + và 2. E + ? Ta có, theo hệ quả về công thức tính bao đóng cho một tập thuộc tính 1. (AHE) + F = AHE() + F\AHE G = F\AHE = {  D, BC   (loại),   BC} ≡ {  BCD}. Từ đây ta tính được ()+G =BCD. Do đó (AHE) + = AHEBCD = U. 2. E + = E()+F\E. G = F\E = {A  D, BC   (loại),   BC} ≡ {A D,   BC}. Từ đây ta tính được ()+G =BC. Do đó E + = EBC. Cho LĐQH a = (U,F), ta nhắc lại các ký hiệu sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 41  Uo là tập các thuộc tính không khóa, hay phi nguyên thủy, tức là thuộc tính không xuất hiện trong bất kỳ khóa nào của a,  UK là tập các thuộc tính khóa, hay nguyên thủy, tức là thuộc tính có trong một khóa nào đó của a (hợp của các khóa),  UI là tập các thuộc tính có trong mọi khóa, tức là giao của các khóa của a. Rõ ràng, UI  UK. Ta cũng đã biết phân hoạch U = Uo | UK và  K  Key(a),  X  Uo  (K  UK )  (K  X = K  Uo = ) Ngoài ra,  X, Y  U: X  Y =   X \ Y = X Để ý rằng nếu M là siêu khóa của LĐQH a = (U,F) thì  Z  Uo ta có M\Z cũng là siêu khóa của a. Nói cách khác từ một siêu khóa bất kỳ bỏ đi một số thuộc tính không khóa ta vẫn thu được siêu khóa. Bổ đ ề (Bổ đề về siêu khóa trong phép dịch chuyển LĐQH) Cho hai LĐQH a = (U,F), b = (V,G) và X  U. Biết b = a\X. Khi đó (i) Nếu M là siêu khóa của a thì M\X là siêu khóa của b. (ii) Nếu Z là siêu khóa của b thì XZ là siêu khóa của a. Nói riêng, nếu X  Uo và Z là siêu khóa của b thì Z là siêu khóa của a. Chứn g m i n h (i) Giả sử M là siêu khóa của a. Đặt P = M\X, ta có X  P =  và M  XP. Vì M là siêu khóa của a, vận dụng tính đồng biến của bao đóng và công thức biểu diễn bao đóng ta có, U = XV = M+F  (XP) + F = XP + F\X . Từ các đẳng thức XV = XP + F\X, X  V =  và X  P + F\X =  ta suy ra P + F\X = V. Vậy P = M\X là siêu khóa của b. (ii) Đảo lại, giả sử Z là siêu khóa của b = a\X. Khi đó Z  X =  và Z+G = V. Đặt M = XZ, ta có M + F = (XZ) + F = XZ + F\X = XZ + G = XV = U. Vậy XZ là siêu khóa của Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 42 a. Nếu X  Uo thì ta có thể loại bỏ khỏi XZ bộ phận thuộc tính không khóa X để thu được Z là siêu khóa của a ■ Hệ q ủ a (Hệ quả về siêu khóa trong phép dịch chuyển LĐQH) Cho LĐQH a = (U,F) và tập thuộc tính X  U. Khi đó nếu Z là siêu khóa của lược đồ a\X + thì XZ là siêu khóa của lược đồ a. Chứn g m i n h Đặt b = a \ X+. Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH, nếu Z là siêu khóa của b thì X+Z là siêu khóa của a, ta có (X+Z)+ = U. Theo tính chất C5 của bao đóng của tập thuộc tính, (X+Z)+ = (XZ)+ = U. Từ đây suy ra XZ là siêu khóa của a ■ C h ú ý Để ý rằng hệ quả trên không hoàn toàn tương tự như bổ đề về siêu khóa trong phép dịch chuyển LĐQH. Điểm khác nhau chính là lượng dịch chuyển trong bổ đề về siêu khóa là X, trong hệ quả này là bao đóng của X, X +  X. (Bổ đề về khóa trong phép dịch chuyển LĐQH) Cho hai LĐQH a = (U,F), b = (V,G) và tập thuộc tính X  Uo. Biết b = a\X. Khi đó Key(a) = Key(b) Chứn g m i n h Giả sử K  Key(a). Khi đó nói riêng K là siêu khóa của a. Do K  UK, X  Uo, UK  Uo =  nên theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH, K = K\X là siêu khóa của b. Giả sử K chứa một siêu khóa M của b. Khi đó lại theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH ta có M là siêu khóa của a. Do K là khóa của a, M là siêu khóa của a chứa trong K, nên theo tính chất tối tiểu của khóa ta phải có M = K. Vậy K là khóa của b. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 43 Đảo lại, Nếu K là khóa của b thì K  X =  và theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH ta có K là siêu khóa của a. Gỉa sử K chứa một siêu khóa M của a. Khi đó ta có M  K và do đó M  X = . Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH ta có M = M\X là siêu khóa của b. Do K là khóa của b và K chứa M nên M = K. Vậy K là khóa của a ■ Cho ,   SubSet(U) và M, P  SubSet(U). Ta định nghĩa phép toán  trên SubSet(U) như sau M  P = MP (hợp của hai tập con M và P, M  P) M   = {MX | X  } và    = { XY | X  , Y   } 2.4. Dạng biểu diễn thứ nhất của khóa Địn h l ý (Dạng biểu diễn thứ nhất của khóa) Nếu dịch chuyển LĐQH a = (U,F) theo tập X  U để nhận được LĐQH b=a\X thì 1. Key(a) = Key(b) khi và chỉ khi X  Uo 2. Key(a) = X  Key(b) khi và chỉ khi X  UI Chứn g m i n h (1) Giả sử Key(a) = Key(b) và A  X và A  Uo. Theo phân hoạch của các thuộc tính trong U, A  UK. Như vậy phải tồn tại một khóa K trong Key(a) để A  K. Do Key(a) = Key(b) nên K  Key(b). Từ đây suy ra K  U\X hay là K  X = . Điều này mâu thuẫn với A  K và A  X. Vậy ta phải có X  Uo. (1) Suy từ bổ đề về khóa trong phép dịch chuyển LĐQH. (2 ) Đẳng thức Key(a) = X Key(b) cho biết X có mặt trong mọi khóa của a, tức là X  UI . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 44 (2 ) Giả sử X  UI. Ta sẽ chứng minh rằng mọi khóa K  Key(a) đều được biểu diễn dưới dạng XM, trong đó M  Key(b) và ngược lại, nếu M  Key(b) thì XM  Key(a). Cho K  Key(a). Khi đó, vì X  UI nên X phải có trong mọi khóa của a, nói riêng X  K. Đặt M = K\X, ta có M  X =  và K = XM. Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH ta suy ra M = K \ X là siêu khóa của b. Giả sử M chứa một siêu khóa P của b. Khi đó XP lại là siêu khóa của a và XP  K. Vì K là khóa của a nên XP = K = XM. Để ý rằng X  P = X  M = , ta suy ra P = M. Vậy M là khóa của b. Cho M  Key(b). Ta có X  M = . Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH thì XM là siêu khóa của a. Gọi K là khóa của a chứa trong siêu khóa XM. Lại theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH, K\X là siêu khóa của b. Vì K là khóa của a và X  UI nên X  K. Từ đây suy ra K\X  M. Áp dụng tính tối tiểu cho khóa M của b ta suy ra K\X = M. hay K = XM. Điều này chứng tỏ XM là khóa của a ■ Th í d ụ 1. Cho LĐQH a = (U,F) với tập thuộc tính U = ABCDEH và tập PTH F = {AE  D, BC  E}. Ta tính được giao các khóa là UI = ABCDEH \ DE = ABCH. Đặt b = (V,G) với V = U\ABCH = DE, G = F\ABCH = {ED, E}. Ta có b = a\ABCH và tính được Key(b) = {}, Vậy Key(a) = ABCH  Key(b) = {ABCH}. 2. Với lược đồ đã cho ta tính được UK = ABCH nên Uo = U\UK = BCDEH\ABCH = DE. Đặt c = a\DE = (P,W) ta có P = U\DE = ABCH, W = F\DE = {A   (loại), BC   (loại)} ≡  và do đó Key(c) = ABCH. Theo định lý về dạng biểu diễn thứ nhất của khóa, vì Uo = DE nên Key(a) = Key(c) = ABCH. Hệ q ủ a (Dịch chuyển LĐQH theo các bộ phận không khóa và giao các khóa) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 45 Cho LĐQH a = (U,F) và các tập thuộc tính X  Uo , Y  UI . Nếu thực hiện phép dịch chuyển theo XY để nhận được LĐQH b = a\XY thì Key(a) = Y  Key(b). Chứn g m i n h Do X  Uo, Y  UI nên X  Y = . Đặt c = a\X, ta có, b = a\XY = (a\X)\Y = c\Y. Áp dụng dạng biểu diễn thứ nhất của khóa ta thu được: Vì X  Uo nên Key(a) = Key(c) và do đó giao các khóa của c vẫn là UI. Vì Y  UI xét trong c nên Key(c) = Y  Key(b). Vậy Key(a) = Y  Key(b) ■ 2.5. Dạng biểu diễn thứ hai của khóa Địn h l ý (Dạng biểu diễn thứ hai của khóa) Cho LĐQH a = (U,F). Khi đó mọi khóa K của a đều biểu diễn được dưới dạng K = LM trong đó L là một vế trái cực tiểu của F và M là khóa của LĐQH a\L+. Chứn g m i n h Giả sử K  Key(a). Nếu K=U thì đương nhiên K chứa mọi vế trái của các PTH trong F, khi đó ta chọn một vế trái cực tiểu tùy ý. Giả sử K  U. Khi đó, để tính bao đóng K+ ta phải tìm được một PTH f: X  Y  F thỏa tính chất X  K. Vì X là vế trái của f nên trong ML(F) phải tồn tại một vế trái cực tiểu L để L  X. Ta chọn một trong số vế trái cực tiểu này. Tóm lại ta đã chứng minh được rằng mọi khóa K đều chứa một vế trái cực tiểu L nào đó. Đặt M=K\L. Ta có K=LM. Ta chứng minh M là khóa của LĐQH a\L+. Nếu L+ = U thì a\L+ = a\U = (,). Lược đồ này có khóa duy nhất là M=. Khi đó, K=L. Giả sử L+  U. Từ đây suy ra L  K vì nếu L=K thì phải có L+ = K+ = U, trái với giả thiết L+  U. Theo tính bộ phận của khóa L +  K = L hay K\L=K\L+=M. Từ đây suy ra M  U\L+. Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH, M sẽ là siêu khóa của lược đồ a\L+. Giả sử M chứa siêu khóa P của lược đồ a\L+. Khi đó theo bổ đề về siêu khóa trong phép dịch Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 46 chuyển LĐQH, L+P sẽ là siêu khóa của a, do đó (L+P)+ = U. Vận dụng tính chất C5 của bao đóng ta có (L+P)+ = (LP) + = U, do đó LP là siêu khóa của a. Vì P  M  K = LM nên LP  K. Vì K là khóa của a nên LP = K = LM. Để ý rằng L  P = , L  M =  và P  M ta suy ra P = M. Điều này chứng tỏ M là khóa của a\L + ■ Th í d ụ Với LĐQH a = (U,F), U = ABCDEH, F = {AE  D, A  C, E  BC, EHA, AC  EH, BD  C}. Ta có ML(F) = {A, E,BD}. Ta thấy, E + = EBC  U. Vậy E không phải là khóa của a. Ta dịch chuyển a theo E+. Đặt b = a\E+ = (V,G), ta có V = ABCDEH\EBC = ADH, F = {A  D, A   (loại),    (loại), H  A, A  H, D   (loại)} = {A  D, H  A, A  H}   {A  DH, H  A}. Dễ thấy H là một khóa của b. Như vậy EH là khóa của a, trong đó E là một vế trái cực tiểu, H là khóa của a\E+. C h ú ý Xét mệnh đề đảo của mệnh đề về dạng biểu diễn thứ hai của khóa, cụ thể là Với mọi vế trái cực tiểu L của LĐQH a, ta có L Key(a\L+)  Key(a) Mệnh đề trên là không đúng. Th í d ụ 1. Theo thí dụ trước ta đã tính được LĐQH b = a\E+ = (V,G), V = ADH, G = {A  DH, H  A}. Ngoài khóa H, lược đồ b còn khóa A, tuy nhiên EA không phải là khóa của a vì riêng A đã là khóa của a. 2. Thí dụ sau đây minh họa sự tồn tại LĐQH có vế trái cực tiểu L không tham gia vào bất kỳ khóa nào. Xét LĐQH a = (U,F), U = ABCDE, F = {BD  CE, AE  D, CE  ABD, BE  ACD}. Ta thấy cả 4 vế trái đều là cực tiểu, như vậy ML(F) = {BD, AE, CE, BE}. Ngoài ra do (BD) + = (CE) + = (BE) + = U nên {BD, CE, BE}  Key(a). Mặt khác, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 47 (AE) + = ADE ≠ U nên AE không thể là khóa. Ta chứng tỏ rằng vế trái cực tiểu AE không có trong bất kỳ khóa nào. Thật vậy, vì (AE)+ = ADE nên để xây dựng một khóa chứa AE ta cần thêm cho AE một vài thuộc tính khác với A, D và E, cụ thể là B hoặc/và C. Nếu thêm cho AE thuộc tính B thì ABE chứa khóa BE; nếu thêm cho AE thuộc tính C thì ACE chứa khóa CE. Vậy vế trái cực tiểu AE không thể là bộ phận của bất kỳ khóa nào của a. Bổ đề sau đây cho ta một dấu hiệu tạo và chọn các khóa từ tập khóa của lược đồ sau dịch chuyển. Bổ đ ề (Các khóa sinh từ khóa của lược đồ sau dịch chuyển) Cho LĐQH a = (U,F) và vế trái cực tiểu L. Khi đó nếu K  L  Key(a\L+) và K không chứa vế trái cực tiểu nào khác ngoài L thì K là khóa của a. Chứn g m i n h Giả sử ta có phân hoạch K =L  M, M  Key(a\L+) và K không chứa vế trái cực tiểu khác L của F. Theo hệ quả về siêu khóa trong phép dịch chuyển LĐQH thì K là siêu khóa của a. Gọi P là khóa của a chứa trong K. Ta chứng minh P = K. Nếu P không chứa vế trái cực tiểu nào của F thì U = P+ = P  K, do đó P = K = U. Giả sử P chứa một vế trái cực tiểu nào đó của F. Do P  K mà K chỉ chứa vế trái cực tiểu L duy nhất nên đương nhiên L  P. Đặt Q = P\L, ta có phân hoạch P = L|Q và do đó Q  M. Vì L là bộ phận của khóa P nên theo định lý về đặc trưng của khóa ta có L +  P = L hay P\L+ = P\L = Q. Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH, Q sẽ là siêu khóa của a\L+. Vì M cũng là khóa của a\L+ và Q  M nên Q = M và do đó P = LQ = LM = K. Vậy K là khóa của a ■ Th í d ụ Xét LĐQH a = (U,F), U = ABCDEH, F = {AE  D, A  C, E  BC, EH  A, AC  EH, BD  C}. Ta có ML(F) = {A, E, BD}. Xét vế trái cực tiểu E. Ta thấy, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 48 E + = EBC  U. Vậy E không phải là khóa của a. Ta thực hiện phép dịch chuyển lược đồ a theo E+. Ta có b = a\E+ = (V,G), V = = ABCDEH\EBC = ADH, G = F\EBC ={A  D, A   (loại),    (loại), H  A, A  H, D   (loại)} ≡ {A  DH, H  A}. Dễ dàng tính được Key(b) = = {A, H}, do đó E  Key(b)={EA, EH}. Thành phần EH không chứa thêm vế trái cực tiểu nào khác E, do đó EH là khóa của a. C h ú ý Tồn tại LĐQH có khóa chứa một vài vế trái cực tiểu. Th í d ụ Xét LĐQH a = (U,F) với U = ABCD, F = {A  B, C  D}. Ta có khóa K=AC chứa đồng thời hai vế trái cực tiểu A và C. Bổ đ ề Cho LĐQH a = (U,F) và vế trái cực tiểu L. Khi đó M  Key(a\L+), mọi khóa K của a chứa trong LM đều phải chứa M. Chứn g m i n h Ta đã biết LM là siêu khóa. Giả sử K là khóa của a và K  LM. Ta xét phân họach K = P|Q, trong đó P = K  L, Q = K  M. Vì L  M = L+  M =  nên P  Q = . Theo bổ đề về siêu khóa trong phép dịch chuyển LĐQH ta có K\L+=K\L= PQ\L = Q là siêu khóa của a\L+. Siêu khóa này chứa trong khóa M của a\L+ do đó, theo tính chất tối tiểu của khóa ta phải có Q = M, hay là K  M ■ Bổ đề trên cho phép ta xây dựng thuật toán GetKey nhận một khóa từ tập LM  L  Key(a\L+) với L là vế trái cực tiểu của lược đồ nguồn a. Trước hết để ý rằng LM đã là một siêu khóa của LĐQH a. Như vậy, để tìm một khóa từ LM ta chỉ cần xét để loại bỏ các phần tử trong vế trái cực tiểu L, vì M chứa trong mọi khóa của a có trong LM. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 49 Algorithm GetKey //Tìm một khóa từ LM Format: GetKey(U,F,L,M) Input: - Vế trái cực tiểu L của LĐQH a = (U,F) - M  Key(a\X+) Output: - Khóa K của lược đồ a chứa trong LM Method K := L  M; for each attribute A in L do if A  Closure(K\A,F) then K:=K\A; endif endfor return K; end GetKey. 2.6. Kết luận Lý thuyết về phép dịch chuyển lược đồ quan hệ nhằm nâng cao hiệu quả của các thuật toán tìm bao đóng và tìm khóa phục vụ cho các quá trình chuẩn hóa lược đồ quan hệ. Qua đó cũng giúp tìm hiểu sâu hơn về các đối tượng khác trong quản lý về cơ sở dữ liệu . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 50 CHƯƠNG 3 CÀI ĐẶT CHƯƠNG TRÌNH ỨNG DỤNG PHÉP DỊCH CHUYỂN LĐQH TRONG CSDL 3.1. Giới thiệu Luận văn tập trung nghiên cứu các phép biến đổi LĐQH, chú trọng là phép dịch chuyển LĐQH [7]. Việc cài đặt chương trình ứng dụng nhằm mục đích mô phỏng các kết quả nghiên cứu được của học viên. Chương trình có giao diện đơn giản, dễ sử dụng, dễ hiểu và được viết bằng ngôn ngữ Visual Basic 6.0, một ngôn ngữ khá phổ biến, dễ học, dễ hiểu, hướng đối tượng… và cho phép tạo giao diện nhanh, dễ dàng. Chương trình cho phép nhập mới vào tập thuộc tính và tập các PTH của LĐQH, cho phép lưu cất LĐQH thành tệp trên ổ đĩa và có thể mở tệp đã có sẵn trên đĩa. Ngoài ra, chương trình còn cho phép thực hiện cập nhật, thay đổi LĐQH qua các thao tác thêm/xoá thuộc tính, thêm/xoá PTH. Các chức năng chính của chương trình bao gồm: Tìm bao đóng của tập thuộc tính, tìm một khoá/mọi khoá, tìm giao các khoá, kiểm tra PTH suy dẫn, xác định dạng chuẩn và chuẩn hoá LĐQH. Chức năng tìm phủ thu gọn, phủ thu gọn tự nhiên, phủ không dư, phủ tối tiểu của tập PTH cũng được thiết kế trong chương trình. Đặc biệt, chương trình xây dựng chức năng ứng dụng phép dịch chuyển LĐQH để có thể vận dụng cho các quy trình thiết kế các CSDL chuẩn hoá. 3.2. Các chức năng của chương trình Với mục đích yêu cầu và nội dung của luận văn, chương trình được xây dựng với một số chức năng chính sau: - Menu Soạn thảo: bao gồm các chức năng: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 51 + Nhập mới lược đồ quan hệ: cho phép nhập mới vào các thuộc tính và các PTH của LĐQH. + Mở lược đồ quan hệ: mở một LĐQH đã được lưu trên đĩa + Lưu lược đồ quan hệ: lưu cất LĐQH trên ổ đĩa + Bên cạnh đó còn có một số chức năng thao tác khác cho phép cập nhật, sửa đổi và lưu trữ LĐQH như xoá/thêm thuộc tính, xoá/thêm PTH... - Menu Chức năng: bao gồm các chức năng sau: + Tìm bao đóng của tập thuộc tính: thực hiện tìm bao đóng của một tập thuộc tính được nhập vào + Phủ của tập phụ thuộc hàm: cho phép tìm các phủ không dư, phủ thu gọn, phủ thu gọn tự nhiên, phủ tối tiểu của tập PTH. + Tìm khoá: chức năng này thực hiện việc tìm một khoá hoặc tìm tất cả các khoá của LĐQH. Trong đó, việc tìm mọi khoá của LĐQH được ứng dụng kết quả nghiên cứu và phát triển thuật toán của học viên. + Xác định chuẩn: xác định dạng chuẩn cao nhất của LĐQH hoặc xác định LĐQH có thuộc dạng chuẩn 2NF, 3NF, BCNF không? + Chuẩn hoá 3NF không tổn thất và bảo toàn tập PTH: thực hiện việc chuẩn hoá LĐQH ở dạng chuẩn 3NF không tổn thất và bảo toàn tập PTH, hiển thị kết quả chuẩn hoá. + Kiểm tra PTH suy dẫn: kiểm tra xem một PTH nhập vào có được suy dẫn từ tập các PTH đã cho của LĐQH không? (bài toán thành viên). + Tìm giao các khoá của LĐQH: tìm tập thuộc tính là giao các khoá của LĐQH + Dịch chuyển LĐQH và tìm khoá: chức năng này mô phỏng kết quả nghiên cứu về phép dịch chuyển LĐQH và ứng dụng việc tìm khoá sau khi dịch chuyển. Kết quả hiển thị khoá của LĐQH nguồn và khoá của LĐQH sau khi dịch chuyển. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 52 3.3. Một số giao diện của chương trình * Giao diện chính của chương trình Khung “Luoc đo quan he” sẽ hiển thị tập thuộc tính và tập các PTH của LĐQH Khung “Noi dung yeu cau” hiển thị các nội dung yêu cầu đặt ra cho chương trình Khung “Hien thi ket qua” sẽ hiển thị các kết quả tìm được theo nội dung yêu cầu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 53 * Giao diện nhập mới thuộc tính của LĐQH - Giao diện nhập PTH Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 54 - Giao diện tìm khoá, tìm mọi khoá - Ngoài ra còn một số các giao diện khác như: giao diện tìm bao đóng và hiển thị kết quả, giao diện dịch chuyển LĐQH và tìm khoá của LĐQH sau khi dịch chuyển, tìm các phủ, kiểm tra PTH suy dẫn, chuẩn hoá 3NF, … 3.4. Các thí dụ: 3.4.1. Thí dụ 1: (Tìm khóa của LĐQH) Cho LĐQH a = (U,F) với tập thuộc tính U = ABCDEH và tập PTH F = {AE  D, BC  E, E  BC}. Để tìm tập khóa Key(a) của lược đồ a chúng ta xây dựng một lược đồ b bằng cách xóa khỏi lược đồ a các thuộc tính A, D và H. Ta thu được lược đồ b = (V,G) trong đó V= U\ADH = BCE, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 55 G = {E  Ø, BC  E, E  BC}. Tiếp đến ta loại PTH tầm thường E  Ø khỏi G. Ta thu được G = {BC  E, E  BC}. Ta dễ dàng tìm được hai khóa của lược đồ b, Key(b) = {BC, E}. Để thu được Key(a) ta chỉ việc thêm tập thuộc tính AH (không thêm D) vào mỗi khóa của lược đồ b. Vậy Key(a) = {AHBC, AHE}. Dù F đã là tập PTH tối ưu [7] nhưng G còn chứa ít ký hiệu hơn F. 3.4.2. Thí dụ 2: (Tìm bao đóng của tập thuộc tính) Cho LĐQH a = (U,F), U = ABCDEH, F = {AE  D, BC  E, E  BC}. Tính 1. (AHE) + và 2. E + ? Giải : Ta có, theo hệ quả về công thức tính bao đóng cho một tập thuộc tính 1. (AHE) + F = AHE() + F\AHE G = F\AHE = {  D, BC   (loại),   BC} ≡ {  BCD}. Từ đây ta tính được ()+G =BCD. Do đó (AHE) + = AHEBCD = U. 2. E + = E()+F\E. G = F\E = {A D, BC   (loại),   BC} ≡ {A D,   BC}. Từ đây ta tính được ()+G =BC. Do đó E + = EBC. 3.4.3. Thí dụ 3: (Dạng biểu diễn thứ nhất của khóa) 1. Cho LĐQH a = (U,F) với tập thuộc tính U = ABCDEH và tập PTH F = {AE  D, BC  E}. Ta tính được giao các khóa là UI = ABCDEH \ DE = ABCH. Đặt b = (V,G) với V = U\ABCH = DE, G = F\ABCH = {ED, E}. Ta có b = a\ABCH và tính được Key(b) = {}, Vậy Key(a) = ABCH  Key(b) ={ABCH}. 2. Với lược đồ đã cho ta tính được UK = ABCH nên Uo= U\UK = ABCDEH\ABCH = DE. Đặt c = a\DE = (P,W) ta có P = U\DE = ABCH, W = Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 56 F\DE = {A   (loại), BC   (loại)} ≡  và do đó Key(c) = ABCH. Theo định lý về dạng biểu diễn thứ nhất của khóa, vì Uo=DE nên Key(a) = Key(c) = ABCH. 3.4.4. Thí dụ 4: (Dạng biểu diễn thứ hai của khóa) Cho LĐQH a = (U,F), U = ABCDEH, F = {AE  D, A  C, E  BC, EH  A, AC  EH, BD  C }. Ta có ML(F) = {A, E, BD}. Ta thấy, E + = EBC  U. Vậy E không phải là khóa của a. Ta thu gọn a theo E+. Đặt b = a\E+ = (V,G), ta có V = ABCDEH\EBC = ADH, F = {A  D , A   ( loại ) ,    ( loại ) , H  A , A H, D  (loại)}={A D, H A, A H }  { A  DH, H  A } . Nhận xét : Dễ thấy H là khóa của b. Như vậy EH là khóa của a, trong đó E là một vế trái cực tiểu, H là khóa của a\E+ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 57 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận. Về lý thuyết, luận văn tập trung vào các kết quả sau đây: - Khái niệm về phép dịch chuyển lược đồ quan hệ, - Phát biểu và chứng minh công thức tính bao đóng qua phép dịch chuyển lược đồ quan hệ, - Phát biểu và chứng minh kết quả về dạng biểu diễn khóa thứ nhất, - Phát biểu và chứng minh kết quả về dạng biểu diễn khóa thứ hai, - Phân tích thuật toán tìm khóa, - Nghiên cứu và phát triển thuật toán tìm tất cả các khoá của LĐQH để vận dụng cho các quy trình thiết kế các CSDL chuẩn hoá. Về thực hành luận văn sẽ cài đặt các kết quả lý thuyết dưới dạng chương trình bao gồm các chức năng sau:  Nạp và cập nhật dữ liệu: thuộc tính và các phụ thuộc hàm.  Tính bao đóng  Tìm các khóa của lược đồ quan hệ.  Chuẩn hoá LĐQH Hướng phát triển Một bài chưa giải quyết trọn vẹn hiện nay là khảo sát tính bất biến của các dạng chuẩn trong phép dịch chuyển lược đồ quan hệ. Bài toán được phát biểu như sau: Cho lược đồ quan hệ  với tập thuộc tính U. Giả sử lược đồ quan hệ  nhận được từ lược đồ  qua phép dịch chuyển theo bộ phận thuộc tính M trong U. Lược Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 58 đồ quan hệ  ban đầu có thể ở một trong các dạng chuẩn 2NF, 3NF hoặc BCNF (Boyce-Codd Normal Form). Có thể nói gì về dạng chuẩn của lược đồ . Một vài công trình đã chỉ ra rằng tương quan về dạng chuẩn của hai lược đồ nguồn  và đích  phụ thuộc vào cấu trúc của tập M [5, 6, 7]. Thí dụ, nếu M là bộ phận trong giao các khóa và  ở dạng là 3NF thì  cũng là 3NF. Việc tiếp tục khảo sát các điều kiện cho bài toán trên sẽ cho ta một số kết quả về tính bất biến của các dạng chuẩn thông qua các phép dịch chuyển lược đồ quan hệ. Các kết quả này có thể vận dụng cho các quy trình thiết kế các cơ sở dữ liệu chuẩn hóa. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 59 DANH MỤC CÔNG TRÌNH CÔNG BỐ 1) VŨ TRÍ DŨNG (2009), ”Về thuật toán tìm tất cả các khoá của lược đồ quan hệ”, Tạp chí Khoa học và Công nghệ, Đại học Thái Nguyên, 58 (10) , 48 - 51. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên _______________________________________________________ Vũ Trí Dũng, Luận văn Thạc sĩ Công nghệ thông tin, Trang 60 TÀI LIỆU THAM KHẢO [1] DEMETROVICS J., NGUYEN XUAN HUY (1991), “Closed Sets and Translations of Relation Schemes”, Computers Math. Applic., 21(1), 13-23. [2] DEMETROVICS J., THI V.D. (1996), “Some Results about Normal Forms for Functional Dependency in the Relational Datamodel”, Discrete Applied Mathematics, 69, 61-74. [3] LE DUC MINH, VU NGOC LOAN, and NGUYEN XUAN HUY (2005), “Some Results Concerning Covers in the Class of Multivalued Positive Boolean Dependencies”, in Book: The Mathematical Foundation of Informatics, Eds. by Do Long Van and M. Ito, Proceeding of the Conference, World Scientific, 119-130. [4] CLAUDIO L. LUCCHESI, SYLVIA L. OSBORN (1978), “Candidate Keys for Relations”, Journal of Computer and System Sciences, 17 (2), 270-279. [5] NGUYỄN XUÂN HUY, ĐOÀN VĂN BAN, ĐÀM GIA MẠNH, NGUYỄN THẾ DŨNG (2001), “Về mối liên hệ giữa suy diễn phụ thuộc hàm và suy diễn logic”, Tạp chí Tin học và điều khiển học, 17 (4), 11-16. [6] NGUYỄN XUÂN HUY, LÊ THỊ MỸ HẠNH (2005), “Giàn giao của ánh xạ đóng”, Chuyên san Các công trình nghiên cứu - triển khai Viễn thông và Công nghệ Thông tin, 14 (4), 35-42. [7] NGUYỄN XUÂN HUY (2006), Các phụ thuộc logic trong cơ sở dữ liệu, Viện Khoa học và Công nghệ Việt Nam, NXB Thống Kê, Hà Nội. [8] VŨ ĐỨC THI (1997), Cơ sở dữ liệu: Kiến thức và thực hành, NXB Thống Kê, Hà Nội.