Download miễn phí 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ở
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 động
tố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
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-07-toi_uu_cac_truy_van_de_quy_huong_doi_tuong_dua_tre.ZyhohrVBk9.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54131/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010
26
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ệ đệ 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 vấn ứng với các
nú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ượng
tổng quát.
ABSTRACT
In the schemata of object-oriented database, recursive relations among classes often
take place with the purpose of increasing the ability of performing their meaning. This causes
more problems to the optimal processing of queries in general and recursive queries based on
complicated 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 as
creating 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 with
an 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ệ đệ quy
nhằ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 ưu
truy 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 ưu
truy 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ến
lượ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ấn
nà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ất
khó để đo được chi phí thực thi. Tiếp cận của nhóm tác giả R.S.G. Lanzelotte [5] dựa
trê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án
trực tiếp một cách dễ dàng dựa trên mô hình chi phí đã cho.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010
27
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 tui mở rộng các hành động
tố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ác
truy vấn được trình bày trong bài báo này.
define class NGUOI:
type tuple (hoTen: String;
ngay Sinh: Date;
hocVi: String;)
end NGUOI
define class BAIGIANG:
type tuple (tenBaiGiang: String;
giaoVien: GIAOVIEN;
taiLieuTK: set(TAILIEU);)
end BAIGIANG
define class TAILIEU:
type tuple (tenTaiLieu: String;
tacGia: String;
namXB: String;)
end TAILIEU
define class GIAOVIEN inherits NGUOI
type tuple (thay: GIAOVIEN;
baiGiang: set(BAIGIANG);)
end GIAOVIEN
Ngữ nghĩa của lược đồ khái niệm trong Ví dụ 1 được giải thích như sau: một
giá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ảng
dạ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ính
thay 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 hay 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 cây, cây này bao gồm các biến hay các đối
tượng. Nhãn cây tại cung ra của nút vị từ cho biết kiểu của nút vị từ tại đầu ra,
để ký hiệu phép chiếu tại đầu ra, chúng ta tham chiếu các biến trong các nhãn
cây của các cung vào.
- Các tên nút: là các tên lớp hay quan hệ của lược đồ khái niệm.
- Các cung có hướng nối các tên nút với các nút vị từ.
2.2. Truy vấn đệ quy
Giả sử rằng lược đồ khái niệm được mở rộng với khái niệm khung nhìn (view)
đệ quy R. Khi đó, một truy vấn đệ quy có thể được chia thành hai bước: cơ sở và đệ
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010
28
quy, có dạng tổng quát như sau:
view R(d, i, j, v)
includes (SELECT 1, a.i, a.j, v
FROM a in T)
Truy vấn Q1 tại
bước cơ sở
Union (SELECT d+1, b.i, c.j, v
FROM b in R, c in T
WHERE )
Truy vấn Q2 tại
bước đệ quy
Trong đó:
- d cho biết độ sâu của đệ quy (thuộc tính này có thể không có mặt trong truy
vấn); v có giá trị số và có thể thay đổi sau mỗi bước đệ quy, tùy thuộc vào
cách mà nó được tính toán.
- chứa biểu thức kết nối b.j = c.i
- T là sưu tập chứa các đối tượng làm đầu vào cho truy vấn đệ quy
- R là sưu tập chứa các đối tượng được trả về sau mỗi bước đệ quy và có cấu trúc
tương tự như T.
Ví dụ 2. Cho truy vấn đệ quy: “Cho biết họ tên giáo viên có thầy hướng dẫn liên
quan ít nhất là 3 thế hệ, soạn các bài giảng đã tham khảo tài liệu của tác giả Nguyễn
An”.
view R(thay, giaovien, thehe)
includes (SELECT [thay: a.thay, giaovien: a, thehe: 1]
FROM a in GIAOVIEN) Bước cơ sở
Union (SELECT [thay: r.thay, giaovien: b, thehe: add1(thehe)]
FROM r in R, b in GIAOVIEN
WHERE r.giaovien = b.thay)
Bước đệ quy
SELECT kq.hoTen
FROM kq in R
WHERE kq.thehe>=3 and
kq.thay.baiGiang.taiLieuTK.tacGia = “Nguyễn An”
Trả về kết quả
Hình 1 là đồ thị truy vấn của truy vấn trong Ví dụ 2. Các nút vị từ P1 và P2 định
nghĩa khung nhìn đệ quy R, khung nhìn này được xem như là bao đóng chuyển tiếp có
dạng R = Q1∪ (R.Q2). Các thể hiện của R là hợp của các thể hiện ở đầu ra của các nút vị
từ P1 và P2, nút vị từ P3 áp dụng cho truy vấn trên khung nhìn đệ quy.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 2(37).2010
29
Hình 1. Đồ thị của truy vấn đệ quy
2.3. Lược đồ thực thi
Chúng ta sử dụng cây xử lý truy vấn PT (Processing Tree) [5] để mô hình hóa
lược đồ thực thi truy vấn. Ví dụ trong Hình 2 chỉ ra hai cây xử lý truy vấn của truy vấn
ở Hình 1.
Định nghĩa. Một nút N của PT, được ký hiệu N(child0, child1,..., childk-1) sao
cho mỗi nút N hay các nút con của nó childi, 0 ≤ i ≤ k-1 hay là:
- Một phép chiếu Proj, một phép chọn Selpred (k = 1),
- Một kết nối ẩn IJatrrName, một kết nối hiển EJpred, một điểm bất động (Fix p...
