Nghiên cứu một số khía cạnh lý thuyết trong mô hình CSDL quan hệ

  • Số trang: 131 |
  • Loại file: PDF |
  • Lượt xem: 19 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ============== VŨ CHÍ QUANG NGHIÊN CỨU MỘT SỐ KHÍA CẠNH LÝ THUYẾT TRONG MÔ HÌNH CSDL QUAN HỆ LUẬN VĂN THẠC SĨ HÀ NỘI – 2007 1 MỤC LỤC MỞ ĐẦU ..................................................................................................................... 3 Chƣơng I - LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ ........................ 5 1.1. Phƣơng pháp thiết kế Bottom – Up .......................................................................... 5 1.1.1. Các khái niệm cơ bản: ........................................................................... 5 1.1.2. Các phép toán trong mô hình quan hệ. .................................................. 7 1.1.3. Phụ thuộc hàm. ...................................................................................... 9 1.1.4. Lý thuyết chuẩn hoá............................................................................. 18 1.2. Phƣơng pháp thiết kế Top – Down ............................................................... 21 1.3. Quá trình thiết kế cơ sở dữ liệu ..................................................................... 26 Chƣơng II - LÝ THUYẾT KẾT NỐI VÀ NỬA KẾT NỐI. ỨNG DỤNG TRONG TỐI ƢU HOÁ CÂU HỎI. ..................................................................... 28 2.1. Lý thuyết kết nối và một số kết quả của lý thuyết kết nối...................................... 28 2.1.1 Kết nối không mất thông tin. ............................................................... 28 2.1.2 Kết nối mất thông tin. .......................................................................... 30 2.2. Một số tính chất, ý nghĩa của nửa kết nối ứng dụng trong cơ sở dữ liệu phân tán. 39 2.2.1 Giới thiệu phép nửa kết nối. ................................................................ 39 2.2.2 Các tính chất của phép nửa kết nối. ..................................................... 41 2.2.3 ý nghĩa của phép nửa kết nối ứng dụng trong CSDL phân tán............ 42 2.3. Tối ƣu hoá câu hỏi trong cơ sở dữ liệu phân tán. ................................................... 42 2.3.1 Khái quát về cơ sở dữ liệu phân tán .................................................... 42 2.3.2 Một số nguyên lý chung của tối ƣu hoá câu hỏi. ................................. 52 2.3.3 Tối ƣu hoá câu hỏi. .............................................................................. 71 Chƣơng III - MỘT SỐ BÀI TOÁN NP-C TRONG MÔ HÌNH QUAN HỆ. ......... 106 3.1. Tổng quan về thuật toán và đánh giá thuật toán ......................................... 106 3.1.1 Khái niệm thuật toán ......................................................................... 106 3.1.2 Các tính chất của thuật toán ............................................................... 107 3.1.3 Hai mô hình tính toán ....................................................................... 108 3.1.4 Khái niệm độ phức tạp thuật toán ...................................................... 108 3.1.5 Phép quy dẫn (dẫn về đƣợc) .............................................................. 110 3.1.6 Phân lớp bài toán theo độ phức tạp ................................................... 111 3.1.7 Cấu trúc của lớp P, NP ...................................................................... 112 3.2. Một số bài toán NP-C trong mô hình quan hệ ............................................ 114 3.2.1 Bài toán siêu khoá có lực lƣợng không quá m .................................. 114 3.2.2 Bài toán quyết định thuộc tính khoá hay không khoá ....................... 117 KẾT LUẬN ............................................................................................................. 120 TÀI LIỆU THAM KHẢO ....................................................................................... 121 2 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Bức tranh về trật tự các dạng chuẩn ........................................................... 18 Hình 1.2 Biểu đồ E-R cho CSDL công ty ................................................................ 24 Hình 1.3 Quá trình thiết kế một cơ sở dữ liệu........................................................... 27 Hình 2.1 Đồ thị biểu diễn lược đồ quan hệ R ........................................................... 31 Hình 2.2 Đồ thị con bị cấm ....................................................................................... 34 Hình 2.3 Mô phỏng quan hệ giữa các đỉnh .............................................................. 36 Hình 2.4: Kiến trúc các lược đồ của một CSDL phân tán ........................................ 46 Hình 2.5: Kiến trúc chức năng của một hệ QTCSDL phân tán ................................ 47 Hình 2.6: Các kiểu phân đoạn của một quan hệ........................................................ 49 Hình 2.7 Lược đồ tổng quát xử lý truy vấn phân tán ................................................ 59 Hình 2.8 Các đồ thị quan hệ ...................................................................................... 63 Hình 2.9 Đồ thị truy vấn không liên thông ............................................................... 63 Hình 2.10 Ví dụ về cây truy vấn ............................................................................... 64 Hình 2.11 Cây truy vấn tương đương ....................................................................... 65 Hình 2.12 Cây truy vấn đã được viết lại ................................................................... 66 Hình 2.13 Cây truy vấn sau khi thay thế ................................................................... 68 Hình 2.14 Rút gọn phân đoạn ngang (với phép chọn) .............................................. 68 Hình 2.15 Rút gọn phân đoạn ngang (với phép nối) ................................................. 69 Hình 2.16 Rút gọn phân đoạn dọc ............................................................................. 70 Hình 2.17 Rút gọn phân đoạn hỗn hợp ..................................................................... 71 Hình 2.18 Quá trình tối ưu hoá truy vấn ................................................................... 72 Hình 2.19 Các cây nối tương đương ......................................................................... 73 Hình 2.20 Đồ thị nối của cây truy vấn ...................................................................... 84 Hình 2.21 Các thứ tự nối khác nhau ......................................................................... 84 Hình 2.22 Đồ thị nối của cây truy vấn phân tán ....................................................... 86 Hình 2.23 Truy vấn mẫu và số liệu thống kê ............................................................ 99 Hình 2.24 Đồ thị câu truy vấn đơn và số liệu thống kê .......................................... 102 Hình 3.1 Sơ đồ minh hoạ các lớp bài toán NP, NP-C, NP-Hard ............................ 114 3 MỞ ĐẦU Trong lĩnh vực công nghệ thông tin, cơ sở dữ liệu là một chuyên ngành được đông đảo người làm công nghệ thông tin quan tâm, nghiên cứu và ứng dụng. Ra đời từ những năm 60 của thế kỷ XX đến nay, các hệ cơ sở dữ liệu ngày càng phát triển và hoàn thiện, nhiều thế hệ quản trị CSDL đã ra đời, tạo ra nhiều sản phẩm ứng dụng trong khoa học kỹ thuật, các ngành kinh tế cũng như trong đời sống xã hội. Việc nghiên cứu CSDL trên thế giới và ở trong nước đã và đang phát triển ngày càng phong phú, đa dạng. Từ những năm 70, E.F. Codd đã đưa ra mô hình dữ liệu quan hệ tạo một cơ sở vững chắc cho các vấn đề nghiên cứu về CSDL. Với ưu điểm về tính cấu trúc 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, làm tăng khả năng xử lý, quản trị và khai thác dữ liệu, phục vụ được hầu hết các yêu cầu của người sử dụng. Trên thực tế, đã có nhiều hệ quản trị CSDL xây dựng trên mô hình CSDL quan hệ được sử dụng phổ biến trên thị trường như: DBASE, FOXPRO, ORACLE, MS SQL,... Cho đến nay CSDL quan hệ đã thu được rất nhiều thành tựu sâu sắc cả về phương diện lý thuyết và ứng dụng. Phần lớn các hệ quản trị CSDL sử dụng trong thực tiễn được thiết kế trong mô hình quan hệ, rất nhiều sản phẩm phần mềm được tạo ra vẫn đang sử dụng rộng rãi và có hiệu quả. Việc tiếp tục nghiên cứu các khía cạnh lý thuyết trong mô hình CSDL quan hệ sẽ tạo điều kiện thuận lợi cho việc nghiên cứu và phát triển các mô hình cơ sở dữ liệu mới như: CSDL phân tán, CSDL suy diễn. Hiện nay đã có nhiều vấn đề về CSDL được nghiên cứu và giải quyết. Với mục đích tiếp tục nghiên cứu một số khía cạnh lý thuyết trong mô hình CSDL quan hệ để nâng cao khả năng ứng dụng của các hệ CSDL, luận văn này tập trung nghiên cứu về các vấn đề: 4 - Nghiên cứu sâu sắc về lý thuyết kết nối và nửa kết nối, ứng dụng lý thuyết kết nối và nửa kết nối trong tối ưu hoá câu hỏi, đặc biệt là trong tối ưu hoá câu hỏi phân tán. - Nghiên cứu độ phức tạp của các thuật toán trong CSDL, giới thiệu một số bài toán trong CSDL là NP-C. Nội dung của bản luận văn này được chia làm 3 chương: Chương 1: Lý thuyết thiết kế cơ sở dữ liệu quan hệ. Chương này trình bày về các phương pháp thiết kế cơ sở dữ liệu quan hệ, quy trình thiết kế và các vấn đề liên quan như: các phép toán trong mô hình quan hệ, phụ thuộc hàm và chuẩn hoá. Chương II - Lý thuyết kết nối và nửa kết nối. Ứng dụng trong tối ưu hoá câu hỏi. Đây là chương chính của luận văn; trong chương này trình bày các vấn đề về lý thuyết kết nối như: kết nối không mất thông tin, kết nối mất thông tin, điều kiện cần và đủ để kết nối không mất thông tin. Phần tiếp theo trình bày về phép nửa kết nối, tính chất và ý nghĩa của nửa kết nối ứng dụng trong cơ sở dữ liệu phân tán. Phần cuối cùng trình bày các vấn đề ứng dụng lý thuyết kết nối và nửa kết nối trong tối ưu hoá câu hỏi phân tán như: khái quát về CSDL phân tán, các vấn đề về tối ưu hoá câu hỏi, các thuật toán để tối ưu hoá câu hỏi trong môi trường tập trung và môi trường phân tán. Chương III - Một số bài toán NP-C trong mô hình quan hệ. Chương này trình bày một khía cạnh lý thuyết trong cơ sở dữ liệu, đó là đánh giá độ phức tạp của các thuật toán trong các hệ cơ sở dữ liệu, vấn đề này ít được đề cập trong các sách về CSDL và chỉ được giới thiệu trong các bài báo hoặc trong các sách nghiên cứu sâu về lý thuyết thuật toán và độ phức tạp của thuật toán. Ngoài ra trong chương này còn giới thiệu một số bài toán cụ thể trong cơ sở dữ liệu là NP-C. Mặc dù đã rất cố gắng để hoàn thành bản luận văn này, nhưng chắc chắn vẫn còn thiếu sót. Rất mong được sự góp ý của các thầy cô giáo và các bạn. 5 Chương I - LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ Trong lý thuyết thiết kế cơ sở dữ liệu quan hệ có hai cách tiếp cận, cách thứ nhất thiết kế theo phương pháp Bottom – Up (dưới - lên), cách thứ hai thiết kế theo phương pháp Top – Down (trên – xuống). Theo phương pháp Bottom – Up: Mục đích của việc thiết kế cơ sở dữ liệu quan hệ là đưa ra một tập các lược đồ quan hệ để lưu trữ các thông tin của một tổ chức xí nghiệp, ngân hàng, đại học, ... một cách không dư thừa đồng thời cũng cho phép cập nhật, truy vấn dễ dàng. Để đạt được mục đích đó khi nghiên cứu và khảo sát bài toán quản lý trong thực tiễn; ta phải xác định các thuộc tính cần quản lý, mối quan hệ giữa các thuộc tính (các phụ thuộc hàm); tiếp theo là chuẩn hoá các lược đồ quan hệ, thực chất là thực hiện các phép tách để có được các lược đồ theo các dạng chuẩn (1NF, 2NF, 3NF, BCNF, 4NF, 5NF); tuy nhiên các phép tách phải đảm bảo các điều kiện như: bảo toàn thuộc tính, bảo toàn phụ thuộc hàm, không mất mát thông tin. Theo phương pháp Top – Down: Khi nghiên cứu và khảo sát bài toán quản lý trong thực tiễn; ta phải xác định các đối tượng của cơ sở dữ liệu và mối liên hệ giữa các đối tượng; tiếp theo là mô hình hoá thành các kiểu thực thể, kiểu liên kết, xây dựng lược đồ thực thể liên kết ER; cuối cùng là áp dụng các nguyên tắc chuyển từ mô hình thực thể liên kết ER sang mô hình quan hệ. 1.1. Phương pháp thiết kế Bottom – Up 1.1.1. Các khái niệm cơ bản: - Thuộc tính: Thuộc tính của một quan hệ là cột của bảng quan hệ. Trong mô hình quan hệ không cho phép thuộc tính phức hợp, đa trị. Chỉ được là thuộc tính đơn, đơn trị. - Miền giá trị: Là giới hạn dữ liệu của thuộc tính ký hiệu DOM(A) trong đó A là một thuộc tính. Ví du: Với thuộc tính Lương miền giá trị là: 0 – 1000000 6 - Lược đồ quan hệ: Mô tả cấu trúc của một quan hệ, được ký hiệu là R(A1, A2, ..., An) trong đó R là tên quan hệ và Ai (i=1..n) là các thuộc tính. Ví dụ: Lược đồ quan hệ NHANVIEN( HOTEN, MSBHXH, DIACHI, LUONG, GIOITINH, NGAYSINH ) - Quan hệ: Là một tập con của tích Descartes của danh sách các miền giá trị, được ký hiệu là: r={t1, t2, ..., tm}  DOM(A1) x ... x DOM(An). Trong đó: + ti = + vij  DOM(Aj) (i=1..m; j=1..n) Chú ý: + Một quan hệ chính là một bảng hai chiều: + Số các thuộc tính của quan hệ là số ngôi của quan hệ. + Thứ tự các dòng, các cột trong bảng quan hệ không quan trọng. + Các giá trị trong bảng phải đơn trị và phù hợp với kiểu dữ liệu của thuộc tính (ký tự, số, Logic, Ngày). + Dữ liệu của quan hệ có thể thay đổi theo thời gian do thường xuyên phải cập nhật dữ liệu. + Quan hệ Nhân viên là quan hệ 6 ngôi. - Lược đồ CSDL: Là một tập các lược đồ quan hệ ký hiệu là: S = {R1, R2, ..., Rm}, trong đó Ri (i=1..m) là một lược đồ quan hệ. - CSDL Quan hệ: Là một tập các quan hệ ký hiệu là: DB = {r1, r2, ... , rm}, trong đó ri (i=1..m) là quan hệ (thể hiện của Ri). - Siêu khoá (SK): SK được gọi là siêu khoá nếu với mọi t1, t2  r thì t1[SK]  t2[SK]. Trong đó: + SK: là một hoặc nhiều cột (thuộc tính) trong bảng. + t1, t2 là các bộ giá trị của mỗi hàng trong bảng. + t1[SK], t2[SK] theo thứ tự là các bộ giá trị của SK tương ứng với các bộ t1, t2. 7 - Khoá (K): Khoá của một lược đồ quan hệ là một siêu khoá tối thiểu (khoá dự tuyển). - Khoá chính (PK): Là một trong các khoá dự tuyển. - Khoá ngoài (FK): Một nhóm các thuộc tính gọi là khoá ngoài (FK) của một quan hệ r1 tham chiếu đến quan hệ r2 nếu miền giá trị FK của r1 phải giống miền giá trị PK của r2. - Ràng buộc: + Ràng buộc miền: vi  DOM(Ai) + Ràng buộc Khoá: Giá trị của khoá phải duy nhất. + Ràng buộc toàn vẹn thực thể: Giá trị của khoá chính (PK) phải xác định (không có giá trị null). + Ràng buộc toàn tham chiếu:  Nếu Khoá ngoài của R1 tham chiếu đến khoá chính của R2 thì phải có cùng miền giá trị với khoá chính của R2.  Mỗi giá trị của Khoá ngoài của R1 hoặc là phải có mặt trong khoá chính của R2 hoặc là nhận giá trị Null (với ngữ nghĩa là một giá trị tồn tại nhưng không biết). 1.1.2. Các phép toán trong mô hình quan hệ. 1.1.2.1 Phép toán cập nhật. - Phép chèn (INSERT): Là phép thêm một bộ (bản ghi) vào quan hệ r. - Phép loại bỏ (DELETE): Là phép loại bỏ một bộ ra khỏi quan hệ r. - Phép cập nhật (UPDATE): Là phép thay đổi giá trị của các thuộc tính trong một hoặc một số bộ nào đó. 1.1.2.2 Đại số quan hệ. - Các phép toán tập hợp: Các quan hệ tham gia một phép toán tập hợp (hợp, giao, trừ) phải có cùng cấu trúc. + Phép hợp r  s: Thực chất của phép hợp là xây dựng một tập các bộ thuộc quan hệ r hoặc quan hệ s hoặc cả 2 quan hệ. 8 Phép hợp được ký hiệu và định nghĩa là: r  s = { t  t  r hoặc t  s } + Phép giao r  s: Thực chất của phép giao là xây dựng một tập các bộ thuộc cả 2 quan hệ r và s. Phép giao được ký hiệu và định nghĩa là: r  s = { t  t  r và t  s } + Phép trừ r \ s: Thực chất của phép trừ là xây dựng một tập các bộ thuộc quan hệ r nhưng không thuộc quan hệ s. Phép trừ được ký hiệu và định nghĩa là: r \ s = { t  t  r và t  s } + Tích Descartes r x s: Tích Descartes của hai quan hệ chỉ xét trên các lược đồ rời nhau (nếu hai lược đồ có thuộc tính cùng tên thì ta có thể đổi tên thuộc tính cùng tên của một trong hai lược đồ, để hai lược đồ rời nhau). Cho hai lược đồ R={A1, A2, …, An} và S={B1, B2, …, Bm}, r và s là hai quan hệ trên R và S tương ứng. Tích Descartes của hai quan hệ r và s là một quan hệ q. Mỗi bộ trong quan hệ q ký hiệu tq là ghép một bộ tr r với một bộ ts s; trong đó tr = (a1, a2, …, an), ts = (b1, b2, …, bm), tq = (a1, a2, …, an, b1, b2, …, bm). Tích Descartes được ký hiệu và định nghĩa là: r x s = {tt=(a1, a2,.., an, b1, b2,.., bm), (a1, a2,.., an)r và (b1, b2,.., bm)s} Như vậy nếu r có x bộ, s có y bộ thì q có x * y bộ. + Phép chia r s: Cho lược đồ R ={A1, A2, …, An}, S  R, r và s là hai quan hệ trên R và S tương ứng. Phép chia của quan hệ r cho s được một quan hệ q trên lược đồ R-S sao cho mỗi bộ t  q ghép với mọi bộ u  s ta được một bộ < t, u >  r. Phép chia được ký hiệu và định nghĩa là: r  s = {t mọi u  s , < t, u >  r } 9 - Phép chiếu X(r): Thực chất của phép chiếu là loại bỏ đi một số thuộc tính và giữ lại những thuộc tính còn lại của quan hệ (các thuộc tính trong tập X, X  R). Phép chiếu được ký hiệu và định nghĩa là: X(r) = {t[X]  t r } - Phép chọn <Điều kiên>(r): Thực chất của phép chọn là xây dựng một tập con của quan hệ thoả mãn điều kiện xác định. <Điều kiện> chính là một biểu thức logic; ta có thể sử dụng các phép toán so sánh: =, >, >=, <, <=, <> và các phép toán logic như: and (), or (), not () để tạo các biểu thức điều kiện thoả mãn các yêu cầu của người sử dụng. Phép chọn được ký hiệu và định nghĩa là: <Điều kiện>(r) = {t t r, <Điều kiện>( t ) = true } - Phép nối r<Điều kiện>s: Thực chất của phép nối là phép chọn của quan hệ (r x s) theo điều kiện xác định. Trong đó: r x s là tích Descartes; <Điều kiện> là một biểu thức logic xác định điều kiện nối giữa hai quan hệ r và s theo , ( là một trong các phép toán so sánh =, >, >=, <, <=,<>) được ký hiệu là: Ai  Bj (Ai  r , Bj  s, Ai và Bj phải có cùng miền giá trị). Phép nối được ký hiệu và định nghĩa là: r <Điều kiện> s = <Điều kiện>(r x s) - Phép nối tự nhiên: Khi các quan hệ r và s có chung một số thuộc tính (cùng tên và có cùng giá trị thuộc một miền nào đó) thì phép kết nối r và s theo điều kiện các thuộc tính đó bằng nhau và một trong hai thuộc tính giống nhau được loại bỏ trong quan hệ kết quả thì phép kết nối này được gọi là phép kết nối tự nhiên và được ký hiệu là r - r s. Phép nửa nối r <Điều kiện> s : Thực chất của phép nửa nối là phép chiếu lên R của s. Kết quả của phép nửa nối một quan hệ r với một quan hệ s theo điều kiện nào đó là một quan hệ gồm tất cả các bộ thuộc r có tính chất kết nối được theo điều kiện với một bộ nào đó trong quan hệ s. 10 Phép nửa nối được ký hiệu và định nghĩa là: r s = R(r <Điều kiện> s) 1.1.3. Phụ thuộc hàm. 1.1.3.1 Khái niệm phụ thuộc hàm: Phụ thuộc hàm trên một lược đồ quan hệ là một khái niệm có tầm quan trọng hết sức lớn đối với việc thiết kế cơ sở dữ liệu. Một phụ thuộc hàm là một phát biểu ký hiệu : X  Y, trong đó  là tên của phụ thuộc hàm, X và Y là các tập thuộc tính. Xét phụ thuộc hàm : X  Y trong lược đồ quan hệ R, với R={A1, A2, ... An} là tập các thuộc tính, X và Y là tập con của R, X  Y = . Khi đó ta nói X xác định hàm Y hay Y phụ thuộc hàm vào X nếu t1, t2 là các cặp bộ xác định trên quan hệ r mà t1[X] = t2[X] thì t1[Y] = t2[Y]. 1.1.3.2 Hệ tiên đề Armstrong. Trước khi đi vào trình bày hệ tiên đề cho phụ thuộc hàm, chúng ta sẽ xem xét một vài khái niệm liên quan đến các phụ thuộc hàm trong lược đồ quan hệ. Gọi F là tập các phụ thuộc hàm cho trước đúng trên lược đồ quan hệ R, và X  Y là một phụ thuộc hàm với X,Y  của tập các thuộc tính. - Suy diễn logic: Nói rằng X  Y được suy diễn logic từ F nếu mỗi quan hệ r trên lược đồ quan hệ R thoả các phụ thuộc hàm của F thì cũng thỏa X  Y. - Bao đóng của tập phụ thuộc hàm: Gọi F+ là bao đóng của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có hệ tiên đề. Hệ tiên đề Armstrong Cho lược đồ quan hệ R với R={A1 , A2, ..., An } là tập các thuộc tính; X, Y, Z  của R. - Tiên đề 1 (Phản xạ) : Nếu Y  X thì X  Y. 11 - Tiên đề 2 (Tăng trưởng): Nếu X  Y thì X  Z  Y  Z. - Tiên đề 3 (Bắc cầu): Nếu X  Y và Y  Z thì X  Z. Tính đúng đắn của các tiên đề này đã được chứng minh một cách tường minh và đầy đủ trong [3] (chương 7, tập II). Ta có một kết quả quan trọng sau : Định lý 1.1 : Hệ tiên đề Armstrong là xác đáng và đầy đủ. Chứng minh : Định lý này đã được chứng minh đầy đủ trong [3] (chương 7, tập II). Từ hệ tiên đề Armstrong suy ra một số luật mở rộng sau: - Luật hợp: Nếu X  Y và X  Z thì X  Y Z. - Luật tựa bắc cầu: Nếu X  Y và Y  W  Z thì X  W  Z. - Luật tách: X  Y và Z  Y thì X  Z. Chứng minh : Các luật mở rộng này đã được chứng minh đầy đủ trong [3] (chương 7, tập II). 1.1.3.3 Bao đóng của một tập thuộc tính : Bao đóng của X đối với F gọi là X+, tức là tập tất cả các thuộc tính phụ thuộc vào X thông qua F. Cho S = <, F> là một lược đồ quan hệ và X  . Bao đóng của X đối với F được định nghĩa : X+ ={A  A   và (X  A)  F+} Thuật toán sau sẽ xác định bao đóng của tập các thuộc tính. Input : X   và F là tập các phụ thuộc hàm của lược đồ quan hệ S=<, F>. Output : X+ Thuật toán 1.1 ( Tính X+) X+ = X REPEAT TAM = X+ Với mọi phụ thuộc hàm Y  Z trong F nếu Y  X+ thì X+ = X+  Z UNTIL X+=TAM 12 Nhận xét: Độ phức tạp của giải thuật là O(n2.p) với n = số thuộc tính và p = số các phụ thuộc hàm. Ví du: - Cho lược đồ quan hệ: R(MASONV, HOTEN, MSDUAN, TENDA, DIADIEM, SOGIO) Tập các phụ thuộc hàm F: MASONV  HOTEN MSDUAN  TENDA, DIADIEM MASONV, MSDUAN  SOGIO - Tính X+ của vế trái các phụ thuộc hàm: MASONV+ = MASONV, HOTEN MSDUAN += MSDUAN, TENDA, DIADIEM {MASONV, MSDUAN}+ = MASONV, MSDUAN , SOGIO, HOTEN, TENDA, DIADIEM 1.1.3.4 Cách xác định khoá: Trong lý thuyết thiết kế cơ sở dữ liệu quan hệ, việc xác định khoá của một lược đồ quan hệ là một bài toán quan trọng. Sau đây tác giả xin trình bày một số kết quả liên quan đến việc xác định khoá của một lược đồ quan hệ. - Định lý của các tác giả Hồ Thuần và Lê Văn Bảo cho một điều kiện cần để tập X   là khoá của một lược đồ quan hệ [2]. Định lý 1.2: Cho S=<,F> là một lược đồ quan hệ, tập các thuộc tính ={A1,...,An}, tập các phụ thuộc hàm F = {LiRi  Li, Ri  , Li  Ri = , i=1,...,p}. Điều kiện cần để X   là khoá của lược đồ S là: (\R)  X  (\R)  (L  R). trong đó: L = L , R = R i i 1 Chứng minh: p p i i 1 . 13 + Trước hết ta chứng minh rằng nếu X là khoá thì (\R)  X Thực vậy nếu X là khoá thì X+ =  Mặt khác, theo thuật toán tính bao đóng ta có: X+  X  R   Từ đó suy ra: X  R =  Vậy (\R)  X. + Ta tiếp tục chứng minh nếu X là khoá thì X  (\R)  (L  R) Ta thấy: X   = (\R)  (L  R)  (R\L) (1) (2) Để chứng minh (1) ta chỉ cần chứng minh X  (R\L) = . Bằng phương pháp chứng minh phản chứng, ta giả sử X  (R\L) ≠ . Khi đó tồn tại một thuộc tính A sao cho A  X, A  R và A  L. Do X là khoá nên ta có X  L Do A  L ta có (X \ {A})  L Mặt khác ta có L  R và R  A. Áp dụng quy tắc bắc cầu ta có (X \{A})A, điều này trái với giả thiết X là khoá. Vậy định lý được chứng minh. Từ định lý 1.2 ta có thể suy ra được các hệ quả sau: Hệ quả 1: Cho S = < , F > là một lược đồ quan hệ. Nếu R \ L ≠  thì tồn tại một khoá X sao cho X ≠ . Hệ quả 2: Cho S = < , F > là một lược đồ quan hệ. Nếu L  R =  thì (\R) là khoá duy nhất của lược đồ S. - Thuật toán xác định một khoá của lược đồ [2]. Input : lược đồ quan hệ < , F >. Output : một khoá của < , F >. Thuật toán 1.2 (Xác định một khoá của lược đồ) Bước 1: X :=  \ R; 14 Bước 2: Nếu X+ =  thì chuyển sang bước 5; Bước 3: X := (\R)  (L  R); Bước 4: Với mọi Ai  L  R thực hiện + X := X \ {Ai} + Nếu X+ ≠  thì X := X  {Ai}; Bước 5: Kết luận X là khoá. - Định lý của các tác giả Lucchesi và Osborn cho phép xây dựng thuật toán tìm tất cả các khoá của lược đồ quan hệ S = <, F> [2] Định lý 1.3 ( Lucchesi và Osborn) Cho S = <, F> là một lược đồ quan hệ. Gọi K là một tập khác rỗng các khoá của S. Điều kiện cần và đủ để họ 2 \ K có chứa khoá của S là có tồn tại một phần tử KK và tồn tại một phụ thuộc hàm (Li0  Ri0)  F sao cho tập T = Li0  (K \ Ri0) không chứa phần tử nào thuộc K. (ở đây 2 ký hiệu họ tất cả các tập con của ). Chứng minh : + Điều kiện đủ : Giả sử tồn tại KK, (Li0Ri0)  F sao cho sao cho tập T=Li0(K \ Ri0) không chứa phần tử nào thuộc K. Dễ thấy T là một siêu khoá và phải chứa ít nhất một khoá của S. Vì T không chứa một khoá nào của K. Vậy T phải chứa một khoá thuộc họ 2 \ K. Nói cách khác 2 \ K có chứa khoá của S. + Điều kiện cần : Giả sử 2 \ K có chứa khoá K’ của S. Gọi K’’ là tập tối đại thoả mãn hai tính chất sau : i) K’’  K’ ii) K’’ không chứa phần tử nào của K. Dễ thấy siêu khoá K’’ như vậy bao giờ cũng tồn tại (do tính chất i). Do tính chất ii) K’’  , và trong quá trình tính bao đóng, rõ ràng tồn tại phụ thuộc hàm Li0Ri0 sao cho Li0  K’’ và Ri0  K’’. 15 Xét tập K’’  Ri0. Vì K’’ là tập tối đại thoả mãn tính chất ii), suy ra K’’ Ri0  K với K K. Từ K  K’’ Ri0 và Ri0  K’’ suy ra K \ Ri0  K’’ Kết hợp với Li0  K’’, ta có T = Li0  (K \ Ri0)  K’’. Điều đó chứng tỏ sự tồn tại của K K và sự tồn tại của (Li0Ri0)  F sao cho tập T không chứa khoá nào thuộc K. - Thuật toán xác định tập tất cả các khoá của lược đồ quan hệ S=<, F> dựa vào định lý 1.3 ( Lucchesi và Osborn) và thuật toán 1.2 (xác định một khoá của lược đồ) [2, 3]. Input : lược đồ quan hệ < , F >. Output : Tập Ks tất cả các khoá của S. Thuật toán 1.3 (Xác định tập tất cả các khoá của lược đồ) 1. Ks := { K  K là một khoá của lược đồ < , F > và K chứa trong siêu khoá (\R)  (L  R)}; 2. For each K in Ks do 3. For each (Lj Rj ) in F do 4. T := Lj  (K \ Rj ) ; 5. Test := True ; 6. For each H in Ks do If H  M then Test := False ; 7. If Test then Ks :=Ks {KK là một khoá của lược đồ <,F> 8. và K chứa trong T} 9. end ; 10. end ; 11. Return Ks 1.1.3.5 Phủ của tập các phụ thuộc hàm: Cho hai tập phụ thuộc hàm F và G trên tập các thuộc tính . Ta nói F phủ G nếu G+  F+. 16 Định nghĩa (hai tập phụ thuộc hàm tương đương): Cho hai phụ thuộc hàm F và G. G và F được gọi là tương đương nếu G+ = F+, khi đó ta nói G là một phủ của F và ngược lại F cũng là một phủ của G. Định nghĩa (phủ tối tiểu): Cho G là một tập phụ thuộc hàm. F được gọi là một phủ tối tiểu của G nếu thoả mãn các tính chất sau: i) F là phủ của G. ii) Mọi f  F, f có dạng X  A (vế phải gồm đúng một thuộc tính) iii) F không chứa phụ thuộc hàm dư thừa theo nghĩa :  f  F : (F \ {f})+ ≠ F+ iv) Các phụ thuộc hàm thuộc F đều có vế trái không thể rút gọn được. Có nghĩa là :  f  F, giả sử f có dạng X  A. Khi đó  X’  X : [ (F \ {f})  (X’  A) ]+ ≠ F+ 1.1.3.6 Lý thuyết phân tách: - Khái niệm phép tách: Cho R(A1, A2, ..., An) là một lược đồ quan hệ. Một phân tách của R là việc thay thế lược đồ R bằng một họ các lược đồ con  = (R1, R2, ..., Rm) m sao cho R i = R. i 1 Cho  = (R1, ..., Rm) là một phân tách của lược đồ quan hệ R(A1, ..., An) và r là một thể hiện của lược đồ quan hệ . Gọi m(r) là ánh xạ được xác định bởi: m(r) = r1 r2 Trong đó : ri = Ri(r) với i = 1, 2, ..., m và ... rm ký hiệu phép kết nối tự nhiên. Khi đó ta có các tính chất sau: a) r  m(r) ; b) Nếu s = m(r) thì Ri(s) = ri ; c) m(m(r)) = m(r). Các tính chất trên đã được chứng minh đầy đủ trong [3]. 17 Trong lý thuyết phân tách lược đồ R(A1, A2, ..., An) thành các lược đồ con  = (R1, ..., Rm) có hai tính chất đó là phân tách không mất mát thông tin và phân tách bảo toàn tập phụ thuộc hàm F. Hai tính chất này độc lập với nhau tức là có phân tách bảo toàn thông tin nhưng không bảo toàn tập phụ thuộc hàm F và ngược lại. - Phân tách không mất thông tin. Định nghĩa: (Phân tách không mất thông tin) Phân tách  = (R1, R2, ..., Rm) được gọi là phân tách có kết nối không tổn thất (tức không mất thông tin) của lược đồ quan hệ nếu như với mọi r là thể hiện của R mà thoả F thì : r = r1 r2 ... rm (tức r = m(r)). Để kiểm tra một phân tách mất thông tin hay không ta sử dụng thuật toán: Input: Lược đồ quan hệ < R, F >, phân tách  = (R1, R2, ..., Rm). Output: Cho câu trả lời sai hay đúng tuỳ thuộc phân tách  có mất thông tin không ? Thuật toán 1.4 (Kiểm tra một phân tách có mất thông tin hay không) Bước 1: Lập bảng ban đầu là ma trận m hàng (ứng với m lược đồ con Ri) và n cột (ứng với tập thuộc tính {A1, A2, ..., An}). Phần tử hàng i, cột j (i, j) của ma trận được xác định theo công thức sau:  aj nÕuA j  Ri (i, j )   bij nÕuA j  Ri trong đó aj, bij  Dom(Aj). Bước 2: Biến đổi bảng. Mục đích của việc biến đổi bảng là để cuối cùng thu được một bảng, xem bảng đó như một quan hệ, thoả tập phụ thuộc hàm F. Muốn vậy ta lần lượt xét các phụ thuộc hàm X  Y thuộc F. Với mỗi phụ thuộc hàm như vậy nếu phát hiện trên bảng có hai hàng giống nhau trên X và khác nhau trên Y thì phải thay đổi bảng sao cho hai hàng đó cũng giống nhau trên Y. Việc thay đổi được thực hiện theo quy tắc : 18  Nếu một trong hai ký hiệu trên Y có dạng ai thì ký hiệu kia sẽ được đổi thành ai.  Nếu cả hai ký hiệu trên Y đều có dạng bij thì lấy tuỳ ý một trong hai ký hiệu đó và gán chung cho cả hai. Tiếp tục làm như vậy cho tới khi không thể biến đổi bảng được nữa. Khi đó ta thu được bảng cuối cùng. Bước 3: Nếu trong bảng cuối cùng có chứa hàng gồm toàn ký hiệu a (tức hàng a1, a2, ..., an), ta kết luận  = (R1, R2, ..., Rm) là phân tách không mất thông tin (tức là cho câu trả lời đúng). Trường hợp ngược lại  là phân tách mất thông tin. Định lý 1.4: Cho là một lược đồ quan hệ. Khi đó  = (R1, R2) là phân tách có kết nối không tổn thất (đối với F) khi và chỉ khi ( R1  R2 )  ( R1 - R2 ) hay ( R1  R2 )  ( R2 - R1 ) - Phân tách bảo toàn các phụ thuộc hàm. Định nghĩa: (Hình chiếu của F lên tập thuộc tính Z) Cho lược đồ quan hệ , và Z  R. Hình chiếu của F lên tập thuộc tính Z, ký hiệu z(F), được định nghĩa là : z(F) = { X  Y  (X  Y)  F+ và XY  Z} Định nghĩa: (Phân tách bảo toàn các phụ thuộc hàm) Phân tách  = (R1, R2, ..., Rm) của lược đồ quan hệ được gọi là phân tách bảo toàn tập phụ thuộc hàm F nếu: m (   Ri (F))  F i 1 1.1.4. Lý thuyết chuẩn hoá. Khi thiết kế cơ sở dữ liệu quan hệ thường nảy sinh các vấn đề như: dư thừa dữ liệu, gây ra các dị thường cập nhật (thêm, xoá, sửa bộ); cho nên các lược đồ quan hệ nhất thiết phải được biến đổi thành các dạng phù hợp. Quá trình đó được gọi là quá trình chuẩn hoá. 19 Một quan hệ được chuẩn hoá có thể tách thành một hoặc nhiều quan hệ chuẩn hoá khác và không làm mất thông tin. Trong mô hình quan hệ phân thành các dạng chuẩn 1NF, 2NF, 3NF, BCNF. Việc đưa các lược đồ quan hệ về các dạng chuẩn là nhằm mục đích: + Tránh dư thừa dữ liệu. + Tránh các dị thường trong cập nhật dữ liệu. Với ý nghĩa đó ta thấy dạng chuẩn BCNF tốt hơn 3NF, 3NF tốt hơn 2NF, 2NF tốt hơn 1NF; và bức tranh về trật tự các dạng chuẩn được mô tả như sau: 1NF 2NF 3NF BCNF Hình 1.1 Bức tranh về trật tự các dạng chuẩn 1.1.4.1 Một số khái niệm trong chuẩn hoá: - Thuộc tính khoá: Một thuộc tính trong lược đồ quan hệ R được gọi là thuộc tính khoá nếu nó tham gia ít nhất một khoá của R. Ngược lại được gọi là thuộc tính không khoá. - Phụ thuộc hàm đầy đủ: Cho lược đồ quan hệ R; R={A1, A2, ..., An } là tập các thuộc tính, X và Y là hai tập con khác nhau của R. Y là phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ tập con thực sự nào của X. Ngược lại ta nói Y là phụ thuộc hàm bộ phận của X. Ví dụ: Ta có các phụ thuộc hàm X  Y , Z  Y mà Z  X thì Y phụ thuộc hàm bộ phận của X. - Phụ thuộc bắc cầu: Cho lược đồ quan hệ R; {A1, A2, ..., An } là tập các thuộc tính; X, Y, Z là tập con của tập các thuộc tính. Ta nói phụ thuộc hàm X  Y
- Xem thêm -