1

Tối ưu hóa truy vấn
cơ sở dữ liệu hướng đối tượng
Query Optimization in Object-Oriented Database
NXB H. : ĐHCN, 2014 Số trang 70 tr. + Phạm Thị Chanh

Đại học Công nghệ
Luận văn ThS ngành: Hệ thống thông tin; Mã số: 60 48 01 04
Người hướng dẫn: PGS.TS Đoàn Văn Ban
Năm bảo vệ: 2014

Keywords: Thuật toán tối ưu hóa; Cơ sở dữ liệu hướng đối tượng; Phương pháp hướng
đối tượng

Content
Chúng ta đang sống trong một thời đại mới, thời đại của Công nghệ thông tin (CNTT).
Công nghệ thông tin ngày một phát triển và trở thành một nhu cầu không thể thiếu trong mọi lĩnh
vực của đời sống xã hội. CNTT là ngành quản lý công nghệ và mở ra nhiều lĩnh vực khác nhau
như phần mềm máy tính, phần cứng máy tính, ngôn ngữ lập trình, ….Và cơ sở dữ liệu cũng là
một lĩnh vực quan trọng của Công nghệ thông tin. Từ khi ra đời cho đến nay, những nghiên cứu
về Cơ sở dữ liệu (CSDL) đã không ngừng phát triển và ngày càng trở nên cần thiết trong các ứng
dụng về CNTT.
CSDL đã trở thành một bộ phận chủ yếu không thể thiếu trong hầu hết các hệ thống thông
tin. Hiện nay, các hệ thống thông tin hay các CSDL đều chủ yếu sử dụng một kiểu CSDL truyền
thống đó là CSDL quan hệ, một trong những CSDL đã được phát triển và ứng dụng rộng rãi. Tuy
nhiên với sự phát triển nhanh chóng của CNTT, CSDL quan hệ đã dần bộc lộ những yếu điểm và
nhiều hạn chế, đặc biệt là trong việc xây dựng các ứng dụng cơ dữ liệu phức tạp, dữ liệu đa

hướng đối tượng là tối ưu hoá truy vấn hướng đối tượng. Với một câu truy vấn, sẽ tồn tại nhiều
phương án mà hệ thống CSDL cho phép xử lý và đưa ra kết quả cuối cùng tương đương nhau,
việc tối ưu hóa câu truy vấn sẽ cho chúng ta lựa chọn phương án nào có tổng thời gian thực hiện
truy vấn hiệu quả hơn, tức là chọn phương án có chi phí ước lượng nhỏ nhất. Hiện nay, các nhà
nghiên cứu đã đề xuất rất nhiều kỹ thuật tối ưu hoá truy vấn hướng đối tượng khả thi và đáp ứng
được các yêu cầu này như: Scott Lee Vanderberg (1993), J. Fong (1997), C. Ramanathan and J.
Hodges (1997), Clement Yu, Yi Zhang, Weiyi Meng, Wom Kim, Gaoming Wang, Tracy Pham
and Son Daop (1997): Giới thiệu giải thuật chuyển đổi các truy vấn hướng đối tượng sang truy
vấn quan hệ để tận dụng các kỹ thuật tối ưu hoá truy vấn đã có trên mô hình quan hệ; Jia Liang
Han (1998): “Optimizing Relational Queries in Connection Hypergraph: Nested Queries, Views,
and Binding Propagations”; Ullman and Jeffrey D. (1999), Lê Mạnh Thạnh và Hoàng Bảo Hùng
(2009): Phương pháp tối ưu hóa 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, Đoàn Văn Ban và Hoàng Bảo Hùng (2005): Phương pháp dùng ký
pháp siêu đồ thị để biểu diễn và tối ưu hoá các truy vấn trong CSDL hướng đối tượng. Tuy
nhiên đối với các truy vấn lồng, khi phân tích ước lượng chi phí của biểu thức đại số lồng thì
việc định giá sẽ cho chi phí chưa đạt hiệu quả như mong muốn. Vì vậy, luận văn tập trung
nghiên cứu việc làm phẳng các truy vấn con trong truy vấn lồng nhờ phương pháp dùng ký pháp
siêu đồ thị để biểu diễn và tối ưu hoá các truy vấn trong CSDL hướng đối tượng. Từ đó, xây
dựng thuật toán ước lượng chi phí xử lý truy vấn đối tượng trên cơ sở ước lượng các siêu cạnh
trong siêu đồ thị để đạt được mức chi phí nhỏ hơn cho mỗi truy vấn. Chính vì lý do trên mà tôi
chọn đề tài “TỐI ƢU HOÁ TRUY VẤN CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG” làm luận
văn tốt nghiệp.
Mục tiêu của luận văn là nghiên cứu các mô hình CSDL hướng đối tượng để giải bài toán
tối ưu hóa truy vấn đối tượng. Đây là vấn đề luôn được các nhà khoa học quan tâm nghiên cứu.
Trong khuôn khổ của luận văn, tôi tập trung nghiên cứu vào phương pháp tối ưu hóa truy vấn mà
hay được sử dụng nhất đặc biệt là đối với các truy vấn lồng đó là sử dụng phương pháp siêu đồ
thị. Nghiên cứu các đặc trưng trong mô hình dữ liệu hướng đối tượng; Tìm hiểu các kỹ thuật xử
lý truy vấn, sự biểu diễn câu truy vấn bằng ngôn ngữ truy vấn đối tượng OQL; Giới thiệu ký
pháp siêu đồ thị [10] trong biểu diễn truy vấn. Từ đó, sử dụng phương pháp này để tối ưu hóa
truy vấn cho lớp các truy vấn lồng trong CSDL hướng đối tượng [3].

[3] Lê Mạnh Thạnh, Hoàng Bảo Hùng (2010), “ Siêu đồ thị kết nối đối tượng – một cách tiếp
cận trong tối ưu hóa câu truy vấn đối tượng lồng nhau”, Tạp chí khoa học, Đại học Huế, số
58.
[4] Đoàn Văn Ban, Lê Mạnh Thạnh và Hoàng Bảo Hùng (2004), “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,
T.20. S.3, tr. 257–269.
[5] Lê Mạnh Thạnh, Hoàng Bảo Hùng (2009) “Phương pháp tối ưu hóa 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”, Tạp chí khoa học, Đại học Huế, số 53.
[6] Hoàng Bảo Hùng (2007), Truy vấn và tối ưu hoá truy vấn trong cơ sở dữ liệu hướng đối
tượng, Luận án Tiến sĩ Toán học, Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ
Việt Nam, Hà Nội.
[7] Hoàng Bảo Hùng (2001), Một vài vấn đề về tối ưu hoá truy vấn trong cơ sở dữ liệu hướng
đối tượng, Luận văn tốt nghiệp Thạc Sĩ chuyên ngành Công nghệ thông tin, Đại học Bách
khoa Hà Nội.
[8] Lê Mạnh Thạnh, Hoàng Bảo Hùng (2006), “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, Hải
Phòng, Nhà xuất bản Khoa học và Kỹ thuật, Hà nội, tr. 568-579.
[9] Lê Mạnh Thạnh, Đoàn Văn Ban, Hoàng Bảo Hùng (2005), “Phương pháp ước lượng các truy
vấn lồng trong cơ sở dữ liệu hướng đối tượng bằng siêu đồ thị kết nối”, Chuyên san Tạp chí
Bưu chính Viễn thông và Công nghệ thông tin, Các công trình nghiên cứu - Triển khai Viễn
thông và Công nghệ thông tin, ISSN 0866-7039, 14, tr. 43–49.
[10] Lê Mạnh Thạnh, Hoàng Bảo Hùng (2001), “Ngôn ngữ truy vấn hướng đối tượng và tối ưu
hoá truy vấn trên cơ sở dữ liệu hướng đối tượng bằng phương pháp biến đổi đại số”, 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.
[11] Đoàn Văn Ban, Nguyễn Thị Tĩnh, Giáo trình phân tích, thiết kế hệ thống hướngđối tượng
bằng UML, Nhà xuất bản Đại học Sư Phạm 2011.
4

[12] Ullman, Jeffrey D. (1999), Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức, Tập 1, 2, Trần

Oriented Databases”, Proceedings of the 21
st
VLDB Conference, Switzerland, pp. 323 – 334.
[24] Bierman G.M. and Trigoni A. (2000), Towards A Formal Type System For ODMG OQL,
Technical Report 497, University of Cambridge, Computer Laboratory.
[25] Elmasri Navathe (2007). Fundamentals Database Systems. 5
th
Edition, the United States of
America.
[26] Yu, T.Clement, Meg, Weiyi (1998), “Principles of Databases Query Processing for
Advanced Applications”, Morgan Kaufmann Publishers, Inc. San Francisco, California.
[27] Cluet, Sophie and Moerkotte, Guido (1995). Nested Queries In Object Bases, In Fifth
International Workshop on Database Programming Languages, Italy.
[28] Vanderberg, Scott Lee (1993), Algebras for Object - Oriented Query Languages, Ph.D.
Dissertation, University of Winconsin-Madison.
[29] Jim Paterson, Stefan Edlich, Henrik Horning, and Reidar Horning (2006), “The Definitive
Guide to db4o”.