Đăng ký Đăng nhập
Trang chủ Tìm hiểu về tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán...

Tài liệu Tìm hiểu về tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán

.DOC
89
143
116

Mô tả:

PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Cùng với sự phát triển như của công nghệ thông tin, các ứng dụng của cơ sở dữ liệu đã xâm nhập vào các hoạt động quản lý, các lĩnh vực kinh tế… đem lại những hiệu quả to lớn và cần thiết. Bên cạnh đó, nhu cầu về xử lí thông tin như: thu thập, lưu trữ, xử lý và trao đổi thông tin ngày càng tăng, nhanh hơn nhiều lần tốc độ phát triển của tài nguyên phần cứng và phần mềm. Trong thực tế các doanh nghiệp, đơn vị kinh doanh liên quan đến nhau hay kể cả các cơ quan hành chính nhà nước được phân bổ ở nhiều khu vực khác nhau do đó dữ liệu không được tập trung tại một địa điểm nhất định mà rải khắp các địa điểm mà cơ quan đơn vị đó hoạt động. Khi dữ liệu không còn tập trung thì vấn đề đưa ra là làm thế nào để quản lý, truy xuất CSDL phục vụ cho công tác chuyên môn không bị ảnh hưởng, không được gián đoạn, tiêu tốn ít thời gian công sức tiền bạc. Một số hệ thống tập trung thông thường không đáp ứng được, không phù hợp với nhu cầu hiện đại hóa. Xây dựng một hệ thống phân tán có khả năng xử lí đồng thời một bài toán trên nhiều máy tính là một hướng giải quyết khả thi và đã được chứng minh tính hữu dụng. Hệ thống phân tán còn tạo nhiều thuận lợi trong việc chia sẻ thông tin trên khắp mọi nơi. Vì vậy, CSDL phân tán được ra đời để giải quyết vấn đề đó. Nếu khối lượng thông tin phải xử lý lớn phong ph và đa dạng th vấn đề được đ t ra là làm thế nào để giảm chi phí một các tối thiểu mà vẫn xử lý thông tin một cách có hiệu quả và thông suốt. Tối ưu hóa các câu lệnh khi truy vấn cơ sở dữ liệu phân tán là một trong những cách giải quyết cho vấn đề này. Vấn đề tối ưu hóa truy vấn trên CSDL phân tán là rất quan trọng và phức tạp do tính phân mảnh, nhân bản, tốn kém chi phí trong việc truyền dữ liệu 1 của nó. Nếu không giải quyết tốt vấn đề tối ưu truy vấn thì hiệu năng của các thao tác trên hệ CSDL phân tán sẽ đạt rất thấp. Những nhận xét đánh giá trên cũng chính là lý do tôi chọn đề tài nghiên cứu là: “Tìm hiểu về tối ƣu hóa truy vấn trong cơ sở dữ liệu phân tán” 2. Mục tiêu nghiên cứu. Nghiên cứu lý thuyết CSDL phân tán, các kỹ thuật truy vấn trong CSDL. Tổng hợp các kết quả đã công bố về truy vấn tối ưu, thực hiện tối ưu hóa truy vấn trong CSDL phân tán. 3. Đối tƣợng và phạm vi nghiên cứu. Đề tài tập trung nghiên cứu về vấn đề cơ bản của CSDL phân tán, các nguyên lý chung của tối ưu hóa truy vấn phân tán, các kỹ thuật, thuật toán tối ưu hóa truy vấn, thực hiện truy vấn cơ sở dữ liệu phân tán, đánh giá kết quả thực hiện. 4. Phƣơng pháp nghiên cứu. Thu thập, tìm kiếm, tham khảo, phân tích, nghiên cứu các tài liệu và thông tin liên quan đến đề tài như: lý thuyết CSDL, CSDL phân tán, các kỹ thuật truy vấn của các tác giả trong và ngoài nước, trên sách báo và internet… có chọn lọc và sắp xếp lại theo ý tưởng của mình. Tổng hợp các kết quả đã nghiên cứu về truy vấn tối ưu và tiến hành thực hiện tối ưu hóa truy vấn phân tán qua một trường hợp nghiên cứu. CHƢƠNG 1: GIỚI THIỆU VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 1.1. Khái niệm về cơ sở dữ liệu phân tán 1.1.1. Khái niệm Cơ sở dữ liệu phân tán [3] là một tập hợp dữ liệu, mà về m t logic tập hợp này thuộc cùng một hệ thống, nhưng về m t vật lý dữ liệu đó được phân tán trên các vị trí khác nhau của một mạng máy tính. Cơ sở dữ liệu phân tán làm tăng khả năng truy cập tới hệ thống CSDL lớn trên mạng. Trong hệ thống đó mỗi máy tính quản lý một CSDL thành phần được gọi là 1 node ho t site. Một cơ sở dữ liệu phân tán là một tập hợp nhiều CSDL có liên đới logic và được phân bố trên một mạng máy tính. Có 2 điểm quan trọng được nêu ra và cần ch ý trong định nghĩa: - Tính chất phân tán: Tất cả dữ liệu của CSDL phân tán không cư tr trên cùng một vị trí mà được phân bố trên nhiều máy trạm đ t tại các vị trí khác nhau thuộc mạng máy tính. Đây là điểm phân biệt giữa CSDL phân tán và CSDL tập trung. - Tương quan logic: Dữ liệu của CSDL phân tán có một số thuộc tính ràng buộc với nhau. Điều này giúp chúng ta có thể phân biệt một CSDL phân tán với một tập hợp CSDL tập trung. Các file dữ liệu được lưu trữ tại nhiều vị trí khác nhau, điều này thường thấy trong các ứng dụng mà hệ thống sẽ phân quyền truy nhập dữ liệu trong môi trường mạng. Ví dụ 1.1: Website của google phân tán tìm kiếm theo cách tự nhận biết, yêu cầu nào gần server nào th server đó xử lý. Các server của google phân bố rông khắp trên toàn thế giới. 1.1.2. Các đặc điểm chính của CSDL phân tán 1. Chia sẻ tài nguyên Việc chia sẻ tài nguyên của hệ phân tán được thực hiện qua mạng truyền thông. Mỗi tài nguyên cần được quản lý bởi một chương tr nh có giao diện truyền thông để chia sẻ một cách có hiệu quả. Các tài nguyên có thể được truy cập, cập nhật một cách tin cậy và nhất quán. Quản lý tài nguyên ở đây bao gồm lập kế hoạch dự phòng, đ t tên cho các lớp tài nguyên, cho phép tài nguyên được truy cập từ nơi này đến nơi khác, ánh xạ tên tài nguyên vào địa chỉ truyền thông, ... 2. Tính mở Tính mở của hệ thống phân tán là tính dễ dàng mở rộng phần cứng của nó. Một hệ thống được gọi là có tính mở thì phải có các điều kiện sau: - Hệ thống có thể tạo nên bởi nhiều loại phần cứng và phần mềm của nhiều nhà cung cấp khác nhau. - Có thể bổ sung vào các dịch vụ dùng chung tài nguyên mà không phá hỏng hay nhân đôi các dịch vụ đang tồn tại. - Tính mở được hoàn thiện bằng cách xác định hay phân định rõ các giao diện chính của một hệ và làm cho nó tương thích với các nhà phát triển phần mềm. - Tính mở của hệ phân tán dựa trên việc cung cấp cơ chế truyền thông giữa các tiến trình và công khai các giao diện dùng để truy nhập các tài nguyên chung. 3. Khả năng song song Hệ phân tán hoạt động trên một mạng truyền thông có nhiều máy tính, mỗi máy có thể có một hay nhiều CPU. Có thể thực hiện nhiều tiến trình trong cùng một thời điểm. Việc thực hiện tiến trình đồng thời theo cơ chế phân chia thời gian (một CPU) hay song song (nhiều CPU). Khả năng làm việc song song trong hệ phân tán được thể hiện qua hai tình huống: - Nhiều người sử dụng đồng thời đưa ra các lệnh hay các tương tác với các chương tr nh ứng dụng (đồng thời xuất hiện nhiều Clients). - Nhiều tiến trình Server chạy đồng thời, mỗi tiến trình phải đáp ứng yêu cầu từ các Clients. Từ điều kiện đa xử lý, khả năng song song của hệ thống phân tán trở thành một thuộc tính của nó. 4. Khả năng mở rộng Hệ phân tán có khả năng hoạt động tốt và hiệu quả ở nhiều mức khác nhau. Khả năng mở rộng của một hệ phân tán được đ c trưng bởi tính không thay đổi phần mềm hệ thống và phần mềm ứng dụng khi hệ thống được mở rộng. Điều này chỉ đạt ở mức độ nào đó đối với hệ phân tán hiện tại (không thể hoàn toàn như định nghĩa trên). Yêu cầu mở rộng không chỉ là mở rộng về phần cứng hay về mạng mà còn cần phải được phân tích, đánh giá trên tất cả các khía cạnh khi thiết kế hệ phân tán. Ví dụ 1.2: Tần suất sử dụng file trên mạng đột ngột tăng cao. Để tránh tình trạng tắc nghẽn xảy ra khi chỉ có một Server và phải đáp ứng các yêu cầu truy nhập file đó. Người ta nhân bản file trên một Server khác và hệ thống được thiết kế sao cho việc bổ sung Server được dễ dàng. Có thể tính đến giải pháp khác là sử dụng Cache và các bản sao dữ liệu. 5. Khả năng thứ lỗi Khả năng thứ lỗi thể hiện việc hệ thống không bị sụp đổ bởi các sự cố do các lỗi thành phần (cả phần cứng lẫn phần mềm) trong một bộ phận nào đó. Việc thiết kế khả năng thứ lỗi các hệ thống máy tính dựa trên hai giải pháp sau: - Dùng khả năng thay thế để đảm bảo sự hoạt động liên tục và hiệu quả. - Dùng các chương tr nh đảm bảo cơ chế phục hồi dữ liệu khi xảy ra sự cố. 6. Đảm bảo tin cậy và nhất quán Hệ thống yêu cầu độ tin cậy như: - Bí mật của dữ liệu. - Các chức năng khôi phục hư hỏng phải đảm bảo. - Ngoài ra các yêu cầu của hệ thống về tính nhất quán cũng thể hiện ở chỗ: không có mâu thuẫn trong nội dung CSDL. 1.1.3. Những ưu nhược điểm của cơ sở dữ liệu phân tán  Những ưu điểm của cơ sở dữ liệu phân tán Lợi ích cơ bản nhất của CSDL phân tán là dữ liệu của các CSDL 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 [6]. - Cho phép quản lý dữ liệu với nhiều mức trong suốt: + Trong suốt mạng - phân tán: Hệ quản trị CSDL phải được trong suốt phân tán theo nghĩa làm cho người sử dụng không cần biết vị trí của dữ liệu và không cần biết sự phức tạp truy cập qua mạng. + Trong suốt bản sao + Trong suốt phân đoạn - Tăng độ tin cậy và khả năng sẵn sàng: Độ tin cậy là khả năng hệ thống đang làm việc (không bị ngừng) tại một thời điểm nào đó, tính sẵn sàng là khả năng hệ thống tiếp tục làm việc trong một khoảng thời gian nào đó. Khi dữ liệu và CSDL phân tán trên một vài trạm, một trạm có thể có sự cố trong khi các trạm khác vẫn có thể hoạt động ho c sử dụng các thành phần khác của CSDL. Chỉ trên trạm bị sự cố, dữ liệu và ứng dụng không thể truy cập được. Để nâng cao độ tin cậy và tính sẵn sàng, có thể áp dụng cơ chế tạo bản sao trên nhiều trạm. - Cải thiện hiệu năng: Một hệ quản trị CSDL phân tán, phân đoạn CSDL có thể làm cho dữ liệu sẽ được lưu giữ tại gần nơi sử dụng nhất. Dữ liệu được lưu giữ cục bộ làm giảm cạnh tranh CPU, giảm các I/O Server và giảm tương tranh truy nhập trên mạng. Dữ liệu được phân tán tại các trạm nên dung lượng dữ liệu cục bộ sẽ nhỏ hơn, các xử lý giao tác và truy vấn cục bộ sẽ được thực hiện tốt hơn. Hơn nữa trên mỗi trạm có ít các giao tác hơn số các giao tác trên CSDL tập trung vì vậy cũng tăng hiệu suất hệ thống. - Dễ dàng mở rộng: Việc thêm CSDL mới, tăng kích cỡ CSDL ho c thêm bộ xử lý trong môi trường phân tán là dễ hơn v cũng chỉ như là thêm các CSDL thành phần.  Những nhược điểm của cơ sở dữ liệu phân tán - Độ phức tạp thiết kế và cài đ t hệ thống tăng: Hệ quản trị CSDL phân tán phải bổ sung thêm các chức năng như: + Theo dõi dấu vết dữ liệu + Xử lý các truy vấn phân tán + Quản lý giao dịch phân tán + Phục hồi CSDL phân tán + Quản lý các bản sao + Quản lý thư mục - catalog phân tán - Hệ thống phần cứng cũng phức tạp hơn v cần có nhiều trạm và các trạm phải được kết nối trên mạng. - Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng. - Bảo mật khó khăn. 1.2. Các đặc trƣng trong suốt của cơ sở dữ liệu phân tán 1.2.1. Trong suốt phân đoạn (fragmentation transparency) Khi dữ liệu đã được phân đoạn thì việc truy cập vào CSDL được thực hiện b nh thường như là chưa bị phân tán và không ảnh hưởng tới người sử dụng. Ví dụ 1.3: Xét quan hệ tổng thể NCC (Id, Tên, Tuổi) và các phân đoạn ngang được tách ra từ nó: NCC1 (Id, Tên, Tuổi) NCC2 (Id, Tên, Tuổi) NCC3 (Id, Tên, Tuổi) Giả sử DDBMS cung cấp tính trong suốt về phân đoạn, khi đó ta có thể thấy tính trong suốt này được thể hiện như sau: Khi muốn tìm một người có Id= “Id1” thì chỉ cần tìm trên quan hệ tổng thể NCC mà không cần biết quan hệ NCC có phân tán hay không. SELECT * FROM NCC WHERE Id=“Id1” Hình 1.1:Trong suốt phân đoạn 1.2.2. Trong suốt về vị trí (location transparency) - Người sử dụng không cần biết về vị trí vật lý của dữ liệu mà có quyền truy cập đến CSDL tại bất cứ vị trí nào. - Các thao tác để lấy ho c cập nhật một dữ liệu từ xa được tự động thực hiện bởi hệ thống tại điểm đưa ra yêu cầu. - Tính trong suốt về vị trí rất hữu ích, nó cho phép người sử dụng bỏ qua các bản sao dữ liệu đã tồn tại ở mỗi vị trí. Do đó có thể di chuyển một bản sao dữ liệu từ một vị trí này đến một vị trí khác và cho phép tạo các bản sao mới mà không ảnh hưởng đến các ứng dụng. Ví dụ 1.4: Với quan hệ tổng thể R và các phân đoạn như đã nói ở trên nhưng giả sử rằng DDBMS cung cấp trong suốt về vị trí nhưng không cung cấp trong suốt về phân đoạn. Xét câu truy vấn t m người có Id=“Id1”. SELECT * FROM NCC1 WHERE Id=“Id1” IF NOT #FOUND THEN SELECT * FROM NCC2 WHERE Id=“Id1” + Đầu tiên hệ thống sẽ thực hiện tìm kiếm ở phân đoạn NCC1 và nếu DBMS trả về biến điều khiển #FOUND thì một câu lệnh truy vấn tương tự được thực hiện trên phân đoạn NCC2 ,... + Ở đây quan hệ NCC2 được sao làm hai bản trên hai vị trí 2 và vị trí 3, ta chỉ cần tìm thông tin trên quan hệ NCC2 mà không cần quan tâm nó ở vị trí nào. Hình 1.2: Sự trong suốt về vị trí 1.2.3. Trong suốt ánh xạ địa phương (local mapping transparency) - Là một đ c tính quan trọng trong một hệ thống DBMS không đồng nhất. - Ứng dụng tham chiếu đến các đối tượng có các tên độc lập từ các hệ thống cục bộ địa phương. - Ứng dụng được cài đ t trên một hệ thống không đồng nhất nhưng được sử dụng như một hệ thống đồng nhất. Hình 1.3: Sự trong suốt ánh xạ địa phương 1.3. Kiến trúc cơ bản của một cơ sở dữ liệu phân tán 1.3.1. Sơ đồ tổng thể (Global Schema) - Xác định tất cả các dữ liệu sẽ được lưu trữ trong CSDL phân tán cũng như các dữ liệu không được phân tán ở các trạm trong hệ thống. - Sơ đồ tổng thể được định nghĩa theo cách như trong CSDL tập trung. - Trong mô hình quan hệ, sơ đồ tổng thể bao gồm định nghĩa của tập các quan hệ tổng thể (Globle relation). 1.3.2. Sơ đồ phân đoạn dữ liệu (fragment schema) - Mỗi quan hệ tổng thể có thể chia thành một vài phần không giao nhau gọi là phân đoạn (fragment). - Có nhiều cách khác nhau để thực hiện việc phân chia này. - Sơ đồ phân đoạn mô tả các ánh xạ giữa các quan hệ tổng thể và các đoạn được định nghĩa trong sơ đồ phân đoạn (fragmentation Schema). - Các đoạn được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục đoạn. Chẳng hạn, Ri được hiểu là đoạn thứ i của quan hệ R. 1.3.3. Sơ đồ định vị dữ liệu (allocation schema) - Các đoạn là các phần logic của một quan hệ tổng thể được định vị vật lý trên một hay nhiều trạm. - Sơ đồ định vị xác định đoạn dữ liệu nào được định vị tại trạm nào trên mạng. - Tất cả các đoạn được liên kết với cùng một quan hệ tổng thể R và được định vị tại cùng một trạm j cấu thành ảnh vật lý quan hệ tổng thể R tại trạm j. - Do đó ta có thể ánh xạ một-một giữa một ảnh vật lý và một c p (quan hệ tổng thể, trạm). - Các ảnh vật lý có thể chỉ ra bằng tên của một quan hệ tổng thể và một chỉ mục trạm. - Ký hiệu Ri để chỉ đoạn thứ i của quan hệ tổng thể R. j - Ký hiệu R để chỉ ảnh vật lý của quan hệ tổng thể R tại trạm j. - Tương tự như vậy, bản sao của đoạn i thuộc quan hệ R tại trạm j được ký j hiệu là Ri . 1.3.4. Sơ đồ ánh xạ địa phương (Local mapping schema) - Thực hiện ánh xạ các ảnh vật lý lên các đối tượng được thực hiện bởi hệ quản trị CSDL địa phương. - Tất cả các đoạn của một quan hệ tổng thể trên cùng một trạm tạo ra một ảnh vật lý. Hình 1.4: Các đoạn và hình ảnh vật lý của một quan hệ tổng thể Ba yếu tố được suy ra từ kiểu kiến trúc này là: - Tách rời khái niệm phân đoạn dữ liệu với khái niệm định vị dữ liệu. - Biết được dữ liệu dư thừa. - Độc lập với các DBMS địa phương. Ba yếu tố này tương ứng với ba mức trong suốt tương ứng a. Tách rời khái niệm phân đoạn dữ liệu với khái niệm định vị dữ liệu. • Phân đoạn dữ liệu, bao gồm những công việc mà người lập trình ứng dụng làm việc với quan hệ tổng thể, phân chia quan hệ tổng thể thành các đoạn. Thông qua tính trong suốt phân đoạn (fragmentation transparency) người lập trình sẽ nhìn thấy được những đoạn dữ liệu bị phân chia như thế nào. • Định vị dữ liệu lại liên quan đến các công việc của người sử dụng và người lập trình ứng dụng tại trên các đoạn dữ liệu được định vị tại các trạm. Thông qua tính trong suốt vị trí (location transparency) người lập trình sẽ biết được vị trí của các đoạn dữ liệu trên các trạm. b. Biết được dữ liệu dư thừa: • Người lập trình ứng dụng có thể biết được dư thừa dữ liệu ở các trạm. • Trên h nh vẽ trên, chúng ta thấy rằng hai ảnh vật lý R2 và R3 có trùng l p dữ liệu. Do đó các đoạn dữ liệu trùng nhau có thể tránh được khi xây dựng các khối ảnh vật lý. c. Độc lập với các DBMS địa phương Tính chất này còn được gọi là trong suốt ánh xạ địa phương (local mapping transparency), cho phép chúng ta khảo sát các vấn đề về quản lý CSDL phân tán mà không cần phải hiểu rõ mô hình dữ liệu của DBMS địa phương đang sử dụng. 1.4. Kết luận CSDL phân tán rất quan trọng vì nhiều lý do khác nhau, nó có thể được cài đ t trên các mạng máy tính diện rộng và các mạng cục bộ nhỏ. Có hai lý do về tổ chức và kỹ thuật đối với sự phát triển CSDL phân tán đó là: CSDL phân tán được xây dựng để khắc phục các thiếu sót của CSDL tập trung và nó phù hợp hơn trong cấu trúc phân quyền của nhiều tổ chức. Kỹ thuật CSDL phân tán được mở rộng và phát triển từ kỹ thuật của CSDL truyền thống. Trong môi trường mới này, một số vấn đề kỹ thuật đòi hỏi các giải pháp khác, và một số giải pháp hoàn toàn mới. Tính trong suốt phân tán cung cấp sự độc lập của các chương tr nh khỏi sự phân tán của CSDL. Các mức trong suốt phân tán khác nhau có thể được cung cấp bởi một hệ quản trị CSDL phân tán; Tại mỗi mức, tính trong suốt làm cho người lập trình ứng dụng không biết được sự phân tán dữ liệu. CHƢƠNG 2: CÁC NGUYÊN LÝ CHUNG CỦA TỐI ƢU HÓA TRUY VẤN PHÂN TÁN Các ngôn ngữ hỏi bậc cao như SQUARE, SEQUEL, SQL,... cho phép viết nhiều câu truy vấn với sự quan tâm nhiều đến thời gian thực hiện, và thời gian thực hiện đó có thể giảm đáng kể nếu bộ xử lý ngôn ngữ hỏi viết lại (bằng cách khác) câu truy vấn trước khi thực hiện. Sự cải tiến như vậy thường gọi là "Sự tối ưu hoá", m c dù câu truy vấn được viết lại không cần tối ưu trên tất cả các cách cài đ t câu truy vấn có thể. Chương này sẽ trình bày một số phương pháp tối ưu hóa các biểu thức quan hệ, đ c biệt là xử lý biểu thức liên quan đến phép kết nối và tích Decartes, xem xét các kỹ thuật điển hình INGRES và System R. 2.1. Các chiến lƣợc tối ƣu hóa cơ bản Trong ngôn ngữ hỏi dựa trên đại số quan hệ, các truy vấn liên quan đến tích Decartes và phép kết nối là rất tốn thời gian. Ví dụ 2.1: Xét biểu thức AB × CD (AB là một quan hệ với các thuộc tính A, B); ta đồng nhất hai quan hệ này với hai tệp dữ liệu. Để đưa ra giá trị của tích Decartes này phải duyệt hết bản ghi của một quan hệ, chẳng hạn AB, ở vòng ngoài, với mỗi bản ghi r của tệp AB, duyệt tệp CD ở vòng trong và nối r với mỗi bản ghi của tệp CD. Giả sử quan hệ AB có n bản ghi, CD có m bản ghi thì tích Decartes AB × CD có n × m bản ghi. Rõ ràng phép tính trên rất tốn kém về thời gian và ô nhớ. Ullman J.D trong các kết quả nghiên cứu của m nh đã tr nh bày 6 chiến lược tổng quát cho việc tối ưu hóa câu truy vấn. ý tưởng tối ưu chia làm 2 nhóm: Nhóm 1 gồm các phép biến đổi đại số có liên quan ho c không liên quan đến cách lưu trữ các quan hệ, nhóm 2 gồm các chiến lược có lợi cho việc lưu trữ các quan hệ như khoá, chỉ số. Các chiến lược thực hiện như sau [4]: 1. Thực hiện phép chọn sớm nhất có thể: Biến đổi câu truy vấn để đưa phép chọn vào thực hiện trước nhằm làm giảm kích thước của kết quả trung gian, do đó tiết kiệm thời gian thực hiện và không gian nhớ. 2. Tổ hợp phép chọn xác định với phép tích Decartes thành phép kết nối: Ta đã biết, phép kết nối đ c biệt là kết nối bằng có thể thực hiện nhanh hơn đáng kể so với phép tích Decartes trên cùng các quan hệ. Nếu kết quả của tích Decartes R × S là đối số của phép chọn và phép chọn có liên quan đến phép so sánh giữa các thuộc tính của R và S th ta đưa về phép kết nối để giảm chi phí tính toán. 3. Tổ hợp dãy các phép toán một ngôi như phép chọn và phép chiếu: Bất kỳ dãy các phép toán một ngôi như phép chọn ho c phép chiếu có kết quả phụ thuộc vào các bộ của một quan hệ độc lập thì có thể nhóm các phép đó lại. Tương tự, ta có thể nhóm các phép toán một ngôi với kết quả của phép toán hai ngôi bằng cách áp dụng các phép toán một ngôi với mỗi bộ kết quả của phép toán hai ngôi. 4. Tìm các biểu thức con chung trong một biểu thức: Nếu kết quả của một biểu thức con chung (biểu thức xuất hiện hơn một lần) là một quan hệ không lớn và nó có thể được đọc từ bộ nhớ thứ cấp với ít thời gian, thì nên tính toán trước biểu thức đó chỉ một lần. Nếu biểu thức con chung, có liên quan đến phép kết nối, th trong trường hợp tổng quát không thể được thay đổi nhờ việc đẩy phép chọn vào trong. 5. Xử lý các tệp trước: Hai vấn đề quan trọng cần xử lý trước cho các tệp số là sắp xếp các tệp và thiết lập các tệp chỉ số, khi đó thực hiện các phép toán liên quan đến hai tệp (phép tính hai ngôi) sẽ nhanh hơn nhiều. 6. Đánh giá trước khi thực hiện phép toán: Khi cần chọn trình tự thực hiện các phép toán trong biểu thức ho c chọn một trong hai đối của phép toán hai ngôi, ta nên tính toán chi phí thực hiện các phép toán đó (thường là số phép tính, thời gian, dung lượng bộ nhớ theo kích thước các quan hệ,...) theo các cách khác nhau. Từ đó sẽ quyết định phương án có chi phí thấp. 2.2. Các phép biến đổi đại số Hầu hết các chiến lược trên liên quan đến biến đổi biểu thức đại số. Một xử lý câu truy vấn bắt đầu với việc xây dựng cây phân tích biểu thức đại số, trong đó các nút biểu diễn toán tử đại số quan hệ và toán tử đ c biệt của ngôn ngữ. Ngôn ngữ hỏi có thể là ngôn ngữ đại số quan hệ như SQUARE, SEQUEL, ho c là một ngôn ngữ phép tính quan hệ mà các biểu thức phép tính được chuyển thành biểu thức đại số. 2.2.1. Các yêu cầu của phép biến đổi tối ưu hóa - Các phép biến đổi phải thực sự hữu hiệu đối với phần lớn các dạng câu truy vấn hay một lớp các câu truy vấn thường dùng mà không phải chi phí quá nhiều để thực hiện quá trình biến đổi đó. - Các phép biến đổi phải bảo toàn kết quả của câu truy vấn trước và sau khi biến đổi, có nghĩa là hai biểu thức trước và sau khi biến đổi phải cho cùng một kết quả khi thay các lược đồ trong biểu thức bởi các thể hiện cụ thể. - Các phép biến đổi phải làm giảm chi phí để thực hiện câu truy vấn. Chi phí cho xử lý câu truy vấn có rất nhiều yếu tố, tuy nhiên ta chỉ quan tâm đến một số thông báo cơ bản nhất sau đây: số lần truy xuất khối nhớ giữa bộ nhớ trong và bộ nhớ ngoài; số bản ghi cần phải xử lý ở thiết bị trung tâm; phần bộ nhớ để lưu trữ các kết quả trung gian trong quá trình thực hiện câu truy vấn. 2.2.2. Biểu thức tương đương Hai biểu thức E1 và E2 gọi là tương đương, ký hiệu E1 E2, nếu quan hệ kết quả của hai biểu thức là như nhau khi thay các lược đồ bởi các thể hiện cụ thể. Với định nghĩa tương đương này ta có một số phép biến đổi đại số có lợi [4]. 2.2.3. Các qui tắc liên quan đến phép kết nối và tích Decartes Qui tắc giao hoán của phép kết nối và qui tắc giao hoán phép tích Decartes: Nếu E1 và E2 là các biểu thức quan hệ; p là điều kiện trên các thuộc tính E1 E1pE2E2pE1 và E2 thì E1E2E2E1 E1E2E2E1 Ta chứng minh qui tắc giao hoán của phép kết nối: Giả sử E1 có các thuộc tính A1, A2, ..., An; E2 có các thuộc tính B1, B2, ..., Bm. Gọi r1 và r2 là hai quan hệ tương ứng của E1, E2. Khi đó giá trị của E1E2 là tập các ánh xạ v từ A1, A2, ..., An, B1, B2,..., Bm vào tập giá trị sao cho các ánh xạ1 r1 và 2r2 thỏa mãn: v[Ai] = m1[Ai], i =1,2, ..., n v[Bi] = m2[Bi], i =1,2, ..., m và biểu thức điều kiện p đ ng khi thay v[C] cho mỗi thuộc tính C trong p. Nếu biểu diễn E2E1 theo kiểu này, nó hoàn toàn cho cùng một tập kết quả. Do vậy hai biểu thức là tương đương. Chú ý: Nếu xem quan hệ là tập các bộ thì phép kết nối, kết nối tự nhiên, tích Decartes sẽ không giao hoán vì thứ tự các thuộc tính trong quan hệ kết quả bị thay đổi. Qui tắc kết hợp của phép kết nối và qui tắc kết hợp phép tích Decartes: Nếu E1, E2, E3 là biểu thức quan hệ; p1, p2 là biểu thức điều kiện thì: (E1p1E2)p2E3E1p1(E2p2E3) (E1E2)E3E1(E2E3) (E1E2)E3E1(E2E3) 2.2.4. Các qui tắc liên quan đến phép chọn và phép chiếu Qui tắc hợp nhất của các phép chiếu: Dãy các phép chiếu có thể tổ hợp thành một phép chiếu.  A1,...,An(B1,...,Bm(E)) A1,...,An(E) Với các thuộc tính A1, A2, …, An phải nằm trong tập các thuộc tính B1, B2, ..., Bm. Qui tắc hợp nhất củya các phép chọn: Dãy các phép chọn có thể tổ hợp thành một phép chọn. p1(p2(E))p1p2(E) Qui tắc giao hoán của phép chọn và phép chiếu: Nếu p liên quan đến các thuộc tính A1, A2, ..., An thì:  A1,...,An(p(E))p(A1,...,An(E)) Nếu p liên quan đến các thuộc tính B1, B2, ..., Bm mà không thuộc tập thuộc tính A1, A2, ....,An thì:  A1,...,An(p(E))A1,...,An(p(A1,...,An, B1,...,Bm(E))) Qui tắc giao hoán của phép chọn và tích Decartes: Nếu tất cả các thuộc tính của p là thuộc tính của E1 thì:  p(E1E2)p(E1)E2 Hệ quả: Nếu p = p1 p2, p1 chỉ liên quan tới các thuộc tính của E1, p2 chỉ liên quan tới thuộc tính E2, từ các qui tắc , ,  ta có:  p(E1E2)p1(E1)p2(E2) Nếu p1 chỉ liên quan tới các thuộc tính E1, còn p2 liên quan tới các thuộc tính của cả E1 và E2 thì:  p(E1E2)p2(p1(E1)E2) Qui tắc giao hoán của phép chọn và phép hợp: Nếu biểu thức E = E1 E2, giả sử các thuộc tính của E1 và E2 có cùng tên như của E ho c ít nhất mỗi thuộc tính của E là phù hợp với một thuộc tính duy nhất của E1 và một thuộc tính duy nhất của E2 thì:  p(E1E2)p(E1)p(E2) Nếu tên các thuộc tính của E1 và/ho c E2 khác tên thuộc tính của E thì trong p ở vế phải của công thức trên cần sửa đổi để sử dụng tên cho phù hợp. Qui tắc giao hoán của phép chọn và phép hiệu tập hợp:  p(E1 - E2)p(E1) -p(E2) Theo qui tắc , nếu tên các thuộc tính của E1 và E2 là khác nhau thì cần thay thế các thuộc tính trong p ở vế phải tương ứng các thuộc tính của E1. Chú ý: Phép chọn p(E2) là không cần thiết, có thể thay bởi E2. Tuy nhiên, trong nhiều trường hợp, việc thực hiện phép chọn p(E2) trước sẽ có hiệu quả hơn là tính toán trực tiếp với E2 v khi đó kích thước quan hệ sẽ nhỏ đi nhiều. Phép kết nối thực hiện tốn thời gian, nên thường đẩy phép chọn xuống trước phép kết nối theo qui tắc , , . Qui tắc đẩy phép chiếu xuống trước phép tích Decartes ho c phép hợp tương tự như qui tắc , , . Không có phương pháp tổng quát cho việc đẩy phép chiếu xuống trước phép hiệu các tập hợp. Qui tắc giao hoán của phép chiếu với tích Decartes: E1, E2 là hai biểu thức quan hệ: A1,...,An là tập các thuộc tính trong đó B1,...,Bm là các thuộc tính của E1, các thuộc tính còn lại C1,...,Ck thuộc E2. Khi đó:  A1,...,An(E1 E2) =B1,...,Bm(E1) C1,...,Ck(E2) Qui tắc giao hoán của phép chiếu và phép hợp:  A1,...,An(E1 E2) =A1,...,An(E1)C1,...,Ck(E2) Như trong quy tắc , nếu tên các thuộc tính của E1 và/ho c E2 là khác với thuộc tính trong E1 E2 thì phải thay A1,...,An ở vế phải bởi các tên phù hợp. 2.2.5. Thuật toán cải tiến cây biểu diễn biểu thức quan hệ Chúng ta có thể áp dụng các qui tắc trên để tối ưu các biểu thức quan hệ. Biểu thức “tối ưu” kết quả phải tuân theo các nguyên tắc trong mục 2.1, m c
- Xem thêm -

Tài liệu liên quan