Luận văn Thu gọn lược đồ quan hệ và ứng dụng

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ XUÂN THU THU GỌN LƯỢC ĐỒ QUAN HỆ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên - 2010 ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ XUÂN THU THU GỌN LƯỢC ĐỒ QUAN HỆ VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 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 Thái Nguyên – 2010 LỜI CẢM ƠN Lời đầu tiên, em xin chân thành bày tỏ lòng cảm ơn và kính trọng sâu sắc đối với PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em trong suốt quá trình hoàn thành luận văn này. Thầy đã mở ra cho em những vấn đề khoa học rất lý thú, hướng em vào nghiên cứu các lĩnh vực hết sức thiết thực và vô cùng bổ ích, đồng thời tạo điều kiện thuận lợi cho em học tập và nghiên cứu. Em đã học hỏi được rất nhiều ở Thầy phong cách làm việc, cũng như phương pháp nghiên cứu khoa học… Em luôn được Thầy cung cấp các tài liệu, các chỉ dẫn hết sức quý báu khi cần thiết trong suốt thời gian thực hiện luận văn. Em cũng xin thể hiện sự kính trọng và lòng biết ơn đến Quý Thầy Cô trong Khoa Công nghệ thông tin - ĐHTN, những người đã trang bị cho em rất nhiều kiến thức chuyên ngành, cũng như sự chỉ bảo, giúp đỡ tận tình của quý Thầy cô đối với em trong suốt quá trình học tập. Tất cả các kiến thức mà em lĩnh hội được từ bài giảng của các Thầy cô là vô cùng quý giá. Cuối cùng, em xin được cảm ơn các bạn học viên trong lớp Cao học K7, những người đã cung cấp và chia sẻ những tài liệu, thông tin quý báu trong suốt quá trình học tập, nghiên cứu để hoàn thành luận văn này. Thái Nguyên, tháng 10 năm 2010 Học viên Nguyễn Thị Xuân Thu MỤC LỤC Trang Trang phụ bìa ................................................................................................... Lời cam đoan.................................................................................................... Lời cảm ơn ....................................................................................................... Mục lục ............................................................................................................ i Danh mục các ký hiệu, chữ cái viết tắt.............................................................. ii Danh mục hình vẽ ............................................................................................ iii MỞ ĐẦU ........................................................................................................ 1 Chương 1 CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU 1.1. Khái quát về cơ sở dữ liệu ........................................................................ 2 1.2. Phụ thuộc hàm .......................................................................................... 3 1.3. Lược đồ quan hệ ....................................................................................... 7 1.4. Bao đóng của tập thuộc tính....................................................................... 7 1.5. Phủ của tập phụ thuộc hàm ........................................................................ 9 1.6. Khoá của lược đồ quan hệ.......................................................................... 14 1.7. Chuẩn hoá LĐQH trên cơ sở PTH ............................................................. 20 Chương 2 KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ 2.1. Định nghĩa kỹ thuật thu gọn LĐQH ........................................................... 25 2.2. Thuật toán thu gọn LĐQH ........................................................................ 25 2.3. Định lý thiết lập công thức biểu diễn bao đóng ......................................... 29 2.4. Bổ đề về siêu khoá trong phép thu gọn ..................................................... 32 2.5. Hệ quả về siêu khoá trong phép thu gọn .................................................... 33 2.6. Bổ đề về khoá trong phép thu gọn.............................................................. 34 2.7. Định lý thứ nhất về cách biểu diễn khoá .................................................... 35 2.8. Định lý thứ hai về cách biểu diễn khoá ...................................................... 38 2.9. Lược đồ cân bằng ...................................................................................... 45 Chương 3 CÀI ĐẶT CHƯƠNG TRÌNH ỨNG DỤNG KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU 3.1. Giới thiệu................................................................................................... 52 3.2. Một số giao diện của chương trình............................................................. 53 3.3. Hướng dẫn sử dụng.................................................................................... 59 KẾT LUẬN VÀ KIẾN NGHỊ 1. Kết luận ........................................................................................................ 61 2. Kiến nghị...................................................................................................... 61 TÀI LIỆU THAM KHẢO ............................................................................. 62 DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT CSDL Cơ sở dữ liệu LĐQH Lược đồ quan hệ LĐCB Lược đồ cân bằng PTH Phụ thuộc hàm LS(F) Tập các vế trái của phụ thuộc hàm RS(F) Tập các vế phải của phụ thuộc hàm 1NF 1st normal form - Dạng chuẩn 1 2NF 2nd normal form - Dạng chuẩn 2 3NF 3rd normal form - Dạng chuẩn 3 FD Phụ thuộc hàm ╞ Suy dẫn lgic ├ Suy dẫn theo quan hệ  Là con  Chứa  Thuộc  Không thuộc  Với mọi X+ Bao đóng của tập thuộc tính X  Tương đương ! Không tương đương  Phép giao  Phép hợp DANH MỤC HÌNH VẼ Hình 3.1. Giao diện chính................................................................................. 53 Hình 3.2. Giao diện tạo LĐQH mới .................................................................. 54 Hình 3.3. Giao diện ghi dữ liệu......................................................................... 55 Hình 3.4. Giao diện mở dữ liệu......................................................................... 56 Hình 3.5. Giao diện xử lý ................................................................................. 57 Hình 3.6. Giao diện help................................................................................... 58 MỞ ĐẦU Thiết kế 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, khoá, phản khoá…Một số thuật toán tốt theo nghĩa độ phức tạp giới hạn ở các hàm tuyến tính như : Thuật toán tìm một khoá, thuật toán xác định thành viên, hay thuật toán xác định PTH suy dẫn, thuật toán tìm giao các khoá, thuật toán xác định một lược đồ quan hệ có một khoá duy nhất hay không … Một nhận xét hết sức tự nhiên là nếu kích thước của LĐQH càng nhỏ thì hiệu quả xử lý hay tính toán càng cao. Một số hướng nghiên cứu cho phép tinh giản lược đồ cơ sở dữ liệu đã được thực hiện thông qua phép biến đổi tương đương như đư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… Trong luận văn này, em xin trình bày một kỹ thuật tinh giản khác, đó là “Kỹ thuật thu gọ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ủa các đối tượng đang quan tâm như bao đóng, khoá, phản khoá… Mặc dù LĐQH thu được qua phép thu gọ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 vào một số thuộc tính. Đặc biệt 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. Kỹ thuật này có thể được ứng dụng để giải quyết các bài toán cơ sở dữ liệu phức tạp. Đây là hướng nghiên cứu chính của đề tài. Luận văn được trình bày trong 3 chương: Chương 1: Trình bày các kiến thức cơ bản về cơ sở dữ liệu. Chương 2: Tìm hiểu về kỹ thuật thu gọn lược đồ quan hệ, các định lý cơ bản của phép thu gọn và các dạng biểu diễn khoá thông qua phép thu gọn. Chương 3: Cài đặt chương trình. Ứng dụng kỹ thuật thu gọn lược đồ quan hệ trong thiết kế cơ sở dữ liệu. CHƯƠNG I : CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU 1.1 Khát quát về cơ sở dữ liệu Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được tập trung nghiên cứu và phát triển của công nghệ thông tin, nhằm giải quyết các bài toán quản lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp cho nhiều người sử dụng trên máy tính điện tử. Cùng với sự ứng dụng mạnh mẽ công nghệ thông tin vào đời sống xã hội, kinh tế, quốc phòng ...Việc nghiên cứu CSDL đã và đang phát triển ngày càng phong phú và hoàn thiện. Từ những năm 70, mô hình dữ liệu quan hệ do E.F. Codd đưa ra với cấu trúc hoàn chỉnh đã tạo nên cơ sở toán học cho các vấn đề nghiên cứu lí thuyết về CSDL. Với ưu điểm về cấu trúc đơn giản và khả năng hình thức hoá phong phú, CSDL quan hệ dễ dàng mô phỏng các hệ thống thông tin đa dạng trong thực tiễn, tạo điều kiện lưu trữ thông tin tiết kiệm, có tính độc lập dữ liệu cao, dễ sửa đổi, bổ sung cũng như khai thác dữ liệu. Mặt khác, việc khai thác và áp dụng các kĩ thuật tổ chức và sử dụng bộ nhớ cho phép việc cài đặt các CSDL quan hệ đưa lại hiệu quả cao và làm cho CSDL quan hệ chiếm ưu thế trên thị trường. Mô hình dữ liệu quan hệ đặt trọng điểm hàng đầu không phải là khai thác các tiềm năng của máy mà ở sự mô tả trực quan dữ liệu theo quan điểm của người dùng, cung cấp một mô hình dữ liệu đơn giản, trong sáng, chặt chẽ, dễ hiểu và tạo khả năng tự động hoá thiết kế CSDL quan hệ. Có thể nói lí thuyết thiết kế và cài đặt CSDL, nhất là mô hình dữ liệu quan hệ đã phát triển ở mức độ cao và đạt được những kết quả sâu sắc. Hàng loạt vấn đề đã được nghiên cứu giải quyết như: - Lý thuyết thiết kế CSDL, các phương pháp tách và tổng hợp các lược đồ quan hệ theo tiêu chuẩn không tổn thất thông tin hay bảo toàn tính nhất thể của các ràng buộc trên dữ liệu . - Các loại ràng buộc dữ liệu, cấu trúc và các tính chất của chúng, ngữ nghĩa và khả năng áp dụng phụ thuộc dữ liệu ví dụ như phụ thuộc hàm, phụ thuộc đa trị, phụ thuộc kết nối, phụ thuộc lôgic... - Các vấn đề tối ưu hoá: ở mức vật lí trong việc tổ chức quản lí các tệp; ở mức đường truy nhập với các tệp chỉ số hay các danh sách sắp xếp; ở mức lôgic trên cơ sở rút gọn các biểu thức biểu diễn các câu hỏi…. Trong luận văn này, em sẽ trình bày một số kiến thức cơ bản nhất về CSDL bao gồm các kiến thức liên quan đến phụ thuộc hàm, khoá, các dạng chuẩn và đặc biệt là đi sâu tìm hiểu kỹ thuật thu gọn lược đồ quan hệ cũng như các thuật toán để áp dụng chúng vào việc xây dựng và thiết kế các bài toán CSDL hiện nay. 1.2 Phụ thuộc hàm 1.2.1 Định nghĩa phụ thuộc hàm Cho tập thuộc tính U. Giả sử X, Y  U. Một phụ thuộc hàm (PTH) trên U là biểu thức dạng f: X  Y. Nếu f: X  Y là một PTH trên U thì ta nói tập thuộc tính Y phụ thuộc hàm 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. Cho quan hệ R(U) và một PTH f: X  Y trên U. Ta nói quan hệ R thỏa PTH f (hay PTH f đúng trong quan hệ R), ký hiệu R(f), nếu hai bộ tùy ý trong R giống nhau trên X thì cũng giống nhau trên Y, tức là R(X  Y)  u,v  R: u.X = v.X  u.Y = v.Y Cho quan hệ R(U) và tập PTH F trên tập thuộc tính U. Ta nói quan hệ R thỏa tập PTH F, ký hiệu R(F), nếu R thỏa mọi PTH trong F, tức là R(F)  f  F: R(f). 1.2.2 Hệ tiên đề Armstrong Cho quan hệ R(U). Giả sử X, Y, Z, W  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+ Chú ý: 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 thoả trong mọi quan hệ. 1.2.3 Bao đóng của tập PTH 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à thỏa mãn các tính chất F1- F3 của hệ tiên đề Armstrong. 1.2.4 Các phép suy dẫn 1.2.4.1 Suy dẫn logic PTH f được suy dẫn logic từ tập PTH F, ký hiệu F╞ f, nếu f  F+. F╞ f  f  F+ Nói cách khác, PTH f được suy dẫn logic từ tập PTH F nếu xuất phát từ F, áp dụng các luật F1, F2, F3 của hệ tiên đề Arsmtrong sau hữu hạn lần ta sẽ thu được PTH f. 1.2.4.2 Suy dẫn theo quan hệ 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, ký hiệu F├ f, nếu mọi quan hệ R(U) thỏa F thì R cũng thỏa f. F├ f  SAT(F)  SAT(f) Ký hiệu SAT(F) là tập toàn thể các quan hệ trên U thỏa tập PTH 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ệ từ tập PTH F. F* = {f: X  Y | X,Y  U, F├ f } 1.2.4.3 Suy dẫn theo quan hệ không có quá p bộ 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, ký hiệu F├p f, nếu mọi quan hệ Rp(U) thỏa F thì R cũng thỏa f. F├p f  SATp(F)  SATp(f) Ký hiệu SATp(F) là tập toàn thể các quan hệ có không quá p bộ trên U và thỏa tập PTH 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á 2 bộ từ tập PTH F. F’ = {f: X  Y | X,Y  U, F├2 f } Đối với PTH, 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 (iii) Suy dẫn theo quan hệ có không quá hai bộ: F├2 f 1.2.5 Một số tính chất của phụ thuộc hàm Cho tập thuộc tính U, các tập PTH F và G trên U, tập một số quan hệ  trên U, các quan hệ R và S trên U. Ta có các tính chất sau: 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 ()  Một số tính chất mở rộng của PTH Sử dụng 3 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 thu hẹp vế phải: X Y  XZ  Y\V F7. Tính cộng đầy đủ: XY, Z V  XZ  YV F8. Mở rộng vế trái: XY, XZ  Y 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 1.3. Lược đồ quan hệ Lược đồ quan hệ (LĐQH) là một cặp p = (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 PTH F, ta xem LĐQH chỉ là một tập hữu hạn các thuộc tính U. 1.4 Bao đóng của 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. Bao đóng của tập thuộc tính X, ký hiệu X+, là tập tất cả các thuộc tính A  U mà PTH XA có thể được suy diễn logic từ F nhờ hệ tiên đề Armstrong: X+ = {A  U | X  A  F+}  Thuật toán tìm bao đóng của 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 của tập thuộc tính X , ký hiệu X+ ta xuất phát từ tập X và bổ sung dần cho X các thuộc tính thuộc vế phải của các PTH LR  F thoả điều kiện L X. Thuật toán sẽ dừng khi không thể bổ sung thêm thuộc tính nào cho X. Algorithm Closure Format: Closure (X, F) Input: - Tập thuộc tính X  U - Tập PTH F Output: 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 ; Enddif ; Endfor ; Until Y: = Z; Return Y; End Closure.  Đánh giá độ phức tạp Giả sử n là số lượng các thuộc tính trong U, m là số lượng các PTH trong F thì thuật toán trên có độ phức tạp đa thức bậc hai theo chiều dài dữ liệu O(mn2).  Một số tính chất của bao đóng Cho LĐQH a = (U, F). Khi đó X, Y  U ta có 1. Tính phản xạ: X  X+ 2. Tính đồng biến: X  Y  X+  Y+ 3. Tính lũy đẳng: (X+)+ = X+ 4. (XY)+  X+Y+ 5. (X+Y)+ = (XY+)+ = (XY)+ 6. X  Y  F+  Y  X+ 7. X  X+ và X+  X 8. X+ =Y+  X  Y và Y  X  Bài toán thành viên Đây là bài toán xác định xem một PTH có thuộc bao đóng của tập PTH không ? Thuật toán giải quyết vấn đề này dựa trên một định lý cơ bản, thể hiện mối liên quan giữa bao đóng của tập thuộc tính và bao đóng của tập PTH. Bài toá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 ? X  Y  F+  Y  X+ Ý tưởng thuật toán : Kiểm tra X  Y  F+ không ? - Tính X+ - Kiểm tra Y  X+ không ? Nếu Y  X+ thì X  Y  F+ , ngược lại thì X  Y  F+  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 nếu f  F+ Method IsMember := (RS(f)  Closure(LS(f),F)) End IsMember. 1.5 Phủ của tập phụ thuộc hàm 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 được ra 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: F không suy dẫn ra được G F! G có nghĩa là 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. 1.5.1 Phủ thu gọn tự nhiên Cho hai tập PTH F và G trên cùng một thuộc tính U. G là phủ thu gọn tự nhiên của F nếu: 1. G là phủ của F, và 2. G có dạng thu gọn tự nhiên theo nghĩa sau: a. 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) =  b. 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 của tập PTH F Algorithm Natural_Reduced Function : Tính phủ thu gọn tự nhiên của tập PTH 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. Độ phức tạp của thuật toán trê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 tập U. Để ý rằng mn là chiều dài dữ liệu vào của thuật toán. 1.5.2 Phủ không dư Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Tập PTH 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 F Algorithm Nonredundant Funtion : Tính phủ không dư 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 U : = Attr (F) ; // Tập thuộc tính của F G : = F; For each FD g : L R in F do If R  Closure (U,G\{g},L) then G := G\{g}; Endif; Endfor; Return G; End Nonredundant. 1.5.3 Phủ thu gọn 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 Funtion: Tính phủ thu gọn của tập PTH 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. 1.5.3.1 Phủ thu gọn trái 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 Ta thấy rằng g: LR  G, A  L : G\{g}{g’: L\{A} R}╞ g vì L\{A} L, do đó ta chỉ cần kiểm tra G ╞ g’ ? Algorithm Left_Reduced Function : Tính phủ thu gọn trái của tập PTH 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 U : = Attr (F) ; // Tập thuộc tính của F G := F; For each FD g: LR in F do X := L; For each attribute A in X do If R Closure (U, G, L\{A}R) then Delete A from L in G; Endif Endfor Endfor Return G; End Left_Reduced 1.5.3.2 Phủ thu gọn phải 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 Ta thấy rằng g: LR  G, A  R : G╞ g’: LR \ {A}, vì R\{A}  R , do đó ta chỉ cần kiểm tra G \ {g}  {g’}╞ g ? Algorithm Right_Reduced Function : Tính phủ thu gọn phải của tập PTH 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 U : = Attr (F) ; // Tập thuộc tính của F G := F; For each FD g: LR in F do X:=R; For each attribute A in X do If A in Closure (U, G\{g}  {LR\{A}},L) then Delete A from R in G; Endif; Endfor; If R =  then Delete LR from G; Endif; Endfor; Return G; End Right_Reduced. 1.5.4 Phủ tối tiểu Cho hai tập 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ủ của F ii) Vế phải của 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 Function: Tính phủ tối tiểu của tập PTH 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 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 Add LA to G; Endif; Endfor; Endfor; G := Reduced (G); Return G; End Mincover. 1.6 Khóa của lược đồ quan hệ Cho LĐQH p = (U, F). Tập thuộc tính K  U được gọi là khóa của LĐQH p 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 thỏa mãn điều kiện (i) thì K được gọi là một siêu khóa. Thuộc tính A  U được gọi là thuộc tính khóa (nguyên thủy hoặc cơ sở) nếu A có mặt trong một khóa nào đấy. A được gọi là thuộc tính không khóa (phi nguyên thủy hoặc thứ cấp) nếu A không có mặt trong bất kỳ khóa nào. Ký hiệu UK là tập các thuộc tính khóa của LĐQH p và U0 là tập các thuộc tính không khóa của p. Chú ý: Trong một số tài 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á.  Thuật toán tìm khoá của LĐQH Tư tưởng: Xuất phát từ một siêu khoá K tuỳ ý 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ì A loại khỏi K. Có thể thay kiểm tra (K\{A})+ = U bằng kiểm tra A  (K\{A})+ . Algorithm Key Function: Tìm một khoá của LĐQH Format: Key (U,F) Input: - Tập thuộc tính U - Tập PTH F Output: Khoá K  U thoả i) K+ = U ii) AK : (K\{A})+  U Method K := U; For each attribute A in U do If A  (K\{A})+ then K := K \ {A} Endif; Endfor; Return K; End key. Độ phức tạp tính toán: 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). Ví dụ 1: Cho LĐQH p = (U,F), trong đó : U = {A, B, C, D, E} F = { D  E AB  CD C  AB } Hãy tìm một khoá của p. Dễ thấy rằng, LĐQH p có khoá K = C, vì thoả mãn hai điều kiện: (i) K+ = C+ = ABCDE = U (ii) C tối tiểu ( theo nghĩa (K \ {C})+  U ). Ví dụ 2: Cho P = (U,F), trong đó : U = ABCDE F = { C B DE  AC A  DE } Tìm khoá của LĐQH đã cho ? Ta thấy, LĐQH P có khoá K = A, vì thoả mãn 2 điều kiện : (i) K+ = A+ = ABCDE = U (ii) A tối tiểu ( theo nghĩa (K \ {A})+  U ). Mặt khác, tương tự như trên, ta cũng dễ thấy rằng LĐQH P còn khoá thứ 2, đó là K = DE. Để trả lời cho câu hỏi: Lược đồ có trên một khoá hay không, ta đi tìm giao các khoá. 1.6.1 Cách tính giao các khoá Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi khoá, đó chính là giao các khoá. Vậy giao các khoá chính là những thuộc tính không xuất hiện ở vế phải. Giả sử M là giao các khoá. Nếu M+ = U thì lược đồ chỉ có đúng 1 khoá, nếu M+  U thì lược đồ có trên 1 khoá. Gọi M là giao các khoá khi và chỉ khi : M+ = U. Cho LĐQH p = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi M là giao các khoá của p. Khi đó có thể xác định giao các khoá bằng một thuật toán tuyến tính theo mn qua công thức:  FRL LRUM   )\(\ .  Thuật toán xác định giao các khoá 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 khoá  FRL LRUM   )\(\ Method M:=U; For each FD LR in F do M:=M\(R\L); Endfor; Return M; End KeyIntersec. 1.6.2 Thuật toán tìm 2 khoá của LĐQH Bước 1: Tính giao các khoá Bước 2: Lấy M+. Nếu M+ = U  Lược đồ có 1 khoá M là duy nhất M+  U  Lược đồ có trên 1 khoá Gọi thuật toán Key – Tìm khoá 1 Gọi thuật toán Key 2 – Tìm khoá 2 Tư tưởng: Xuất phát từ tập thuộc tính M = U, trước hết duyệt các thuộc tính A của K, nếu bất biến (M\{A})+ = U được bảo toàn thì loại A khỏi M. Sau đó duyệt tương tự với các thuộc tính trong U\K. Algorithm Key 2 Function: Tìm một khoá thứ 2 của LĐQH Format: Key 2 (U,F) Input: - Tập thuộc tính U - Tập PTH F - Khoá K  U Output: Khoá thứ hai, nếu có, M  U thoả i) M+ = U ii) AM : (M\{A})+  U Nếu không có khoá thứ 2:  Method M := U; For each attribute A in K do If A  (M\{A})+ then M := M \ {A} Endif; Endfor; For each attribute A in U \ K do If A  (M\{A})+ then M := M \ {A} Endif; Endfor; If M = K then return  Else return M; Endif End key 2. Ví dụ: Cho LĐQH P = (U,F) trong đó: U = ABCDE F = { BC  D CD  A D  E A  B } a. Hãy xác định phần giao của các khoá trong P b. Tìm một khoá K1 của P c. P có còn khoá nào khác ngoài K1 không ? Vì sao ? d. Xác định tập các thuộc tính không khoá U0 của P Giải a. Xác định phần giao của các khoá trong P Theo công thức, ta có:  FRL LRUM   )\(\ = ABCDE – ABDE = C b. Tìm một khoá K1 của P Đặt K0 = U = ABCDE K1 = K0 – E = ABCD vì (K0 - E)+ = U và D E K2 = K1 – D = ABC vì (K1 - D)+ = U và BC D K3 = K2 = ABC vì (K2 - C)+  U K4 = K3 – B = AC vì (K3 - B)+ = U và A B K5 = K4 = AC vì (K4 - A)+  U Vậy khoá K1 của P là AC. c. P còn khoá khác ngoài khoá K1 vì: M+ = C+ = C  U nên lược đồ có hơn một khoá. Dễ thấy rằng, ngoài khoá K1, lược đồ còn có khoá K2 = BC vì thoả mãn 2 điều kiện sau: (i) K+ = BC+ = ABCDE = U (ii) BC tối tiểu ( theo nghĩa (K \ {BC})+  U ). Tương tự, ta còn tìm được khoá thứ 3 của lược đồ quan hệ P như sau: K3 = CD. d. Xác định tập các thuộc tính không khoá U0 của P. - Thuộc tính khoá là thuộc tính có mặt trong mọi khoá, ký hiệu là Uk. - Thuộc tính không khoá là thuộc tính không có mặt trong bất cứ khoá nào, ký hiệu U0. Ta có: Uk = ABCD,  U0 = E. 1.7 Chuẩn hóa LĐQH trên cơ sở PTH 1.7.1 Các dạng chuẩn a. Dạng chuẩn 1 (1NF) LĐQH p = (U,F) được gọi là lược đồ ở 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 (điều này có nghĩa là những thuộc tính này không thể chia nhỏ được nữa bằng các phép toán quan hệ). b. Dạng chuẩn 2 (2NF) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 2 (2NF) nếu p là lược đồ 1NF và mọi thuộc tính không khoá phụ thuộc đầy đủ vào mọi khoá.  A  U0, K  Key (p): K+  A c. Dạng chuẩn 3 (3NF) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 3 (3NF) nếu p là lược đồ 1NF và mọi thuộc tính không khoá đều phụ thuộc trực tiếp vào mọi khoá.  A  U0, K  Key (p): K*  A LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 3 (3NF) nếu p là lược đồ 1NF và mọi PTH không tầm thường X  A, A là thuộc tính không khoá đều cho ta X là một siêu khoá.  (X A, A  U0 \ X)  X+ = U d. Dạng chuẩn BCNF (Boyce - Codd) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn BCNF nếu p là lược đồ 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 LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn BCNF nếu p là lược đồ 1NF và mọi PTH không tầm thường X  Y đều cho ta X là một siêu khoá.  (X Y, Y \ X  )  X+ = U 1.7.2 Định nghĩa phép tách Cho lược đồ quan hệ p = (U,F). Một phép tách trên tập thuộc tính U là một họ các tập con của U,  = (X1, X2, ..., Xk) thoả tính chất  K i i UX 1  . Phép tách  = (X1, X2, ..., Xk) trên tập thuộc tính U đượ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. 1.7.3 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 hoá 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ả i) RSAT(F): R[U1] * R[U2] * ... * R[Us] = R ii) K1, K2, ..., Ks là các khoá của các lược đồ tương ứng iii) Tập PTH F được bảo toàn Method 1. Tìm khoá K của p 2. Tìm phủ tối thiểu của F G = {K1A1, K2A2, ..., KmAm } 3. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1X1, K2X2, ..., KsXs } 4. Xét phép tách  = (K1X1, K2X2, ..., KsXs). Nếu khóa K không có mặt trong thành phần nào của  thì thêm thành phần K vào . 5. Return {(K1X1,K1), (K2X2, K2), ..., (KsXs, Ks)} End 3NF. 1.7.4 Ví dụ a. Ví dụ 1 : Chuẩn hoá 3NF LĐQH p = (U,F) sau : U = ABCDEGH F = { A  C DH  A DC  H AE  G DE  H } Bước 1: Tìm một khoá Ta có, giao các khoá  FRL LRUM   )\(\ = ABCDEGH \ ACGH = BDE. Tính M+ = (BDE)+ = ABCDEGH = U. Vì M+ = U nên lược đồ p có một khoá duy nhất là K = BDE. Tập các thuộc tính khoá Uk = BDE, tập các thuộc tính không khoá U0 = ACGH Bước 2 : Vì bộ phận thực sự của khoá K là DE và DE  H, H  U0 nên p không ở dạng 2NF và do đó cũng không ở dạng 3NF. Bước 3: Để ý rằng, F đã ở dạng tối tiểu, ta có:  = (AC, DHA, DCH, AEG, DEH) Khoá K = BDE không có trong thành phần nào của  nên ta thêm K vào để thu được kết quả sau: Lược đồ Khoá AC A DHA DH DCH DC AEG AE DEH DE BDE BDE b. Ví dụ 2: Chuẩn hoá 3NF cơ sở dữ liệu sau : SV (SV#, HT, NS, QUE, HL) DT (DT#, TDT, CN, KP) SD (SV#, DT#, NTT, KM, KQ) với các tập PTH sau: FSV = {SV#  HT, NS, QUE, HL} FDT = {DT#  TDT, CN, KP} FSD = {SV#, DT#  NTT, KQ; NTT  KM} Giải: Hai quan hệ SV và DT chỉ có 1 khoá đơn (1 thuộc tính) tương ứng là SV# và DT# và hai tập PTH tương ứng chỉ chứa 1 PTH nên hai quan hệ này ở BCNF. Quan hệ SD có 1 khoá là K = SV# DT#. SD không ở 3NF vì có phụ thuộc bắc cầu của thuộc tính không khoá KM vào khoá K. Ta chuẩn hoá SD như sau: 1. Tách SV#, DT#  NTT SV#, DT#  KQ NTT  KM 2. Tìm phủ tối thiểu G = {SV#, DT#  NTT; SV#, DT#  KQ; NTT  KM} 3. Gộp: Gộp lại ta thu được F. Thành phần thứ nhất chứa khoá {SV#, DT#}. 4. Kết quả:  = ({ SV#, DT#, NTT, KQ}, {NTT, KM}) Ta thu được hai quan hệ : SD ( SV#, DT#, NTT, KQ) với khoá K = SV#, DT# Và NK ( NTT, KM ) với khoá là NTT. c. Ví dụ 3 Xác định và giải thích dạng chuẩn cao nhất của LĐQH sau: p = (U,F), U = ABCD, F = {A C, D B, C ABD} Ta thấy: LĐQH p có hai 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á Uo = BD. Ta có DB, B là thuộc tính không khoá, D không phải là siêu khoá đó do đó a không ở 3NF đươ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. CHƯƠNG II: KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ 2.1 Định nghĩa kỹ thuật thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và tập thuộc tính M  U. Ta nói LĐQH q nhận được từ LĐQH p qua phép thu gọ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 đồ p thì thu được lược đồ q. Nếu sau khi thực hiện phép thu gọn theo M cho LĐQH p ta thu được LĐQH q thì ta viết q = p\M. Thao tác loại bỏ M được thực hiện trên lược đồ p = (U,F) để thu được lược đồ q = (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. Mỗi PTH XY trong F ta tạo ra PTH X\MY\M cho G. Thủ tục này 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 q = p\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 (của LĐQH p). Sau khi thực hiện thủ tục G = F\M nếu: - G chứa PTH tầm thường (dạng XY, XY) thì ta loại các PTH này khỏi G. - G chứa các PTH trùng lặp thì ta bớt các PTH này.  Ví dụ 1: Cho LĐQH p = (U, F); U = abcdefg F = {abc  de, bcd  ag, de  fc, ce  fg} Với M = cfg, hãy xác định q = (V,G) = p\M. Ta có: V = U \ cfg = abcdefg \ cfg = abde G = { ab  de, bd a, de  , (Loại) e  , (Loại) } = {ab  de, bd a } Ta cũng dễ nhận thấy kỹ thuật thu gọn LĐQH thoả tính hợp thành và giao hoán, cụ thể nếu p là LĐQH trên tập thuộc tính U và X, Y là hai tập con rời nhau của U thì p\XY = (p\X)\Y = (p\Y)\X 2.2 Thuật toán thu gọn LĐQH Algorithm Translation Format: Translation (p,M) Input: - LĐQH p = (U,F) - Tập thuộc tính M U Output: - LĐQH q = (V,G) = p\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); 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 có hai vế trái phải rời nhau và gộp các PTH có cùng vế trái.  Ví dụ 2: Cho LĐQH p = (U,F), U = ABCDEH F={ AE  D, A  DH, BC  E, E  BC} Với M = ADH, hãy xác định q = (V,G) = p\M ? Ta có: V = U\ADH = ABCDEH\ADH = BCE, G = {E   (loại) ,    (loại), BC  E, E  BC} = {BC  E, E  BC} Ta nhận thấy phép thu gọn thoả tính hợp thành và giao hoán, cụ thể nếu p là LĐQH trên tập thuộc tính U và X, Y là hai tập con rời nhau của U thì p\XY = (p\X)\Y = (p\Y)\X  Ví dụ 3 : Cho LĐQH p = (U,F), U = ABCDEH F= {AE  D, BC  E, E  BC } Để tìm tập khoá Key (p) của lược đồ p chúng ta xây dựng một lược đồ q bằng cách xoá khỏi lược đồ p các thuộc tính A,D,H. Ta thu được lược đồ q = (V,G) trong đó: V = U \ ADH = ABCDEH \ ADH = BCE, G = { E (loại), BCE, EBC} = { BCE, EBC} Ta dễ dàng tìm được Key (q) = {BC,E}. Để thu được Key (p) ta chỉ việc thêm tập thuộc tính AH (không thêm D) vào mỗi khoá của lược đồ q. Vậy Key (p) = {AHBC, AHE}. Dù F đã là tập PTH tối ưu theo nghĩa chứa ít ký hiệu nhất, nhưng G còn chứa ít ký hiệu hơn F.  Ví dụ 4 : Cho LĐQH p = (U,F), Với tập thuộc tính U = ABCDEIH. Tập thuộc tính F = {AD, ABDE, CEI, EH} Tính Key (p)? Để tìm tập khoá của p bằng cách thu gọn LĐQH p theo M= ABC. Ta thu được LĐQH q = p\M = (V,G). V= U \ M = ABCDEIH \ ABC = DEIH. G = F \ M = {D, DE, EI, EH} = {DE, EIH} Ta dễ dàng suy ra Key (q) = . Để thu được Key (p), ta chỉ cần thêm vào Key (q) các thuộc tính vừa thu gọn ABC. Ta được Key (p) =ABC.  Ví dụ 5 : Cho LĐQH p = (U,F). Với tập thuộc tính U =ABCDEH. Tập PTH F = {AB  C, C  A, BC  D, ACD  B, D  EH, BE  C, CH  BD, CE  CH}. Tìm Key(p)? Ta thu gọn lược đồ quan hệ p theo thuộc tính C. Thu được LĐQH: q = p\C = (V,G). V = ABDEH. G = {AB   (loại),   A, B  D, AD  B, D  EH, BE   (loại), H  BD, EH } = {   A, BD, ADB, DEH, HBD, EH}. Ta tìm được khóa của lược đồ q Key (q)={B,D,E,H}. Để thu được Key(p), ta thêm thuộc tính C vào khoá của lược q. Ta được Key (p) = {BC, DC, EC, HC}. 2.3 Định lý 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 thu gọn lược đồ quan hệ Cho LĐQH a=(U,F) và hai tập con rời nhau X và Y trong U. Khi đó (XY)+F = XY+F\X . Chứng minh Đặt V=U\X và G=F\X. 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 = . 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 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ể 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 thì hai tập (XY)(h) và XY(h) sẽ được bổ sung thêm cùng một số thuộc tính. Đầu tiên, do XY= và X không có mặt trong LĐQH p = p\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 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 thoả 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 thu gọ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). Ta thấy, 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: Cho LĐQH p = (U,F) và tập XU. Khi đó X+F =X()+F/X.  Ví dụ 6: Cho LĐQH a = (U,F). U=ABCDEH. F = {AED, BCE, EBC}. Tính: (CE)+, (AHE)+ và E+ ? Áp dụng hệ quả về công thức tính bao đóng cho mọi tập thuộc tính, ta có: 1. (CE)+F = CE()+F\CE. G = F\CE={AD, B (loại), B}  {AD, B}. Từ đây ta tính được ()+G = B. Do đó (CE)+ = BCE 2. (AHE)+F = AHE()+F\AHE. G = F\AHE={D, BC (loại), BC}  {BCD}. Từ đây ta tính được ()+G = BCD. Do đó (AHE)+ = U 3. 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.  Ví dụ 7: Cho LĐQH a= (U,F). U =ABCDEHKIL F = {ABC, DEH, HKI, EAB} Tính (DHE)+ , (ABDE)+ ? 1. Tính (DHE)+ Áp dụng hệ quả của công thức bao đóng ta có: (DHE)+ = DHE()+F\DHE . G = F\DHE = {ABC, , KI, AB} Suy ra ()+F\DHE = ABKI Vậy (DHE)+ = DHEABKI. 2. Tính (ABDE)+ Áp dụng hệ quả của công thức bao đóng: X+ = X()+F\X Ta có (ABDE)+ = ABDE()+F\ABDE G = F\ABDE = {C, H, HKI,  (loại)} = {CH, HKI}. Suy ra ()+F\X = CH Vậy (ABDE)+ = ABCDEHKI. 2.4 Bổ đề về siêu khoá trong phép thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và X  U. Biết q = p\X. Khi đó: i) Nếu M là siêu khóa của p thì M \ X là siêu khoá của q. ii) Nếu Z là siêu khoá của q thì ZX là siêu khoá của p. Nói riêng nếu XUo và Z là siêu khoá của q thì Z là siêu khoá của p. Chứng minh i) Giả sử M là siêu khoá của a. Đặt P = M\X, ta có XP =  và M  XP. Vì M là siêu khoá của p, 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ừ đẳ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 khoá của q. ii) Đảo lại, giả sử Z là siêu khóa của q = p\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 khoá của p. Nếu XUo thì ta có thể loại bỏ XZ bộ phận thuộc tính không khoá X để thu được Z là siêu khoá của p.  Ví dụ 8: Cho LĐQH p = (U,F). Với U = ABCDEHKI. F = {ABC, CDEH, HK}  Ta có siêu khoá Key(p) = ABI. Ta thu gọn p theo X = BI ta được lược đồ q = p\BI = (V,G) V = ABCDEHKI\BI = ACDEHK G = {AC, CDEH, HK}  Ta có siêu khoá Key(q) = A Ta kiểm tra Key(p)\BI = ABI\BI = A = Key(q) Hay nói cách khác Key(p) = Key(q)X = ABI. 2.5 Hệ quả về siêu khoá trong phép thu gọn LĐQH Cho LĐQH p = (U,F) và tập thuộc tính X  U. Khi đó nếu Z là siêu khoá của lược đồ p\X+ thì XZ là siêu khoá của lược đồ p.  Ví dụ 9: Cho LĐQH p = (U,F). Với U = ABCDEHKI F = {ABC, CDEH, HK} Ta dễ dàng tính được siêu khoá Key(p) = ABI. Cho X = AB suy ra X+ = (AB)+ = ABCDEHK. Ta thu gọn lược đồ p theo X+ = ABCDEHK ta thu được lược đồ q = p\X+ = p\ABCDEHK = (V,G). V = U\BI = ABCDEHKI\ABCDEHK = I. G = F\ABCDEHK = { (loại) ,  (loại) ,  (loại)} Ta tính được siêu khoá Key(q) = I. Như vậy Key(p) = Key(q)X = ABI. 2.6 Bổ đề về khoá trong phép thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và tập thuộc tính X  Uo. Biết q = p\X. Khi đó Key(p) = Key(q). Chứng minh Giả sử K Key(p). Khi đó nói riêng K là siêu khoá của p. Do K  UK, X  Uo, UK Uo =  nên theo bổ đề về siêu khóa trong phép thu gọn LĐQH, K = K\X là siêu khoá của q. Giả sử K chứa siêu khoá M của q. Khi đó lại theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta có M là siêu khoá của p. Do K là khoá của p, M là siêu khoá của p chứa trong K, nên theo tính chất tối thiểu của khoá ta phải có M = K. Vậy K là khoá của q. Đảo lại, nếu K là khóa của q thì KX= và theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta có M\X là siêu khoá của q. Do K là khoá của q và K chứa M nên M = K . Vậy K là khoá của p.  Ví dụ 10: Cho LĐQH p = (U,F). Với U = ABCDEHIK. F={ABC, CEH, HAB} Ta có Key(p) = HDIK. Ta tính được UK = HDIK suy ra Uo = U\UK = ABCE. Ta thu gọn lược đồ p theo ABCE được lược đồ q = (V,G) với V = U\ABCE = DHIK. G = F\ABCE = { (loại), H, H(loại)} Ta tính được Key(q) = HDIK. Vậy Key(p) = Key(q). 2.7 Định lý thứ nhất về cách biểu diễn khoá Nếu thu gọn LĐQH p = (U,F) theo tập XU để nhận được LĐQH q = p\X thì: 1. Key(p) = Key(q) khi và chỉ khi XUo 2. Key(p) = XKey(q) khi và chỉ khi XUI Chứng minh 1. Giả sử Key(p) = Key(q), AX và AUo. Theo phân hoạch của các thuộc tính trong U, AUK thì phải tồn tại một khoá K trong Key(p) để AK. Do Key(p) = Key(q) nên K = Key(q). Từ đây ta suy ra K  U\X hay là KX = . Điều chỉnh mâu thuẫn với AK và AX. Vậy ta phải có XUo (Suy từ bổ đề về khoá trong phép thu gọn LĐQH). 2. Đẳng thức Key(p) = XKey(q) cho biết X có mặt trong mọi khoá của p, tức là XUI. Giả sử XUI. Ta sẽ chứng minh rằng mọi khoá KKey(p) đều được biểu diễn dạng XM, trong đó MKey(q) và ngược lại, nếu MKey(q) thì MXKey(p). Cho K=Key(p). Khi đó , vì XUI nên X phải có trong mọi khoá của p, nói riêng X K. Đặt M=K\X, ta có MX= và K=XM. Theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta suy ra M=K\X là siêu khoá của q. Giả sử M chứa một siêu khoá P của q. Khi đó XP lại là siêu khoá của p và XPK. Vì K là khoá của p nên XP = K = XM. Để ý rằng XP = XM = , ta suy ra P = M. Vậy M là khoá của q. Cho MKey(q). Ta có XM = . Theo bổ đề về siêu khoá trong phép thu gọn LĐQH thì XM là siêu khoá của p. Gọi K là khoá của p chứa trong siêu khoá XM. Lại theo bổ đề về siêu khoá trong phép thu gọn LĐQH, K\X là siêu khoá của q. Vì K là khoá của p và X  UI nên X  K. Từ đây suy ra K\X=M, hay K = XM. Điều này chứng tỏ XM là khoá của p.  Ví dụ 11: 1. Cho LĐQH p = (U,F). Với U = ABCDEH. F={AED, BCE} Gọi UI là giao các khoá. Ta có: UI = ABCDEH\DE = ABCH. Đặt q = (V,G) với V=U\ABCH = DE, G=F\ABCH={ED, E}. Ta tính được Key(q) = {}. Vậy Key(p) = ABCH  Key(q) = {ABCH} 2. Với lược đồ đã cho ta tính được UK = ABCH, suy ra Uo=U\UK =ABCDEH\ABCH = DE. Đặt c = p\DE = (P,W). P = U\DE = ABCH. W = F\DE = {A(loại), BC(loại)}  . Do đó Key(c) = ABCH. Theo định lý thứ nhất về cách biểu diễn khoá, vì Uo = DE nên Key(p) = Key(c) = ABCH.  Ví dụ 12: 1. Cho LĐQH p = (U,F). Với U = ABCDEHIK. F={ABC, CEH, HAB} Ta tính được UI = U\ABCEH = DIK. Ta thu gọn lược đồ a theo DIK ta được: LĐQH q = (V,G). V=U\DIK=ABCEH. G = {ABC, CEH, HAB} Ta tính được Key(q) = H. Vậy Key(p) = DIKKey(q) = DHIK. 2. Với lược đồ trên ta tính được UK = DHIK  Uo = U\UK = ABCDEHIK\DHIK = ABCE. Đặt c = p\ABCE =(P,W) ta có P = U\ABCE = DHIK. W=F\ABCE = { (loại) , H, H (loại)}  . Suy ra Key(c) = DHIK. Theo định lý thứ nhất về cách biểu diễn khoá, vì Uo = ABCE nên: Key(p) = Key(c) = DHIK. 2.7.1 Hệ quả về phép thu gọn LĐQH theo các bộ phận không khoá và các giao khoá Cho LĐQH p = (U,F) và các tập thuộc tính XUo, YUI. Nếu thực hiện phép thu gọn theo XY để nhận được LĐQH q = p\XY thì: Key(p) = Y  Key(q) Chứng minh Do XUo, YUI nên XY = . Đặt c = p\X, ta có q = p\XY = (p\X)\Y = c\Y. Áp dụng dạng biểu diễn thứ nhất của khoá ta thu được: Vì XUo nên Key(p) = Key(c) và do giao các khoá của c vẫn là UI Xét trong c nên Key(c) = YKey(q). Vậy Key(p) = Y  Key(q).  Ví dụ 13: Cho LĐQH a = (U,F).Với U = ABCDEHIK. F= {ABC, DEH, HI } Ta có UI = U\CEHI = ABDK, UK = ABDK. Ta có Uo = U\UK = U\ABDK = CEHI. Ta thu gọn p theo X = Uo và Y = UI ta được: LĐQH q = p\XY = (V,G) . V = U\XY = U\U = . G = F\XY =  suy ra Key(q) = . Vậy Key(p) = YKey(q) = ABDK. 2.8 Định lý thứ hai về cách biểu diễn khoá Cho LĐQH p = (U,F). Khi đó mọi khoá K của p đề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à khoá của LĐQH p\L+. Chứng minh Giả sử K  Key(p). Nếu K=U thì đương nhiên chứa mọi vế trái của PTH trong F, khi đó ta chọn một vế trái cực tiểu tuỳ ý. Giả sử K  U, khi đó để tính bao đóng K+ ta phải tìm được một PTH f: XY  F thoả 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 số vế trái cực tiểu này. Như vậy ta đã chứng minh được rằng mọi khoá 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à khoá của LĐQH p\L+. Nếu L+ = U thì p\L+ = p\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 khoá L+ K = L hay K\L = K\L+ = M. Từ đây suy ra MU\L+. Theo bổ đề về siêu khoá trong phép thu gọn LĐQH, M sẽ là siêu khoá của lược đồ p\L+ . Giả sử M chứa siêu khoá P của lược đồ p\L+. Khi đó theo bổ đề về siêu khoá trong phép thu gọn LĐQH, L+P sẽ là siêu khoá của p, do đó (L+P)+ = U. Áp dụng tính chất của bao đóng ta có (L+P)+ = (LP)+ = U, do đó LP là siêu khoá của p. Vì P  M  K = LM nên LPK. Vì K là khoá của p 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à khoá của p\L+ . 2.8.1 Định nghĩa tập các vế trái cực tiểu Cho LĐQH p = (U,F). Ta ký hiệu ML(F) là tập các vế trái cực tiểu của F, ML(F) = MIN{LS(f)|fF}. 2.8.2 Bổ đề vế trái cực tiểu Cho LĐQH p = (U,F). Nếu L ML(F) thì L  Key(p) khi và chỉ khi L+ = U.  Ví dụ 14: Cho lược đồ quan hệ p = (U,F). U= ABCDEH. F = { AED, AC, EBC, EHA, ACEH, BDC } Ta có ML (F) = {A,E,BD}. - Trường hợp 1: Xét A trong ML(F). Ta thấy A+ = ABCDEH = U. Vậy A là khoá của p. - Trường hợp 2: Xét E trong ML(F). Ta thấy E+ = EBC U. Vậy E không phải là khoá của p. Ta thu gọn p theo E+. Đặt q = p\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ễ dàng thấy H là một khóa của q. Như vậy EH là khoá của p, trong đó E là một vế trái cực tiểu, H là khoá của p\E+. - Trường hợp 3: Xét BD trong ML(F). Ta thấy BD+ = BDC ≠ U. Vậy BD không phải là khoá của p. Ta thu gọn p theo BD+. Đặt q = p\BD+ = (V,G). Ta có V = ABCDEH\BCD = AEH, G = F\BCD = {AE (loại), A (loại), E (loại), EHA, AEH,  (loại)} = { EHA, AEH }. Dễ dàng thấy Key(q) = {A,EH}.Ta thấy {A, EH} lại là khoá của p trong 2 trường hợp trên.  Như vậy p có 2 khoá Key(p) = {A, EH} Chú ý: Ở ví dụ này, trong trường hợp 2 ta đã tính được LĐQH q = p\E+ = (V,G), V=ADH, G={ADH, HA}. Ngoài khoá H, lược đồ q còn có khoá A, tuy nhiên EA không phải là khoá riêng của p vì bản thân A đã là khoá của p.  Ví dụ 15: Minh hoạ 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ỳ khoá nào. Xét LĐQH p = (U,F), Với 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, (AE)+ = ADE  U nên AE không thể là khoá. Ta chứng tỏ rằng vế trái cực tiểu AE không có bất kỳ khoá nào. Thật vậy, vì (AE)+ = ADE nên để xây dựng một khoá chứa AE ta cần thêm vào AE một vài thuộc tính khác với A, D và E cụ thể là B hoặc C. Nếu thêm cho AE một thuộc tính B thì ABE chứa khoá BE; nếu thêm cho AE thuộc tính C thì ACE chứa khoá CE. Vậy vế trái cực tiểu AE không thể là bộ phận của bất kỳ khoá nào của p. Bổ đề sau đây cho ta một dấu hiệu tạo và chọn các khoá từ tập khoá của lược đồ thu gọn. 2.8.3 Bổ đề các khoá sinh từ khoá của lược đồ sau khi thu gọn Cho LĐQH p = (U,F) và vế trái cực tiểu L. Khi đó nếu KLKey(p\L+) và K không chứa vế trái cực tiểu nào khác ngoài L thì K là khoá của p. Chứng minh Giả sử ta có phân hoạch K = LM, MKey (p\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 khoá trong phép thu gọn LĐQH thì K là siêu khoá của p. Gọi P là khoá của p 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 khoá P nên theo định lý về đặc trưng của khoá ta có: L+ P = L hay P\L+ = P\L = Q. Theo bổ đề về siêu khoá trong phép thu gọn LĐQH, Q sẽ là siêu khoá của p\L+. Vì M cũng là khoá của p\L+ và QM nên Q = M và do đó: P = LQ = LM = K. Vậy K là khoá của p.  Ví dụ 16: Xét LĐQH a = (U,F). Với 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, E+ = EBC U. Vậy E không phải là khoá của p. Ta thực hiện phép thu gọn lược đồ p theo E+. Ta có q = p\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(q) = {A, H}, do đó EKey(q) = {EA,EH}. Thành phần EH không chứa thêm vế trái cực tiểu nào khác, do đó EH là khoá của p.  Ví dụ 17: Xét LĐQH a = (U,F), U = ABCD, F = {AB, CD}. Ta có khoá K=AC chứa đồng thời 2 vế cực trái cực tiểu A và C. Vậy, ta thấy rằng tồn tại LĐQH có khoá chứa một vài vế trái cực tiểu. 2.8.4 Bổ đề Cho LĐQH p = (U,F) và vế trái cực tiểu L. Khi đó MKey(p\L+), thì mọi khoá K của p chứa trong LM đều phải chứa M. Chứng minh Ta đã biết LM là siêu khoá. Giả sử K là khoá của p và K LM. Ta xét phân hoạch K = P|Q, trong đó P = KL, Q = KM. Vì LM = L+M =  nên PQ=. Theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta có K\L+ = K\L = PQ\L = Q là siêu khoá của a\L+ . Do đó, theo tính chất tối tiểu của khoá ta phải có Q= M, hay K  M. Bổ đề trên cho phép ta xây dựng thuật toán GetKey nhận một khoá từ tập LML  Key(p\L+) với L là vế trái cực tiểu của LĐQH nguồn p. Trước hết ta để ý rằng LM đã là một siêu khoá của LĐQH p. Như vậy, để tìm khoá 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 khoá của a có trong LM.  Thuật toán Algorithm GetKey //Tìm một khoá từ LM Format: GetKey (U,F,L,M) Input: - Vế trái cực tiểu L của LĐQH p = (U,F) - M Key (p\L+) Output: - Khoá K của lược đồ p 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; EndGetKey.  Ví dụ 18: Cho LĐQH p = (U,F). Với U = ABCDEHG. F = { DE  G, H  C, E  A, CG  H, DG  EA, D  B}. Tìm Key (p)? Ta có vế trái cực tiểu ML(F) = {D,E,H,CG} Tính D+ = DB; E+ = EA; H+ = HC; CG+ = CGH - Với L = D ta có: q = p\L+ = p\DB = (ACEHG,{EG, HC, CGH, GEA}). Ta dễ dàng tính được M = Key (b) = {GH,CE,HE}. Suy ra: Key(p) = LM={DGH,DCE,DHE} - Với L = E ta có: q = p\L+= p\EA = (BCDHG, {DG, HC, (loại), CGH, DG(loại), DB}) = (BCDHG, DBG, HC, CGH}). Ta dễ dàng tính được M = Key(q) = {CD,DH}. Suy ra Key(p) = LM = {ECD,EDH}. - Với L = H ta có: q = p\L+ = p\HC = (ABDEG, {DEG, (loại), EA, G(loại), DGEA, DB} = (ABDEG, {DEG, EA, DGEA, DB}). Ta tìm được M = Key(q) = {DG,DE}. Suy ra Key(p) = LM = {HDG,HDE}. - Với L = CG ta có q = p\L+ = p\CGH = (ABDE, {DE(loại), (loại), EA, (loại), DEA, DB} = (ABDE, {EA, DEAB}). Ta tìm được M = Key(q) = D. Suy ra Key (p) = LM = CGD. Như vậy ta có: Key (p) = {DGH,DCE,DEH, CGD}. 2.9 Lược đồ cân bằng LĐQH p = (U,F) được gọi là cân bằng nếu tập PTH F trong p thoả các tính chất sau đây: 1. Hợp các vế trái, các vế phải của các PTH trong F đúng bằng tập thuộc tính U: LS(F) = RS(F) = U 2. F không chứa các PTH tầm thường, tức là các PTH có vế trái chứa vế phải: X,YU: XY  (XYF) 3. Cả hai vế trái và phải của mọi PTH trong F rời nhau (không giao nhau): f  F: LS(f)RS(f) =  4. Các vế trái của mọi PTH trong F khác nhau đôi một: f, g  F: LS(f) = LS(g)  f = g Các tính chất thứ 2, 3, 4 cho biết F có dạng thu gọn tự nhiên. Như vậy LĐQH là cân bằng khi và chỉ khi tập PTH có dạng thu gọn tự nhiên và mọi thuộc tính đều xuất hiện ít nhất một lần ở vế trái, một lần ở vế phải.  Ví dụ 19: 1. Cho LĐQH p = (U,F). Với U = ABCD và F = {ADC, BAC, BCA, DB}. Suy ra p = (U,F) là lược đồ cân bằng. 2. Nếu thêm cho U một thuộc tính, chẳng hạn E và giữ nguyên tập PTH thì thu được một LĐQH không cân bằng q = (UE,F) vì tính chất 1 bị vi phạm: LS(F) = RS(F) = ABCD  ABCDE. 2.9.1 Một số tính chất của lược đồ cân bằng Ngoài các tính chất trên, lược đồ cân bằng (LĐCB) còn có những tính chất sau đây: 5. Nếu tập PTH F trong LĐQH p = (U,F) ở dạng thu gọn tự nhiên và chỉ có một PTH thì p không thể là LĐCB. Thật vậy, nếu F = {XY} và F ở dạng thu gọn tự nhiên thì: LS(F) = X  Y = RS(F), vi phạm tính chất 1. 6. Từ tính chất 5 ta suy ra LĐQH chỉ có một thuộc tính thì không thể là LĐCB. Thật vậy, gọi thuộc tính duy nhất là A, ta chỉ thấy có 4 khả năng tạo các PTH sau đây: a. AA (Tầm thường) b. A (Tầm thường) c.  (Tầm thường) d. A Như vậy chỉ có thể chọn U=A và F= hoặc F={A}. - Trường hợp 1: U=A, F= cho ta LS(F) = RS(F) =   U. - Trường hợp 2: U=A, F={A} cho ta LS(F)=  A=RS(F). Cả hai trường hợp đều không cho LĐCB. Để ý rằng trường hợp U= và F= ta có LĐCB (,). 7. Trong LĐCB p = (U,F), tập giao các khoá UI = . Thật vậy theo công thức tính giao các khoá và theo tính chất 3 fF: RS(f)LS(f) =  ta suy ra : fF: RS(f)\LS(f) = RS(f) Do đó  FfFf fRSfRSfLSfRSM   )()())(\)(( theo tính 1 ta có: RS(F)=U, do đó UI = U\M = U\U = . 2.9.2 Thuật toán thu gọn LĐQH về dạng cân bằng Algorithm BS // Thu gọn LĐQH về dạng cân bằng Format: BS(a) Input: - LĐQH p = (U,F) Output: - LĐCB q = (V,G) Method 1. Đưa F về dạng thu gọn tự nhiên G:=Natural_Reduced(F); 2. Tính giao các khoá UI := U\RS(G); 3. Tính lượng thu gọn M 3.1. P := RS(G)\LS(G) 3.2. M := (PUI)G+ 3.3. Tạo LĐQH q = (V,G); V:=U; G:=F; 4. While M   do 4.1. Thu gọn q theo M q:=q\M; // q= (V,G); V:=V\M; G:=G\M 4.2. Loại khỏi G các PTH dạng X 4.3. Nhóm các PTH có cùng vế trái trong G XY1, XY2,....,XYk thành XY1Y2...YK; 4.4. M := V\LS(G); Endwhile; 5. Return(q); End BS.  Ví dụ Cho LĐQH p = (U,F). Với tập thuộc tính U = ABCDEH . Tập PTH F = {AED, BCCE, EB, EC, HC}. Theo thuật toán BS ta có: 1. G := Natural_Reduced(F) = {AED, BCE, EBC, HC} 2. RS(G) = BCDE; UI = U\RS(G) = ABCDEH\BCDE = AH 3. LS(G) = ABCEH; 3.1. P = RS(G)\LS(G)=BCDE\ABCEH = D 3.2. M = (PUI)+ = (ADH)+ = ACDH 3.3. Xét LĐQH q = (V, G); V = ABCDEH, G = {AED, BCE, EBC, HC}. 4. Lặp 4.1. q = (V,G) = q\M = q\ACDH; V = ABCDEH\ACDH = BE; 4.2. G = G\ACDH = {E(loại), BE, EB, (loại)} 4.3. G = {BE, EB} 4.4. M = V\LS(G) = BE\BE =  5. Kết quả: q = (V,G); V = BE; G = {BE, EB}. 2.9.3 Định lý 1 LĐQH thu được sau khi thực hiện thuật toán BS là lược đồ cân bằng. Chứng minh Để ý rằng sau bước 1 của thuật toán BS ta thu được phủ tự nhiên G của F, nghĩa là G đã thoả các tính chất 2-4. Ta rút ra nhận xét sau đây: Nếu PTH G thoả tính chất 3 thì sau khi thực hiện phép thu gọn G:= G\M tính chất 3 vẫn được bảo toàn. Vậy tính chất 3 là bất biến của vòng lặp While trong thuật toán BS. Nếu G có chứa PTH tầm thường thì PTH đó chỉ có thể ở dạng X, bởi vậy nếu XY và XY thì theo tính chất 3 ta suy ra XY = Y = . Trước hết ta chứng minh rằng nếu lược đồ q = (V,G) đã ở dạng thu gọn tự nhiên, nghĩa là đã thoả các tính chất 2-4 thì sau bước 4.1 của thuật toán BS ta thu được LĐQH thoả tính chất 1. Thật vậy lúc đầu ta có, P = RS(G)\LS(G), M = (PUI)G+, V = U và G = F. Theo tính chất 3 của G ta có f  G: RS(f)LS(f) = , hay: RS(f)\LS(f) = RS(f) và do đó  GRL I GRSULRUU   )(\)\(\ Ta có  Gf MGLSMfLSGLS   \)()\)(()( tương tự RS(G) = RS(G)\M Ta chứng minh đẳng thức LS(G)\M = RS(G)\M = V\M theo sơ đồ sau: LS(G)\M  V\M  RS(G)\M  LS(G)\M Tại bước lặp đầu tiên ta có, a) LS(G)\M  V/M. Hiển nhiên b) V\M  RS(G)\M. Nếu AV\M thì AM = (PUI)G+  UI , do đó AUI = V\RS(G). Từ đó suy ra ARS(G) và do đó ARS(G)\M. c) RS(G)\M  LS(G)\M. Nếu ARS(G)\M thì A RS(G), và AM = (PUI)G+  P, do đó AP = RS(G)\LS(G). Từ đây suy ra ALS(G) và do đó ALS(G)\M. Từ lần lặp thứ hai trở đi, tại bước 4.2 của thuật toán, sau khi loại bỏ các phụ thuộc hàm dạng X khỏi G, các tập V và RS(G) không thay đổi, cụ thể là đẳng thức V = RS(G) vẫn bảo toàn. Tuy nhiên, tập LS(G) có thể bị giảm đi. Như vậy là sau bước 4.2 tính chất 1 có thể bị vi phạm. Vòng lặp while có nhiệm vụ cân bằng 3 tập V, LS(G) và RS(G), trong đó V = RS(G). Muốn vậy, trước hết phải tính lượng chênh lệch M := V\LS(G) tại bước 4.4. Theo bổ đề các thuộc tính phi nguyên thuỷ ta có MUo. Nếu M ta tiếp tục thu gọn lược đồ q = (V,G) theo lược chênh lệnh M. Vì MUo nên tập khoá Key(q) luôn luôn được bảo toàn. Vì LĐQH lúc đầu là hữu hạn và các phép thu gọn đều thu nhỏ kích thước của tập V, LS,và RS nên đến một lúc nào đó ta phải thu được điều kiện kết thúc vòng lặp, cụ thể là M=. Ta chỉ cần chứng minh rằng khi kết thúc vòng lặp, tức là khi M= ta sẽ thu được lược đồ thoả tính chất 1. Thật vậy, từ M= ta suy ra V=LS(G), kết hợp với bất biến V=RS(G) của vòng lặp ta thu được tính chất 1: LS(G) = RS(G) = V. 2.9.4 Định lý 2 Mọi lược đồ quan hệ p = (U,F) đều đưa về dạng cân bằng q = (V,G) thoả tính chất Key(p) = UI  Key(q) Trong đó UI là giao các khoá của p. Thuật toán thu gọn có độ phức tạp đa thức theo chiều dài dữ liệu vào O(n2m), n là số thuộc tính trong U, m là số PTH trong F. Chứng minh Thuật toán BS đưa LĐQH p về LĐQH q. Theo bổ đề trên LĐQH q thoả các tính chất 1-4 của LĐCB. Ngoài ra theo bổ đề về thu gọn LĐQH theo các bộ phận không khoá và giao các khoá ta nhận được hệ thức: Key (p) = UI  Key (q). Mọi bước của thuật toán BS đều có độ phức tạp không quá O(nm). Vì M là tập thuộc tính có tối đa n phần tử do đó để M tiến đến , vòng lặp While cần thực hiện tối đa n lần. Tổng hợp lại, độ phức tạp của thuật toán BS là O(n2m).  Ví dụ Cho LĐQH p = (U,F). Với tập thuộc tính U = ABCDEH. Tập PTH F = {AED, BCCE, EB, EC, HC}. Sau khi đưa tập PTH F về dạng thu gọn tự nhiên {AED, BCE, EBC, HC} và tính được UI =U\BCDE = AH, ta thu gọn p về lược đồ cân bằng q = (V,G), V = BE, G = {BE, EB}. Dễ thấy q có hai khoá, cụ thể là Key (q) = {B,E}. Từ đây suy ra Key(p) = UI  Key(q) = AH  {B,E} = {AHB, AHE}. CHƯƠNG III: CÀI ĐẶT CHƯƠNG TRÌNH ỨNG DỤNG KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU 3.1 Giới thiệu Cơ sở dữ liệu là một trong những chuyên ngành quan trọng bậc nhất trong lĩnh vực công nghệ thông tin. Hầu hết, cơ sở dữ liệu được vận dụng để xây dựng những phần mềm nhằm đáp ứng các yêu cầu trong thực tế. Tuy nhiên, những phần mềm được xây dựng để hỗ trợ việc thiết kế và kiểm tra tính chất của cơ sở dữ liệu là chưa nhiều. Trong luận văn này, em tập trung tìm hiểu và nghiên cứu các phép biến đổi lược đồ quan hệ, đặc biệt là tìm hiểu sâu về kỹ thuật thu gọn lược đồ quan hệ. 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ễ hiểu, dễ sử dụng và được viết bằng ngôn ngữ C# , một ngôn ngữ hướng đối tượng khá phổ biến, cho phép tạo giao diện nhanh, dễ dàng. Chương trình cho phép tạo lược đồ quan hệ mới, lưu và có thể mở tệp đã có sẵn trong máy. Các chức năng chính của chương trình bao gồm: Tìm phủ tối thiểu của tập phụ thuộc hàm, tìm bao đóng của tập thuộc tính được nhập từ bàn phím, tìm khóa, các dạng biểu diễn khóa và giao các khóa. Đặc biệt, chương trình xây dựng chức năng ứng dụng kỹ thuật thu gọn lược đồ quan hệ để 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. 3.2 Một số giao diện của chương trình 3.2.1 Giao diện chính Hình 3.1. Giao diện chính 3.2.2 Giao diện tạo lược đồ quan hệ mới Hình 3.2. Giao diện tạo LĐQH mới 3.2.3 Giao diện ghi dữ liệu Hình 3.3. Giao diện tạo ghi dữ liệu 3.2.4 Giao diện mở dữ liệu Hình 3.4. Giao diện tạo mở dữ liệu 3.2.5 Giao diện xử lý Hình 3.4. Giao diện xử lý 3.2.6 Giao diện Help Hình 3.4. Giao diện Help 3.3 Hướng dẫn sử dụng a. Tạo một lược đồ quan hệ mới File/New  cửa sổ nhập dữ liệu, dữ liệu được xử lý dưới dạng văn bản. Tập thuộc tính U được nhập đầu tiên với các chữ cái Latin viết liền không có ký tự trống. Sau khi nhập xong tập thuộc tính ta có thể Enter, hoặc cách, hoặc phẩy để nhập tiếp tập phụ thuộc hàm, các phụ thuộc hàm có thể được ngăn cách nhau bằng ký tự trống hoặc enter hoặc dấu phẩy. Tiếp theo Click nút Save để ghi, chương trình mặc định với đuôi .inp. b. Mở một quan hệ đã có File/Open (CTRL+O)  xuất hiện hộp thoại c. Tìm khoá Click vào nút Tìm khoá để tìm khoá của lược đồ p. Kết quả hiện trong ô kết quả. d. Tìm bao đóng của tập thuộc tính Nhập tập thuộc tính thuộc U vào hộp X. Bấm chuột nút Tìm bao đóng, kêt quả hiện ở ô kết quả. e. Tìm tập giao của các khoá Bấm chuột vào nút Tìm giao khoá, giao của khoá hiển thị trong ô Ui. g. Tìm cực tiểu vế trái Bấm chuột vào nút cực tiểu vế trái, các vế trái cực tiểu được hiển thị trong ô ML(F). h. Thu gọn theo M Ta nhập tập thuộc tính cần thu gọn vào ô M. Bấm chuột nút Thu gọn. Kết quả hiển thị lược đồ quan hệ q = p\M. i. Tìm khoá của lược đồ q Bấm chuột vào nút Tìm Key(q), kết quả hiện trong ô kết quả. j. Biểu diễn thứ nhất của khoá Sau khi tìm được khoá của lược đồ q, ta bấm vào nút Biểu diễn khoá thứ nhất, kết quả là khoá của lược đồ quan hệ p được hiển thị theo công thức biểu diễn khoá. k. Biểu diễn thứ 2 của khoá Sau khi tìm được khoá của lược đồ q và tìm được cực tiểu vế trái, ta bấm vào nút Biểu diễn thứ hai ta được kết quả là khoá của lược đồ p. KẾT LUẬN VÀ KIẾN NGHỊ 1. Kết luận Những nội dung chính đã được giải quyết trong luận văn Về lý thuyết: - Tìm hiểu kỹ thuật thu gọn lược đồ quan hệ - Định lý về công thức biểu diễn bao đóng theo phép thu gọn - Bổ đề về khóa, siêu khoá trong phép thu gọn - Khái niệm và tính chất của lược đồ cân bằng - Hai dạng biểu diễn khoá thông qua phép thu gọn. Về thực nghiệm: - Luận văn 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: o Tìm phủ tối thiểu o Tìm bao đóng o Tìm khóa, tìm giao các khóa o Hai cách biểu diễn khóa o Thu gọn LĐQH theo tập thuộc tính M ... 2. Kiến nghị - Vận dụng phép thu gọn lược đồ quan hệ trên có thể thiết kế một cở sở dữ liệu lớn có tính thực tiễn cao - Có thể phát triển ánh xạ đóng trên phép thu gọn - Tiếp tục xây dựng và hoàn thiện phần mềm hỗ trợ thiết kế cở sở dữ liệu dựa trên kỹ thuật thu gọn và áp dụng với cơ sở dữ liệu cụ thể. TÀI LIỆU THAM KHẢO Tiếng Việt 1. 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. 2. 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ê. 3. 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. 4. J.D Ullman Tập 1,2 (2001), Trần Đức Quang biên dịch, Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức, Nxb Thống kê. 5. Lê Tiến Vương (1999), Nhập môn cơ sở dữ liệu quan hệ, Nxb Thống kê. 6. Vũ Đức Thi (1997), Cơ sở dữ liệu: Kiến thức và thực hành, Nxb Thống kê. Tiếng Anh 7. Demetrovic J., Nguyen Xuan Huy (1991), Closed Sets and Translations of Relation Schemes, Computers math applic.