1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM THỊ CHANH
TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ
LIỆU HƢỚNG ĐỐI TƢỢNG
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI – 2014.
2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM THỊ CHANH
TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ
LIỆU HƢỚNG ĐỐI TƢỢNG
Ngành: CÔNG NGHỆ THÔNG TIN
Chuyên ngành : HỆ THỐNG THÔNG TIN
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC : PGS. TS. ĐOÀN VĂN BAN
HÀ NỘI – 2014
3
LỜI CAM ĐOAN
Tôi xin cam đoan, kết quả của luận vă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
đủ.
Tác giả
Phạm Thị Chanh
4
LỜI CẢM ƠN
Lời đầu tiên của luận văn em xin gửi lời cảm ơn chân thành nhất đến PGS.TS
Đoàn Văn Ban, ngƣời đã trực tiếp hƣớng dẫn, giúp đỡ và tạo mọi điều kiện thuận lợi
cho em từ lúc tìm hiểu, định hƣớng cũng nhƣ tìm kiếm tài liệu trong lĩnh vực cơ sở
dữ liệu hƣớng đối tƣợng cho đến lúc hoàn thành luận văn.
Em xin gửi lời cám ơn sâu sắc đến tất cả các thầy cô giáo đã dạy dỗ và truyền
đạt những kinh nghiệm quý báu cho chúng em trong suốt hai năm cao học ở trƣờng
Đại học Công nghệ - Đại học Quốc gia Hà nội.
Cuối cùng, em xin biểu thị sự biết ơn tới những ngƣời thân trong gia đình và
bạn bè đã ƣu ái, giúp đỡ, động viên, khích lệ để em hoàn thành luận văn này.
Hà nội, ngày ….., tháng ….., năm 2014
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
CÁC KÝ HIỆU
Ký hiệu
STT
Diễn giải
1
Att (Attribute)
Thuộc tính
2
R
Tập thuộc tính trong mệnh đề Select
3
E
Siêu cạnh
4
Oid
OID của đối tƣợng
5
O (Object)
Tập các đối tƣợng
6
V (Value)
Giá trị
7
D
Tập các đối tƣợng
8
H (HyperGraph)
Siêu đồ thị
9
Mid (Method Identify)
Định danh phƣơng thức
10
Odb (Object database)
Cơ sở dữ liệu đối tƣợng
11
Dom (Domain)
Miền trị
12
Obj (Object)
Đối tƣợng
13
Val (Value)
Giá trị
14
Sup (Super)
Siêu lớp/ lớp cha
15
Meth (Method)
Phƣơng thức
16
Attrs (Attributes)
Tập thuộc tính
CÁC CHỮ VIẾT TẮT
Ký hiệu
STT
Diễn giải
1
CSDL
Cơ sở dữ liệu
2
OID (Object Identifier)
Định danh đối tƣợng
3
UML (Unified Modeling Language)
Ngôn ngữ mô hình hợp nhất
4
ODMG
(Object Database Management Group)
Nhóm quản trị CSDL đối tƣợng
5
ODL(Object Definition Language)
Ngôn ngữ định nghĩa đối tƣợng
6
OQL (Object Query Language)
Ngôn ngữ truy vấn đối tƣợng
7
OODB(Object-Oriented Database)
CSDL Hƣớng đối tƣợng
8
OODBMS (Object-Oriented Database Hệ quản trị CSDL Hƣớng đối tƣợng
Management System)
9
ADTs (Abtract Data Types)
Tập kiểu dữ liệu trừu tƣợng
10
SFW (Select...From...Where)
Khối lệnh trọng tâm của ngôn ngữ
truy vấn OQL
6
DANH MỤC CÁC THUẬT NGỮ
Biến thể hiện dựa trên giá trị
Biến thể hiện lớp
Đối tƣợng phức hợp
Value based instance variable
Class instance varSSiable
Composite object
Kiểu đặc trƣng
Kiểu dữ liệu “túi”, đa tập là kiểu sƣu tập
Specific types
Bag
Kiểu tổng quát
General types
Lƣợc đồ đối tƣợng
Mối quan hệ kế thừa
Mối quan hệ kết nhập
Object schemas
Inheritance relationship
Aggregation relationship
Phân cấp lớp
Class hierarchy
Phân cấp lớp hợp thành
Phƣơng thức nạp chồng
Class composition hierarchy
Overloading method
Phƣơng thức thuộc tính - suy dẫn
Siêu lớp
Lớp con
Truy vấn lồng
Mô hình dữ liệu hƣớng đối tƣợng
Thực thể
Derived-attribute method
Metaclass/Superclass
Subclass
Nested query
Object-Oriented Model
Entity
Viết đè
Liên kết muộn
Overriding
Late binding
Thuộc tính đơn
Thuộc tính đơn trị
Thuộc tính đa trị
Thuộc tính phức hợp
Tính đa hình
Tính đóng gói thông tin
Tính kế thừa bội
Single attribute
Single-valued attribute
Multivalued attribute
Composite attribute
Polymorphism
Encapsulation
Multiple inheritance
7
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Sự phát triển của các mô hình dữ liệu ........................................................ 4
Hình 1.2. Mô hình dữ liệu hƣớng đối tƣợng nguyên mẫu .......................................... 6
Hình 1.3. Kế thừa đơn................................................................................................. 14
Hình 1.4. Kế thừa bội từ hai lớp khác nhau và có lớp cơ sở chung ........................... 14
Hình 1.5. Kế thừa bội không có lớp cơ sở chung ....................................................... 15
Hình 1.6. Sự phân cấp các kiểu trong OQL ................................................................ 20
Hình 1.7. Lƣợc đồ CSDL Quản lý Nhân viên ............................................................ 21
Hình 2.1. Siêu đồ thị H ............................................................................................... 28
Hình 2.2. Siêu đồ thị kết nối đối tƣợng của ví dụ 2.1 ................................................. 30
Hình 2.3. Siêu đồ thị kết nối của ví dụ 2.2 ................................................................. 34
Hình 2.4. Siêu đồ thị kết nối của ví dụ 2.3 ................................................................. 35
Hình 2.5. Siêu đồ thị kết nối của ví dụ 2.4. ................................................................ 36
Hình 3.1. Lƣợc đồ CSDL Quản lý Nhân sự ............................................................... 52
Hình 3.2. Form luận văn ............................................................................................. 61
Hình 3.3. Kết quả truy vấn 1 ....................................................................................... 62
Hình 3.4. Kết quả truy vấn 2 ....................................................................................... 63
Hình 3.5. Kết quả truy vấn 3 ....................................................................................... 65
8
DANH MỤC CÁC BẢNG, BIỂU ĐỒ
Bảng 2.1. Kết quả ƣớc lƣợng siêu cạnh của ví dụ 2.3 ................................................ 44
Bảng 2.2. Kết quả ƣớc lƣợng khi áp dụng thuật toán 2.5 Tinh chỉnh siêu đồ thị của ví
dụ 2.3 .......................................................................................................................... 46
Bảng 2.3. Kết quả ƣớc lƣợng siêu cạnh của ví dụ 2.4 ................................................ 46
Bảng 2.4. Kết quả ƣớc lƣợng khi áp dụng thuật toán 2.5 Tinh chỉnh siêu đồ thị của ví
dụ 2.4 .......................................................................................................................... 47
Biều đồ 3.1. So sánh thời gian thực hiện truy vấn 1 ................................................... 62
Biều đồ 3.2. So sánh thời gian thực hiện truy vấn 2 ................................................... 64
Biều đồ 3.3. So sánh thời gian thực hiện truy vấn 3 ................................................... 65
9
LỜI MỞ ĐẦU
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 chiều, dữ liệu có nhiều mối
quan hệ, hay các dữ liệu đa phƣơng tiện nhƣ: hình ảnh, âm thanh, video,…
Ngày nay, phƣơng pháp hƣớng đối tƣợng đƣợc sử dụng rất phổ biến trong lĩnh
vực phát triển phần mềm, vì cho phép lập trình viên tạo ra các đối tƣợng trong code
trừu tƣợng hóa các đối tƣợng thực tế trong cuộc sống. Trong thế giới thực, đối tƣợng
là thực thể tồn tại nhƣ con ngƣời, xe, máy tính,…Trong ngôn ngữ lập trình, đối tƣợng
có thể là màn hình, điều khiển,…Kỹ thuật hƣớng đối tƣợng là kỹ thuật nhằm vào sự
tƣơng tác giữa các đối tƣợng. Mỗi đối tƣợng có những thuộc tính (thông tin lƣu trữ),
những phƣơng thức xác định các chức năng của đối tƣợng và các đối tƣợng chỉ đƣợc
tạo ra và tồn tại trên bộ nhớ chính, còn việc lƣu trữ và tƣơng tác dữ liệu dƣới dạng
các đối tƣợng trên bộ nhớ thứ cấp vẫn chủ yếu kế thừa từ mô hình quan hệ truyền
thống. Hiện đã có rất nhiều kết quả nghiên cứu, cho phép chuyển đổi qua lại giữa các
bảng trong mô hình quan hệ sang tập các đối tƣợng tƣơng ứng. Mặc dù kế thừa đƣợc
tính năng mạnh của hƣớng đối tƣợng, nhƣng việc chuyển đổi qua lại này càng làm
cho mã lệnh của chƣơng trình phức tạp thêm, đồng thời hiệu suất chƣơng trình cũng
giảm đi rõ rệt.
CSDL hƣớng đối tƣợng là giải pháp cho những hạn chế của CSDL quan hệ.
Trong CSDL hƣớng đối tƣợng, dữ liệu đƣợc lƣu trữ dƣới dạng các đối tƣợng của
ngôn ngữ lập trình nên cho phép lƣu trữ đƣợc các dạng dữ liệu phức tạp, lƣợng thông
tin lớn, đa chiều, đa quan hệ, hay có thể mở rộng lƣu trữ các dữ liệu đa phƣơng tiện
nhƣ hình ảnh, âm thanh, video. Trên thế giới, một số hệ quản trị cơ sở dữ liệu hƣớng
đối tƣợng đƣợc phát triển bởi các nhà phân phối sản phẩm thƣơng mại, tại các phòng
10
nghiên cứu công nghệ và các Viện Đại học nhƣ: Gemstone, ObjectStores, IRIS,
Orion, Extra, Oracle, Db4o,… Một mô hình dữ liệu đối tƣợng chuẩn ODMG đã đƣợc
phát triển và dựa vào đó để thiết lập một số khái niệm cơ sở đƣợc gọi là mô hình hạt
nhân cho mô hình CSDL hƣớng đối tƣợng. Mô hình hạt nhân đủ mạnh để thỏa mãn
nhiều đòi hỏi của các ứng dụng mới, hơn nữa còn đƣợc dùng làm cơ sở để xác định
những khác biệt chính giữa mô hình dữ liệu hƣớng đối tƣợng và các mô hình dữ liệu
truyền thống khác. Hệ thống hƣớng đối tƣợng là tập các lớp đối tƣợng có mối quan hệ
với nhau, trao đổi thông tin với nhau để thực hiện những nhiệm vụ đặt ra của bài toán
ứng dụng trong thực tế.
Một trong những hƣớng nghiên cứu quan trọng đƣợc đề cập trong các hệ thống
CSDL 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
11
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].
Với mục tiêu của luận văn nhƣ vậy, bố cục của luận văn gồm: phần mở đầu, ba
chƣơng nội dung và phần kết luận.
Chƣơng 1: Giới thiệu các khái niệm, định nghĩa cơ bản nhƣ: lớp, đối tƣợng,
định danh đối tƣợng trong mô hình CSDL hƣớng đối tƣợng; kế đến, trình bày sự mở
rộng ngữ nghĩa của mô hình nhƣ hệ thống phân cấp và quan hệ kế thừa. Tìm hiểu kỹ
thuật xử lý truy vấn và các thay đổi so với kỹ thuật xử lý truy vấn quan hệ. Để thực
hiện đƣợc các câu truy vấn đối tƣợng một cách hiệu quả và tiếp tục nghiên cứu các
vấn đề về tối ƣu hoá truy vấn trong các CSDL hƣớng đối tƣợng, ngôn ngữ truy vấn
OQL là ngôn ngữ truy vấn đƣợc chọn giới thiệu trong chƣơng này.
Chƣơng 2: Trình bày khái niệm siêu đồ thị kết nối đối tƣợng. Sau đó sử dụng ký
pháp siêu đồ thị để biểu diễn truy vấn OQL. Xây dựng giải thuật khởi tạo siêu đồ thị
trong các trƣờng hợp truy vấn đối tƣợng đơn và lồng. Đƣa ra giải thuật ƣớc lƣợng
siêu cạnh cho các trƣờng hợp tách biệt hay liên thông của các siêu đồ thị con hợp
thành siêu đồ thị mà biểu diễn cho một truy vấn đối tƣợng lồng. Cuối chƣơng, là mở
rộng thuật toán tối ƣu hóa truy vấn trên cơ sở xây dựng danh sách các bƣớc thực thi
câu truy vấn theo quy tắc có thứ tự loại bỏ siêu cạnh.
Chƣơng 3: Giới thiệu về hệ quản trị CSDL đối tƣợng DB4O. Phát biểu bài toán
quản lý nhân sự trong công ty, đó là bài toán đƣợc áp dụng trong các ví dụ cho thuật
toán tối ƣu hóa truy vấn. Đƣa ra kết quả thực nghiệm cho bài toán tối ƣu hóa truy vấn
CSDL hƣớng đối tƣợng dựa trên siêu đồ thị. Cuối cùng là kết luận và hƣớng phát
triển của đề tài.
Nội dung cơ bản của luận văn đã đƣợc trình bày, thảo luận tại xêmina khoa học
ở Bộ môn Hệ thống thông tin, khoa Công nghệ Thông tin, trƣờng Đại học Công nghệ
- Đại học Quốc gia Hà nội.
12
Chƣơng 1
MÔ HÌNH CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG
1.1. Tổng quan về hệ thống dữ liệu hƣớng đối tƣợng
1.1.1. Mô hình dữ liệu
Các hệ thống quản trị cơ sở dữ liệu (CSDL) đầu tiên xuất hiện trƣớc những năm
1970. Những hệ thống này đƣợc phát triển từ hệ thống các tệp tin (File Systems) để
hỗ trợ cho việc lƣu trữ và xử lý số lƣợng lớn các dữ liệu. Tuy nhiên, các nhà nghiên
cứu trong lĩnh vực CSDL nhận thấy giá trị của dữ liệu cần đƣợc lƣu trữ để xử lý, và
các mô hình dựa trên dữ liệu cần đƣợc nghiên cứu để cải thiện độ tin cậy, đảm bảo an
ninh, an toàn dữ liệu và nâng cao hiệu quả của việc truy cập vào hệ thống.
Mô hình dữ liệu cung cấp cách thức tổ chức các dữ liệu đƣợc lƣu trữ theo cấu
trúc đặc biệt hoặc theo các mối quan hệ sao cho việc truy cập và quản lý nhanh
chóng, hiệu quả. Nhiều mô hình CSDL nhƣ mô hình phân cấp (Hierarchical model),
mô hình mạng (Network model), mô hình quan hệ (Relational model), mô hình
hƣớng đối tƣợng (Object-Oriented model) nhƣ Hình 1.1 đã xuất hiện và đóng vai trò
quan trọng trong việc nghiên cứu phát triển các hệ thống quản trị CSDL (DataBase
Management System).
File Systems
Hierarchical
Network
Relational
Object-Oriented
System
Semantic Data
Model (ERD)
Complex Object
Model
Object-Oriented Databases
Hình 1.1. Sự phát triển của các mô hình dữ liệu [1]
1.1.2. Những hạn chế của cơ sở dữ liệu quan hệ
Mô hình CSDL quan hệ truyền thống đƣợc sử dụng nhiều nhƣng chƣa đáp ứng
đƣợc hết các yêu cầu của thực tế. Mô hình quan hệ chỉ phù hợp cho những bài toán có
bộ dữ liệu nhỏ và không đáp ứng đƣợc cho những bài toán ở lĩnh vực ứng dụng mới,
nhiều kiểu dữ liệu phức tạp. Ví dụ, khi cần lƣu trữ và xử lý một số lƣợng lớn dữ liệu,
dữ liệu hình ảnh, âm thanh hay video, … thì việc sử dụng mô hình quan hệ sẽ không
đạt hiệu quả. Nhƣng đa phần những ứng dụng mới hiện nay đòi hỏi hệ thống cơ sở dữ
13
liệu phải xử lý đƣợc các tính năng nhƣ: các kiểu dữ liệu phức tạp, đóng gói dữ liệu
(Data Encapsulation) và cấu trúc dữ liệu trừu tƣợng, cùng với những phƣơng pháp
mới để lập chỉ mục và truy vấn thông tin. Phần lớn các hệ quản trị CSDL phổ biến
hiện nay trên thị trƣờng là các hệ quản trị dữ liệu theo mô hình quan hệ. Tuy nhiên,
các hệ quản trị CSDL quan hệ có những hạn chế nhƣ sau [13,19]:
Hạn chế trong vấn đề biểu diễn thế giới thực (Real world): Các quan hệ
(relations) không đủ mạnh để thể hiện các thực thể (entities) trong thế giới thực. Rất
khó để mà biểu diễn đƣợc mối quan hệ kế thừa, mối quan hệ thành viên (IS-A
relationships). Ví dụ nhân viên là một ngƣời, trong ví dụ này, hệ quản trị CSDL quan
hệ phải định nghĩa 2 bảng là bảng Nguoi và bảng NhanVien, trong đó bảng NhanVien
nhận đƣợc những thông tin từ lớp cha (superclass) Nguoi để kết nối lại.
Hạn chế về nạp chồng ngữ nghĩa (Semantic overloading): Thành phần chuẩn
trong mô hình quan hệ là quan hệ (relation) không đủ mạnh để biểu diễn cho dữ liệu
và các mối quan hệ phức tạp của dữ liệu. Nó thƣờng phải chia một đối tƣợng thành
một số các quan hệ (bảng) và truy vấn tin thì phải thực hiện các phép: chiếu, chọn và
kết nối để tái cấu trúc các đối tƣợng đó.
Chỉ biểu diễn những dữ liệu thuần nhất: Những hạn chế về kiểu dữ liệu trong
mô hình quan hệ làm nó không thể biểu diễn đƣợc các đối tƣợng trong thế giới thực.
Một mục (item) bất kỳ trong một bộ dữ liệu (tuple) thực chất là phần giao nhau của
hàng với cột, nó phải là dữ liệu của một kiểu dữ liệu nguyên tố, bởi vì theo giả thuyết,
cả chiều ngang và chiều dọc đều phải có kiểu thuần nhất.
Hệ thống khép kín: Những lĩnh vực ứng dụng còn tồn tại không thể bổ sung
đƣợc vào hệ thống sau khi phát triển hệ quản trị CSDL, nhƣ không thể bổ sung các
kiểu dữ liệu mới vào hệ thống. Nhƣng thực tế đòi hỏi các hệ quản trị CSDL phải hỗ
trợ để xử lý những kiểu dữ liệu mới nhƣ kiểu hình ảnh (images), video, audio, …
Giới hạn các phép toán: Mô hình quan hệ có một tập cố định các phép toán
trong SQL. Ngoài ra, không cho phép mở rộng hay bổ sung thêm những phép toán
mới.
Khó thực hiện truy vấn đệ qui: Các câu truy vấn đệ qui cực kỳ khó đặc tả và cài
đặt trong mô hình quan hệ. Đây cũng chính là điểm yếu làm cho SQL không thực
hiện đƣợc đầy đủ trong tính toán.
Những trở ngại trong đối sánh: Mô hình quan hệ sử dụng những mô thức lập
trình hỗn hợp khác nhau, trong đó cho phép các dữ liệu với kiểu khác nhau và nhiều
vị trí khác nhau có thể đƣợc xử lý trong cùng một thời điểm.
1.1.3. Mô hình dữ liệu hƣớng đối tƣợng
Trong số các mô hình dữ liệu hiện nay, mô hình dữ liệu đối tƣợng là mô hình
đảm bảo tính mềm dẻo, tính linh hoạt, và tính “mở” của hệ thống. Mô hình dữ liệu
14
hƣớng đối tƣợng đang đƣợc phát triển một cách phổ dụng trong lĩnh vực phát triển
CSDL. Đƣợc xây dựng theo cách tiếp cận hƣớng đối tƣợng nhằm khắc phục những
hạn chế của những mô hình dữ liệu truyền thống. Mô hình dữ liệu hƣớng đối tƣợng
có các đặc trƣng cơ bản sau [6, 13]:
- Thông tin đƣợc biểu diễn thành các đối tƣợng giống nhƣ các đối tƣợng trong lập
trình hƣớng đối tƣợng. Lớp bao gồm các thông tin:
+ Dữ liệu thuộc tính mô tả các đặc trƣng của các thực thể (đối tƣợng)
+ Các phƣơng thức mô tả hành vi ứng xử của đối tƣợng
-
+ Mối quan hệ giữa các lớp với nhau.
Mỗi đối tƣợng (thực thể) có một định danh ID để xác định duy nhất trong hệ
-
CSDL.
Các CSDL hƣớng đối tƣợng đƣợc thiết kế để làm việc tốt đối với những ngôn
ngữ lập trình hƣớng đối tƣợng nhƣ: Java, C++, C#, Smalltalk,….
Mục đích của CSDL hƣớng đối tƣợng là để quản trị hiệu quả những kiểu dữ liệu
phức hợp, dữ liệu đa phƣơng tiện nhƣ âm thanh, hình ảnh, ... , nhằm khắc phục những
hạn chế của CSDL quan hệ. Hình vẽ sau đây giới thiệu về mô hình dữ liệu hƣớng đối
tƣợng nguyên mẫu.
Hệ thống CSDL
truyền thống
- Sự bền vững
- Tính chia sẻ
- Các giao dịch
- Kiểm soát trùng lặp
- Kiểm soát phục hồi
- Tính bảo mật
- Tính toàn vẹn
- Truy vấn
Ngữ nghĩa mô
hình dữ liệu
- Sự tổng quát hoá
- Sự kết nhập
Lập trình hướng đối
tượng
- Nhận dạng đối tƣợng
- Sự đóng gói
- Sự kế thừa
- Kiểu và các lớp
- Phƣơng thức
- Đối tƣợng phức
- Tính đa hình thái
- Tính mở
Các chức năng đặc
biệt
- Phiên bản
- Sự tiến hoá lƣợc đồ
MÔ HÌNH DỮ LIỆU
HƢỚNG ĐỐI TƢỢNG
Hình 1.2. Mô hình dữ liệu hướng đối tượng nguyên mẫu [13]
Trên cơ sở kế thừa và phát triển các điểm mạnh của CSDL quan hệ thì CSDL
đối tƣợng đã bổ sung các tính chất mà CSDL quan hệ vẫn còn thiếu sót. Cũng nhƣ hệ
thống CSDL truyền thống, hệ thống CSDL hƣớng đối tƣợng có tính bền vững, tính
chia sẻ dữ liệu, tính bảo mật, tính toàn vẹn và truy vấn dữ liệu. Ngoài ra, CSDL
hƣớng đối tƣợng còn có những ƣu điểm khác nhƣ [13]:
15
Hỗ trợ những kiểu dữ liệu được định nghĩa bởi người sử dụng: CSDL hƣớng
đối tƣợng có khả năng lƣu trữ các kiểu phức hợp, kiểu đƣợc định nghĩa bởi ngƣời sử
dụng, cho phép thao tác trong kiểu dữ liệu một cách dễ dàng.
Cải tiến đáng kể về chất lượng dữ liệu: Ta có thể đƣa ra nhiều ràng buộc vào
cấu trúc dữ liệu. Mô hình còn cho phép thể hiện đƣợc cả những ràng buộc không có
cấu trúc mà chƣơng trình phải thoả mãn khi nó thực hiện trong hệ CSDL. Một CSDL
quan hệ đƣợc chuẩn hóa có thể xem nhƣ một trƣờng hợp đặc biệt của CSDL hƣớng
đối tƣợng.
Tốc độ phát triển phần mềm nhanh hơn: Cấu trúc CSDL nhất quán và rõ ràng
giúp cho lập trình ứng dụng trở nên đơn giản và nhanh hơn. Những ngƣời phát triển
ứng dụng có kinh nghiệm thƣờng sử dụng những câu lệnh rất mạnh của các hệ quản
trị CSDL thay cho những đoạn chƣơng trình của ngƣời sử dụng.
Tích hợp dữ liệu dễ dàng và tiện lợi: Việc tích hợp nhiều hệ thống độc lập có
thể làm giảm bớt sự sao chép dữ liệu của con ngƣời và mở rộng những câu truy vấn
có thể trả lời đƣợc. Mô hình hƣớng đối tƣợng cung cấp cách biểu diễn thống nhất làm
thuận tiện hơn cho việc tìm hiểu và tích hợp thông tin.
Không cần các khóa chính (Primary Keys): ngƣời sử dụng hệ quản trị CSDL
quan hệ thƣờng phải lo lắng về tính duy nhất để phân biệt các bộ dữ liệu và đảm bảo
rằng không có hai bộ dữ liệu có cùng giá trị của khóa chính để tránh xảy ra xung đột.
Nhƣng trong một hệ quản trị CSDL hƣớng đối tƣợng, việc xác định duy nhất của các
đối tƣợng đƣợc thực hiện bởi định danh đối tƣợng (OID) và ngƣời sử dụng không cần
phải quan tâm về chúng.
Một mô hình dữ liệu thống nhất: Một mô hình dữ liệu thông thƣờng phải mô
hình hóa các thực thể, các mối quan hệ, các ràng buộc và các hoạt động thay đổi trạng
thái của dữ liệu trong hệ thống. Với hệ quản trị CSDL quan hệ ta không thể mô hình
đƣợc các hoạt động và không đƣa ra đƣợc những quy tắc để làm thay đổi trạng thái
của dữ liệu trong hệ thống, bởi vì điều này vƣợt quá phạm vi của cơ sở dữ liệu. Vì
vậy, các ứng dụng sử dụng hệ thống CSDL quan hệ thƣờng sử dụng một sơ đồ quan
hệ - thực thể để mô hình các bộ phận tĩnh của hệ thống và một mô hình riêng biệt cho
các hoạt động và hành vi của các thực thể trong ứng dụng. Với hệ quản trị CSDL
hƣớng đối tƣợng, không có sự tách biệt giữa các mô hình dữ liệu và mô hình ứng
dụng để mô tả đầy đủ các đặc trƣng, tính chất tĩnh cũng nhƣ hành vi ứng xử động của
các đối tƣợng. Toàn bộ ứng dụng nhƣ vậy có thể đƣợc mô hình đầy đủ trong các biểu
đồ UML.
1.2. Các khái niệm cơ sở
1.2.1. Đối tƣợng, Định danh đối tƣợng và Lớp đối tƣợng
Đối tƣợng (Object)
16
Đối tƣợng là một khái niệm cơ sở quan trọng nhất của cách tiếp cận hƣớng đối
tƣợng. Đối tƣợng là thực thể của hệ thống, của CSDL chỉ một ngƣời, một địa điểm
hay một vật nào đó tồn tại trong thế giới thực. Một thực thể bất kỳ trong thế giới thực
là một đối tƣợng. Đối tƣợng trong thế giới thực đƣợc xác định duy nhất, chứa một
tập nhất định các thông tin về đối tƣợng và các hành vi dựa trên các thông tin đó.
Một đối tƣợng cũng có thể có các mối quan hệ hay có khả năng trao đổi thông tin với
các đối tƣợng khác.
Ví dụ: Một đối tƣợng Nhân viên là một ngƣời đang làm việc cho một công ty
hay doanh nghiệp nào đó, đƣợc xác định duy nhất trong thế giới thực, chứa một tập
nhất định các thông tin về Nhân viên đó nhƣ: mã nhân viên, họ tên, ngày sinh, nơi
sinh, lƣơng, dự án mà nhân viên đang tham gia,…Một đối tƣợng Nhân viên có thể có
các quan hệ với các đối tƣợng khác, nhƣ quan hệ với đối tƣợng Phòng ban hay đối
tƣợng Dự án mà nhân viên đó đang tham gia làm việc.
Trong CSDL hƣớng đối tƣợng, các đối tƣợng trong thế giới thực đƣợc mô hình
hóa, biểu diễn vào CSDL theo các đặc trƣng của đối tƣợng và luôn duy trì sự tƣơng
ứng trực tiếp giữa các đối tƣợng trong CSDL với các đối tƣợng trong thế giới thực.
Định danh đối tƣợng (OID: Object Identity)
Một đối tƣợng đƣợc xác định duy nhất trong thế giới thực, và do đó cũng phải
đƣợc biểu diễn duy nhất trong CSDL. Việc xác định duy nhất đối tƣợng trong CSDL
đƣợc thực hiện bằng cách sử dụng các Định danh đối tƣợng (Object Identity) hay
OID. Hệ thống CSDL hƣớng đối tƣợng cung cấp một định danh duy nhất cho mỗi
đối tƣợng và đƣợc lƣu trữ trong CSDL. Định danh duy nhất này do hệ thống tự động
tạo ra và đƣợc gọi là định danh đối tƣợng. Giá trị OID ngƣời dùng không nhìn thấy
đƣợc, nó đƣợc sử dụng bên trong hệ thống để xác định duy nhất một đối tƣợng và
dùng để tạo ra các tham chiếu bên trong đối tƣợng. OID của mỗi đối tƣợng phải thỏa
mãn hai tính chất sau:
1. Giá trị OID của một đối tƣợng không đƣợc thay đổi trong CSDL hƣớng đối
tƣợng. Điều này đảm bảo tính duy nhất của mỗi đối tƣợng. Do đó, một hệ thống
CSDL hƣớng đối tƣợng phải có cơ chế tạo ra các OID và đảm bảo tính bất biến.
2. Mỗi giá trị OID chỉ đƣợc sử dụng duy nhất một lần; nghĩa là khi một đối
tƣợng bị xóa đi từ CSDL thì OID của nó cũng không đƣợc gán cho đối tƣợng bất kỳ
nào khác.
Định danh đối tƣợng OID khác với khóa chính của đối tƣợng. Khóa chính của
đối tƣợng là một thuộc tính của đối tƣợng, đƣợc ngƣời dùng gán giá trị và có thể
nhìn thấy, thay đổi đƣợc và có thể đƣợc cấp lại, còn OID thì không.
Ví dụ: Một Nhân viên đƣợc biểu diễn trong CSDL có một OID duy nhất, xác
định sự tƣơng ứng Nhân viên đó trong thế giới thực. Một Nhân viên khác trong thế
17
giới thực nếu đƣợc biểu diễn trong CSDL thì phải có một OID khác với OID của
Nhân viên trên, thậm trí cả khi Nhân viên trên bị xóa khỏi hệ thống. Điều này đảm
bảo sự tƣơng ứng của CSDL với thế giới thực, tránh sự nhầm lẫn về các đối tƣợng
đƣợc biểu diễn trong CSDL.
Lớp đối tƣợng (Class)
Đối tƣợng là thể hiện, là đại diện 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ử, có cùng mối liên quan với các đối tƣợng của các lớp khác và có chung ngữ nghĩa
trong hệ thống. Trong các mô hình và các ngôn ngữ lập trình hƣớng đối tƣợng, lớp
thƣờng đƣợc mô tả bằng từ khóa Class. Ví dụ trong lƣợc đồ quản lý nhân viên ta có
các lớp: NhanVien, PhongBan, DuAn …Trong đó, lớp Nhân viên mô tả cấu trúc
chung của các đối tƣợng Nhân viên, đƣợc khai báo nhƣ sau:
Class NhanVien
{
Private:
// khai báo các thuộc tính của đối tượng
int manso;
string hoten;
datetime ngaysinh;
string diachi;
double luong;
Public:
// khai báo các hành vi của đối tượng
Void Thongtin_nhanvien();
Float Tinhluong();
}
1.2.2. Thuộc tính và phƣơng thức
Thuộc tính (Attribute)
Thuộc tính để miêu tả những đặc điểm của đối tƣợng. Việc khai báo các thuộc
tính thể hiện cấu trúc của lớp đƣợc khai báo. Mỗi thuộc tính có một tên duy nhất trong
đối tƣợng và giá trị đƣợc biểu diễn trong miền giá trị của một kiểu dữ liệu nào đó. Các
kiểu dữ liệu này có thể là các kiểu dữ liệu cơ bản nhƣ: kiểu số nguyên, số thực, kiểu
xâu ký tự…, hoặc các kiểu phức tạp do ngƣời dùng định nghĩa, các kiểu đối tƣợng
hoặc cũng có thể là các con trỏ hay vector đến các kiểu dữ liệu đó.
Thuộc tính có thể là thuộc tính đơn trị hoặc thuộc tính đa trị, thuộc tính đa trị
đƣợc khai báo bởi từ khóa set. Ngoài ra một thuộc tính có thể là thuộc tính phức hợp,
đƣợc xác định từ tập các thuộc tính khác (sử dụng từ khóa tuple để khai báo).
Ví dụ 1.1. Khai báo về các thuộc tính có trong lớp QuanLy
18
Class NhanSu
Type tuple ( maso: string[20];
hoten: string[20];
gioitinh: string[10];
diachi: string[20];
ngaysinh: tuple (ngay: integer;
thang: integer;
nam: integer;)
sonamcongtac: integer;
luongcoban: double)
Class QuanLy inherits NhanSu
Type tuple ( chucvu: string;
phong: PhongBan;
duan: set( DuAn))
Trong ví dụ trên các thuộc tính hoten, giới tính, diachi… là các thuộc tính đơn
trị, thuộc tính ngaysinh là thuộc tính phức hợp. Còn thuộc tính duan là thuộc tính đa
trị, với ngữ nghĩa rằng mỗi đối tƣợng thuộc lớp QuanLy có thể tham gia vào nhiều
dự án khác nhau; nghĩa là mỗi đối tƣợng thuộc lớp QuanLy cho tƣơng ứng một tập
các giá trị OID của các đối tƣợng thuộc lớp DuAn.
Phƣơng thức (Method)
Phƣơng thức của một lớp thƣờng đƣợc dùng để mô tả các hành vi của đối tƣợng
(hoặc của lớp). Ví dụ nhƣ đối tƣợng thuộc lớp điện thoại có các hành vi sau: Đổ
chuông, chuyển tín hiệu từ sóng sang dạng nghe đƣợc, chuyển tín hiệu giọng nói
sang dạng chuẩn, chuyển tín hiệu lên tổng đài.v.v. Khi thiết kế, ngƣời ta có thể dùng
các phƣơng thức để mô tả và thực hiện các hành vi của đối tƣợng. Mỗi phƣơng thức
thƣờng đƣợc định nghĩa là một hàm, các thao tác để thực hiện hành vi đó đƣợc viết
tại nội dung của hàm. Khi thực hiện hành vi này, đối tƣợng có thể phải thực hiện các
hành vi khác. Ví dụ nhƣ điện thoại phải chuyển tín hiệu giọng nói sang dạng chuẩn
trƣớc khi chuyển lên tổng đài. Cho nên một phƣơng thức trong một lớp có thể sử
dụng phƣơng thức khác trong quá trình thực hiện hành vi của mình.
1.2.3. Các kiểu dữ liệu
Các khái niệm sau đây đƣợc sử dụng trong hầu hết các hệ CSDL hƣớng đối
tƣợng, chẳng hạn nhƣ Gemstone, Orion, Ontos, O2, ObjectStore, ODMG. Để thuận
tiện trong trình bày, chúng ta sử dụng một số ký hiệu sau [4, 6, 21]:
T – tập hữu hạn các kiểu
L – tập các kiểu nguyên thuỷ nhƣ: byte, int, long, float, double, char, string và
boolean.
19
Att – tập tất cả thuộc tính của các đối tƣợng trong hệ thống
O – tập tất cả đối tƣợng và các đại lƣợng trong một CSDL.
Class – tập các tên lớp
Tập Dom các giá trị nguyên thuỷ là hợp của tất cả các miền giá trị cơ sở của
ngôn ngữ lập trình. Các phần tử của Dom đƣợc gọi là hằng, trong đó nil là một hằng
đặc biệt biểu diễn giá trị không xác định.
Tập Obj = {o1, o2, …} là tập vô hạn các định danh đối tượng (OID) và tập Oid là
tập con các định danh đối tƣợng, Oid Obj. Họ giá trị trên Oid, ký hiệu Val(Oid),
đƣợc xác định nhƣ sau:
(i) Hằng nil Val(Oid)
(ii) Nếu v Dom thì v Val(Oid)
(iii) Nếu o Oid thì o Val(Oid)
(iv) Tập {vi | vi Val(Oid), (i = 1,..., n)} Val(Oid)
(v) Cho tập các giá trị {vi | vi Val(Oid), (i = 1,..., n)} và tập các tên thuộc tính
rời nhau {Ai | Ai, Aj Att, (i j Ai Aj), (i, j = 1, ..., n)} thì bộ [Ai : v1, ..., An : vn]
Val(Oid).
Một đối tƣợng trong hệ thống thƣờng đƣợc mô tả là một cặp (o, v), trong đó o là
định danh đối tƣợng và v là trạng thái hay bộ giá trị hiện thời của đối tƣợng. Các đối
tƣợng cùng tính chất và hành vi đƣợc nhóm lại để tạo thành một lớp. Mỗi lớp C có
một kiểu xác định, ký hiệu là σ(C) - kiểu của các đối tƣợng trong lớp. Thuật ngữ
Class đƣợc sử dụng để mô tả định nghĩa kiểu của lớp các đối tƣợng.
Ví dụ 1.2: Cho lƣợc đồ CSDL hƣớng đối tƣợng sau:
Class NhanVien
Type tuple (hoten: string;
gioitinh: boolean,;
luongCB: double;
phongban: PhongBan)
Class PhongBan
Type tuple (tenphong : string;
truongphong: NhanVien;
SoNV: set (NhanVien ))
Ta tiến hành biểu diễn một số đối tƣợng từ lƣợc đồ CSDL đối tƣợng trên, trong
đó mỗi đối tƣợng là một cặp (o, v). Xét các đối tƣợng
Ob1 = (o1, [hoten: “Nam Phong”, gioitinh: false, luong: 6000000, phong: o5])
Ob2 = (o2, [hoten: “Nguyên Minh”, gioitinh: true, luong: 4000000, phong: o5])
Ob3 =(o3, [hoten: “Trần Hùng”, gioitinh: false, luong: 5000000, phong: o5])
20
Ob4 =(o4, [hoten: “Minh Châu”, gioitinh: true, luong: 3500000, phong: o5])
Ob5 =(o5, [tenphong: “Kinh Doanh”, truongphong: o1, SoNV: {o1, o2, o3, o4}])
Đối tƣợng Ob1 theo định nghĩa trong lƣợc đồ trên sẽ gồm định danh o1 và một
bộ (tuple) các giá trị: [hoten : “Nam Phong”, gioitinh : false, luong : 6000000, phong :
o5]. Đối tƣợng Ob5 có định danh là o5 và một giá trị bộ: [tenphong : “Kinh Doanh”,
truongphong : o1, SoNV : {o1, o2, o3, o4}], trong đó, thuộc tính tenphong có giá trị
nguyên thủy, thuộc tính truongphong tham chiếu đến đối tƣợng có định danh đối
tƣợng là o1, thuộc tính SoNV (số lƣợng nhân viên) có giá trị tập (set) tham chiếu đến
các đối tƣợng với các định danh đối tƣợng o1, o2, o3, o4.
Trong mô hình dữ liệu quan hệ, so sánh bằng của các bộ trong quan hệ luôn dựa
trên các giá trị của bộ, hai bộ bằng nhau nếu tất cả các thuộc tính khoá của hai bộ có
cùng giá trị. Tuy nhiên, trong mô hình CSDL hƣớng đối tƣợng cần phân biệt hai khái
niệm “đồng nhất” và “bằng nhau” của các đối tƣợng nhƣ trong thực tế. Hai quan hệ
này đƣợc định nghĩa nhƣ sau:
Định nghĩa 1.1: Cho hai đối tƣợng S1(o1, v1) và S2(o2, v2).
i. Đối tượng đồng nhất: Hai đối tƣợng S1 và S2 đƣợc gọi là đối tƣợng đồng nhất,
ký hiệu S1 = oidS2 nếu chúng có cùng định danh đối tƣợng, tức là S1.o1 = S2.o2
ii. Đối tượng bằng nhau: Hai đối tƣợng S1 và S2 đƣợc gọi là bằng nhau về giá trị,
ký hiệu S1 = vS2
-
Nếu kiểu của đối tƣợng là nguyên thuỷ thì chúng phải có cùng giá trị
Nếu kiểu của đối tƣợng là kiểu không nguyên thuỷ thì chúng phải có cùng số
các tính chất và với mọi tính chất pi của S1 đều tồn tại tính chất pj của S2 bằng
nhau về giá trị.
Các kiểu dữ liệu
Các kiểu cơ sở bao gồm các kiểu chuẩn trong SQL nhƣ: integer, string, float,
char, double, ….và các kiểu do ngƣời dùng định nghĩa nhƣ lớp hoặc cấu trúc
Các kiểu tập hợp đây là các kiểu đặc trƣng chỉ có ở truy vấn hƣớng đối tƣợng
nhƣ: set, bag, list, array chỉ đến một tập hợp các đối tƣợng.
-
-
Set: Với T là một kiểu bất kỳ, set(T) đƣợc định nghĩa là một kiểu tập hợp gồm
các phần tử phân biệt nhau có kiểu là T. Ví dụ {1, 2, 5, 8, 9} là một thể hiện của
set(integer)
Array: Với T là một kiểu bất kỳ và i có kiểu integer, array là một dãy
gồm i phần tử có kiểu T. Mỗi phần tử đƣợc gắn liền với một chỉ số
Bag: Với T là một kiểu bất kỳ, bag(T) đƣợc định nghĩa nhƣ một kiểu tập hợp
gồm các phần tử thuộc kiểu T. Khác với set, một phần tử trong bag có thể xuất
hiện nhiều hơn một lần và không phân biệt thứ tự giữa chúng. Ví dụ {1, 2, 2, 5}
là một thể hiện của bag(integer).
- Xem thêm -