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.


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 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 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.

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ừ P
1
và P
2
đị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 = Q
1
∪
(R.Q
2
). 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ị

atrrName
, một kết nối hiển EJ
pred
, một điểm bất động (Fix point)
Fix, một phép hợp Union (k = 2),
- Một kết nối ẩn thực hiện bởi một chỉ mục đường dẫn PIJ
pathIndex
(k ≥ 2),
- Một thực thể nguyên tử của lược đồ vật lý hoặc một tập tin tạm (k = 0).
2.4. Mô hình chi phí [4, 5, 6]Ký hiệu C
i
là tên của quan hệ hay lớp, N là nút của PT, A
i
là thuộc tính của C
i
, P
là vị từ. Ta có chi phí cho các phép toán cơ bản như sau:
+ access_cost(C
i
): chi phí truy cập các thể hiện của C
i
.
+ access_cost(C
i
, P): chi phí truy cập các thể hiện của C
i
thỏa mãn vị từ P.

thehe

TRUE
thay
y
GIAOVIE
N
R
x
thay
y
y = d
thay
g
giaovie the
h
m
thay
d g
giaovie
add1
baiGiang
d
taiLieuTK
tacGia
i
i = “Nguyễn An”
and g >= 3
P
3

i
| đã được rút gọn
bởi vị từ P.
+ nbtuples(C
i
, P): trả về số đối tượng đã truy cập, nghĩa là ||C
i
|| đã được rút gọn
bởi vị từ P.
Bảng 1. Các công thức tính chi phí cho các nút trong cây xử lý truy vấn
Nút của PT Công thức chi phí
Sel
selpred
(C) access_cost(C, selpred) + nbpages(C, selpred)*eval_cost(C,
selpred)
EJ
pred
(C
i
, C
j
) access_cost(C
i
, pred) + nbtuples(C
i
, pred)*(access_cost(C
j
,
pred) + nbpages(C
j

‘Nguyễn An’
IJ
giaovien
GIAOVIEN

GIAOVIEN

GIAOVIEN
GIAOVIE
N
R

T1
T2
T3
T4
T6
T5
(i)
GIAOVIEN
TAILIEU
IJ
thay
GIAOVIEN
IJ
thay
R’ GIAOVIEN
PIJ
baiGiang.taiLieuTK
BAIGIANG

T14
T15
(ii)