Tài liệu Các thuật toán xử lý phụ thuộc hàm nới lỏng

ĐẠ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Ị LINH CÁC THUẬT TOÁN XỬ LÝ PHỤ THUỘC HÀM NỚI LỎNG Chuyên ngành: Khoa học Máy tính Mã số: 8 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TSKH NGUYỄN XUÂN HUY Thái Nguyên năm 2020 1 LỜI CAM ĐOAN Tên tôi là: Nguyễn Thị Linh Sinh ngày: 18/08/1989 Học viên lớp Cao học CK17A - Trường Đại học Công nghệ Thông tin và Truyền thông - Thái Nguyên. Tôi xin cam đoan toàn bộ nội dung liên quan tới đề tài được trình bày trong luận văn là do bản thân tôi tìm hiểu và nghiên cứu, dưới sự hướng dẫn khoa học của Thầy giáo PGS. TSKH. Nguyễn Xuân Huy. Các nội dung trong luận văn đúng như nội dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và trước pháp luật. Tác giả luận văn Nguyễn Thị Linh 2 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.TS 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 Trường ĐH CNTT&TT, trang bị cho chúng em đầy đủ về cơ sở vật chất cũng như tri thức để em hoàn thành khóa học. Cuối cùng em xin cảm ơn các bạn học viên trong lớp Cao học, 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, ngày 26 tháng 8 năm 2020 Học viên Nguyễn Thị Linh 3 MỤC LỤC LỜI CAM ĐOAN ..................................................................................................... 2 LỜI CẢM ƠN ........................................................................................................... 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ......................................... 8 DANH MỤC CÁC BẢNG........................................................................................ 9 DANH MỤC CÁC HÌNH ...................................................................................... 10 LỜI NÓI ĐẦU ......................................................................................................... 11 CHƯƠNG 1 CÁC KIẾN THỨC CƠ SỞ .............................................................. 16 1.1. Giới thiệu chung ................................................................................... 16 1.2. Định nghĩa về quan hệ, bộ, thuộc tính.................................................. 16 1.3. Bao đóng của tập thuộc tính.................................................................. 17 1.4. Các kí hiệu và một số quy ước .............................................................. 18 1.5. Lược đồ quan hệ và khóa của lược đồ quan hệ ................................... 19 1.5.1. Định nghĩa lược đồ quan hệ .......................................................... 19 1.5.2. Khóa của lược đồ quan hệ ............................................................. 19 1.6. Các phép toán quan hệ .......................................................................... 21 1.6.1. Phép chọn (phép lọc, Selection) .................................................... 21 1.6.2. Phép chiếu (Projection) ................................................................. 21 1.6.3. Phép kết nối tự nhiên (Natural Join) ............................................. 21 1.6.4. Phép cộng (hợp, Union) ................................................................ 22 1.6.5. Phép trừ (hiệu, Substraction/Minus) ............................................. 22 1.6.6. Phép giao (Intersection) ................................................................ 22 1.6.7. Phép chia (Division)...................................................................... 22 1.6.8. Thứ tự thực hiện các phép toán quan hệ ....................................... 22 1.6.9. Một số hàm tiện ích ....................................................................... 23 4 1.6.10. Một số ví dụ ................................................................................ 23 1.7. Phụ thuộc hàm ........................................................................................ 25 1.7.1. Các tính chất của phụ thuộc hàm .................................................. 27 1.7.2. Suy dẫn theo tiên đề (suy dẫn logic) ............................................. 27 1.7.3. Phủ................................................................................................. 28 1.8. Chuẩn hóa ............................................................................................... 30 CHƯƠNG 2 CÁC THUẬT TOÁN QUẢN LÝ LƯỢC ĐỒ QUAN HỆ ............ 32 2.1. Thuật toán tập hợp................................................................................. 32 2.1.1. Thuật toán tìm hợp của hai tập hợp .............................................. 32 2.1.2. Thuật toán tìm giao của hai tập hợp .............................................. 33 2.1.3. Thuật toán tìm hiệu của hai tập hợp .............................................. 34 2.3. Thuật toán tìm phủ không dư ............................................................... 36 2.4. Thuật toán tìm phủ tối tiểu ................................................................... 36 2.5. Thuật toán kiểm tra tính tổn thất của phép tách bằng kỹ thuật bảng................................................................................................................. 37 CHƯƠNG 3 CHƯƠNG TRÌNH THỬ NGHIỆM ............................................... 41 3.1. Lớp tập hợp Set ...................................................................................... 41 3.1.1. Cấu tử Set ...................................................................................... 42 3.1.2. Hàm Reset ..................................................................................... 42 3.1.3. Hàm Card ...................................................................................... 43 3.1.4. Hàm Empty ................................................................................... 43 3.1.5. Hàm IsIn ........................................................................................ 43 3.1.6. Toán tử gán tập hợp ...................................................................... 43 3.1.7. Toán tử lấy hợp của hai tập hợp .................................................... 43 3.1.8. Toán tử lấy giao của hai tập hợp ................................................... 44 5 3.1.9. Toán tử lấy hiệu của hai tập hợp ................................................... 44 3.1.10. Toán tử in ra tập hợp ................................................................... 44 3.1.11. Toán tử so sánh ........................................................................... 44 3.2. Lớp phụ thuộc hàm FD.......................................................................... 45 3.2.1. Cấu tử khởi tạo phụ thuộc hàm ..................................................... 46 3.2.2. Hàm đặt vào phụ thuộc hàm ......................................................... 46 3.2.3. Hàm lấy vế trái của phụ thuộc hàm .............................................. 46 3.2.4. Hàm lấy vế phải của phụ thuộc hàm ............................................. 46 3.2.5. Hàm thêm vào vế trái của phụ thuộc hàm..................................... 47 3.2.6. Hàm thêm vào vế phải của phụ thuộc hàm ................................... 47 3.2.7. Toán tử gán phụ thuộc hàm........................................................... 47 3.2.8. Toán tử in ra phụ thuộc hàm ......................................................... 47 3.3. Lớp lược đồ quan hệ RSC .................................................................... 47 3.3.1. Cấu tử khởi tạo lược đồ quan hệ ................................................... 48 3.3.2. Hủy tử của lược đồ quan hệ .......................................................... 49 3.3.3. Hàm gán giá trị rỗng cho lược đồ quan hệ .................................... 49 3.3.4. Hàm gán giá trị cho lược đồ quan hệ ............................................ 49 3.3.5. Hàm trả về khóa của lược đồ quan hệ ........................................... 50 3.3.6. Hàm mở rộng để đưa thêm phụ thuộc hàm ................................... 50 3.3.7. Toán tử gán lược đồ quan hệ ......................................................... 50 3.3.8. Hàm chèn thêm một lược đồ quan hệ ........................................... 50 3.3.9. Hàm chuẩn hóa tự nhiên ............................................................... 51 3.3.10. Hàm tìm bao đóng ....................................................................... 51 3.3.11. Hàm tìm khóa .............................................................................. 52 3.3.12. Hàm kiểm tra siêu khóa .............................................................. 52 6 3.3.13. Hàm kiểm tra khóa ...................................................................... 53 3.3.14. Hàm kiểm tra chuẩn BCNF ......................................................... 53 3.3.15. Hàm kiểm tra dẫn xuất ................................................................ 53 3.3.16. Hàm tìm phủ không dư ............................................................... 54 3.3.17. Toán tử in ra lược đồ quan hệ ..................................................... 54 3.4. Minh họa chương trình .......................................................................... 54 KẾT LUẬN ............................................................................................................. 63 TÀI LIỆU THAM KHẢO...................................................................................... 63 7 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu, chữ viết tắt Ý nghĩa CSDL Cơ sở dữ liệu ĐTB Điểm trung bình GV Giáo viên HB Học bổng HS Học sinh LĐQH Lược đồ quan hệ LĐQH Lược đồ quan hệ |X| Lực lượng của tập X 8 DANH MỤC CÁC BẢNG Bảng 3.1. Một số hàm và toán tử lớp tập hợp ................................................. 42 Bảng 3.2. Một số hàm và toán tử lớp phụ thuộc hàm ..................................... 46 Bảng 3.3. Một số hàm và toán tử lớp lược đồ quan hệ ................................... 48 9 DANH MỤC CÁC HÌNH Hình 3.1. Thử nghiệp với lớp Set ............................................................................ 56 Hình 3.2. Thử nghiệm với lớp FD ........................................................................... 57 Hình 3.3. Thử nghiệm với lớp RSC ......................................................................... 58 Hình 3.4. Thử nghiệm lớp RSC với cơ sở dữ liệu học sinh .................................... 60 Hình 3.5. Thử nghiệm lớp RSC với cơ sở dữ liệu thời khóa biểu ........................... 61 Hình 3.6. Thử nghiệm lớp RSC với cơ sở dữ liệu thiết bị ....................................... 62 10 LỜI NÓI ĐẦU 1. Đặt vấn đề Năm 1970 Codd đề xuất khái niệm phụ thuôc hàm như một cơ chế quản lý ngữ nghĩa dữ liệu trong cơ sở dữ liệu quan hệ [8], [9], [10]. Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng f: X  Y; X, Y  U trong đó ta gọi X là vế trái và Y là vế phải của PTH f. Cho quan hệ R(U) và một PTH f: X  Y trên U. Ta nói quan hệ R thoả PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống nhau trên Y, R(XY)  (u, vR): (u.X = v.X)  (u.Y = v.Y) Nếu f: X  Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc 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. Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY). Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH F, và viết R(F), nếu R thoả mọi PTH trong F: R(F)  ( f  F): R(f) Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ trên U thoả tập PTH F. Cho tập  các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng trong mọi quan hệ của . Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F + là tập nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề Armstrong Ao sau đây [1], [2], [3]:  X, Y, Z  U: F1. Tính phản xạ: Nếu X  Y thì X  Y  F + F2. Tính gia tăng: Nếu XY  F + thì XZYZ  F + F3. Tính bắc cầu: Nếu X  Y  F + và Y  Z  F + thì X  Z  F + 11 Sau đó hàng loạt công trình nghiên cứu đề xuất các loại phụ thuộc dữ liệu khác được xuất hiện trong lý thuyết cơ sở dữ liệu [4],[5],[10]. Các phụ thuộc dữ liệu đảm bảo cho dữ liệu trong các cơ sở dữ liệu phản ánh sát với thế giới thực, phi mâu thuẫn có tính nhất quán và trợ giúp tối ưu hóa trong tìm kiếm dữ liệu [6], [7]. Trong số các biến thể của phụ thuộc hàm thì các phụ thuộc nới lỏng (Relaxed Functional Dependencies) được nghiên cứu và ứng dụng với tần xuất cao vì các lý do sau đây. Thứ nhất, các điều kiện bổ sung cho phụ thuộc hàm để tạo ra các phụ thuộc nới lỏng thường khá gần với các yêu cầu trong đời thường. Thứ hai, các phụ thuộc nới lỏng có thể được dùng làm cơ sở để đặc tả các loại phụ thuộc khác [6], [7]. Cho tập thuộc tính U. Một phụ thuộc hàm nới lỏng trên U là công thức dạng f: (γ)X  (δ)Y; X, Y  U trong đó ta gọi X là vế trái và Y là vế phải của phụ thuộc hàm nới lỏng f. Cho quan hệ R(U) và một phụ thuộc hàm nới lỏng f: (γ)X  (δ)Y trên U. Ta nói quan hệ R thoả phụ thuộc hàm nới lỏng f, hoặc phụ thuộc hàm nới lỏng f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R thỏa điều kiện γ và giống nhau trên X thì chúng cũng giống nhau trên miền Y thỏa điều kiện δ, R(XY)  (γ)X, (δ)Y, (u,vR): (u.X = v.X)  (u.Y = v.Y) Nếu f: (γ)X  (δ)Y là một phụ thuộc hàm nới lỏng trên U thì ta nói tập thuộc tính Y phụ thuộc (hàm) nới lỏng vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm nới lỏng tập thuộc tính Y. Dưới đây xin trích dẫn một số thí dụ về các phụ thuộc hàm nới lỏng. Trong bảng tuần hoàn các nguyên tố hóa học Mendelev, hai chất có cùng số electron tại lớp ngoài cùng thì có cùng ái lực, tức là chúng có cùng xu thế nhận thêm cho đủ số electron từ nguyên tố khác. 12 Phụ thuộc hàm nới lỏng f: (E = s)E  (true)A Ý nghĩa của phụ thuộc hàm nới lỏng trong trường hợp này là: Chỉ xét trên các bộ thỏa điều kiện số điện tử tại lớp ngoài cùng bằng s, E = s, thì hai nguyên tố có cùng lượng E sẽ có cùng ái lực. Một dạng khác của phụ thuộc hàm nới lỏng là phân loại học sinh. Hai học sinh có thể có điểm khác nhau nhưng vẫn được xếp vào cùng loại. g: (a  ĐTB  b)ĐTB  (true)Loại Phụ thuộc hàm nới lỏng g cho biết hai học sinh có điểm trung bình (ĐTB) trong cùng một đoạn [a; b] thì có cùng loại đánh giá. 13 Trong công trình của nhóm nghiên cứu Loredana Caruccio, Vincenzo Deufemia, và Giuseppe Polese [7] đã phân loại hầu hết các phụ thuộc hàm nới lỏng từ năm 1970 đến 2016. Trong khuôn khổ khóa luận thạc sĩ này, học viên chọn đề tài: “Các thuật toán xử lý phụ thuộc hàm nới lỏng”. 2. Đối tượng và phạm vi nghiên cứu Luận văn tập trung khảo sát các đối tượng liên quan đến các lược đồ cơ sở dữ liệu quan hệ sau đây: - Lý thuyết phụ thuộc hàm và phụ thuộc hàm nới lỏng. - Các thuật toán cơ bản xử lý các đối tượng trong phụ thuộc hàm nới lỏng. 3. Hướng nghiên cứu của đề tài - Nghiên cứu lý thuyết liên quan đến đề tài: Cơ sở dữ liệu quan hệ, phụ thuộc hàm, phụ thuộc hàm nới lỏng, các thuật toán tính bao đóng, khóa. - Cài đặt các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc hàm, phụ thuộc hàm nới lỏng, khóa. - Thử nghiệm các lược đồ quan hệ trang bị phụ thuộc hàm nới lỏng. 4. Cấu trúc của luận văn và những nội dung nghiên cứu chính 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, các chuẩn 1NF, 2NF, 3NF, BCNF, chuẩn hóa 3NF và bảo toàn thuốc tính PTH, PTH nới lỏng. 14 - - Chương 2 trình bày một số thuật toán về: quản lý tập hợp, quản lý tập thuộc tính, quản lý tập phụ thuộc hàm nới lỏng, tính bao đóng, khóa. Chương 3 là cài đặt chương trình mô phỏng “Thuật toán xử lý phụ thuộc hàm nới lỏng” và ứng dụng. 5. Phương pháp nghiên cứu Trong luận văn học viên sử dụng các phương pháp nghiên cứu chính sau: - Nghiên cứu lý thuyết: Tổng hợp tài liệu, hệ thống lại các kiến thức, tìm hiểu các khái niệm, thuật toán sử dụng trong đề tài. - Lập trình thử nghiệm. - Lấy ý kiến chuyên gia. 6. Ý nghĩa khoa học của đề tài Việc nghiên cứu đề tài có thể đóng góp thêm một vài chức năng quản lý ngữ nghĩa dữ liệu thông qua các phụ thuộc hàm nới lỏng. Loại phụ thuộc hàm này cho phép xử lý dữ liệu mịn hơn và linh hoạt hơn. Luận văn thiết kế và cài đặt một hệ thống với các chức năng nhập xuất, lưu trữ, tính bao đóng và khóa của các lược đồ quan hệ có trang bị các phụ thuộc hàm nới lỏng. Hệ thống có thể được sử dụng để khảo sát và kiểm định một số tính chất của các lược đồ quan hệ với phụ thuộc hàm nới lỏng. 15 CHƯƠNG 1 CÁC KIẾN THỨC CƠ SỞ Chương này trình bày một số khái niệm cơ bản về tập hợp, về phụ thuộc hàm và về lược đồ quan hệ. Nội dung chương sẽ là cơ sở để nghiên cứu những vấn đề trong các chương sau. 1.1. Giới thiệu chung 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ý. 1.2. Đị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à 16 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. 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. 1.3. 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 thuộc tính X+ = {A  U | X  A  F+} 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 và viết F ├ f, nếu mọi quan hệ R(U) thoả F thì R cũng thoả f: F ├ f  SAT(F)  SAT(f). Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F* là tập toàn bộ các PTH f được suy dẫn theo quan hệ từ tập PTH F F* = {f: X  Y | X, Y  U, F ├ f} Ta viết F !├ f hoặc F ├ f để biểu thị tập PTH F không dẫn theo quan hệ ra được PTH f . Định lý (Tính đủ và chặt của hệ tiên đề Armstrong) F+ = F* Nói cách khác, suy dẫn theo quan hệ và suy dẫn theo tiên đề là một, tức là F ╞ f  F ├ f. 17 Quy ước giản lược: Ta thường viết X  Y thay vì viết X  Y  F+ hoặc F ╞ X  Y. 1.4. Các kí hiệu và một số quy ước Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các quy định sau đây: Các thuộc tính được kí hiệu bằng các chữ 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ử. 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 18 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). Với mỗi bộ u trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký hiệu uv là phép dán bộ. uv cho ta bộ t trên tập thuộc tính UV thoả điều kiện t.U = u và t.V = v. Với mỗi bộ u trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu uS là phép dán bộ u với quan hệ S. uS cho ta quan hệ P(UV) = {uv | v  S} Để thể hiện các phép toán quan hệ ta sẽ dùng các ký pháp tựa như ký pháp của hệ ISBL (Information System Base Language). 1.5. Lược đồ quan hệ và khóa của lược đồ quan hệ 1.5.1. Định nghĩa 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 phụ thuộc hàm 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.5.2. 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à khoá của LĐQH p nếu (i) K+ = U 19 (ii)  A  K: (K  {A})+  U Hai điều kiện trên tương đương với (i') K  U (ii')  A  K: (K  {A}) ! U Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá. Thuộc tính A  U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở) nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH (U,F), ta kí hiệu UK là tập các thuộc tính khóa và UO là tập các thuộc tính không khóa. Ví dụ: Cho U = {A,B,C,D,E} và F = {ABC, ACB, BCDE}, hãy tìm một khóa của lược đồ quan hệ r xác định trên U và F. Bước 1: K = U tức là K = ABCDE Bước 2: Tính bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy kết quả tính bao đóng không bằng U+ nên K = ABCDE Bước 3: Tính bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K = ACDE. Bước 4: Tính bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy kết quả tính bao đóng không bằng U+ nên không bỏ C ra tập K ta có K = ACDE. Bước 5: Tính bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K = ACE. Bước 6: Tính bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K = AC. Kết quả: Khóa là K = AC. 20