ĐẠI HỌC QUỐC GIA TP HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN


ĐÀO TẤN NGỌC

KHÓA LUẬN CAO HỌC
NGÀNH: Khoa Học Máy Tính
Mã số:

60 48 01 01

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. PHẠM QUỐC TRUNG

HỒ CHÍ MINH - Năm 2015


LỜI CAM ĐOAN

Tôi xin cam đoan, kết quả của khóa luận hoàn toàn là kết quả của tự bản thân tôi
tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ và rõ
ràng, tên tác giả, tên công trình, thời gian, địa điểm công bố.
Tác giả

Đào Tấn Ngọc

i


LỜI CẢM ƠN


Trước tiên, em xin chân thành cảm ơn quý thầy cô trường Đại học Công nghệ
Thông tin - ĐHQG thành phố Hồ Chí Minh đã tận tình dạy bảo cho em nhiều kiến thức
bổ ích trong thời gian học tập tại trường, cũng như tạo điều kiện cho em thực hiện đề tài
này. Kính chúc quý thầy cô luôn dồi dào sức khoẻ và thành công trong cuộc sống.
Đặc biệt, em xin bày tỏ lòng biết ơn chân thành, sâu sắc đến Thầy TS. Phạm Quốc
Trung. Mặc dù rất bận rộn với công việc nghiên cứu, giảng dạy và công việc gia đình, tuy
nhiên trong suốt thời gian thực hiện đề tài, dù bất kỳ thời gian ngoài giờ làm việc hay
trong các ngày nghỉ, lễ, Thầy luôn sẵn sàng nhiệt tình sắp xếp thời gian để định hướng,
hướng dẫn, động viên, giúp đỡ rất tận tình giúp tôi hoàn thành khóa luận này.
Xin gửi lời cám ơn sâu sắc đến gia đình, người thân và các bạn cùng khóa đã chia
sẽ, động viên tôi trong suốt thời gian học tập và nghiên cứu, đã tạo nên sức mạnh to lớn
để tôi hoàn thành kết quả học tập này.
Sau cùng, xin kính chúc quý Thầy Cô trong khoa Khoa Học Máy Tính – Trường
Đại Học Công Nghệ Thông Tin và TS. Phạm Quốc Trung thật dồi dào sức khỏe, niềm tin
để tiếp tục thực hiện sứ mệnh cao đẹp là truyền đạt kiến thức cho thế hệ mai sau.
Mặc dù đã rất cố gắng nhưng khóa luận khó tránh khỏi những thiếu sót, tôi kính
mong Quý thầy, cô và bạn bè hướng dẫn, góp ý để nội dung nghiên cứu này ngày càng
hoàn thiện hơn.
Một lần nữa, em xin chân thành cảm ơn!
Trân trọng.
TP. HCM, tháng 11 năm 2015

Đào Tấn Ngọc – CH1301043

ii


MỤC LỤC
Số trang

Trang phụ bìa
LỜI CAM ĐOAN ...................................................................................................... i
LỜI CẢM ƠN .......................................................................................................... ii
MỤC LỤC ............................................................................................................... iii
Danh mục các ký hiệu và chữ viết tắt ...................................................................... v
Danh mục các hình vẽ và đồ thị .............................................................................. vi
MỞ ĐẦU ................................................................................................................ vii
CHƯƠNG 1 - GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI .................................... 1
1.1 Đặt vấn đề ................................................................................................... 1
1.2 Mục đích nghiên cứu................................................................................... 2
1.3 Đối tượng và phạm vi nghiên cứu............................................................... 2
1.4 Phương pháp, quy trình thực hiện khóa luận .............................................. 2
1.5 Ý nghĩa khoa học và thực tiễn .................................................................... 4
CHƯƠNG 2 – CƠ SỞ LÝ THUYẾT ................................................................... 5
2.1

Đối tượng, lớp và định danh đối tượng ................................................... 5

2.2 Các mối quan hệ giữa các lớp ..................................................................... 9
2.3 Truy vấn đối tượng.................................................................................... 12
2.4 Ngôn ngữ đối tượng OQL ......................................................................... 13
2.5 Đại số đối tượng ........................................................................................ 17
2.6 Lược đồ quan hệ nhúng............................................................................. 20
CHƯƠNG 3 - TỐI ƯU HÓA TRUY VẤN TRONG CƠ SỞ DỮ LIỆU HƯỚNG
ĐỐI TƯỢNG ................................................................................................................. 24

iii


3.1 Mô tả vấn đề .............................................................................................. 24

3.2 Các cách tiếp cận tối ưu hóa truy vấn hướng đối tượng ........................... 24
3.3 Cách tiếp cận tối ưu truy vấn hướng đối tượng của khóa luận ................. 26
3.4 Kết luận ..................................................................................................... 53
CHƯƠNG 4 – CHƯƠNG TRÌNH THỬ NGHIỆM VÀ ĐÁNH GIÁ .............. 54
4.1 Mô tả cách sử dụng ................................................................................... 54
4.2 Mô tả các bước thực hiện của chương trình .............................................. 55
4.3 Một số nhận xét, đánh giá kết quả thực hiện của chương trình. ............... 57
CHƯƠNG 5 – KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................. 58
5.1 Kết quả đạt được ....................................................................................... 58
5.2 Hướng phát triển ....................................................................................... 58
TÀI LIỆU THAM KHẢO ...................................................................................... 59
PHỤ LỤC ............................................................................................................... 60

iv


Danh mục các ký hiệu và chữ viết tắt
Viết tắt

Mô tả

Annotation

Chú thích

API

Application Programming Interface - Giao diện
chương trình ứng dụng


Classes

Các lớp khái niệm

CNTT

Công nghệ thông tin

CSDL

Cơ sở dữ liệu

SQL

Structured Query Language

OQL

Object Query Language

ODMG

Object Database Management Group

OID

Object Identifier

OODB


Object Oriented Database

OPG

OODB Predicate Graph

TID

Tuple Identifier

UML

Unified Modeling Language

ODL

Object Definition Language

DCL

Data Control Language

DDL

Data Definition Language

RPG

Relational Predicate Graph


URI

Uniform Resource Identifier

WWW

World Wide Web

XML

Extensible Markup Language

XML

Extensible Markup Language

XMLS

Extensible Markup Language Schema

v


Danh mục các hình vẽ và đồ thị

Hình 2.2. Sự phân cấp các kiểu trong OQL ................................................................................. 15
Hình 3.1. Quy trình thực hiện tối ưu hóa truy vấn ....................................................................... 24
Hình 3.2. Biểu diễn lược đồ quan hệ nhúng dưới dạng cây ......................................................... 31
Hình 3.3. Đồ thị tân từ đối tượng của mệnh đề where ................................................................. 43
Hình 3.4. Chuyển đổi đồ thị tân từ đối tượng thành đồ thị tân từ quan hệ................................... 44

Hình 3.5. Tiến trình khung xử lý truy vấn ................................................................................... 46
Hình 3.6. Khởi tạo cây phân tích cú pháp của ví dụ 3.6 .............................................................. 51
Hình 3.7. Bước chuyển đổi đầu tiên của hình 3.6 ........................................................................ 51
Hình 3.8. Khởi tạo cây của ví dụ 3.7 ............................................................................................ 52
Hình 3.9. Cây kết quả sau khi áp dụng các luật chuyển đổi......................................................... 52

vi


MỞ ĐẦU


Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được quan tâm nhiều trong
công nghệ thông tin, và đã có nhiều ứng dụng trong khoa học kỹ thuật cũng như trong các
ngành kinh tế khác.
Suốt những năm 70, các lĩnh vực nghiên cứu về lý thuyết CSDL tập trung giải
quyết trên mô hình dữ liệu quan hệ do E. F. Codd đề xuất. Đây là mô hình được xây dựng
trên cơ sở lý thuyết toán học về các quan hệ với cấu trúc chặt chẽ và hoàn chỉnh. Những
kết quả nghiên cứu đạt được trên mô hình này không những tạo nền tảng về lý thuyết
CSDL, mà còn mang tính ứng dụng cao, đó là các hệ thống quản trị CSDL thương mại
phát hành vào cuối thập kỷ 70 và đầu thập kỷ 80 như Oracle, SQL/DS và DB2,...v.v. Tuy
nhiên, sự đa dạng của các ứng dụng trong công nghệ phần mềm, các hệ thống tự động
hóa, hệ thống đa phương tiện với sự tích hợp âm thanh, hình ảnh, tài liệu toàn văn và các
ngôn ngữ lập trình, làm nảy sinh yêu cầu cần phải có một mô hình dữ liệu với các tính
năng mạnh, phong phú để có thể đặc tả các đối tượng phức trong thế giới thực và đảm
bảo tính mềm dẻo, khả chuyển của hệ thống khi có sự thay đổi, những đòi hỏi này tạo
tiền đề cho sự hình thành và phát triển của mô hình CSDL hướng đối tượng.
Trong những năm gần đây, việc phát triển các ngôn ngữ CSDL trên các hệ thống
CSDL hướng đối tượng được xem là một hướng nghiên cứu quan trọng. Các ngôn ngữ
CSDL được mở rộng theo hướng tích hợp với ngôn ngữ lập trình hướng đối tượng, điều

này sẽ tạo điều kiện cho các hệ thống tăng khả năng tính toán phức tạp và xây dựng giao
diện lập trình hướng đối tượng trong các hệ thống.
Như ta đã biết, thành công ngày càng tăng của công nghệ CSDL quan hệ trong
việc xử lý dữ liệu một phần là do tính dễ dùng khả năng khai thác, tìm kiếm dữ liệu của
các ngôn ngữ phi thủ tục (như SQL), và chính nó đã cải thiện đáng kể công việc phát
triển ứng dụng và khả năng sáng tạo của người dùng. Các ngôn ngữ phi thủ tục của
CSDL quan hệ đã cho phép diễn tả câu truy vấn phức tạp một cách chính xác và đơn
giản. Đặc biệt là để có được câu trả lời cho một truy vấn, người sử dụng không cần phải
vii


xác định chính xác trình tự tiến hành các thao tác/ phép toán trong một câu truy vấn.
Trình tự này được xử lý bởi Bộ xử lý truy vấn (query processor) của hệ quản trị CSDL,
và đó là bài toán xử lý truy vấn hay tối ưu hóa truy vấn.

viii


Chương 1 - Giới thiệu tổng quan về đề tài

CHƯƠNG 1 - GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
Chương 1 giới thiệu tổng quan về đề tài bao gồm các nghiên cứu khảo sát tình
hình ứng dụng tối ưu hóa truy vấn trong các hệ quản trị cơ sở dữ liệu nói chung và
hệ quản trị cơ sở dữ liệu hướng đối tượng nói riêng; phân tích đánh giá thực trạng,
hạn chế và xác định các nhu cầu mà hệ thống ứng dụng chưa đáp ứng được, từ đó đề
xuất nghiên cứu phát triển giải pháp tối ưu truy vấn để khai thác cơ sở dữ liệu tốt
hơn.
1.1 Đặt vấn đề
1.1.1 Lý do hình thành đề tài
Cơ sở dữ liệu là một thành phần không thể thiếu trong quá trình phát

triển các hệ thống thông tin. Trong thực tế, các ứng dụng thông tin không chỉ
dừng lại ở các ứng dụng trong lĩnh vực xử lý dữ liệu kinh doanh, thương mại
mà còn phát triển sang các lĩnh vực khác như trí tuệ nhân tạo, thông tin văn
phòng, đa phương tiện… Do đó, việc phát triển hệ thống cơ sở dữ liệu hướng
đối tượng là điều tất yếu.
Một trong những hướng nghiên cứu quan trọng được đề cập trong hệ
thống cơ sở dữ liệu hướng đối tượng là tối ưu hóa truy vấn hướng đối tượng.
Khi thực thi một truy vấn trong cơ sở dữ liệu hướng đối tượng, có thể có
nhiều phương án mà hệ thống cơ sở dữ liệu cho phép xử lý. Các phương án
có kết quả cuối cùng là tương đương nhau nhưng khác nhau về chi phí thực
hiện hay tổng thời gian thực hiện một truy vấn.
Tối ưu hóa truy vấn là lựa chọn phương án để có tổng thời gian thực
hiện truy vấn là nhỏ nhất. Như vậy, vấn đề chúng ta quan tâm là làm sao cực
tiểu tần suất sử dụng của CPU, bộ nhớ, chi phí nhập/xuất và các nguồn tài
nguyên về lĩnh vực truyền thông. Vì với kỹ thuật phần cứng hiện nay việc tối
ưu thực thi một truy vấn chỉ còn là vấn đề làm cực tiểu thời gian trả lời của
truy vấn
Vấn đề đặt ra là với lượng thông tin ngày càng lớn song việc vấn tin là
vấn đề thường xuyên và đòi hỏi việc xử lý thông tin phải nhanh chóng và
1


Chương 1 - Giới thiệu tổng quan về đề tài

hiệu quả, để tạo ra một hoạch định thực thi vấn tin nhằm hạ thấp tối đa chi
phí thì việc tối ưu câu vấn tin là vấn đề mà ai cũng phải quan tâm. Từ đó có
thể nhận thấy rằng vấn đề “tối ưu hóa truy vấn trong hệ quản trị cơ sở dữ
liệu hướng đối tượng” là cần thiết trong quản trị hệ cơ sở dữ liệu.
1.1.2 Một số vấn đề còn hạn chế
Để lấy được thông tin cần thiết ta cần thực hiện hàng loạt các thao tác

trên cơ sở dữ liệu thông qua các câu truy vấn. Từ câu truy vấn ban đầu có thể
thực hiện theo các phương pháp khác nhau để có kết quả song cần phải hạ
thấp chi phí thực hiện truy vấn. Tuy nhiên để có được phương án tối ưu nhất
thì có thể chi phí cho quá trình tối ưu lại rất cao.
Cùng với sự phát triển của khoa học kỹ thuật là sự bùng nổ của công
nghệ dữ liệu mới và lượng dữ liệu rất lớn nên việc nâng cấp và tối ưu truy
vấn là vấn đề cấp thiết để phục vụ tốt hơn cho người sử dụng.
1.2 Mục đích nghiên cứu
Nghiên cứu các vấn đề, hạn chế của các kỹ thuật hiện nay cho bài toán
tối ưu hóa truy vấn cơ sở dữ liệu hướng đối tượng.
Đưa ra một số đề xuất giúp cải tiến quá trình tối ưu hóa câu truy vấn
trong cơ sở dữ liệu.
Thử nghiệm và đánh giá giải pháp đề xuất.
1.3 Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu là tối ưu hóa câu truy vấn dữ liệu hướng đối
tượng
Phạm vi nghiên cứu là mô hình dữ liệu hướng đối tượng có hỗ trợ tập
luật.
1.4 Phương pháp, quy trình thực hiện khóa luận
Phương pháp lý thuyết: tổng quan của mô hình dữ liệu hướng đối tượng; tìm
hiểu các tài liệu liên quan đến query optimization; tìm hiểu các kỹ thuật xử lý câu
truy vấn; khái niệm, kiểu và lược đồ suy dẫn trong ngôn ngữ truy vấn OQL, biến
tham chiếu, phương thức tham chiếu; tổ chức biểu diễn dữ liệu.

2


Chương 1 - Giới thiệu tổng quan về đề tài

Phương pháp thực nghiệm: xây dựng thuật toán chuyển đổi từ lược đồ hướng

đối tượng sang lược đồ quan hệ nhúng; triển khai thuật toán cải tiến câu truy vấn
trong cơ sở dữ liệu hướng đối tượng bằng các phép biến đổi biểu thức đại số đối
tượng.
Quy trình thực hiện khóa luận:
Mục tiêu

Nội

Phương pháp

Kết quả

dung
− Tổng quan của mô
hình dữ liệu hướng
đối tượng như định
− Tìm hiểu các tài
Khảo sát

liệu liên quan đến

tổng quan về bài

query

toán tối ưu hóa

optimization như:

cơ sở dữ liệu

1 hướng

đối

tượng,

những

vấn đề và hạn

+ Các tutorial.
+ Các bài báo
khoa học.
− Khảo sát, lấy ý

chế của các kỹ

kiến của chuyên

thuật hiện nay

gia.

danh đối tượng,
kiểu, lớp, lược đồ
quan hệ kế thừa
phương thức.
− Khái niệm, kiểu và
lược đồ suy dẫn
trong ngôn ngữ

truy vấn OQL,
biến tham chiếu,
phương thức tham
chiếu.
− Bản báo cáo thống
kê giải pháp của
các kỹ thuật tối ưu
truy vấn hiện nay.

Cải

tiến

− Tìm hiểu mô hình

− Thuật toán chuyển

quá trình tối ưu

xử lý truy vấn và

đổi từ lược đồ

2 hóa câu truy vấn

các quy tắc tối ưu

hướng đối tượng

trong cơ sở dữ


hóa truy vấn

sang lược đồ quan

liệu

hướng đối tượng.

hệ nhúng.

3


Chương 1 - Giới thiệu tổng quan về đề tài

− Cài đặt một số

− Các thuật toán

thuật toán để cái

biên dịch các

tiến câu truy vấn

mệnh đề trong

trong cơ sở dữ


OQL sang mệnh

liệu hướng đối

đề trong SQL.
− Tối ưu hóa truy

tượng.

vấn đối tượng
bằng các phép biến
đổi biểu thức đại
số đối tượng.
Dùng
Thử

ngôn

ngữ lập trình C# kết

3 nghiệm và đánh hợp với cơ sở dữ liệu
giá giải pháp

hướng đối tượng MS

Chương

trình

demo


SQL Server.

1.5 Ý nghĩa khoa học và thực tiễn
Việc tối ưu hóa truy vấn trên cơ sở dữ liệu hướng đối tượng quyết
định tốc độ hồi đáp nhanh nhất có thể có cho các truy vấn, qua đó giúp việc
nghiên cứu, tổ chức và khai thác các cơ sở dữ liệu có hiệu quả tốt hơn…
Trình bày phương pháp chuyển đổi lược đồ hướng đối tượng sang
lược đồ quan hệ nhúng, cải tiến và hoàn chỉnh các thuật toán biên dịch truy
vấn đối tượng OQL về truy vấn quan hệ SQL.
Trình bày thuật toán tối ưu hóa truy vấn đối tượng dựa vào tập luật và
các quy tắc tối ưu hóa truy vấn đối tượng tổng quát.
Tích hợp môđun biên dịch và tối ưu hóa truy vấn đối tượng trong hệ
thống cơ sở dữ liệu đối tượng quan hệ.

4


Chương 2 – Cơ sở lý thuyết

CHƯƠNG 2 – CƠ SỞ LÝ THUYẾT
Chương 2 trình bày nhiều kiến thức nền tảng của mô hình dữ liệu
hướng đối tượng như định danh đối tượng, kiểu/lớp, lược đồ mối quan hệ kế
thừa phương thức.
Ngôn ngữ truy vấn đối tượng OQL và đại số đối tượng tương ứng
được chọn làm cơ sở cho những nghiên cứu, mở rộng các thuật toán tối ưu
hóa truy vấn đối tượng và là công cụ minh họa cho các thuật toán tối ưu hóa
truy vấn được đề xuất trong chương 3.
2.1 Đối tượng, lớp và định danh đối tượng
2.1.1 Đối tượng và định danh đối tượng

Khái niệm cơ bản của mô hình HĐT là đối tượng. Đối tượng là một
khái niệm, một sự trừu tượng hóa, hay một sự vật có nghĩa trong bài toán
đang khảo sát. Đó chính là các mục (item) mà ta đang nghiên cứu, đang thảo
luận về chúng. Đối tượng là thực thể của hệ thống, của CSDL và được xác
định thông qua định danh (OID – Object Identifier) của chúng. Thông
thường các đối tượng được mô tả bởi các danh từ riêng (tên gọi) hoặc được
tham chiếu tới trong các mô tả của bài toán hay trong các thảo luận với người
sử dụng. Có những đối tượng là những thực thể trong thế giới thực như
người, sự vật cụ thể, hoặc là những khái niệm như một công thức, hay khái
niệm trừu tượng... Có những đối tượng được bổ sung và hệ thống với lý do
phục vụ cho việc cài đặt và có thể không có trong thực tế.
Mỗi đối tượng có thể được biểu thị bởi bộ ba (oid, class-name, value).
Trong đó oid là giá trị thuộc tính định danh OID của đối tượng, class-name là
tên lớp chứa đối tượng này và value là giá trị của đối tượng đó.
2.1.2 Lớp đối tượng
Đối tượng là một thể hiện, một đại biểu của một lớp. Lớp là một mô tả
về một nhóm các đối tượng có những tính chất (thuộc tính) giống nhau, có
chung các hành vi ứng xử (thao tác gần như nhau), có cùng mối liên quan với

5


Chương 2 – Cơ sở lý thuyết

các đối tượng khác và có chung ngữ nghĩa trong hệ thống. Lớp thường xuất
hiện dưới dạng những danh từ chung trong các tài liệu mô tả bài toán hay
trong các thảo luận với người sử dụng. Cũng như các đối tượng, lớp có thể là
những nhóm thực thể có trong thế giới thực, cũng có những lớp là khái niệm
trừu tượng và có những lớp được đưa trong thiết kế để phục vụ cho cài đặt hệ
thống…

Một cách hình thức, ta có một số ký hiệu được qui ước như sau:
Alloid: Tập tất cả các định danh đối tượng.
C: Tập các tên lớp.
A: Tập các tên thuộc tính.
Integer, Real, Boolean, String: Tập các kiểu nguyên tố (kiểu cơ sở) có
miền trị tương ứng lần lượt là D1, D2, D3, D4.
D: Tập các giá trị nguyên tố D= D1  D2  D3  D4.
O: Tập các đối tượng.
2.1.3 Giá trị và kiểu
Các giá trị trên tập các đối tượng (O) được định nghĩa như sau:
• Một phần tử thuộc D hoặc thuộc Alloid là một giá trị, được gọi
là giá trị nguyên tố.
• Nếu v1, v2, …., vn là các giá trị và a1, a2, …, an là cá tên thuộc
tính, thì [a1: v1, a2: v2, an: vn] là một giá trị được gọi là giá trị
bộ.
• Nếu v1, v2, …., vn là các giá trị phân biệt thì { v1, v2, …., vn} là
một giá trị được gọi là giá trị tập.
Khái niệm về kiểu trên tập các lớp (C) cũng được định nghĩa như sau:
• Integer, Real, Boolean, String: là các kiểu gọi là kiểu nguyên
tố.
• Các tên lớp trong C cũng là các kiểu.

6


Chương 2 – Cơ sở lý thuyết

• Nếu T1, T2, …., Tn là các kiểu và a1, a2, …, an là cá tên thuộc
tính phân biệt của C thì [a1: T1, a2: T2, an: Tn] là một kiểu còn
gọi là kiểu bộ.

• Nếu T là một biểu thức kiểu, thì {T} hoặc Set(T) cũng là kiểu
còn được gọi là kiểu tập.
2.1.4 Thuộc tính, thao tác và phương thức
Mỗi thuộc tính có thể là thuộc tính đơn trị hoặc thuộc tính đa trị. Trái
với thuộc tính đơn vị, một thể hiện của thuộc tính đa trị là tương ứng với một
tập các giá trị.
Class HoSo
Type tuple (mahs: int, hoten: char, thanhpho: char, ngaysinh:
tuple(ngay, thang, nam))
Class NhanVien inherits HoSo
Tupe tuple (manv: int, luong: float, thuong: float, tenphong: Phong)
Class Phong
Type tuple (maphong: int, tenphong: char, diadiem: char)
NhanVien là lớp được kế thừa từ lớp HoSo, có thuộc tính tenphong là
thuộc tính tham chiếu đối tượng đến lớp Phong, ngaysinh là thuộc tính đa trị.
• Set (tập hợp): Các phần tử không có thứ tự, không lặp, không
cố định số phần tử.
• List (danh sách): Các phần tử có thứ tự, có lặp, không cố định
số phần tử.
• Array (mảng): Các phần tử có thứ tự, có lặp, cố định số phần tử
tối đa.
Một thuộc tính có trong một lớp còn có thể là thuộc tính phức hợp, là
thuộc tính được xây dựng từ tập các thuộc tính khác. Việc khai báo một
thuộc tính phức hợp được thực hiện bằng toán tử xây dựng tuple (bộ).
Thao tác (Operation) là một hàm hay thủ tục có thể áp dụng (gọi hàm)
cho hoặc bởi các đối tượng trong một lớp. Khi nói tới một thao tác là ngầm
7


Chương 2 – Cơ sở lý thuyết


định nói tới một đối tượng đích để thực hiện thao tác đó. Ví dụ, thao tác
(hàm) hienthi() của lớp MonHoc khi gọi để hiển thị về các sinh viên học một
môn học cụ thể như “Lập trình hướng đối tượng” chẳng hạn.
Một phương thức là một cách thức cài đặt của một thao tác trong một
lớp.
Một số thao tác có thể là đa xạ (polymorphic), được nạp chồng, nghĩa
là nó có thể áp dụng cho nhiều lớp khác nhau với những nội dung thực hiện
có thể khác nhau, nhưng cùng tên gọi. Ví dụ lớp ThietBi có hàm TinhGia().
Hàm này có thể nạp chồng (đa xạ), bởi có nhiều phương thức (công thức)
tính giá bán khác nhau tùy thuộc từng loại thiết bị. Tất cả các phương thức
này đều thực hiện một nhiệm vụ TinhGia(), nhưng được cài đặt với nội dung
(các đoạn chương trình) khác nhau. Hệ thống hướng đối tượng tự động chọn
phương thức tương ứng với ngữ cảnh của đối tượng đích để thực hiện.
Việc khai báo các toán tử hay các phương thức sử dụng từ khóa
operations của mỗi đối tượng thuộc một lớp đối tượng nhằm phản ánh các
hành vi được thực hiện trên mỗi đối tượng thuộc lớp đó. Mỗi phương thức
nhằm đặc tả tên của phương thức, các tham số kèm kiểu dữ liệu của chúng,
kiểu của phương thức và phần thân là phần chứa mã lệnh của phương thức.
Dưới đây là mẫu đặc tả cho một lớp thường được xây dựng như sau:
class

<class name>
Properties
{Các thuộc tính}
Operations
{Các phương thức}
<class name>

End

Các đối tượng đều được đóng gói. Có nghĩa là cấu trúc bên trong của
đối tượng được che dấu, người dùng chỉ có thể biết được các phương thức
thực hiện của đối tượng đó. Các thao tác trên các giá trị của một đối tượng
chỉ được thực hiện thông qua các phương thức được định nghĩa trên đối
8


Chương 2 – Cơ sở lý thuyết

tượng đó. Đây chính là tính đóng gói thông tin trong mô hình dữ liệu hướng
đối tượng. Việc đóng gói thông tin độc lập với dữ liệu vật lý.
Các phương thức được gọi bởi các thông điệp. Một thông điệp về cơ
bản chỉ là một lời gọi đến một phương thức nào đó, trong đó tham số đích
được phân biệt và có cách xử lý riêng về cú pháp.
2.2 Các mối quan hệ giữa các lớp
2.2.1 Sự phân cấp lớp
Các lớp trong mô hình hướng đối tượng có thể được tổ chức theo một
phân cấp lớp (Class hierarchy). Ta nói lớp C2 là một lớp con của lớp C1, hay
lớp C1 là lớp cha của lớp C2 nếu tập các thuộc tính và phương thức là tập con
của các tập thuộc tính và phương thức của C2 đồng thời tập các đối tượng
thuộc C2 là tập con của tập các đối tượng thuộc C1. Điều đó có nghĩa rằng
một lớp con sẽ kế thừa tất cả các đặc tính cho phép của lớp cha, ngoài ra các
lớp con còn có thể bổ sung các đặc tính khác. Nguyên tắc này tạo thuận lợi
trong việc tái sử dụng các thuộc tính và các phương thức của lớp cha bên
trong các lớp con, cho phép tạo ra một hệ thống hiệu quả và tin cậy hơn.
2.2.2 Sự kế thừa
Trong các mô hình hệ thống hướng đối tượng, một số hệ thống chỉ
cho phép một lớp con có tối đa một lớp cha, trong khi các hệ thống khác cho
phép một lớp con có thể có nhiều lớp cha. Một lớp con kế thừa các thuộc tính
và các phương thức từ chỉ một lớp cha được gọi là kế thừa đơn, ngược lại

một lớp con kế thừa các thuộc tính và phương thức từ nhiều hơn một lớp cha
được gọi là kế thừa bội.
Việc khai báo một mối quan hệ kế thừa giữa một lớp con và một lớp
cha được thực hiện bằng cách sử dụng từ khóa inherits kèm tên lớp cha khi
định nghĩa lớp con đó.
Ví dụ 1.1:

9


Chương 2 – Cơ sở lý thuyết

Để định nghĩa lớp GiaoVien là lớp con của lớp Nguoi, theo cách này,
ta chỉ cần khai báo các thuộc tính và các phương thức được bổ sung cho lớp
GiaoVien.
Class GiaoVien
Inherits: Nguoi
Properties
Luong: Real;
Tdo-Ngoaingu: Char;
Chunhiem: String;
Giang: String;
Operations
……
End GiaoVien;
Thông thường, các hệ thống quy định nếu một lớp không có lớp cha
thì sẽ được xem như là lớp con của lớp Object được định nghĩa bởi hệ thống.
Quan hệ kế thừa tồn tại một số vấn đề sau:
• Vấn đề thứ nhất là tồn tại sự xung đột về tên giữa một lớp con
và lớp cha của nó, và giữa các lớp cha của một lớp. Nếu tên

của một thuộc tính hay một phương thức xung đột giữa một lớp
con và lớp cha của nó, thì tên dùng trong lớp con được ưu tiên
trước, tức thuộc tính và phương thức đó của lớp cha không
được kế thừa. Đối với trường hợp xung đột về tên các thuộc
tính và phương thức giữa các lớp cha, thông thường ta chọn
một lớp cha trên cơ sở thứ tự về quyền ưu tiên trước. Phần lớn
các hệ thống yêu cầu một thứ tự ưu tiên về tên giữa các lớp cha
trong mô tả sự phân cấp lớp, tuy nhiên một số hệ thống khác lại
xác định thứ tự ưu tiên này khi thực hiện.

10


Chương 2 – Cơ sở lý thuyết

• Vấn đề thứ hai là phạm vi tác động của tính kế thừa. Cách giải
quyết thứ nhất là phạm vi tác động của sự kế thừa yêu cầu sẽ
kế thừa đầy đủ hoặc cho phép kế thừa có chọn lựa. Kế thừa đầy
đủ có nghĩa là một lớp kế thừa đầy đủ tất cả các thuộc tính và
phương thức gây nên xung đột về tên. Kế thừa có chọn lựa cho
phép một lớp con không kế thừa một số thuộc tính và phương
thức từ lớp cha. Mặc dù kế thừa có chọn lựa có một số thuận
lợi hơn, nhưng hầu hết các hệ thống chấp nhận kế thừa đầy đủ
vì kế thừa có chọn lựa có sự khó khăn là phải lưu vết kế thừa.
Hướng thứ hai là cho phép kế thừa các thuộc tính cùng tên
nhưng khác đặc tả, cụ thể là đặc tả về kiểu.
• Vấn đề thứ ba là vi phạm nguyên tắc đóng gói. Nếu người
dùng có thể truy nhập trực tiếp đến các thuộc tính của một lớp
cha từ một lớp con như các phép toán đổi tên hoặc xóa một
thuộc tính thì có thể làm mất hiệu lực xác định trong lớp con

mà chúng tham chiếu đến các thuộc tính đó. Một hướng khắc
phục là giới hạn việc truy vập đối với các thuộc tính của một
lớp thông qua các phương thức xác định chúng.
Tóm lại, một lược đồ CSDL hướng đối tượng có thể được mô tả bởi
một đồ thị phân cấp phức hợp lớp, do trên đó ta có thể mô tả phân cấp lớp
cùng với phân cấp phức hợp. Cụ thể mỗi nút của đồ thị là tương ứng với một
lớp (kèm cấu trúc các thuộc tính). Nếu lớp C1 là lớp con của lớp C2 thì sẽ có
một cung đi từ nút C1 đến nút C2 (sử dụng cung nét đậm trên hình vẽ). Ngoài
ra bên trong đồ thị phân cấp này người ta còn biểu diễn mối quan hệ giữa các
lớp. Nếu lớp C1 có thuộc tính mối quan hệ A với kiểu dữ liệu là lớp C2, thì sẽ
có một cung xuất phát từ thuộc tính A và trỏ vào tên lớp C2 (sử dụng cung
nét mỏng). Các thuộc tính đa trị được đánh dấu *. Bằng cách này ta có thể
mô tả trực quan một lược đồ CSDL hướng đối tượng.

11


Chương 2 – Cơ sở lý thuyết

2.3 Truy vấn đối tượng
Cú pháp của khối lệnh trọng tâm select trong OQL là [14]:
select [distinct]

<Danh sách kết quả>

from

<Danh sách lớp/ sưu tập lớp>

where


<Biểu thức điều kiện>

[group by

<Các thuộc tính phân nhóm>]

[having

<Điều kiện lọc>]

[order by

(<Khóa sắp xếp> asc|desc,…)]

Trong đó, từ khóa distinct nếu sử dụng thì kết quả của truy vấn có
kiểu tập đối tượng. Mệnh đề group by phân nhóm trên lớp sưu tập, các đối
tượng được nhóm theo giá trị của các thuộc tính phân nhóm. Mỗi cấu trúc
của nhóm chứa một nhóm các thuộc tính và nhóm các đối tượng có cùng giá
trị. Mệnh đề order by sắp thứ tự các đối tượng trong lớp sưu tập kết quả.
Sử dụng lược đồ CSDL VienDH được biểu diễn trong hình 2.1 minh
họa cho các ví dụ về các dạng thức biểu diễn của truy vấn OQL:

Hình 2.1. Biểu diễn lược đồ VienDH bằng ký pháp UML

12


Chương 2 – Cơ sở lý thuyết


Người ta sử dụng tên của đối tượng kết hợp với tên các đặc trưng của
đối tượng (thuộc tính, mối quan hệ và các phép toán) để truy nhập vào các
thành phần của một đối tượng hoặc các đặc tính liên quan đến nó.
Đối tượng và tên các đặc trưng được đặt trong đường dẫn. Các bước
trong đường dẫn được ngăn cách bằng dấu chấm ‘.’ Hoặc dấu mũi tên ‘→’.
Dấu chấm và dấu mũi tên có thể được dùng thay cho nhau, nhưng người ta
quy ước dùng dấu chấm là ký hiệu đường dẫn từ một đối tượng đến các đặc
trưng của nó, còn dấu mũi tên là ký hiệu đường dẫn từ một đối tượng này có
mối quan hệ với một đối tượng khác.
Ví dụ 2.1. select s.hoten
from s
where s.DaiHoc.truong_khoa.hoten = ‘Thanh’
Cấu trúc như s.DaiHoc.truong_khoa.hoten gọi là biểu thức đường dẫn.
2.4 Ngôn ngữ đối tượng OQL
OQL (Object Query Language) là ngôn ngữ truy vấn CSDL hướng
đối tượng đã đề xuất trong ODMG-93. Phiên bản cuối cùng của OQL trong
ODMG 93 (Release 1.2) là siêu tập của SQL92, được mô tả như là một phần
của ODMG chuẩn, OQL là ngôn ngữ truy vấn không đưa ra môi trường lập
trình đầy đủ, chẳng hạn như OQL không thể biểu diễn cho tất cả các tính
toán phức tạp. Do đó, nó không phải là hệ tính toán đầy đủ. Vì vậy, để tăng
khả năng tính toán cho OQL cần thiết phải liên kết với các ngôn ngữ lập
trình khác:
(i)

OQL được dùng để mô tả truy vấn và các thao tác của đối
tượng;

(ii)

Ngôn ngữ định nghĩa đối tượng (ODL): sử dụng mã OQL để

định nghĩa giao diện với các kiểu đối tượng;

(iii)

Các ngôn ngữ lập trình khác như C++, Smalltalk và Java được
dùng để cài đặt các phương thức và các chương trình ứng dụng.

13


Chương 2 – Cơ sở lý thuyết

Đồng thời có thể nhúng các câu lệnh OQL trong các thao tác
trên CSDL đối tượng.
Trong (iii) OQL được dùng như ngôn ngữ truy vấn nhúng, nó cũng có
thể được sử dụng như một ngôn ngữ truy vấn độc lập, nghĩa là người dùng có
thể biểu diễn các thao tác CSDL đối tượng hoàn toàn bằng OQL mà không
cần một chương trình nhúng nào được viết bằng ngôn ngữ lập trình khác.
OQL được thiết kế theo hướng phát triển kế thừa, đó là thiết kế một
ngôn ngữ mới đầy đủ dựa trên SQL, ngôn ngữ chuẩn của CSDL quan hệ.
Thiết kế của OQL ở dạng hàm, kết quả của truy vấn có kiểu, điều này cho
phép kết quả của truy vấn này là đầu vào của một truy vấn khác, vì vậy các
truy vấn phức tạp có thể được xây dựng bằng OQL Bằng cách tích hợp các
tính năng của SQL, OQL xây dựng trên nền tảng của CSDL quan hệ. Mục
đích của mô hình ODMG là duy trì một mức độ tương thích giữa kỹ thuật
CSDL hướng đối tượng và kỹ thuật CSDL đối tượng – quan hệ bằng cách
tích hợp các tính năng của phiên bản tương lai của SQL trong phiên bản
tương lai của OQL.
2.4.1 Kiểu và lược đồ suy dẫn kiểu trong ngôn ngữ truy vấn OQL
Hệ thống các kiểu dữ liệu nguyên thủy và các kiểu dữ liệu suy dẫn

gắn với phân cấp kiểu được giới thiệu trong hình 2.2. Trên cây phân cấp, ta
nhận thấy rằng các kiểu tổng quát là các nút nằm ở nút nhánh trên cây, các
kiểu này sẽ không được sử dụng trong các lược đồ CSDL (khai báo hình
thức). Kiểu được gọi là kiểu đặc trưng, nếu nó được suy dẫn từ các kiểu cơ
sở. Tất cả các nút lá trong hình 2.2 là các kiểu đặc trưng.

14


Chương 2 – Cơ sở lý thuyết

Hình 2.2. Sự phân cấp các kiểu trong OQL
2.4.2 Thuộc tính và lượng từ
Biểu thức logic trong OQL thực hiện việc kiểm tra trên các thành viên
của một lớp sưu tập. Các phép toán kiểm tra được sử dụng trong biểu thức
logic là:
(i)

forall - kiểm tra với một điều kiện đúng (true) cho tất cả các
đối tượng chứa trong lớp sưu tập.

(ii)

exists – kiểm tra sự tồn tại của một đối tượng trong lớp sưu tập
thỏa mãn một điều kiện cho trước.

(iii)

unique – kiểm tra tính duy nhất của các đối tượng trong lớp
sưu tập.


(iv)

in – kiểm tra một đối tượng có thuộc về một lớp sưu tập hay
không.

15


Chương 2 – Cơ sở lý thuyết

(v)

Some, any và all - đây là những lượng từ được dùng để so
sánh sự ít nhất (some hay any) hay với mọi (all) cho các đối
tượng thuộc (in) trong một lớp sưu tập.

(vi)

Set inclusion – các phép toán so sánh bao hàm {<, <=, >, >=}
áp dụng với các lớp sưu tập để kiểm tra sự bao hàm của một
lớp sưu tập này và lớp kia.

Cú pháp của truy vấn có lượng từ forall, exists và in là:
<Truy vấn>::=forall <Truy vấn> in <Truy vấn>:<Truy vấn>
|exists <Tên> in <Truy vấn>:<Truy vấn>
|exists|unique (<Truy vấn>)
|<Truy vấn><Phép toán so sánh>[some | any |
all]<Truy vấn>
Ví dụ 2.2 Truy vấn sử dụng toán tử in và lượng từ exists

select f.hoten
from Khoa as f
where exists ‘Am nhac’ in f.so_thich
Trong biểu thức đường dẫn có thể dùng nhiều hơn một lượng từ với
sự kết hợp giữa exists và forall.
Ví dụ 2.3 select s.hoten
from Khoa as f
where exists f.gv_hd in (forall KhoaHoc.DaiHoc.ten_nganh =
‘cong nghe thong tin’)
2.4.3 Biến tham chiếu
Biến vùng mô tả cho một biểu thức đường dẫn có thuộc tính cuối
cùng là một thuộc tính phức được gọi là biến tham chiếu. Người ta sử dụng
các biến vùng biểu diễn cho các đối tượng của lớp trong một biểu thức
đường dẫn.

16