Giải pháp rút gọn câu vấn tin phân tán để xử lý song song - Luận văn Nguyễn Tuấn Anh

Khám phá các giải pháp rút gọn câu vấn tin phân tán, tối ưu hóa xử lý song song. Nâng cao hiệu suất truy vấn dữ liệu trong môi trường phân tán.

• Tác giả: Nguyễn Tuấn Anh
• Người hướng dẫn: Pgs. Lê Huy Thập
• Trường học: Trường Đại Học Công Nghệ Thông Tin Và Truyền Thông - Đại Học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Một Số Giải Pháp Rút Gọn Câu Vấn Tin Phân Tán Để Xử Lí Song Song
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2013
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH MỤC CHỮ VIẾT TẮT
• PHẦN MỞ ĐẦU
• 1.1. Đối tượng và phạm vi nghiên cứu
• 1.2. Hướng nghiên cứu của đề tài
• 1.3. Phương pháp nghiên cứu
• 1.4. Ý nghĩa khoa học của đề tài
• 1. CHƯƠNG 1: CƠ SỞ LÍ THUYẾT
• 1.1. Giới thiệu về logic
• 1.2. Logic hình thức
• 1.3. Tổng quan về CSDL phân tán
• 1.4. Các phương pháp phân mảnh và tái thiết
• 1.5. Cách tạo cây toán tử từ câu SQL
• 1.6. Kết luận chương 1
• 2. CHƯƠNG 2: PHÂN RÃ VẤN TIN VÀ CỤC BỘ HÓA DỮ LIỆU
• 2.1. Phân rã vấn tin câu vấn tin SQL
• 2.2. Phân tích câu vấn tin trên cơ sở “kiểu dữ liệu” và “ngữ nghĩa”
• 2.3. Loại bỏ dư thừa
• 2.4. Viết lại câu vấn tin
• 2.5. Cục bộ hóa dữ liệu phân tán và các phương pháp rút gọn câu vấn tin phân tán
• 2.6. Cục bộ hóa dữ liệu phân tán
• 2.7. Rút gọn câu vấn tin SQL phân tán
• 2.8. Kết luận chương 2
• 3. CHƯƠNG 3: ỨNG DỤNG
• 3.1. Ứng dụng tại trường THPT Trung Nghĩa (Dạng demo)
• 3.2. Giới thiệu CSDL của trường THPT Trung Nghĩa năm học 2012-201363
• 3.3. Một số dạng rút gọn câu vấn tin trên CSDL (tại mục 3.1) đã được phân mảnh
• 3.4. Kết luận chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Hướng dẫn toàn diện tối ưu câu vấn tin phân tán song song

Trong kỷ nguyên dữ liệu lớn, việc xây dựng một hệ thống làm việc dựa trên cơ sở dữ liệu phân tán (CSDL phân tán) là xu hướng tất yếu. Lợi ích cơ bản của mô hình này là dữ liệu từ các cơ sở vật lý riêng biệt được tích hợp logic, cho phép nhiều người dùng trên mạng cùng truy cập. Tuy nhiên, hiệu năng truy vấn trở thành một bài toán lớn. Do đó, tối ưu câu vấn tin phân tán để xử lý song song là một nhiệm vụ quan trọng. Quá trình này không chỉ làm giảm thời gian tính toán và khối lượng truyền thông tin giữa các trạm mà còn giảm không gian bộ nhớ cần thiết. Các giải pháp rút gọn câu vấn tin giúp loại bỏ những phần tính toán dư thừa, vô ích, tạo tiền đề cho việc thực thi các tác vụ song song một cách hiệu quả nhất. Luận văn “Một số giải pháp rút gọn câu vấn tin phân tán để xử lý song song” của Nguyễn Tuấn Anh (2013) đã đi sâu vào các kỹ thuật phân rã vấn tin và cục bộ hóa dữ liệu để giải quyết vấn đề này. Bài viết này sẽ phân tích và tổng hợp các phương pháp cốt lõi từ nghiên cứu đó, cung cấp một cái nhìn chuyên sâu về cách tối ưu hóa các hệ thống CSDL phân tán hiện đại. Việc áp dụng các kỹ thuật này giúp các tổ chức khai thác tối đa sức mạnh của hạ tầng phân tán, đảm bảo tốc độ và hiệu quả trong việc xử lý các yêu cầu dữ liệu phức tạp.

1.1. Khái niệm về hệ cơ sở dữ liệu phân tán DDBS

Một Hệ CSDL phân tán (Distributed Database System – DDBS) được định nghĩa 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. Đi kèm với nó là Hệ quản trị CSDL phân tán (Distributed Database Management System – DDBMS), một hệ thống phần mềm cho phép quản lý DDBS và làm cho việc phân tán trở nên vô hình đối với người dùng. Cần phân biệt rõ DDBS với một tập hợp các tệp dữ liệu riêng rẽ. Trong DDBS, dữ liệu không chỉ được phân tán về mặt vật lý mà còn phải có liên đới logic, có cấu trúc và được truy xuất thông qua một giao diện chung. Điều này đảm bảo tính nhất quán và toàn vẹn của dữ liệu trên toàn hệ thống, một yếu tố then chốt cho các ứng dụng quy mô lớn.

1.2. Vai trò của xử lý song song trong tối ưu hiệu năng

Xử lý song song là nền tảng của tính toán hiệu năng cao trong các hệ thống phân tán. Bằng cách sử dụng nhiều bộ xử lý hoạt động đồng thời, hệ thống có thể áp dụng quy tắc “chia để trị” để giải quyết các bài toán lớn và phức tạp. Trong bối cảnh truy vấn dữ liệu, xử lý song song cho phép thực thi các phần của một câu vấn tin trên nhiều mảnh dữ liệu khác nhau cùng một lúc. Khi kết hợp với các kỹ thuật rút gọn câu vấn tin, hệ thống chỉ thực hiện các tác vụ song song trên những mảnh dữ liệu thực sự liên quan, từ đó tối đa hóa hiệu suất, giảm độ trễ và tận dụng hiệu quả tài nguyên tính toán của toàn mạng.

II. Các thách thức cốt lõi khi xử lý song song CSDL phân tán

Việc xử lý câu vấn tin trong môi trường phân tán đặt ra nhiều thách thức phức tạp hơn so với hệ thống tập trung. Quá trình xử lý không chỉ đơn thuần là tìm kiếm dữ liệu mà còn bao gồm các giai đoạn phức tạp như phân rã vấn tin, cục bộ hóa dữ liệu, và tối ưu hóa toàn cục. Giai đoạn đầu tiên, phân rã vấn tin, yêu cầu biến đổi một câu vấn tin cấp cao (như SQL) thành một biểu thức đại số quan hệ cấp thấp. Quá trình này phải đảm bảo tính đúng đắn về cú pháp, kiểu dữ liệu và ngữ nghĩa. Một câu vấn tin có thể bị từ chối nếu sai kiểu hoặc nếu các thành phần của nó không tham gia vào việc tạo ra kết quả. Một trong những công cụ hữu ích để kiểm tra tính đúng đắn ngữ nghĩa là đồ thị vấn tin (query graph). Nếu đồ thị này không liên thông, câu vấn tin có thể bị xem là sai ngữ nghĩa. Thách thức tiếp theo là cục bộ hóa dữ liệu, tức là ánh xạ câu vấn tin trên các quan hệ toàn cục thành một chương trình hoạt động trên các mảnh dữ liệu vật lý. Điều này đòi hỏi hệ thống phải có thông tin chi tiết về lược đồ phân mảnh, làm tăng độ phức tạp của bộ xử lý vấn tin. Cuối cùng, việc lựa chọn chiến lược thực thi tối ưu nhất để xử lý song song là bài toán khó, cần cân nhắc chi phí truyền dữ liệu qua mạng và chi phí xử lý tại mỗi nút.

2.1. Phân rã vấn tin Từ SQL đến đại số quan hệ

Phân rã vấn tin là bước đầu tiên và quan trọng nhất, bao gồm các công đoạn: chuẩn hóa, phân tích, loại bỏ dư thừa và viết lại câu vấn tin. Chuẩn hóa nhằm biến đổi câu vấn tin thành một dạng chuẩn, thường là dạng chuẩn hội (Conjunctive Normal Form), để dễ dàng xử lý. Phân tích sau đó sẽ kiểm tra tính hợp lệ của câu vấn tin. Theo nghiên cứu, "Một câu vấn tin gọi là sai kiểu (type incorrect) nếu nó có một thuộc tính hoặc tên quan hệ chưa được khai báo... Một câu vấn tin gọi là sai nghĩa (semantically incorrect) nếu các thành phần của nó không tham gia vào việc tạo ra kết quả". Việc xây dựng đồ thị kết nối giúp phát hiện các vấn tin sai nghĩa một cách hiệu quả.

2.2. Cục bộ hóa dữ liệu và tái thiết quan hệ toàn cục

Sau khi có được biểu thức đại số quan hệ trên các quan hệ toàn cục, tầng cục bộ hóa dữ liệu sẽ chuyển nó thành một câu vấn tin đại số trên các mảnh vật lý. Quá trình này sử dụng thông tin từ lược đồ phân mảnh để xác định những mảnh dữ liệu nào cần được truy cập. Thách thức ở đây là làm thế nào để tái thiết lại quan hệ ban đầu từ các mảnh một cách hiệu quả. Ví dụ, nếu một quan hệ được phân mảnh ngang, việc tái thiết sẽ dùng toán tử Hợp (Union). Nếu là phân mảnh dọc, sẽ cần đến toán tử Nối (Join). Việc lựa chọn sai chiến lược có thể dẫn đến chi phí truyền thông và tính toán khổng lồ.

III. Phương pháp phân mảnh dữ liệu tối ưu cho vấn tin phân tán

Phân mảnh dữ liệu là kỹ thuật chia một quan hệ trong CSDL thành nhiều mảnh nhỏ hơn và lưu trữ chúng tại các vị trí khác nhau trong mạng. Một chiến lược phân mảnh dữ liệu hiệu quả là tiền đề cho việc tối ưu câu vấn tin phân tán. Mục tiêu chính là giảm lượng dữ liệu không liên quan cần truy cập khi thực thi một câu vấn tin. Có ba loại phân mảnh chính: phân mảnh ngang, phân mảnh dọc và phân mảnh hỗn hợp. Mỗi loại có ưu và nhược điểm riêng, phù hợp với các loại ứng dụng khác nhau. Việc lựa chọn phương pháp phân mảnh phải dựa trên việc phân tích kỹ lưỡng các ứng dụng và câu vấn tin thường xuyên chạy trên hệ thống. Ví dụ, phân mảnh ngang phù hợp khi các ứng dụng thường truy cập vào các tập con của các bộ dữ liệu (hàng), trong khi phân mảnh dọc hiệu quả khi các ứng dụng chỉ cần một vài thuộc tính (cột) của quan hệ. Luận văn nhấn mạnh tầm quan trọng của các quy tắc về tính đúng đắn: tính đầy đủ (không mất dữ liệu), tính tái thiết (có thể tạo lại quan hệ gốc) và tính tách rời (các mảnh không trùng lặp dữ liệu).

3.1. Kỹ thuật phân mảnh ngang Horizontal Fragmentation

Phân mảnh ngang chia một quan hệ thành các tập con gồm các bộ (hàng) dựa trên các vị từ (predicates) được định nghĩa trên quan hệ đó. Có hai loại chính: nguyên thủy và dẫn xuất. Phân mảnh ngang nguyên thủy phân rã một quan hệ dựa trên các thuộc tính của chính nó. Ví dụ, quan hệ DuAn có thể được phân mảnh theo NganSach <= 200000 và NganSach > 200000. Ngược lại, phân mảnh ngang dẫn xuất phân mảnh một quan hệ dựa trên một vị từ được định nghĩa trên một quan hệ khác có liên kết. Kỹ thuật này rất hữu ích trong việc duy trì các phép nối cục bộ, giảm thiểu chi phí truyền dữ liệu qua mạng.

3.2. Chiến lược phân mảnh dọc Vertical Fragmentation

Phân mảnh dọc chia một quan hệ thành các mảnh chứa tập con các thuộc tính (cột) cùng với khóa chính của quan hệ. Chiến lược này đặc biệt hiệu quả khi các ứng dụng khác nhau thường xuyên truy cập các tập thuộc tính khác nhau. Yếu tố cốt lõi trong phân mảnh dọc là ái lực thuộc tính (attribute affinity), một số đo chỉ ra mức độ liên đới giữa các thuộc tính. Các thuộc tính có ái lực cao (thường được truy cập cùng nhau) sẽ được nhóm vào cùng một mảnh. Thuật toán Năng lượng Nối BEA (Bond Energy Algorithm) thường được sử dụng để gom nhóm các thuộc tính dựa trên ma trận ái lực, từ đó xác định các điểm phân chia tối ưu.

3.3. Áp dụng phân mảnh hỗn hợp và đảm bảo tính đúng đắn

Trong thực tế, việc chỉ áp dụng một loại phân mảnh thường không đủ đáp ứng yêu cầu phức tạp của ứng dụng. Phân mảnh hỗn hợp (Hybrid Fragmentation) cho phép áp dụng tuần tự cả phân mảnh ngang và dọc, tạo ra một cấu trúc phân hoạch dạng cây. Ví dụ, một quan hệ có thể được phân mảnh ngang trước, sau đó mỗi mảnh ngang lại tiếp tục được phân mảnh dọc. Dù áp dụng chiến lược nào, việc đảm bảo tính đúng đắn là tối quan trọng. Tính tái thiết yêu cầu quan hệ gốc có thể được tạo lại bằng các toán tử như Hợp (Union) cho phân mảnh ngang và Nối (Join) cho phân mảnh dọc.

IV. Bí quyết rút gọn câu vấn tin phân tán để xử lý song song

Sau khi dữ liệu đã được phân mảnh và câu vấn tin đã được phân rã thành biểu thức đại số quan hệ, bước tiếp theo là rút gọn câu vấn tin. Đây là giai đoạn cốt lõi để tối ưu câu vấn tin phân tán. Mục tiêu là biến đổi biểu thức đại số thành một dạng tương đương nhưng có chi phí thực thi thấp hơn. Một heuristic phổ biến là thực hiện các phép toán đơn ngôi (như phép Chọn và Chiếu) càng sớm càng tốt để giảm kích thước của các quan hệ trung gian trước khi thực hiện các phép toán hai ngôi tốn kém (như phép Nối). Công cụ chính cho việc này là cây toán tử (operator tree) và các quy tắc biến đổi tương đương. Bằng cách tái cấu trúc cây toán tử, hệ thống có thể tìm ra một kế hoạch thực thi hiệu quả hơn. Đối với các hệ thống phân tán, việc rút gọn còn bao gồm việc loại bỏ hoàn toàn các truy vấn đến những mảnh dữ liệu không liên quan, dựa trên sự mâu thuẫn giữa vị từ của câu vấn tin và vị từ dùng để phân mảnh. Khi đã xác định được tập các mảnh cần thiết, các cấu trúc lệnh song song như Parbegin...Parend có thể được áp dụng để thực thi các truy vấn đồng thời, khai thác tối đa khả năng xử lý song song.

4.1. Xây dựng cây toán tử và các quy tắc biến đổi tương đương

Một cây toán tử là một biểu diễn trực quan của câu vấn tin đại số. Các nút lá đại diện cho các quan hệ trong CSDL, trong khi các nút trong biểu thị các quan hệ trung gian được tạo ra bởi các phép toán. Gốc của cây là kết quả cuối cùng. Việc tối ưu câu vấn tin có thể được xem như việc tìm kiếm một cây toán tử tương đương có chi phí thấp nhất. Các quy tắc biến đổi như tính giao hoán của phép nối, đẩy phép chọn xuống gần các nút lá, hay gộp các phép chọn liên tiếp là những kỹ thuật cơ bản để tái cấu trúc và đơn giản hóa cây, giúp giảm đáng kể khối lượng tính toán.

4.2. Kỹ thuật rút gọn cho phân mảnh ngang nguyên thủy

Đây là một kỹ thuật rút gọn câu vấn tin cực kỳ hiệu quả. Khi một quan hệ R được phân mảnh ngang thành các mảnh Ri dựa trên các vị từ phân mảnh pi, một câu vấn tin với vị từ chọn pj có thể được tối ưu. Luận văn đã chỉ ra quy tắc quan trọng: "Nếu x R: (pi(x) pj(x)) thì Pj(Ri) = ". Điều này có nghĩa là nếu vị từ của câu vấn tin (pj) mâu thuẫn logic với vị từ phân mảnh (pi) của mảnh Ri, thì mảnh Ri chắc chắn không chứa bất kỳ kết quả nào. Do đó, hệ thống có thể loại bỏ hoàn toàn việc truy vấn trên mảnh Ri, giúp tiết kiệm tài nguyên và giảm đáng kể thời gian phản hồi.

4.3. Áp dụng cấu trúc lệnh song song Parbegin Forall

Sau khi đã rút gọn và xác định được tập các mảnh cần thiết, xử lý song song phát huy tác dụng. Các cấu trúc lệnh như Parbegin/Parend hoặc Cobegin/Coend cho phép các tiến trình độc lập được thực thi đồng thời. Thay vì truy vấn tuần tự từng mảnh, hệ thống có thể gửi các yêu cầu truy vấn đến nhiều nút mạng cùng một lúc. Ví dụ, thuật toán rút gọn phép chọn có thể được song song hóa bằng cách kiểm tra điều kiện mâu thuẫn trên tất cả các mảnh đồng thời, sau đó chỉ thực hiện phép chọn trên các mảnh hợp lệ. Điều này giúp tận dụng triệt để kiến trúc phân tán và tăng tốc độ xử lý một cách ngoạn mục.

V. Case study Tối ưu câu vấn tin phân tán trong CSDL thực tế

Lý thuyết về tối ưu câu vấn tin phân tán sẽ trở nên rõ ràng hơn khi được áp dụng vào một kịch bản thực tế. Nghiên cứu gốc đã sử dụng mô hình CSDL của trường THPT Trung Nghĩa làm ví dụ minh họa. Hệ thống này bao gồm các quan hệ quen thuộc như NhanVien, DuAn, PhanNhiem, và TraLuong. Bằng cách áp dụng các kỹ thuật phân mảnh dữ liệu và rút gọn câu vấn tin trên CSDL này, có thể thấy rõ hiệu quả của các giải pháp đề xuất. Giả sử quan hệ DuAn được phân mảnh ngang dựa trên thuộc tính ViTri (địa điểm), chia thành các mảnh DuAn_HN (Hà Nội), DuAn_HP (Hải Phòng), và DuAn_HCM (TP.Hồ Chí Minh). Khi một người dùng thực hiện một câu vấn tin để tìm các dự án chỉ ở Hà Nội, hệ thống tối ưu sẽ ngay lập tức nhận diện và chỉ gửi yêu cầu đến nút chứa mảnh DuAn_HN. Các nút chứa dữ liệu của Hải Phòng và TP.HCM sẽ không cần xử lý, giúp tiết kiệm băng thông mạng và thời gian xử lý. Đây là một minh chứng đơn giản nhưng mạnh mẽ về lợi ích của việc kết hợp phân mảnh thông minh và rút gọn câu vấn tin để tăng cường khả năng xử lý song song.

5.1. Bối cảnh ứng dụng Mô hình CSDL quan hệ giả định

Mô hình CSDL được sử dụng bao gồm các quan hệ chính: NhanVien(MaNV, TenNV, TrinhDoCM), DuAn(MaDuAn, TenDuAn, NganSach, ViTri), và PhanNhiem(MaNV, MaDuAn, ThoiGianLV, ChucVu). Các quan hệ này được liên kết với nhau qua các khóa ngoại, tạo thành một lược đồ logic hoàn chỉnh. Dữ liệu giả định phản ánh các hoạt động của một tổ chức có nhiều dự án và nhân viên, là một môi trường lý tưởng để thử nghiệm các chiến lược phân mảnh dữ liệu và tối ưu hóa truy vấn.

5.2. Minh họa rút gọn vấn tin trên dữ liệu đã phân mảnh

Xét câu vấn tin: SELECT * FROM EMP WHERE “E3” < ENO AND ENO < “E5”. Giả sử quan hệ EMP được phân mảnh thành ba mảnh: EMP1 (ENO <= “E3”), EMP2 (“E3” < ENO <= “E6”), và EMP3 (ENO > “E6”). Vị từ của câu vấn tin là pj = (“E3” < ENO < “E5”). Áp dụng quy tắc rút gọn, hệ thống sẽ kiểm tra: pj mâu thuẫn với vị từ của EMP1 và EMP3. Do đó, câu vấn tin sẽ không được thực thi trên hai mảnh này. Chỉ có mảnh EMP2 được truy vấn, giúp giảm 2/3 khối lượng công việc. Quá trình kiểm tra và loại bỏ này có thể được thực hiện song song để tối ưu hóa hơn nữa.

VI. Tương lai xử lý song song và các hướng tối ưu vấn tin mới

Các giải pháp rút gọn câu vấn tin và xử lý song song được trình bày trong nghiên cứu từ năm 2013 vẫn giữ nguyên giá trị nền tảng cho các hệ thống CSDL phân tán hiện đại. Việc phân mảnh dữ liệu một cách chiến lược, kết hợp với việc tái cấu trúc cây toán tử và loại bỏ các truy vấn thừa, là những nguyên tắc cốt lõi giúp tối ưu hóa hiệu năng. Tuy nhiên, lĩnh vực này vẫn đang không ngừng phát triển. Các hệ thống ngày nay phải đối mặt với khối lượng dữ liệu khổng lồ và các loại truy vấn phức tạp hơn. Hướng phát triển trong tương lai không chỉ dừng lại ở các thuật toán heuristic mà còn mở rộng sang việc tích hợp các công nghệ tiên tiến như Trí tuệ nhân tạo (AI) và Học máy (Machine Learning). Những công nghệ này hứa hẹn sẽ mang lại các bộ tối ưu hóa thông minh hơn, có khả năng tự động học hỏi từ các mẫu truy vấn trong quá khứ và thích ứng với sự thay đổi của dữ liệu theo thời gian thực. Việc tiếp tục nghiên cứu và cải tiến các phương pháp tối ưu câu vấn tin phân tán sẽ luôn là một nhiệm vụ quan trọng để khai phá toàn bộ tiềm năng của thế giới dữ liệu kết nối.

6.1. Tổng kết các giải pháp rút gọn câu vấn tin hiệu quả

Tóm lại, các giải pháp hiệu quả để tối ưu câu vấn tin phân tán xoay quanh ba trụ cột chính. Thứ nhất là thiết kế một lược đồ phân mảnh dữ liệu thông minh (ngang, dọc, hoặc hỗn hợp) dựa trên đặc điểm của ứng dụng. Thứ hai là phân rã và viết lại câu vấn tin bằng cách sử dụng cây toán tử và các quy tắc đại số quan hệ để giảm thiểu các phép toán tốn kém. Cuối cùng là áp dụng các quy tắc rút gọn dựa trên vị từ để loại bỏ các truy vấn đến những mảnh không liên quan, tạo điều kiện cho việc xử lý song song hiệu quả trên tập dữ liệu đã được thu hẹp.

6.2. Hướng phát triển Tích hợp AI và Machine Learning

Trong tương lai, các bộ tối ưu hóa câu vấn tin có thể sử dụng Machine Learning để dự đoán chi phí của các kế hoạch thực thi khác nhau với độ chính xác cao hơn. Các mô hình AI có thể phân tích lịch sử truy vấn để tự động đề xuất hoặc điều chỉnh chiến lược phân mảnh dữ liệu. Hơn nữa, các hệ thống tự trị (self-driving database) có thể tự động điều chỉnh các tham số tối ưu hóa trong thời gian thực mà không cần sự can thiệp của con người. Sự kết hợp này sẽ tạo ra một thế hệ mới của các hệ thống CSDL phân tán thông minh, linh hoạt và hiệu quả hơn bao giờ hết.

Trích đoạn nội dung tài liệu

PHẦN MỞ ĐẦU 1. Ngày nay các lĩnh vực như giáo dục, thương mại. ngày càng mở rộng và phát triển. Để hoạt động được thuận lợi và có hiệu quả cần phải nắm bắt thông tin nhanh nhất khi các địa điểm ở xa nhau.

Do đó xây dựng 1 hệ thống làm việc dựa trên cơ sở dữ liệu phân tán là phù hợp với xu hướng hiện nay. Cơ sở dữ liệu phân tán đã, đang được nghiên cứu và ứng dụng vào thực tế. Việc cần làm là nghiên cứu và làm sáng tỏ thêm khả năng ứng dụng thực tiễn của cơ sở dữ liệu phân tán. Lợi ích cơ bản nhất của cơ sở dữ liệu phân tán là dữ liệu của các cơ sở dữ liệu vật lý riêng biệt được tích hợp logic với nhau làm cho nhiều người sử dụng trên mạng có thể truy nhập được.

Cơ sở dữ liệu phân tán với cấp độ tự trị cao ở mỗi điểm. Trong hệ phân tán các giải pháp rút gọn câu vấn tin phân tán làm giảm thời gian tính toán, khối lượng truyền thông tin giữa các trạm và giảm không gian bộ nhớ, tránh được các công việc dư thừa, loại bỏ những phần vô ích và để phục vụ cho việc xử lí song song, nên tôi chọn nghiên cứu “Một số giải pháp rút gọn câu vấn tin phân tán để xử lý song song” làm đề tài luận văn tốt nghiệp của mình. Đối tượng và phạm vi nghiên cứu Logic Cơ sở dữ liệu có cấu trúc Các phương pháp phân mảnh trong CSDL có cấu trúc Phân rã vấn tin và cục bộ hóa dữ liệu 3. Hướng nghiên cứu của đề tài Nghiên cứu các phương pháp phân mảnh CSDL có cấu trúc.

Phân rã vấn tin và cục bộ hóa dữ liệu Các loại rút gọn câu vấn tin Số hóa bởi trung tâm học liệu http://lrc. 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. Nắm vững các kiến thức cơ bản phân mảnh và về cây toán tử. Nghiên cứu các phương pháp rút gọn câu vấn tin trên cơ sở phân mảnh và cục bộ hóa dữ liệu.

Ý nghĩa khoa học của đề tài Luận văn giúp cho việc phân mảnh thích hợp cho các loại dữ liệu có cấu trúc và phân rã, phân tán các loại câu SQL trên các CSDL đó. Số hóa bởi trung tâm học liệu http://lrc.vn/ 3 CHƢƠNG 1: CƠ SỞ LÍ THUYẾT 1. Giới thiệu về 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 trị của biểu thức đó. Logic mệnh đề và chân trị - 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ờ. - Giá trị đúng hay sai của mệnh đề được gọi là chân trị của mệnh đề và thường được kí hiệu là 1 (hoặc T hoặc True) đối với chân trị đúng , còn chân trị sai được kí hiệu là 0 (hoặc F hoặc False). Số hóa bởi trung tâm học liệu http://lrc.vn/ 4 - 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. Chân trị của phép toán logic được cho ở bảng 1.1 sau: Số hóa bởi trung tâm học liệu http://lrc.1 Chân trị của các phép toán logic p q p p q p q p q p q p q 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 trị. 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 http://lrc.vn/ 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 = F1 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 http://lrc.vn/ 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 http://lrc.vn/ 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.