Báo cáo nghiên cứu khoa học: TỐI ƯU CÁC TRUY VẤN ĐỆ QUY HƯỚNG ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH CHI PHÍ CƠ SỞ

Trong các lược đồ cơ sở dữ liệu hướng đối tượng thường xảy ra các quan hệ đệ quy giữa các lớp, nhằm mục đích làm tăng khả năng biểu diễn ngữ nghĩa của chúng, điều này làm phức tạp thêm vấn đề xử lý tối ưu các truy vấn nói chung và các truy vấn đệ quy nói riêng trên các đối tượng phức. Dựa vào các kết quả trong [5], bài báo tập trung nghiên cứu, phân tích và cải tiến các phương pháp tối ưu truy vấn đệ quy, như: tạo các cây xử lý truy...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: " TỐI ƯU CÁC TRUY VẤN ĐỆ QUY HƯỚNG ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH CHI PHÍ CƠ SỞ" TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 TỐI ƯU CÁC TRUY VẤN ĐỆ QUY HƯỚNG ĐỐI TƯỢNG DỰA TRÊN MÔ HÌNH CHI PHÍ CƠ SỞ OPTIMIZATION OF OBJECT-ORIENTED RECURSIVE QUERIES BASED ON THE COST MODEL Trương Ngọc Châu Trường Đại học Bách khoa, Đại học Đà Nẵng TÓM TẮT Trong các lược đồ cơ sở dữ liệu hướng đối tượng thường xảy ra các quan hệ đệ quygiữa các lớp, nhằm mục đích làm tăng khả năng biểu diễn ngữ nghĩa của chúng, điều này làmphức tạp thêm vấn đề xử lý tối ưu các truy vấn nói chung và các truy vấn đệ quy nói riêng trêncác đối tượng phức. Dựa vào các kết quả trong [5], bài báo tập trung nghiên cứu, phân tích vàcải tiến các phương pháp tối ưu truy vấn đệ quy, như: tạo các cây xử lý truy vấn ứng với cácnút vị từ; biến đổi các cây xử lý truy vấn dựa trên mô hình chi phí cơ sở, sử dụng chiến lượcđiều chỉnh chi phí, với tham số đầu vào là đồ thị truy vấn của truy vấn đệ quy hướng đối tượngtổng quát. ABSTRACT In the schemata of object-oriented database, recursive relations among classes oftentake place with the purpose of increasing the ability of performing their meaning. This causesmore problems to the optimal processing of queries in general and recursive queries based oncomplicated objects in particular. Based on the results in [5], this article focuses on the study,analysis and improvement of a number of optimal methods for recursive queries such ascreating trees of processing queries with the predicates performance at nodes; changing query-processing trees based on a model of the basic cost by using a strategy for controlling cost withan input querying graph of general recursive queries.1. Giới thiệu Các mô hình dữ liệu hướng đối tượng được mở rộng với các quan hệ đệ quynhằm mục đích làm tăng khả năng biểu diễn ngữ nghĩa, điều này làm phức tạp thêm vấnđề tối ưu các truy vấn nói chung và các truy vấn đệ quy nói riêng. Các tiếp cận tối ưutruy vấn đang tồn tại [2][3][8][10] để tối ưu hóa các truy vấn đệ quy không thể áp dụngđược. R.S.G. Lanzelotte, P. Valduriez, M. Zait [5] đã đề xuất một cách tiếp cận tối ưutruy vấn đệ quy hướng đối tượng dựa trên một mô hình chi phí cơ sở, sử dụng các chiếnlược điều chỉnh chi phí. Nguyên tắc chung khi tối ưu một truy vấn là biến đổi truy vấnnày về một lược đồ thực thi, có tổng chi phí là thấp nhất. Cách tiếp cận thông thường,chủ yếu sử dụng các quy tắt viết lại truy vấn dựa trên lược đồ khái niệm [3][8][10] rấtkhó để đo được chi phí thực thi. Tiếp cận của nhóm tác giả R.S.G. Lanzelotte [5] dựatrên các thực thể vật lý, do đó chi phí của lược đồ thực thi truy vấn có thể được tính toántrực tiếp một cách dễ dàng dựa trên mô hình chi phí đã cho.26 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010 Bài báo tập trung nghiên cứu và phân tích các chiến lược tối ưu dựa trên môhình chi phí cơ sở, sử dụng các chiến lược điều chỉnh chi phí, với tham số đầu vào làcác đồ thị truy vấn. Tiếp theo những kết quả trong [5], chúng tôi mở rộng các hành độngtối ưu một cách tổng quát hơn, dựa trên câu truy vấn đệ quy hướng đối tượng tổng quát.2. Một số khái niệm Ví dụ 1. Xét lược đồ cơ sở dữ liệu hướng đối tượng sau đây làm cơ sở cho cáctruy vấn được trình bày trong bài báo này.define class NGUOI: define class BAIGIANG:type tuple (hoTen: String; type tuple (tenBaiGiang: String; ngay Sinh: Date; giaoVien: GIAOVIEN; hocVi: String;) taiLieuTK: set(TAILIEU);) end BAIGIANGend NGUOIdefine class TAILIEU: define class GIAOVIEN inherits NGUOItype tuple (tenTaiLieu: String; type tuple (thay: GIAOVIEN; tacGia: String; baiGiang: set(BAIGIANG);) namXB: String;) end GIAOVIENend TAILIEU Ngữ nghĩa của lược đồ khái niệm trong Ví dụ 1 được giải thích như sau: mộtgiáo viên khi mới được nhận về giảng dạy tại một khoa ở một trường Đại học nào đó.Giáo viên này sẽ được khoa phân công soạn một số bài giảng trước khi tham gia giảngdạy. Các giáo viên được phân công soạn bài giảng, được khoa cử một thầy (thuộc tínhthay trong lớp GIAOVIEN) có chuyên môn liên quan hướng dẫn.2.1. Đồ thị truy vấn [5] Đồ thị truy vấn là một đồ thị có hướng bao gồm các thành phần sau: - Các nút vị từ: biểu diễn các vị từ trong câu truy vấn và được ký hiệu bởi các hình vuông, có một hoặc nhiều cung vào và một cung ra. Các cung vào và ra của một nút vị từ được gán nhãn ...