Tài liệu Rút gọn câu truy vấn sql qua phán đoán và cưỡng chế

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BÙI MẠNH HÙNG RÚT GỌN CÂU TRUY VẤN PHÂN TÁN QUA PHÁN ĐOÁN VÀ CƢỠNG CHẾ LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN 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 BÙI MẠNH HÙNG RÚT GỌN CÂU TRUY VẤN PHÂN TÁN QUA PHÁN ĐOÁN VÀ CƢỠNG CHẾ Thuộc chuyên ngành : Khoa học máy tính Mã số chuyên ngành : 60 48 01 LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH PGS. TS. LÊ HUY THẬP THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn i LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Qua đây em xin chân thành cảm ơn toàn thể các thầy cô trong khoa đào tạo sau đại học trường Đại học Công nghệ Thông tin và Truyền thông và đặc biệt là thầy PGS.TS. Lê Huy Thập, đã tạo điều kiện thuận lợi và hướng dẫn em để hoàn thành luận văn này. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii MỤC LỤC LỜI CAM ĐOAN .................................................................................................................. i DANH MỤC BẢNG BIỂU ................................................................................................. iv DANH MỤC HÌNH ............................................................................................................. v BẢNG DANH MỤC CÁC KÍ HIỆU ................................................................................ vii LỜI MỞ ĐẦU....................................................................................................................... 1 1. Đặt vấn đề ...................................................................................................................... 1 2. Đối tượng và phạm vi nghiên cứu ................................................................................. 1 3. Hướng nghiên cứu của đề tài ......................................................................................... 1 4. Phương pháp nghiên cứu. .............................................................................................. 1 5. Ý nghĩa khoa học của đề tài. .......................................................................................... 2 6. Các kết quả dự kiến đạt được......................................................................................... 2 Chƣơng 1. CƠ SỞ LÝ THUYẾT ........................................................................................ 3 1.1. Mệnh đề logic và các phép toán mệnh đề ................................................................... 3 1.1.1 Khái niệm về mệnh đề .......................................................................................... 3 1.1.2 Biến mệnh đề và biểu thức mệnh đề ..................................................................... 3 1.1.3 Các phép toán mệnh đề ......................................................................................... 4 1.1.4. Các biểu thức logic cơ bản ................................................................................... 5 1.2. Các khái niệm cơ bản của CSDL phân tán ................................................................ 6 1.2.1. Khái niệm về phán đoán ...................................................................................... 8 1.2.2. Khái niệm về cưỡng chế .................................................................................... 13 1.3. Kết luận chương 1 ..................................................................................................... 19 Chƣơng 2: RÚT GỌN CÂU TRUY VẤN PHÂN TÁN QUA PHÁN ĐOÁN VÀ CƢỠNG CHẾ..................................................................................................................... 20 2.1. Các thuật toán rút gọn câu truy vấn .......................................................................... 20 2.1.1. Rút gọn cho phân mảnh ngang. ......................................................................... 21 2.1.2. Rút gọn phân mảnh dọc ..................................................................................... 32 2.1.3. Rút gọn phân mảnh hỗn hợp .............................................................................. 35 2.2. Rút gọn câu truy vấn phân tán qua phán đoán và cưỡng chế ................................... 39 2.2.1. Rút gọn phân mảnh ngang qua phán đoán và cưỡng chế .................................. 40 2.2.2. Rút gọn phân mảnh dọc qua phán đoán và cưỡng chế....................................... 47 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii 2.2.3. Rút gọn phân mảnh hỗn hợp qua phán đoán và cưỡng chế ............................... 49 2.3. Kết luận chương 2 ..................................................................................................... 53 Chƣơng 3: CHƢƠNG TRÌNH ỨNG DỤNG .................................................................. 54 3.1. Chương trình ứng dụng hỗ trợ khách hàng sử dụng dịch vụ viễn thông tại Bưu điện Cầu Giấy .......................................................................................................................... 54 3.2. Kết luận chương 3 ..................................................................................................... 54 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA LUẬN VĂN ........................................ 68 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iv DANH MỤC BẢNG BIỂU Bảng 1.1. Bảng chân trị các phép toán mệnh đề .........................................................5 Bảng 1.2. Mức ưu tiên của các phép toán logic ..........................................................5 Bảng 2.1-1. Quan hệ NhanVien ................................................................................20 Bảng 2.1-2. Quan hệ DuAn .......................................................................................20 Bảng 2.1-3. Quan hệ TraLuong.................................................................................21 Bảng 2.1-4. Quan hệ PhanNhiem ..............................................................................21 Bảng 2.1-5 Mảnh ngang DuAn H1 ............................................................................23 Bảng 2.1-6 Mảnh ngang DuAn H2 .............................................................................24 Bảng 2.1-7. Mảnh ngang DuAn H3 ............................................................................24 Bảng 2.1-8. TraLuong1 ..............................................................................................26 Bảng 2.1-9. TraLuong2 ..............................................................................................26 Bảng 2.1-10. Phân hoạch ngang cho quan hệ DuAn: DuAnH1, DuAnH3, DuAnH4, DuAnH6 ...28 Bảng 2.1-11. Khoa ....................................................................................................28 Bảng 2.1-12. Sinhvien ..............................................................................................29 Bảng 2.1-13. Monhoc ................................................................................................29 Bảng 2.1-14. Diem ....................................................................................................29 Bảng 2.1-15: Sinhvien1 .............................................................................................30 Bảng 2.1-16: Sinhvien2 .............................................................................................30 Bảng 2.1-17 ...............................................................................................................33 Bảng 2.1-18 ...............................................................................................................33 Bảng 2.2-1. Quan hệ EMP ........................................................................................50 Bảng 2.2-2. Mảnh hỗn hợp EMPHH1 ......................................................................50 Bảng 2.2-3. Mảnh hỗn hợp EMPHH2 ......................................................................50 Bảng 2.2-4. Mảnh hỗn hợp EMPHH3 ......................................................................50 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn v DANH MỤC HÌNH Hình 1.1. CSDL tập trung, không phải là DDBS .................................................................. 7 Hình 1.2. CSDL được phân tán trên mạng, DDBS ................................................................ 7 Hình 2.1: Biểu diễn mối liên hệ giữa các quan hệ nhờ các đường nối ................................ 22 Hình 2.2: Mối liên hệ giữa các quan hệ. .............................................................................. 29 Hình 2.3. Rút gọn phân mảnh ngang với phép nối .............................................................. 34 Hình 2.4. Phép chiếu vô dụng .............................................................................................. 35 Hình 2.7. (b) vấn tin đã rút gọn............................................................................................ 44 Hình 2.8. Vấn tin gốc của ví dụ 2.16 ................................................................................... 46 Hình 2.9. Vấn tin gốc đã được giao hoán ............................................................................ 46 Hình 2.10. Vấn tin sau khi dùng mệnh đề mâu thuẫn .......................................................... 46 Hình 2.11. Cây vấn tin sau khi giao hoán phép hợp và phép nối ....................................... 47 Hình 2.12. Rút gọn cho phân mảnh dẫn xuất....................................................................... 47 Hình 2.13 a,b,c. Rút gọn cho phân mảnh dọc ...................................................................... 49 Hình 2.14. Cây vấn tin gốc .................................................................................................. 51 Hình 2.15. Cây vấn tin đã loại EMPHH1 ............................................................................ 52 Hình 2.16: Cây vấn tin đã đẩy phép chiếu xuống, phép nối lên .......................................... 52 Hình 2.17. Câu vấn tin đã rút gọn ........................................................................................ 53 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vi DANH MỤC CÁC CHỮ VIẾT TẮT CSDL Cơ sở dữ liệu CPU Central Processing Unit (Bộ xử lý trung tâm) SQL Structured Query Language (Ngôn ngữ truy vấn có cấu trúc) DDBS Distributed Database System (Hệ cơ sở dữ liệu phân tán) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vii BẢNG DANH MỤC CÁC KÍ HIỆU Phép giao Phép hợp ∈ Ký hiệu thuộc Ký hiệu không thuộc - Phép trừ X Tích đề các ⨝ Phép nối π Phép chiếu θ Tê ta * Kết nối tự nhiên > Phép so sánh lớn hơn < Phép so sánh bé hơn ÷ Phép chia ˄ Phép và ˄ Phép hoặc Tập rỗng ¬ Phủ định = Phép bằng ≥ Lớn hơn hoặc bằng ≤ Nhỏ hơn hoặc bằng σ Phép chọn Π Pi Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 LỜI MỞ ĐẦU 1. Đặt vấn đề Ngày nay cùng với sự phát triển về khoa học kỹ thuật, bùng nổ về thông tin. cung cấp đa dạng các loại hình thương mại, quản lý và các dịch vụ đa phương tiện cho người sử dụng. Kết nối máy tính thành mạng với mục tiêu chia sẻ tài nguyên, khai thác có hiệu quả các tài nguyên thông tin, nâng cao khả năng tích hợp và trao đổi các loại dữ liệu giữa các thành phần trên mạng, nhu cầu thu thập, lưu trữ, xử lý và trao đổi thông tin ngày càng tăng . Khi khối lượng thông tin phải xử lý ngày càng lớn, phong phú và đa dạng thì vấn đề đặt ra là xử lý thông tin như thế nào để tìm cách giảm thiểu thời gian và các chi phí hoặc tăng cao hiệu năng xử lý Một trong những giải pháp có tính khả thi là phải xử lý các câu lệnh SQL khi truy vấn dữ liệu dựa vào các quy tắc phán đoán – cưỡng chế và các phương pháp rút gọn ngay trên cây thứ tự hoặc gộp nhóm khi phân mảnh mà chúng ta sẽ gọi là các giải pháp tiền xử lý. Đó cũng chính là mục đích tôi chọn nghiên cứu “ Rút gọn câu truy vấn SQL qua phán đoán và cưỡng chế ” làm đề tài luận văn tốt nghiệp của mình. 2. Đối tƣợng và phạm vi nghiên cứu - Đối tượng nghiên cứu là cơ sở dữ liệu phân tán, xử lý song song và phân tán. - Phạm vi nghiên cứu là một số các phương pháp rút gọn câu truy vấn SQL trong cơ sở dữ liệu phân tán. 3. Hƣớng nghiên cứu của đề tài - Nghiên cứu tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán, các phương pháp, kỹ thuật, các thuật toán liên quan đến rút gọn câu truy vấn SQL đặc biệt là phương pháp phán đoán, cưỡng chế. - Nghiên cứu các mô hình chi phí song song và mô hình chi phí song song trên bộ tối ưu hóa truy vấn. Nghiên cứu mô hình tối ưu hóa hai pha. 4. Phƣơng pháp nghiên cứu. - Nghiên cứu kỹ các kiến thức, chủ đề có liên quan đến đề tài. - Nghiên cứu các quy tắc và phương pháp phán đoán và cưỡng chế. - Nắm vững các kiến thức về rút gọn câu vấn tin dựa vào phán đoán. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 5. Ý nghĩa khoa học của đề tài. Luận văn giúp cho việc tiền xử lý câu lệnh SQL bằng phương pháp phán đoán cưỡng chế và rút gọn các câu lệnh loại này. 6. Các kết quả dự kiến đạt đƣợc - Giới thiệu tổng quan về CSDL phân tán. - Trình bày các phương pháp, thuật toán xử lý, tối ưu hóa truy vấn phân tán đặc biệt bằng phương pháp phán đoán và cưỡng chế. - Cài đặt thử nghiệm một thuật toán rút gọn câu truy vấn phân tán. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 Chƣơng 1. CƠ SỞ LÝ THUYẾT 1.1. Mệnh đề logic và các phép toán mệnh đề 1.1.1. Khái niệm về mệnh đề Mệnh đề là một câu khẳng định đúng hoặc một câu khẳng định sai. Câu khẳng định đúng gọi là mệnh đề đúng (mệnh đề có chân trị đúng). Câu khẳng định sai gọi là mệnh đề sai (mệnh đề có chân trị sai). Kí hiệu các mệnh đề: P, Q, R… Kí hiệu chân trị đúng là 1 (hay T - True), chân trị sai là 0 (hay F - False) Ví dụ: a) Hà Nội là thủ đô nước Việt Nam: Là mệnh đề đúng (1). Kí hiệu mệnh đề: P b) 11 chia hết cho 5: Là mệnh đề sai (0). Kí hiệu mệnh đề: Q c) 4+4=8: Là mệnh đề đúng (1). Kí hiệu mệnh đề: R d) Hôm nay trời có đẹp không?: Không phải là mệnh đề. Câu hỏi nghi vấn. Mệnh đề sơ cấp: (elementary proposition) Là mệnh đề không thể phân nhỏ hơn được nữa – có thể nói đó là phát biểu đơn giản nhất. Ví dụ: “Một cộng một bằng 2” “ 7 là số nguyên tố” Các mệnh đề sơ cấp thường được gắn với các ký hiệu như các chữ p, q, r,... mà ta gọi là các biến mệnh đề logic. Mệnh đề phức hợp: (compound proposition) Mệnh đề phức hợp là mệnh đề được tạo ra từ các mệnh đề bằng cách dùng các từ liên kết như “và” (AND), “hoặc” (OR),.... Ví dụ:  “Số 2 là số chẵn và là số nguyên tố” gồm 2 mệnh đề: “Số 2 là số chẵn” từ nối “và” và “ Số 2 là số nguyên tố”; 1.1.2. Biến mệnh đề và biểu thức mệnh đề Biến mệnh đề: p gọi là biến mệnh đề nếu nó nhận giá trị là một mệnh đề nào đó. Ví dụ: p là biến mệnh đề có thể nhận giá trị là các mệnh đề P, Q, R ở trên. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 Biểu thức mệnh đề: Cho P, Q, R…là các mệnh đề. Nếu các mệnh đề này liên kết với nhau bằng các phép toán thì ta được một biểu thức mệnh đề. 1.1.3. Các phép toán mệnh đề Phép phủ định (NOT): Phủ định của mệnh đề p kí hiệu là p. Chân trị của p là 0 nếu chân trị của p là 1 và ngược lại. Ví dụ: p=“2>0” p=“2≤0” Phép hội (AND): Phép hội của hai mệnh đề q, q kí hiệu là p q (đọc là p và q) chỉ đúng khi cả p và q cùng đúng. Ví dụ: “Chiều nay trời đẹp và trận bóng đá sẽ hấp dẫn”: p q Phép tuyển (OR): Phép tuyển của hai mệnh đề p, q kí hiệu là p q (đọc là p hoặc q) chỉ sai khi cả p và q cùng sai Ví dụ: “Danh sách sinh viên quê ỏ Thái Nguyên hoặc/hay/và Hà Nội”: p q Điều kiện lọc danh sách là: (QUEQUAN=”Thái Nguyên”) OR (QUEQUAN=”Hà Nội”) Phép tuyển loại (XOR): Phép tuyển loại của hai mệnh đề p, q kí hiệu là p q (đọc là hoặc p hoặc q) chỉ đúng khi chỉ 1 trong 2 mệnh đề là đúng. Ví dụ: “Sinh viên A quê ở Thái Nguyên hoặc Hà Nội”: p q Phép kéo theo: Phép kéo theo của 2 mệnh đề p, q kí hiệu là p q là một mệnh đề chỉ sai khi p đúng q sai. Ví dụ: “Nếu A vượt đèn đỏ thì A sẽ vi phạm luật giao thông”: p q Phép tương đương: Phép tương đương của 2 mệnh đề p, q kí hiệu là p một mệnh đề chỉ đúng khi cả p và q cùng đúng hoặc cùng sai. Ví dụ: p: “Tứ giác ABCD là hình vuông” q: “Tứ giác ABCD là hình chữ nhật có 2 đường chéo vuông góc” Ta có p q Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn q là 5 Bảng chân trị của các phép toán mệnh đề p q p q 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 p q p q p q p q p q Bảng 1.1. Bảng chân trị các phép toán mệnh đề Mức ƣu tiên của các phép toán logic Thứ tự ưu tiên của các phép toán logic được liệt kê theo mức yếu dần từ trên xuống dưới ở bảng sau: Ký hiệu phép toán , Nghĩa của phép toán Phủ định , Hội, tuyển, tuyển loại , , Kéo theo, tương đương , Bảng 1.2. Mức ưu tiên của các phép toán logic 1.1.4. Các biểu thức logic cơ bản Biểu thức logic Biểu thức logic có thể nói chính là mệnh đề phức hợp, biểu thức logic thường được ký hiệu bởi các chữ in to. Ví dụ: (r s), E = (p P = E, F G, (G ( q H) r) ) ( G E), trong đó P, E, F, G, H là các biểu thức logic. Bảng chân trị của biểu thức logic là bảng liệt kê chân trị có thể có theo mọi khả năng chân trị của các biến mệnh đề có trong biểu thức. Hai biểu thức logic E và F được gọi là tương đương với nhau và viết E F khi E và F luôn luôn có cùng chân trị, khi đó ta nói “E tương đương với F”. Để kiểm tra xem hai biểu thức logic có tương đương với nhau hay không chúng ta dựa vào bảng chân trị hay bằng phương pháp chứng minh logic. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 Hai biểu thức logic E và F tƣơng đƣơng sẽ đƣợc viết E F. Ví dụ: Cho hai biểu thức logic E = p q và F = p q thì E F. Biểu thức logic E được gọi là hằng True nếu chân trị của E luôn luôn là 1, tức là E 1. Ví dụ: E=p p thì E 1. Biểu thức logic E được gọi là hằng False nếu chân trị của E luôn luôn là 0, tức là E 0. Ví dụ: E=p p thì E 0. Chú ý Theo định nghĩa E1 F1 khi và chỉ khi E1 F1, điều này có thể viết gọn lại như sau: E1 F1 1. Ví dụ: E1 = p p thì E1 1. F1 = (p q) q) thì F1 ( p Ta có thể kết luận E1 Quan hệ bắc cầu: nếu E F1 1. 1. F và F G thì E G. 1.2. Các khái niệm cơ bản của CSDL phân tán Hệ cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán Hệ CSDL phân tán (Distributed Database System – DDBS) là một tập hợp dữ liệu có liên đới logic và được phân bố trên các nút của một mạng máy tính. Hệ quản trị CSDL phân tán (Distributed Database Management System – DDBMS) là một hệ thống phần mềm cho phép quản lý các DDBS và làm cho việc phân tán trở nên vô hình đối với người sử dụng. Như vậy DDBS là một tập các tệp dữ liệu vừa có liên đới logic, vừa phải có cùng cấu trúc và vừa phải được truy xuất qua một giao diện chung. Và phân bố vật lý của các dữ liệu không phải là vấn đề quyết định. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 Nhận xét: Nếu CSDL nằm tại một nút mạng thì nó không phải là DDBS, vì vấn đề quản trị CSDL không khác với quản trị CSDL trong môi trường tập trung kiểu client/server của mạng. Ví dụ: CSDL trong hình 1.1 không phải là DDBS. Workstation1 Workstation2 Workstation5 Mạng Truyền DL Workstation4 Workstation3 Hình 1.1. CSDL tập trung, không phải là DDBS Nếu một cơ sở dữ liệu được phân tán trên nhiều nút mạng. khi đó CSDL sẽ là cơ sở dữ liệu phân tán. Ví dụ: hình 1.2 Workstation1 Workstation2 Workstation5 Mạng Truyền DL Workstation4 Workstation3 Hình 1.2. CSDL được phân tán trên mạng, DDBS Hệ quản trị CSDL phân tán có khả năng phân mảnh CSDL khái niệm và cho phép cục bộ hoá dữ liệu. Có hai ưu điểm nổi bật: • Vì mỗi trạm chỉ xử lý một phần CSDL, sự tranh chấp về CPU và các dịch vụ vào/ra không nghiêm trọng như trong các hệ CSDL tập trung. • Tính cục bộ làm giảm trễ truy nhập từ xa thường gặp trên các mạng diện rộng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 Hầu hết các hệ CSDL phân tán được cấu trúc nhằm tận dụng tối đa những ưu điểm của tính cục bộ dữ liệu. Lợi ích đầy đủ của việc giảm tranh chấp và giảm chi phí truyền chỉ có thể có được bằng cách phân mảnh và phân tán dữ liệu hợp lý. Mỗi quan hệ toàn cục có thể chia thành nhiều phần không chồng lặp lên nhau được gọi là phân mảnh. Ánh xạ giữa các quan hệ toàn cục và phân mảnh được định nghĩa là lược đồ phân mảnh. Ánh xạ này là mối quan hệ một-nhiều. Ví dụ, nhiều phân mảnh tương ứng với một quan hệ toàn cục, nhưng chỉ một quan hệ toàn cục tương ứng với một phân mảnh. Các phân mảnh được chỉ ra bằng tên của quan hệ toàn cục với một chỉ số (chỉ số phân mảnh), ví dụ, Ri chỉ đến phân mảnh thứ i trong quan hệ toàn cục R Các kiểu phân mảnh dữ liệu bao gồm phân mảnh ngang và phân mảnh dọc và một kiểu phân mảnh phức tạp hơn là sự hết hợp của 2 loại trên. Trong tất cả các kiểu phân mảnh, một phân mảnh có thể được định nghĩa bằng một biểu thức ngôn ngữ quan hệ cho các quan hệ toàn cục như là các toán hạng và kết quả đầu ra là các phân mảnh. Các khái niệm, điều kiện về phán đoán và cƣỡng chế Dùng tập các mệnh đề để kiểm tra các giao dịch, cú pháp và tính toàn vẹn ngữ nghĩa…nếu thỏa mãn thì đó là một phán đoán, sai cũng là phán đoán nhưng nếu phán đoán đúng thì sẽ cưỡng chế thực hiện các câu vấn tin có liên quan còn nếu sai thì: • Hoặc hủy câu vấn tin • Hoặc chỉnh sửa câu vấn tin Từ đó để quyết định câu vấn tin có được thực hiện hoặc không Ví dụ: Khi nhập một bản ghi vào quan hệ con thì bản ghi đó có liên quan đến một bản ghi ở quan hệ mẹ. Vậy liệu ở quan hệ mẹ đã có bản ghi liên quan. 1.2.1. Khái niệm về phán đoán Dựa vào việc phát hiện mâu thuẫn (Phán đoán): Giả sử khi thực hiện cập nhật u sẽ chuyển CSDL từ D sang Du. Thuật toán cưỡng chế phải xác nhận rằng tất cả các ràng buộc liên đới vẫn đúng trong Du. Nếu trạng thái Du không nhất quán thì DBMS sẽ cố gắng chuyển sang trạng thái khác là D‟u bằng cách hiệu chỉnh Du qua các thao tác “bù trừ” để có D‟u nhất quán, nếu không được thì phải quay lại trạng thái D. Cách kiểm tra này được áp dụng sau khi trạng thái của SCDL đã thay đổi nên nó được gọi là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 9 kiểm tra sau (Posttest). Cách tiếp cận này sẽ không hiệu quả nếu hệ thống phản hồi lại rất nhiều thao tác khi ràng buộc bị vi phạm. Ví dụ 1.1: g ASG, j PROJ: g.PNO = j.PNO Đây là phán đoán khoá ngoại, nói rằng một dự án được tham chiếu trong quan hệ ASG phải tồn tại (chứ không phải là ) trong quan hệ PROJ, do đó j không được lượng từ hoá phổ dụng cho nên câu vấn tin trên không thể được xử lý bởi phép hiệu chỉnh vấn tin. Phương pháp ngăn chặn mâu thuẫn (kiểm tra trước) khác là dựa vào việc tạo ra các phán đoán. Biên dịch vào lúc định nghĩa phán đoán và có thể sử dụng để ngăn chặn sự xuất hiện các mâu thuẫn trong CSDL. Đây là một phương pháp ngăn chặn tổng quát, có thể xử lý được toàn bộ các phán đoán đã được giới thiệu ở trên. Định nghĩa các phán đoán biên dịch dựa trên khái niệm quan hệ vi phân (differentinal relation). Gọi u là một cập nhật trên quan hệ R; R+ và R- là các quan hệ vi phân của R do u gây ra; R+ gồm các bộ được chèn vào R, còn R- gồm các bộ được xoá khỏi R; R+ = nếu u là thao tác xoá, R- = nếu u là thao tác chèn và R+ (R-R-) là tập các bộ (từ R) nếu u là sửa đổi bộ. Một phán đoán biên dịch là bộ ba (R,T,C), trong đó R là quan hệ, T là kiểu cập nhật; C là một phán đoán biến thiên trên các quan hệ vi phân có mặt trong một cập nhật kiểu T. Khi một ràng buộc I được định nghĩa, một tập phán đoán biên dịch có thể được sinh ra cho các quan hệ. Mỗi khi một quan hệ có trong I được cập nhật bởi chương trình u, các phán đoán biên dịch cần phải được kiểm tra chỉ là các phán đoán được định nghĩa trên I cho kiểu cập nhật của u. Cách làm này sẽ làm giảm số lượng phán đoán vì chỉ có các phán đoán thuộc kiểu u cần được kiểm tra, chi phí cưỡng chế thi hành cũng nhỏ hơn chi phí cưỡng chế I vì các hệ vi phân nhỏ hơn nhiều so với quan hệ gốc. Phán đoán biên dịch, thu được bằng cách dùng các qui tắc biến đổi cho phán đoán gốc. Các qui tắc này dựa trên ngữ nghĩa của phán đoán và các hoán vị lượng từ. Chúng cho phép thay các quan hệ cơ sở bằng các quan hệ vi phân. Quá trình tạo ra phán đoán biên dịch từ các quan hệ gốc được gọi là quá trình đơn giản hoá. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 10 Ví dụ 1.2: Xét lại ví dụ 1.1. Phán đoán biên dịch đi kèm với ràng buộc này là: (ASG, INSERT, C1), (PROJ, DELETE, C2), và (PROJ, MODIFI, C3) Trong đó: C1 là NEW ASG+, j PROJ : NEW.PNO = j.PNO C2 là g ASG , OLD PROJ- : g.PNO ASG , OLD PROJ- : OLD.PNO C3 là g g.PNO NEW PROJ+ : OLD.PNO OR OLD.PNO = NEW.PNO Ưu điểm của phán đoán biên dịch là hiển nhiên. Chẳng hạn thao tác xóa trên quan hệ ASG không gây ra bất kỳ một kiểm tra nào. Thuật toán cưỡng chế sử dụng phán đoán biên dịch và được chuyên biệt hóa theo từng lớp phán đoán. Có 3 lớp phán đoán cơ bản: phán đoán đơn quan hệ, đa quan hệ và các phán đoán có hàm gộp nhóm. Kiểm soát toàn vẹn ngữ nghĩa phân tán 1.2.1.1. Lớp phán đoán riêng Là các phán đoán đơn biến và đơn quan hệ. Chúng chỉ đề cập đến các bộ được cập nhật, độc lập với phần còn lại của CSDL. Định nghĩa phán đoán riêng được gửi đến tất cả vị trí lưu các mảnh của quan hệ có mặt trong phán đoán. Các phán đoán phải tương thích với vị trí phân mảnh ở hai cấp: cấp vị trí và cấp dữ liệu. Phán đoán C xem là không tương thích với vị trí phân mảnh P, nếu C đúng suy ra p sai. Khi đó p‟ đoán C bị loại bỏ toàn cục. Nếu có tương thích, thì phán đoán C sẽ được lưu lại tại mọi vị trí. Chú ý, việc thẩm tra tính tương thích được thực hiện cho các phán đoán biên dịch kiểu cập nhật chèn. Xét CSDL sau: EMP (ENO, ENAME, TITLE) PROJ(PNO, PNAME, BUDGET) ASG(ENO, PNO, RESP, DUR) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 11 Ví dụ 1.3: Khoá ngoại PNO IN ASG REFERENCES PNO IN PROJ Khoá, mã số PNO trong quan hệ ASG là khoá ngoại tương ứng với khoá chính PNO trong quan hệ PROJ. Nói cách khác, một dự án được tham chiếu trong quan hệ ASG phải tồn tại trong quan hệ PROJ. Ví dụ 1.4: Phụ thuộc hàm ENO IN EMP DETERMINES ENAME Giá trị mã số nhân viên ENO, xác định giá trị hàm tên nhân viên ENAME. Ví dụ 1.5: Giả sử quan hệ EMP được phân mảnh ngang bởi 3 vị trí: P1 : 0 ENO “E3” P2: “E3” < ENO “E6” P3: ENO > “E6” Và cho phán đoán miền biến thiên C: ENO < “E4” thì phán đoán C tương thích với p1 (nếu C đúng thì p1 đúng) và p2 (nếu C đúng thì chưa chắc p2 sai, nhưng không tương thích với p3) nếu C đúng thì p3 sai. Nhưng rõ ràng là P3 sai (vì ENO > “E6”) nên phán đoán C không tương thích với P3 khi đó C bị loại bỏ và EMP không thoả mãn phán đoán C. 1.2.1.2. Phán đoán hƣớng tập hợp Phán đoán hướng tập hợp thuộc loại đa biến; nghĩa là chúng chứa mệnh đề nối biến đơn quan hệ (như phụ thuộc hàm ở ví dụ 1.2), mã số nhân viên xác định phụ thuộc hàm tên nhân viên là: ENO IN EMP DETEMINES ENAME Và đa biến đa quan hệ nhưng ràng buộc khoá ngoại ở ví dụ 1.1: Mã số PNO dự án trong quan hệ ASG là khoá ngoại tương ứng với khoá chính PNO của hệ PROJ. Nói cách khác là một dự án được tham chiếu trong quan hệ ASG phải tồn tại trong quan hệ PROJ. Mặc dù mệnh đề phán đoán có thể thuộc loại đa quan hệ nhưng một phán đoán Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn