Tài liệu Các dạng biểu diễn khóa trong lược đồ quan hệ

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUNG CÁC DẠNG BIỂU DIỄN KHÓA TRONG LƯỢC ĐỒ QUAN HỆ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên – 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUNG KEY REPRESENTATIONS IN RELATIONAL SCHEMATA Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TSKH NGUYỄN XUÂN HUY Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CẢM ƠN Lời đầu tiên, em xin bày tỏ lòng cảm ơn và kính trọng sâu sắc đối với Thầy PGS.TSKH Nguyễn Xuân Huy, người đã tận tình hướng dẫn em trong suốt quá trình làm luận văn này. Thầy giúp em hiểu và tiếp cận 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 rất thiết thực và bổ ích. Em đã học hỏi được rất nhiều ở Thầy cũng như phong cách làm việc, phương pháp tiếp cận tri thức....Em luôn được Thầy chỉ bảo tận tình trong suốt quá trình làm luận văn. Em cũng xin thể hiện sự kính trọng và biết ơn đến Quý Thầy Cô trong ĐHCNTT-TT, trang bị cho chúng em đầy đủ về cơ sở vật chất cũng như tài liệu chuyên ngành.... Cuối cùng em xin cảm ơn các bạn học viên trong lớp Cao học K9A, những người luôn bên cạnh và cung cấp những 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 06 năm 2012 Học viên Nguyễn Thị Dung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii LỜI CAM ĐOAN Tôi xin cam đoan, luận văn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii MỤC LỤC Trang Lời cảm ơn ................................................................................................... i Lời cam đoan ................................................................................................ ii Mục lục ......................................................................................................... iii Danh mục các kí hiệu, chữ cái viết tắt ......................................................... v Danh mục hình vẽ ........................................................................................ vi MỞ ĐẦU ...................................................................................................... 1 Chƣơng I: CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU 5 1.1 Khái quát về cơ sở dữ liệu quan hệ ............................. 5 1.2 Lược đồ quan hệ...........................................................7 1.3 Phụ thuộc hàm...............................................................7 1.3.1 Định nghĩa phụ thuộc hàm............................................7 1.3.2 Hệ tiên đề Armstrong....................................................8 1.3.3 Bao đóng của tập phụ thuộc hàm..................................8 1.4 Bao đóng của tập thuộc tính..........................................8 1.5 Khóa của lược đồ quan hệ............................................11 1.5.1 Cách tính giao các khóa...............................................14 1.5.2 Thuật toán tìm 2 khóa của LĐQH................................15 1.5.3 Các ví dụ......................................................................16 Chƣơng II: THU GỌN LƢỢC ĐỒ QUAN HỆ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 21 iv 2.1 Định nghĩa kỹ thuật thu gọn LĐQH..............................22 2.2 Thuật toán thu gọn LĐQH.............................................23 2.3 Các ví dụ........................................................................23 2.4 Bổ đề về siêu khóa trong phép thu gọn LĐQH.............25 2.5 Hệ quả về siêu khóa trong phép thu gọn LĐQH...... ....26 2.6 Bổ đề về khóa trong phép thu gọn LĐQH....................27 Chƣơng III: CÁC DẠNG BIỂU DIỄN KHOÁ TRONG 29 LƢỢC ĐỒ QUAN HỆ 3.1 Dạng biểu diễn thứ nhất của khoá................................29 3.1.1 Các ví dụ.......................................................................30 3.1.2 Hệ quả về phép thu gọn LĐQH....................................35 3.2 Dạng biểu diễn thứ hai của khoá..................................35 3.2.1 Các ví dụ.......................................................................36 3.2.2 Định nghĩa tập các vế trái cực tiểu...............................42 3.2.3 Bổ đề vế trái cực tiểu....................................................42 3.2.4 Bổ đề các khóa sinh ra từ khóa của lược đồ.................45 3.2.5 Bổ đề.............................................................................48 3.3 Giới thiệu......................................................................50 3.4 Một số giao diện của chương trình...............................52 3.5 Các ví dụ......................................................................56 TÀI LIỆU THAM KHẢO ............................................................................ 60 1. Kết luận .................................................................................................... 59 2. Kiến nghị .................................................................................................. 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v 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ệ PTH Phụ thuộc hàm FD Phụ thuộc hàm  Thuộc  Là con  Chứa ╞ Suy dẫn logic ├ Suy dẫn theo quan hệ SAT(F) Là tập toàn thể các quan hệ trên U thỏa tập PTH F X+ Bao đóng của tập thuộc tính X \ Phép trừ logic  Phép giao  Phép hợp ≡ Tương đương !≡ Không tương đương ≠ Khác  Với mọi LS(F) Tập các vế trái của phụ thuộc hàm F RS(F) Tập các vế phải của phụ thuộc hàm F Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi DANH MỤC HÌNH VẼ Hình 3.4.1 Giao diện chính ................................................................ 52 Hình 3.4.2 Giao diện nhập các thuộc tính ......................................... 53 Hình 3.4.3 Giao diện nhập các PTH .................................................. 53 Hình 3.4.4 Giao diện dạng thứ nhất biểu diễn khóa .......................... 54 Hình 3.4.5 Giao diện dạng thứ hai biểu diễn khóa ............................ 55 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU Cơ sở khoa học của luận văn 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. Cùng với sự phát triển của công nghệ thông tin, việc sử dụng các kiến thức về cơ sở dữ liệu ngày càng trở lên cần thiết. 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. Trong thực tế phụ thuộc dữ liệu nào cũng giới hạn ở việc so sánh hai bộ theo đẳng thức, nghĩa là chỉ so sánh từng cặp trị tương ứng của hai bộ đó xem chúng giống hay khác nhau. Ở đây từ kỹ thuật thu gọn các 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... Chẳng hạn như nếu dịch chuyển LĐQH a=(U,F) thu được LĐQH b=a/X(X  U) thì ta có khoá của LĐQH a sẽ được biểu diễn như thế nào hay nếu ta có K=LM với L là vế trái cực tiểu của F thì M phải được tính như nào?. Vậy là 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ề Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 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. Mục tiêu và nhiệm vụ của luận văn Đề tài này tập trung vào tìm hiểu nghiên cứu cách biểu diễn khóa trong lược đồ quan hệ qua thuật toán thu gọn lược đồ quan hệ theo thuộc tính khóa hay giao các khóa cũng như tập các vế trái cực tiểu. Như vậy theo nhận xét tự nhiên khi dịch chuyển lược đồ quan hệ về kích thước càng nhỏ thì thuật toán càng phát huy hiệu quả. Phạm vi nghiên cứu Phạm vi nghiên cứu của đề tài 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 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 lược đồ quan hệ - Thu gọn lược đồ quan hệ - Các dạng biểu diễn khóa trong lược đồ quan hệ 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ơ sở toán học 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 đủ 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 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. Phạm vi nghiên cứu 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 tong 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 LĐQH - Thu gọn LĐQH - Các dạng biểu diễn khóa của LĐQH Cấu trúc của luận văn Cấu trúc của luận văn gồm: - Phần mở đầu - Chương 1, 2 và 3 - Phần kết luận và đề nghị - Tài liệu tham khảo Nội dung chính của luận văn Chương 1 giới thiệu các kiến thức cơ bản về CSDL, các định nghĩa về quan hệ, thuộc tính, bộ. Phụ thuộc hàm cũng như thuật toán tính bao đóng của các tập thuộc tính, tìm khóa của LĐQH. Chương 2 trình bày một kỹ thuật thu gọn LĐQH hay còn gọi là phép dịch chuyển LĐQH. 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...Và 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 trở thành 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. Chương 3 là chương mang nội dung trọng tâm của đề tài, chương này trình bày về hai dạng biểu diễn khóa trong LĐQH. Dạng thứ nhất ta đi thu gọn LĐQH theo thuộc tính không khóa và giao các khóa. Dạng thứ hai ta đi tìm tập vế trái cực tiểu để từ đó có quyết định thu gọn LĐQH theo tập vế trái cực tiểu nào. Phần cuối cùng của chương 3 là cài đặt chương trình mô phỏng Các dạng biểu diễn khóa trong LĐQH. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Chƣơng I: 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 quan hệ 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. 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. Một cách giải thích rất trực quan cho bài toán quản lý được tổ chức theo hàng và cột, trong đó cột được 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 gọi là tiêu đề của 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ề đối tượng đang quản lý. Định nghĩa về Quan hệ, bộ, thuộc tính: 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 2 phần tử dom(Ai) được gọi là miền giá trị của Ai, gọi D là tập hợp 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 R(U) là một á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 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ộ. Ta kí hiệu t(U) là một bộ trên 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 http://www.lrc-tnu.edu.vn 6 Một quan hệ rỗng là một 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ó 2 bộ trùng lặp. Các kí hiệu và một số quy ƣớc Các thuộc tính được kí hiệu bằng các chữ LATINH HOA đầu bảng chữ A, B, C, D... Tập thuộc tính được kí hiệu bằng các chữ LATINH 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, i1... 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 giá trị của mọi thuộc tính chứa ít nhất hai phần tử. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 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ệ. 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 Artr(R) cho tập thuộc tính của quan hệ R Hàm Card(R) cho lực lượng (số bội) 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). 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 Artr(U) = Artr(S). 1.2. 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à 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.3. Phụ thuộc hàm 1.3.1 Định nghĩa phụ thuộc hàm 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) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 1.3.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+ thì 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 thỏa trong mọi quan hệ. 1.3.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.4. Bao đóng của tập thuộc tính Cho tập hợ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 hợp 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ổ xung dần cho X các thuộc tính thuộc vế phải của các PTH L  R  f thỏa điều kiện L  X. Thuật toán sẽ dừng khi không thể bổ xung thuộc tính nào cho X. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Algorithm Closure Format : Closure (X, F) Input : - Tập thuộc tính X  U - Tập PTH F 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  Đá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+ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 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ó 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ậpPTH F trên U - PTH f trên U Output: - True nếu f  F+, - False nếu f  F+ Method IsMember: = (RS(f)  End Closure (LS (f),F) IsMember. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn