109
TẠP CHÍ KHOA HỌC, Đại học Huế, Số 53, 2009

PHƯƠNG PHÁP TỐI ƯU HOÁ TRUY VẤN ĐỐI TƯỢNG BẰNG CÁC PHÉP
BI
ẾN ĐỔI BIỂU THỨC ĐẠI SỐ ĐỐI TƯỢNG OQL
Lê M nh Th nh, i h c Hu
Hoàng B
o Hùng
S
Thông tin và Truy n thông t nh Th a Thiên Hu
TÓM TẮT
T i u hóa truy v n là v n c quan tâm nghiên c u v lý thuy t c s d li u.
Nh
ng k t qu khá tr n v n v t i u hóa truy v n trên mô hình c s d li u quan h ã là l i
gi
i cho nhi u l p bài toán qu n lý nói chung và lý thuy t c s d li u nói riêng. T c s ó,
vi
c nghiên c u m r ng các ph ng pháp t i u hóa truy v n quan h trên mô hình c s d
li
u h ng i t ng là ph ng pháp c xu t trong bài báo này. i u khác bi t so v i mô
hình quan h
là vi c t i u hóa truy v n i t ng d a trên t p lu t – bi n i bi u th c truy
v
n b ng các phép bi n i i s i t ng, c th c hi n qua vi c chuy n i t ng ng
gi
a truy v n vi t b ng OQL (Object Query Language) và i s i t ng t ng ng, k t qu
gi
a truy v n vi t b ng OQL và bi u th c i s i t ng t ng ng là t ng ng. Bài báo

ấn đối tượng, chuyển đổi các truy vấn thành các biểu thức đại số đối tượng tương
đương. Sau đó, áp dụng các luật biến đổi trên các phép toán đại số như chọn, chiếu, kết
n
ối đối với các lớp đối tượng, loại bỏ trùng lặp trong các đa tập, Cuối cùng, chúng ta
có k
ết quả là phương án thực thi được chọn trong tiến trình tối ưu truy vấn.
Ngôn ng truy v n
Ki m tra ki u
T i u hoá các
ki
u i t ng
Chuy n i ngôn
ng
truy v n v i
s
i t ng
Bi
u th c i
s
i t ng
T i u hoá
Các ph ng án
th
c thi t ng quát
Ph
ng án
th
c thi truy v n

Hình 1. Ti n trình khung x lý truy v n

2.1. S
ự biểu diễn tương đương giữa truy vấn OQL và đại số đối tượng
Định nghĩa. Nếu E là biểu thức đại số đối tượng và Q là truy vấn đối tượng
OQL cùng xác
định một tập đối tượng thì ta nói E biểu diễn Q hay Q biểu diễn E, ta gọi
E t
ương đương với Q, ký hiệu E
≈
Q.
S
ự biểu diễn tương đương giữa truy vấn viết bằng ngôn ngữ OQL và đại số đối
t
ượng được thể hiện qua hai định lý 1 và 2 sau:
Định lý 1. [3] Mọi biểu thức đại số đối tượng đều biểu diễn được bằng các truy
v
ấn đối tượng trong OQL.
Định lý 2. [3] Mọi truy vấn đối tượng trong OQL đều biểu diễn được bằng các
bi
ểu thức đại số đối tượng.
Nh
ư vậy, việc viết lại một truy vấn đã cho thành các biểu thức đại số với tập
phép toán
đại số đối tượng là tương đương. Các biểu thức đại số này có thể được ước
l
ượng với các chi phí xử lý khác nhau. Vì vậy, về mặt lý thuyết chúng ta mong muốn
tìm
được biểu thức đại số tương đương với một truy vấn sao cho có thể đạt được một
ph
ương án thực thi hiệu quả hơn. Tuy nhiên, trong các giải pháp cài đặt, vì số lượng các
truy v

ử dụng các ký hiệu phép toán một cách hình thức [6], [7], [8], các phép toán này có thể
được cài đặt với một số thay đổi trong các mô hình khác nhau.
L1. Hoán v
ị phép chọn:
σ
λ
t.g
(
σ
λ
s.f
(S)) =
σ
λ
s.f
(
σ
λ
t.g
(S))
L2. T
ổ hợp các phép chọn:
σ
λ
s.(f
∧
g
∧
…
∧

aa
m
bb
n
aa
π
π
π
=
, với {a
1
, , a
n
}
⊂
{b
1
, , b
m
}
L4. Hoán v
ị phép chọn và phép chiếu
))(())((
.) () (.
11
SS
esaaaaes
nn
λλ
σππσ

1
op S
2
) =
σ
λ
s.f
(S
1
) op S
2
, nếu f chỉ liên quan với S
1
.
T
ổng quát:
σ
λ
s.(f
∧
g
∧
h
(S
1
op S
2
) =
σ
λ

(
σ
λ
t.f
(S)) =
σ
λ
t.f
(apply
λ
s.e
(S))
L8. Hoán v
ị giữa phép làm phẳng (flat) và phép apply trên tập/đa tập: giả sử
S là th
ể hiện của một lớp và X là một tập thuộc tính phức của lớp.
)))((())((
))((
)(
))))((
)(
(
.
.(
SapplyflatapplySapplyflat
S
VX
setS
VXet
applys

là một lớp con
c
ủa S
1
, thì thể hiện của S
2
là một tập con của thể hiện của S
1
:
σ
λs.f
(S
1
) union σ
λs.f
(S
2
) = σ
λs.f
(S
1
)
apply
λs.e
(S
1
) union apply
λs.e
(S
2

ể nhóm gộp bằng một phép chọn hoặc một phép chiếu (luật L3). Với phép biến đổi
này chúng ta s
ẽ làm giảm số lần truy xuất trên các lớp.
(R3) Làm ph
ẳng các cấu trúc phức với các phép toán set_flat, bag_flat,
list_flag: chuy
ển các cấu trúc phức về các kiểu tập, bộ và các danh sách với các phần tử
đơn trị (lồng nhau). Với phép biến đổi này chúng ta loại bỏ được các tham chiếu lồng,
l
ặp (tự trỏ) trong các cấu trúc phức làm giảm độ phức tạp tính toán trong quá trình xử lý
truy v
ấn.
(R4) X
ử lý trước các lớp đối tượng bằng các phép toán một ngôi: làm giảm kích
th
ước các lớp đối tượng khi tham gia kết nối hay lập nhóm.
(R5) Tính các thành ph
ần cơ sở trong một biểu thức đại số đối tượng: Xác định
thành ph
ần cơ sở chung nhất trên các biến vùng, nếu tồn tại một thành phần cơ sở chung
nh
ất thì chúng ta sẽ tính trước các biểu thức con chung này, chúng được xem là đầu vào
cho các b
ước truy vấn tiếp theo.
Th
ủ tục xác định thành phần cơ sở chung nhất trên các biến vùng: Để thuận tiện
trong trình bày, chúng ta bi
ểu diễn lại cú pháp của truy vấn đối tượng OQL:
Truy v
ấn:

114

Cho hai <
kq_ ích
> R
1
và R
2
, thì thành phần cơ sở chung nhất, ký hiệu GC(R
1
,
R
2
) là “tiền tố” chung nhất của các <
kq_ ích
>. Chúng ta xác định thành phần cơ sở của
m
ỗi <
kq_ ích
> trong <
ds_ ích
> bằng thuật toán:
Thu
ật toán 2.1: Xác định thành_phần_cơ_sở_chung_nhất
Vào: R
1
, R
2
là các kết quả thuộc <
ds_ ích

trong
đó, GC là thành phần cơ sở chung nhất của R
1
và R
2
, PC: thành phần cơ sở của R
i
.
2.4. Thuật toán tối ưu hoá truy vấn đối tượng dựa trên tập luật
Thu
ật toán được giới thiệu trong phần này tập trung xử lý các phép toán chiếu,
ch
ọn, áp dụng biểu thức đại số (set_apply) trên các kiểu đối tượng và phép toán loại bỏ
trùng l
ặp trên các đa tập, lớp đối tượng.
Thu
ật toán 2.2: Tối ưu hoá các biểu thức đại số đối tượng dựa trên tập luật.
Vào: Bi
ểu thức đại số đối tượng.
Ra: M
ột dãy các bước ước lượng biểu thức đại số đối tượng.
Phương pháp:
(1) Kh
ởi tạo cây phân tích cú pháp từ biểu thức đại số đối tượng.
(2) Sử dụng luật (L2) tách phép chọn σ
λs.(f∧g∧…∧h
(S) thành chuỗi các phép chọn:
σ
λs.f
(σ

ại bỏ trùng lặp trong các đa tập (bagtoset) lên trước các phép toán nhóm
ho
ặc kết nối.
(7) Tạo ra dãy các bước biến đổi để ước lượng mỗi nhóm theo một thứ tự sao
cho không có nhóm nào
được ước lượng trước các nhóm con của nó.
M
ệnh đề. Thuật toán trên là đúng đắn và kết quả của thuật toán là phương án
truy v
ấn có chi phí thấp hơn chi phí ước lượng của biểu thức đầu vào thuật toán.
Ch
ứng minh.
Theo
định lý 1, 2 và tập các luật biến đổi biểu thức đại số đối tượng, chúng ta
suy ra các b
ước thực thi trong thuật toán cho kết quả đúng và tương đương.
Áp d
ụng các phép toán chiếu trên các lớp đối tượng làm giảm kích thước các lớp và
các
đối tượng tham gia trong biểu thức, điều này sẽ làm giảm chi phí nạp lớp vào bộ nhớ
trong (IO_Load). M
ặt khác, phép toán làm phẳng (set_flat) và loại bỏ trùng lặp (bagtoset)
áp d
ụng cho đa tập, lớp đối tượng sẽ làm giảm một cách đáng kể các biến thể của các lớp
tham gia trong các phép k
ết nối, nhóm tương đương (IO_Eval). 
Độ phức tạp tính toán của thuật toán có thời gian đa thức theo kích thước (số các
bi
ến thể) của các lớp tham gia trong biểu thức.
III. Ví dụ minh hoạ

tenkh
(ví dụ: Sinh học,
Công ngh
ệ thông tin):
define SinhVien as s
select (s.hoten)
group by s.tenkhoa.tenkh
where s.tenkhoa.diadiem = 5
Hình 4 biểu diễn cây phân tích cú pháp đại số cho ví dụ 3, ta nhóm đa tập trên
thu
ộc tính
tenkh
của thuộc tính
tenkhoa
, sau đó loại bỏ các sinh viên của các khoa
không
ở tầng 5, cuối cùng chiếu lấy thuộc tính
hoten
.

Hình 4. Kh i t o cây c a ví d 3 117

Một phương pháp tối ưu ví dụ 3 được suy trực tiếp từ hình 4. Trước hết, ta đưa
phép ch
ọn lên trước phép tạo nhóm GRP và sử dụng các phép chiếu trên đối tượng (π
V
)

các truy v
ấn đối tượng lồng bằng các phép biến đổi đại số trên các biểu thức đại số đối
t
ượng lồng nhau.
TÀI LIỆU THAM KHẢO
1. Bierman G.M. and Trigoni A. Towards A Formal Type System For ODMG OQL,
Technical Report 497, University of Cambridge, Computer Laboratory, 2000.
2. Cattel R.G.G., Barry D.K. The Object Database Standard: ODMG 3.0, Morgan
Kaufmann Publishers, 2000.
118

3. oàn V n Ban, Lê M nh Th nh và Hoàng B o Hùng. S t ng ng trong bi u di n
gi
a ngôn ng truy v n OQL và i s i t ng, T p chí Tin h c và i u khi n h c,
20(3), (2004), 257–269.
4. Lê M nh Th nh, Hoàng B o Hùng, Ngôn ng truy v n h ng i t ng và t i u hoá
truy v
n trên CSDL h ng i t ng b ng ph ng pháp bi n i i s , K y u H i
ngh
khoa h c k ni m 25 n m thành l p Vi n Công ngh Thông tin, Hà N i, (2001),
175–185.
5. Lê M
nh Th nh, Hoàng B o Hùng, Mô hình c l ng chi phí x lý truy v n i t ng
trong c
s d li u h ng i t ng, K y u H i th o Qu c gia, l n th VIII, “M t s
v
n ch n l c v CNTT và truy n thông”, ch “Mã ngu n m ”, 25/8-27/8/2005,