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