Download miễn phí 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
Phép kết nối trong ngôn ngữtruy vấn CSDL hướng đối tượng OQL được biểu diễn bằng 3 dạng thức kết nối là kết nối hàm (hay kết nối ẩn dùng ký hiệu “.&rdquo
; kết nối đồng nhất tường minh (các thực thể được so sánh với nhau một cách trực tiếp) và kết nối quan hệ truyền thống là kết nối dựa vào giá trị. Ví dụ2
kết nối hàm) Xét truy vấn tìm tên các khoa của các trường Đại học ởthành phố“Hà Nội”Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Abstract: The basic various of the relational databasesfor data types, the presentation of complex objetcs, class
hierarchy, methods in object-oriented databases which
query processing and the optimizing query become more
difficult. However, one of the methods query processing for
the relational databases can be inheritance and advanced
for the optimizing query in object-oriented databases. In
this paper, we propose a method for estimating the object-
oriented query that extended from the algorithms of Ullman
[7] and Han [3] by connection hypergraphs for the nested
queries.
I. GIỚI THIỆU
Một trong lĩnh vực quan trọng được đề cập trong
CSDL hướng đối tượng là tối ưu hoá truy vấn hướng
đối tượng. Khi thực thi một truy vấn, có thể có nhiều
phương án mà hệ thống CSDL cho phép xử lý và sản
sinh câu trả lời. Các phương án có kết quả cuối cùng
là tương đương về kết quả tính toán nhưng khác nhau
trong chi phí thực hiện, tức là tổng thời gian cần để
thực hiện một truy vấn. Lựa chọn phương án nào để
có tổng thời gian thực hiện là nhỏ nhất? Như vậy, vấn
đề tối ưu hoá truy vấn là cấp thiết trong các hệ thống
quản trị CSDL.
Trong những năm gần đây vấn đề tối ưu hoá truy
vấn hướng đối tượng được nhiều nhà nghiên cứu quan
tâm, các kỹ thuật tối ưu hoá truy vấn được phát triển
có tính kế thừa từ mô hình CSDL quan hệ như tối ưu
hoá trên các biểu thức đại số [4] và các giải thuật
chuyển đổi truy vấn hướng đối tượng sang truy vấn
quan hệ để áp dụng các kỹ thuật tối ưu hoá truy vấn
đã có trên mô hình quan hệ [8].
Tuy nhiên, vấn đề tối ưu hoá truy vấn trên CSDL
hướng đối tượng có những điểm khác biệt so với các
phương pháp tối ưu hoá truy vấn trên CSDL quan hệ
– điều này xuất phát từ ngữ nghĩa của mô hình dữ liệu
hướng đối tượng và các ngôn ngữ truy vấn trên mô
hình này, vì vậy cần nghiên cứu các phương
pháp, đề xuất các kỹ thuật tối ưu hoá truy vấn phù hợp
cho các truy vấn hướng đối tượng.
Tối ưu hóa các truy vấn lồng trong CSDL hướng
đối tượng đã được Cluet, S. [2] đề xuất theo cách tiếp
cận 2 giai đoạn trong ngữ cảnh hướng đối tượng. Giai
đoạn đầu tiên được gọi là tối ưu hóa trên cơ sở phụ
thuộc: biến đổi các truy vấn ở mức ngôn ngữ nhằm
thực hiện các biểu thức con chung và các truy vấn con
độc lập một cách hiệu quả hơn. Các truy vấn đã biến
đổi được biên dịch thành các biểu thức đại số lồng
nhau. Sự định giá các vòng lặp lồng nhau có thể
không hiệu quả. Vì vậy, ở giai đoạn 2 là giai đoạn
“làm phẳng” các biểu thức đại số lồng nhau giúp cho
phép định giá hiệu quả hơn. Trong bài báo này, chúng
tui đề xuất cách tiếp cận bằng phương pháp biểu diễn
các truy vấn lồng bằng siêu đồ thị kết nối, sau đó thực
hiện tiến trình ước lượng các siêu cạnh trên siêu đồ thị
kết nối của truy vấn lồng. Xuất phát từ ý tưởng biểu
diễn và tối ưu hóa các truy vấn (ngôn ngữ
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
The Method for Estimating the Nested Queries
in Object-Oriented Databases by Connection Hypergraphs
Lê Mạnh Thạnh, Đoàn Văn Ban, Hoàng Bảo Hùng
QUEL/SQL) bằng siêu đồ thị của J.D Ullman [7] và
Han [3], chúng tui mở rộng phương pháp biểu diễn
này trong ngôn ngữ truy vấn OQL trên CSDL hướng
đối tượng.
II. BIỂU DIỄN TRUY VẤN OQL BẰNG SIÊU
ĐỒ THỊ KẾT NỐI
Các truy vấn được viết bằng ngôn ngữ truy vấn
OQL (ODMG-93) [5, 6] rất phong phú và đa dạng,
trong bài báo này chúng tui chỉ biểu diễn cho một tập
con của các truy vấn viết bằng ngôn ngữ OQL: các
truy vấn lồng.
Ví dụ 1: Để thống nhất trong trình bày một số ví dụ,
chúng ta sử dụng CSDL nhân sự minh hoạ như sau [4,
9]:
class NHAN_SU
type tuple (maso: integer,
hoten: string,
pho: string[20],
tpho: string[10],
matinh: integer,
ngaysinh: tuple (ngay: integer,
thang: integer,
nam:integer))
class SINH_VIEN inherits NHAN_SU
type tuple (gvhd: string,
dtb: float,
hocbong: float,
tenkhoa: KHOA)
class GIANG_VIEN inherits NHAN_SU
type tuple ( bomon: string[20],
mabomon: integer,
chucvu: string[20],
tenkhoa: KHOA,
luong: integer,
con: set(NHAN_SU))
class KHOA
type tuple (makhoa: integer,
tenkh: string,
diadiem: string,
ngansach: float,
GIANG_VIEN: set(GIANG_VIEN))
1. Siêu đồ thị kết nối
Chúng ta nhắc lại định nghĩa của một siêu đồ thị.
Một siêu đồ thị H = (V, E) chứa một tập các đỉnh V và
tập các siêu cạnh E. Trong đó, tập đỉnh V tương ứng
với tập các mục dữ liệu (thuộc tính), và mỗi siêu cạnh
e ∈ E tương ứng với một tập các mục dữ liệu có liên
quan với nhau (lớp, điều kiện). Siêu đồ thị là sự mở
rộng của một đồ thị mà mỗi siêu cạnh của nó được kết
nối từ tập các đỉnh.
Trong bài báo này, chúng ta giới thiệu khái niệm
siêu đồ thị kết nối biểu diễn cho câu truy vấn lồng
trong CSDL hướng đối tượng, là một sự mở rộng
phương pháp biểu diễn siêu đồ thị đối với các thành
phần của câu truy vấn lồng.
Trước hết, chúng ta xét biểu thức điều kiện trong
mệnh đề Where, các biểu thức điều kiện được chia ra
bốn dạng sau:
A = a, (1)
A = B (2)
A θ B, θ ∈ { , ≥}, (3)
A θ B, θ ∈ {⊂ , ⊆ , ≠ , ⊃ , ⊇}. (4)
trong đó, A, B là thuộc tính của các lớp và a là
hằng.
Truy vấn OQL đơn chỉ có một khối
Select...From...Where (SFW); Truy vấn OQL lồng
có nhiều hơn 1 khối SFW. Mỗi khối SFW được biểu
diễn bằng siêu đồ thị kết nối như sau:
− Đồ thị có các cạnh là các tập với số lượng nút hữu
hạn, ta gọi một cạnh như vậy là siêu cạnh. Siêu đồ
thị này được gọi là siêu đồ thị kết nối, mỗi thuộc
tính của lớp Ci được biểu thị bằng một nút. Nếu hai
lớp Ci và Cj đều có cùng một số các thuộc tính kế
thừa từ một siêu lớp nào đó, hay chúng cùng kế
thừa tất cả các thuộc tính từ một siêu lớp, chúng ta
vẫn tạo riêng cho các thuộc tính này các nút khác
nhau.
− Các siêu cạnh của siêu đồ thị kết nối được tạo thành
từ các biểu thức điều kiện và các lớp Ci như sau:
Đối với mỗi lớp Ci , có một siêu cạnh chứa tất cả
các nút là các thuộc tính của Ci , ta gọi là siêu cạnh
đối tượng và được vẽ bằng 1 đường khép kín bao
quanh tất cả các nút của siêu cạnh.
Đối với mỗi biểu thức điều kiện dạng (3) hay (4),
chúng ta sẽ tạo ra một siêu cạnh chứa tất cả các
thuộc tính có mặt trong biểu thức. Những siêu cạnh
này được gọi là siêu cạnh điều kiện và chúng được
biểu thị bằng đường nét chấm khép kín.
Điều kiện có dạng (1) trong siêu đồ thị, được gán
nhãn nút là “A = a”.
Biểu thức điều kiện có dạng A = B (dạng (2)), với
A, B là các thuộc tính trong hai lớp (có thể cùng là
những thuộc tính được kế thừa từ một siêu lớp nào
đó), thì chúng ta “trộn” các nút A và B lại với nhau
đặt nhãn chung là tên của một trong hai thuộc tính.
Các thuộc tính trong mệnh đề Select được bao trong
một đường khép kín và gán nhãn là “head”, gọi là siêu
cạnh đỉnh. Siêu cạnh đỉnh tương ứng với một lớp - kết
quả của truy vấn.
Nếu có hai điều kiện trên cùng một tập thuộc tính
hay một điều kiện trên m