CHƯƠNG 1: LÝ THUYẾT VỀ THAO TÁC TRÊN CƠ SỞ DỮ LIỆU QUAN HỆ 1. Các phép toán logic 1. Logic hình thức Logic hình thức là loại logic được xác định bởi cú pháp và ngữ nghĩa như sau: Cú pháp Cú pháp của logic hình thức là việc sử dụng các đối tượng và các phép kết nối logic các đối tượng lại để tạo ra một biểu thức logic chuẩn (theo một nghĩa nào đó). Như vậy biểu thức logic bao gồm: - Tập kí hiệu là các kí tự: a, b, c, …, A, B, C, … - Tập các phép toán logic: NOT, AND, OR, XOR (tương ứng với các phép toán đại số quan hệ , , , ) - Dùng một dãy hữu hạn các ký hiệu và các phép toán trên để tạo ra biểu thức logic.
- Cho trước một tập các quy tắc, dựa vào tập quy tắc này để tạo ra các biểu thức logic chuẩn. Ngữ nghĩa Ngữ nghĩa của biểu thức logic là ý nghĩa của biểu thức logic đó. Có thể dùng các phương pháp: quy nạp, đệ quy, suy luận, các quy tắc, các lược đồ chứng minh,. để chỉ ra một biểu thức logic cho trước là chuẩn hay không chuẩn và cho biết chân lý của biểu thức đó.
Logic mệnh đề và chân lý - Mệnh đề là một phát biểu để diễn tả một khẳng định là đúng hoặc sai, nó không thể vừa đúng lại vừa sai, hay mang tính chất mập mờ. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 - Giá trị đúng hay sai của mệnh đề được gọi là chân lý của mệnh đề và thường được kí hiệu là 1 (hoặc T hoặc True) đối với chân lý đúng , còn chân lý sai được kí hiệu là 0 (hoặc F hoặc False). - Mệnh đề logic rất quan trọng trong khoa học máy tính. Các kí hiệu dùng trong mệnh đề logic () Dùng để chỉ độ ưu tiên của phép toán logic.
Phủ định (NOT) Hội (Conjunction AND) Tuyển (Disjunction OR) Ký hiệu điều kiện (If…Then…) Kéo theo hai chiều (If AND Only If) Tổng trực giao (XOR) Kí hiệu Ai i 1, n là mệnh đề thứ i, có thể dùng mệnh đề như là tham số, các kí hiệu logic có ý nghĩa không đổi, còn các tham số có nội dung phụ thuộc và ngữ cảnh. Nói chung các kí hiệu trong biểu thức logic là hữu hạn hoặc đếm được, nhưng hầu hết các kết luận vẫn đúng cho trường hợp không đếm được. Mệnh đề được chia làm hai loại cơ bản: - Mệnh đề sơ cấp (elementary), nó là các nguyên tử (atom)-không thể chia nhỏ được; - Mệnh đề phức hợp (compound), đó mệnh đề được tạo ra từ các mệnh đề khác bằng cách sử dụng các phép toán logic. Để máy tính hiểu được, chúng ta dùng các kí hiệu cho các mệnh đề, được gọi là biến mệnh đề.
Các biến mệnh đề được kí hiệu bởi các chữ cái thường. Biểu thức logic: Biểu thức logic chính là mệnh đề phức hợp. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Chân lý của phép toán logic được cho ở bảng 1.1 Chân lý của các phép toán logic p q p pq pq p q pq pq 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 Mức ưu tiên của các phép toán logic được thể hiện ở bảng 1. Ưu tiên các phép toán logic Ký hiệu phép toán Nghĩa của phép toán , , Phủ định , Hội, tuyển , , Kéo theo, tương đương, tổng trực giao Tương đương của hai biểu thức logic 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 lý.
Các quy tắc thay thế Quy tắc 1: (Quy tắc thay thế tương đương). Cho E là một biểu thức logic, nếu thay thế một biểu thức con của nó bởi một biểu thức tương đương với biểu thức con đó, biểu thức logic E’ mới nhận được sẽ tương đương với E. Quy tắc 2: (Tính bất biến đối với biểu thức logic hằng đúng) Cho E là biểu thức hằng đúng, nếu thay thế một mệnh đề p nào đó trong E bởi một biểu thức logic bất kỳ ta sẽ nhận được biểu thức logic E’ mới cũng là hằng đúng. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Ghi chú: Kết quả tương tự cho biểu thức hằng sai.
Các dạng chính tắc Biểu thức hội cơ bản. Biểu thức logic F = F (p1, p2, ., pn ), trong đó pi ( i 1, n ) là các biến mệnh đề sơ cấp, được gọi là biểu thức hội cơ bản, nếu: F = q 1 q2 . qn ; với qi = pi hoặc qi =pi ( i 1, n ) Biểu thức tuyển cơ bản. Biểu thức logic E = E (p1, p2, .pn ), trong đó pi ( i 1, n ) là các biến mệnh đề sơ cấp, được gọi là biểu thức tuyển cơ bản, nếu: E = q1 q2 . qn; với qi = pi hoặc qi =pi ( i 1, n ) Biểu thức logic E = E (p1, p2, .pn ), trong đó pi ( i 1, n ) là các biến mệnh đề sơ cấp, được gọi là dạng tuyển chính tắc, nếu: E = E1 E2 . En ; trong đó mỗi Ei ( i 1, n ) là một biểu thức hội cơ bản của các pi ( i 1, n ). Định lý: Mọi biểu thức logic E (p1, p2, ., pn ) đều tương đương với một biểu thức tuyển chính tắc duy nhất. Em (duy nhất ) với Ei ( i 1, m ) là các biểu thức hội cơ bản.
Nghĩa là Ei = q1 q2 . qn với qi = pi hoặc qi =pi ( i 1, n ). Biểu thức logic hội chính tắc Biểu thức logic F = F (p1, p2, ., pn ), trong đó pi ( i 1, n ) là các biến mệnh đề sơ cấp, được gọi là dạng hội chính tắc, nếu: F = F 1 F2 . Fn , trong đó mỗi Fi ( i 1, n ) là một biểu thức tuyển cơ bản của các pi ( i 1, n ) Định lý: Mọi biểu thức logic F (p1, p2, ., pn ) đều tương đương với một biểu thức hội chính tắc duy nhất. Fm Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 (duy nhất ) với Fi ( i 1, m ) là các biểu thức tuyển cơ bản. Nghĩa là Fi = q1 q2 . qn với qi = pi hoặc qi =pi ( i 1, n ).2 Tổng quan về CSDL phân tán Xử lý phân tán hay còn gọi là hệ thống tính toán phân tán đó là một hệ thống bao gồm một số bộ xử lý tự vận hành được liên kết thành mạng và hợp đồng thực hiện các nhiệm vụ mà chúng được phân công. Các bộ xử lý có thể thực hiện được các chương trình tiền định trên đó.
Những đối tượng được phân tán: - Các thiết bị xử lý, các chức năng xử lý: Nhiều chức năng của hệ thống có thể được chuyển giao cho các thành phần: phần cứng và phần mềm. - Dữ liệu: Dữ liệu được dùng bởi một số ứng dụng có thể được phân tán tới một số vị trí xử lý. - Quyền điều khiển: cũng có thể được phân tán. Quyền điều khiển một số nhiệm vụ cũng được phân tán.
Hệ thống xử lý phân tán có thể phân thành các loại như sau: - Mức độ kết nối, - Sự liên đới giữa các thành phần, - Cấu trúc tương giao, - Sự đồng bộ hoá giữa các thành phần. Sự cần thiết phân tán: -Nhằm thích ứng tốt hơn với việc phân bố rộng rãi của các công ty, xí nghiệp, cơ quan. - Nhiều ứng dụng công nghệ hiện đại cần được phân tán. Lý do của việc xử lý phân tán: Để thực hiện tốt hơn các bài toán lớn và phức tạp mà chúng gặp phải hiện nay bằng cách sử dụng quy tắc ”Chia để trị”.
Các ưu điểm cơ bản của xử lý phân tán: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 - Tận dụng được sức mạnh tính toán xử lý song song bằng cách sử dụng nhiều bộ xử lý đồng thời. - Giải quyết bài toán theo từng nhóm hoạt động độc lập nên có thể kiểm soát được chi phí phát triển phần mềm. - Các hệ cơ sở dữ liệu phấn tán cũng có thể được xem xét trong khuôn khổ của bộ khung này làm cho việc xử lý dữ liệu phân tán dễ dàng và hiệu quả hơn. Một số hệ thống xử lí hay được dùng: - Hệ thống đa xử lý có bộ nhớ chung [2].
- Hệ đa bộ xử lý có shared disk [2]. - Hệ đa bộ xử lý sở hữu cá nhân [2]. Ghi chú: Phân bố vật lý của bộ xử lý không nhất thiết là phải cách xa nhau về mặt địa lý; chúng có thể ở trong cùng máy, một văn phòng,… giao tiếp giữa các bộ xử lý được thực hiện thông qua mạng truyền thông. 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 không phải là một tập hợp các tệp dữ liệu được lưu trữ riêng rẽ tại các nút của mạng máy tính mà 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ấu trúc và vừa phải được truy xuất qua một giao diện chung. Phân bố vật lý của các dữ liệu không phải là vấn đề quyết định trong DDBS. Tuy vậy, viêc phân bố vật lý của các dữ liệu sẽ nảy sinh ra các vấn đề rất phức tạp như thực hiện các cấu trúc truy vấn, vấn đề cấp phát.
Nhận xét: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.vn/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 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 (hình 1.1) khi đó tất cả yêu cầu truy xuất CSDL điều được chuyển đến workstation 2.