Truy vấn hướng đối tượng dựa trên đồ thị chữ ký

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 
DOI: 10.15625/vap.2015.000212 
TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ 
Trần Minh Bảo1, Trương Công Tuấn2 
1, 2Trường Đại học Khoa học, Đại học Huế 
tmbaovn@gmail.com, tctuan_it_dept@yahoo.com 
TÓM TẮT - Các kỹ thuật lập chỉ mục luôn luôn là một vấn đề quan trọng trong việc tìm kiếm thông tin hiệu quả từ cơ sở dữ 
liệu (CSDL). Đối với CSDL hướng đối tượng, việc sử dụng các tập tin chữ ký như là một phương pháp chỉ mục đã được thừa nhận 
là một tiếp cận phổ biến trong việc xử lý truy vấn trên CSDL hướng đối tượng. Các đối tượng của lớp được mã hóa thành các chữ 
ký đối tượng bằng cách dùng hàm băm và được lưu trữ trong một tập tin chữ ký. Tuy nhiên, mỗi khi xử lý truy vấn thì toàn bộ tập tin 
chữ ký phải được quét. Vì vậy phương pháp này đòi hỏi chi phí xử lý cao. Để khắc phục nhược điểm này, chúng tôi đề xuất một mô 
hình cấu trúc đồ thị được xây dựng trên chữ ký của các đối tượng trong một CSDL hướng đối tượng, gọi là đồ thị chữ ký. Đồng thời 
đề xuất cách thức xây dựng đồ thị chữ ký và thuật toán truy vấn trên đồ thị chữ ký cùng với phần mô phỏng ứng dụng của phương 
pháp này. 
Từ khóa - Truy vấn hướng đối tượng, chữ ký đối tượng, tập tin chữ ký, đồ thị chữ ký. 
I. MỞ ĐẦU 
Việc nghiên cứu các kỹ thuật lập chỉ mục luôn luôn là một vấn đề quan trọng trong việc tìm kiếm thông tin hiệu 
quả từ cơ sở dữ liệu (CSDL). Đối với CSDL hướng đối tượng, truy vấn trực tiếp trên các đối tượng có chi phí thời gian 
thực hiện lớn. Đã có nhiều kỹ thuật chỉ mục CSDL nhằm xử lý truy vấn trên CSDL hướng đối tượng, trong đó phương 
pháp tập tin chữ ký được thừa nhận rộng rãi và là một tiếp cận khá hiệu quả trong việc xử lý truy vấn trên CSDL hướng 
đối tượng. Đối với phương pháp này, các đối tượng của lớp được mã hóa thành các chữ ký đối tượng bằng cách dùng 
hàm băm và được lưu trữ trong một tập tin chữ ký. Tuy nhiên, việc truy vấn trên tập tin chữ ký lại có nhược điểm là tốn 
kém chi phí do phải quét toàn bộ tập tin. Một số các phương pháp chỉ mục khác nhằm khắc phục điều này và có thể tìm 
thấy trong nhiều công trình nghiên cứu [1] [2] [3] [8] [9]. 
Trong bài báo này, chúng tôi đề xuất việc tổ chức tập tin chữ ký của một lớp trong CSDL hướng đối tượng 
trong một đồ thị chữ ký và xây dựng các thuật toán để tạo đồ thị chữ ký và truy vấn đối tượng trên đồ thị chữ ký. Việc 
sử dụng đồ thị chữ ký có không gian tìm kiếm nhỏ hơn để từ đó giảm thời gian truy vấn dữ liệu. 
Bài báo này được tổ chức như sau: Phần đầu của bài báo sẽ giới thiệu khái quát về chữ ký đối tượng, tập tin chữ 
ký, chữ ký truy vấn và cấu trúc đồ thị chữ ký, sau đó bài báo thực hiện việc xây dựng đồ thị chữ ký và thuật toán truy 
vấn đối tượng trên đồ thị chữ ký, đồng thời xây dựng mô hình ứng dụng, phần cuối của bài báo là kết luận. 
II. MỘT SỐ KHÁI NIỆM CƠ SỞ 
Phần này chỉ trình bày một số khái niệm cơ sở liên quan đến chữ ký đối tượng và tập tin chữ ký. Chi tiết đầy đủ 
hơn có thể xem trong [1] [2]. 
A. Chữ ký đối tượng, tập tin chữ ký 
Trong một CSDL hướng đối tượng, mỗi đối tượng được biểu diễn bởi một bộ giá trị của các thuộc tính. Chữ ký 
của một giá trị thuộc tính là một chuỗi các bit được mã hóa bằng hàm băm. Chữ ký đối tượng được xây dựng bằng 
phép toán logic OR cho tất cả các chữ ký của các giá trị thuộc tính của đối tượng. Sau đây là một ví dụ về chữ ký của 
đối tượng: 
Ví dụ 2.1. Xét một đối tượng có các giá trị thuộc tính lần lượt là “Dung”, “12345678”, “giao su”. Giả sử chữ ký của 
các đối tượng này là: 
 010 000 100 110 
 100 010 010 100 
 110 100 011 000 
Lúc đó chữ ký của đối tượng là 110 110 111 110, nhận được từ chữ ký các giá trị thuộc tính bằng phép toán 
logic OR. 
Các chữ ký đối tượng của một lớp được lưu trữ trong một tập tin, gọi là tập tin chữ ký đối tượng. 
B. Chữ ký truy vấn 
Một truy vấn đối tượng sẽ được mã hóa thành một chữ ký truy vấn theo cùng hàm băm đã thực hiện đối với các 
đối tượng. Khi có một truy vấn cần thực hiện, các chữ ký đối tượng sẽ được quét và những đối tượng không phù hợp sẽ 
bị loại trừ. Lúc đó chữ ký truy vấn được so sánh đối với mọi chữ ký đối tượng trong tập tin chữ ký. Có ba trường hợp 
có thể xảy ra: 
TV
c
m
A
c
th
h
V
d
h
x
lư
Đ
V
rần Minh Bảo, T
(1) Đối tư
đối tư
(2) Đối tư
(3) Chữ k
trong 
được 
í dụ 2.2. Ví 
Nhận x
hữ ký truy vấ
ọi bit 0 trong
. Đồ thị chữ
Để tìm 
hữ ký đó. Nế
iện quá trình
iện được do v
í dụ 3.1. Xem
Giả sử 
ụng tìm kiếm
iện nhiều chữ
uất hiện của đ
u trữ được d
ịnh nghĩa 3.
1. Mỗi n
ký sig
bit thứ
2. Đặt e
nhãn 
thứ i 
í dụ 3.2. Hìn
rương Công Tuấn
ợng phù hợp
ợng s cũng ch
ợng không p
ý được đối sá
truy vấn. Để
đối sánh phù 
dụ này minh h
 T
 D
 B
 D
ét: Việc so sá
n ݏ௤ phù hợp 
 ݏ௤ thì không
 ký 
một chữ ký đ
u tập tin là lớ
 này là sắp xế
iệc đối sánh t
 tập tin chữ k
chữ ký truy v
 nhị phân thì 
 ký giống nh
ối tượng phù
anh sách các c
1. Đồ thị chữ 
út u ∈ V có d
ሺuሻ trong tập
 i của chữ ký
ൌ ሺu, vሻ ∈ E
là 0 và i ൐ 0 
của chữ ký đư
h vẽ sau min
 với truy vấn,
ính là nó, tức
hù hợp với câ
nh và cho ra 
 loại ra trườn
hợp. 
ọa việc truy 
ruy vấn 
ung 
inh 
uong 
nh chữ ký tru
chữ ký s nếu 
 quan trọng bi
III. 
ối tượng tron
n thì thời gia
p tập tin chữ 
rên tập tin ch
ý đã được sắ
010 0
100 0
010 1
ấn s୯	là 000 
chữ ký 100 0
au ứng với cá
 hợp. Vì lý do
hữ ký và cho
ký Gୱ đối với
ạng ൏ lpሺuሻ,
 tin chữ ký S v
 truy vấn s୯	sẽ
. Lúc đó	e đư
thì bit thứ i c
ợc trỏ lpሺvሻ l
h họa một tập
Hìn
 nghĩa là đối 
 là ݏ௤ ∧ ݏ = ݏ
u truy vấn, ng
một kết quả p
g hợp này, c
vấn đối với ch
Chữ ký tr
010 000 
011 000 
110 100 
y vấn ݏ௤ với
mọi bit 1 tron
t tương ứng t
ĐỒ THỊ C
g tập tin chữ 
n để tìm kiếm
ký và sau đó 
ữ ký là một đố
p xếp gồm 3 c
00 100 110
10 010 100
00 011 000
010 010 100. 
10 010 100 k
c đối tượng c
 này, ta sẽ tổ
 phép truy ng
 tập tin chữ ký
skipሺuሻ ൐, vớ
à skipሺuሻ là 
 được kiểm tr
ợc gán nhãn 
ủa chữ ký đư
à 1. Một nút v
 tin chữ ký và
h 1. Minh họa
với mọi bit tro
௤, đối tượng th
hĩa là ݏ௤	∧ ݏ 
hù hợp nhưn
ác đối tượng 
ữ ký đối tượn
uy vấn 
100 110
100 100
100 000
chữ ký đối tư
g ݏ௤, các bit
rong s là 0 hay
HỮ KÝ VÀ T
ký có phù hợ
 trên một tập
sử dụng việc t
i sánh không
hữ ký đối tượ
Nó phù hợp v
hông thể tìm 
ó nội dung gi
 chức tập tin c
ược lại vị trí c
 S là một đồ 
i lpሺuሻ là dan
một số nguyê
a khi tìm kiếm
là 0 hoặc 1 v
ợc trỏ bởi lpሺ
 với skipሺuሻ
 đồ thị chữ ký
tập tin chữ ký 
ng chữ ký tru
ực sự chứa từ
≠ ݏ௤; 
g đối tượng k
phải được kiể
g ở ví dụ 1.1
Kết quả 
thành công
không thàn
thành công
ợng s là loại
tương ứng tro
 1. 
HUẬT TOÁ
p với chữ ký 
 tin như vậy 
ìm kiếm nhị p
 chính xác. Ta
ng: 
ới chữ ký 10
thấy. Mặt khá
ống nhau, quá
hữ ký thành 
ủa dữ liệu tươ
thị có hướng 
h sách các co
n i không âm,
. Nếu i ൌ 0, s
à skipሺuሻ ൐
vሻ là 0. Nếu e
ൌ 0 thì không
 của nó: 
và đồ thị chữ ký
y vấn ݏ௤, bit 
 truy vấn; 
hông phù hợp
m tra sau kh
: 
h công 
 nhưng khôn
 đối sánh khô
ng s cũng là b
N 
truy vấn, ta c
là đáng kể. Ý
hân. Tuy nhi
 xem ví dụ sa
0 010 010 10
c, trong tập t
 trình truy vấ
một đồ thị, gọ
ng ứng. Ta c
Gୱ = (V, E) sa
n trỏ tham chi
 gọi là bước n
igሺuሻ	sẽ được
0. Đặt skipሺ
 được gán nh
 có nút con. 
tương ứng tro
 với điều kiện
i các chữ ký
g phù hợp 
ng chính xác
it 1. Tuy nhi
ần phải quét m
 tưởng trước 
ên, điều này k
u đây: 
0. Tuy nhiên
in chữ ký có 
n cần tìm ra t
i là đồ thị ch
ó định nghĩa s
o cho: 
ếu đến các vị 
hảy nhảy bit. 
 so sánh với s
uሻ ൌ i. Nếu	e
ãn là 1 và i ൐
723 
ng chữ ký 
 tìm kiếm 
đối tượng 
. Nghĩa là, 
ên, đối với 
ột tập tin 
tiên để cải 
hông thực 
, nếu ta sử 
thể sẽ xuất 
ất cả vị trí 
ữ ký nhằm 
au: 
trí của chữ 
Nếu i ൐ 0, 
୯. 
 được gán 
0 thì bit 
724 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ 
B. Thuật toán 
1. Thuật toán tạo đồ thị chữ ký 
Thuật toán 1: Thuật toán xây dựng đồ thị chữ ký của một lớp các đối tượng: 
Vào: Lớp đối tượng 
Ra: Đồ thị chữ ký 
Phương pháp: 
Begin 
objs = {oj | oj∈ class, j = 1,, n} 
lp(root) = null; sig1 = Hashing(o1); 
lp(root) = lp(root) ∪ sig1; 
root = ; 
j = 2; 
Bước 1. Tạo chữ ký sigj = Hashing(oj); 
v ← root; 
Qua bước 2; 
Bước 2. if (v không đánh dấu và skip(root) ≠ 0 ) then Qua bước 3; 
else{i ← skip(v) đánh dấu v; 
 if (sigv[i] = 1) then v = v→right; 
 else v = v→left; 
 Quay lại bước 2; } 
Bước 3. 
if (sigj = sigv) then 
{ lp(v) = lp(v) ∪ sigj; 
j ← j + 1; Quay lại bước 1; } 
 else{o ← v; s=; Qua bước 4;} 
Bước 4. 
Gọi k+1 là vị trí khác nhau đầu tiên giữa sigj và sigv; 
Thay thế nút v trở thành: 
; 
if (sigj[k+1] = 1) then 
 {v → right = s; v → left = o;} 
else {v → right = o; v → left = s;} 
 j ← j + 1; Quay lại bước 1; 
End. 
Trong thuật toán tạo đồ thị chữ ký Gୱ, vì mỗi lớp là hữu hạn có n đối tượng, đặt: 
 objs ൌ ൛o୨หo୨∈	class, j ൌ 1, , nሽ	 
Do đó, sẽ tạo được tập hữu hạn có n chữ ký đối tượng: 
Sig ൌ ൛sig୨หsig୨ ൌ Hashing൫o୨൯, j ൌ 1, , nሽ 
Với mỗi giá trị j, thuật toán sẽ duyệt từ nút gốc của đồ thị Gୱ để đi tìm nút phù hợp, quá trình này là hữu hạn vì 
số nút tạo ra trong đồ thị Gୱ là hữu hạn. Vì vậy thuật toán sẽ tìm được nút phù hợp để đưa chữ ký sig୨ vào hoặc tạo ra 
một nút mới. Do đó, sau hữu hạn bước ứng với giá trị của j ൌ 1, , n thì thuật toán cho kết quả là một đồ thị chữ ký Gୱ 
với các nút u có dạng ൏ lpሺuሻ, skipሺuሻ ൐. 
Gọi n là số đối tượng trong một lớp, khi đó n ൌ |objs|. Mỗi lần duyệt đồ thị chữ ký sẽ duyệt theo nhánh con bên 
trái hoặc nhánh bên phải, nên sẽ có )1k(2 − lần duyệt, với k ൌ 0, 1,  , ሾlogଶnሿ. Vì có n chữ ký lần lượt đưa vào đồ thị ∑
=
k
i
i
0
2
Tc
c
l
V
2
h
t
v
T
V
R
P
v
đ
h
tr
th
rần Minh Bảo, T
hữ ký Gୱ, nên
hữ ký trong q
à n. ሺ2.mሻ. D
í dụ 3.3. Mộ
. Thuật toán 
Sau khi
iện. Dữ liệu c
iến hành tìm k
ị trí chữ ký tr
huật toán 2:
ào: Chữ ký s
a: Tập các co
hương pháp
Begin 
lp =
Bư
 e
 i
 e
if s
 S
 els
Qu
} 
Bư
lp =
Qu
End. 
Đối với
୨ sẽ được duy
Khi duy
i qua. Thuật t
ạn các nút củ
ỏ tham chiếu
Trong t
ị Gୱ nên số l
rương Công Tuấn
 số lần duyệt 
uá trình duyệ
o đó, độ phức
t ví dụ về tạo 
truy vấn đối tư
 đã tạo ra đồ 
ần truy vấn sẽ
iếm trên đồ t
ong tập tin ch
 Thuật toán tr
ig và đồ thị G
n trỏ lp liên k
: 
 ∅; v ← roo
ớc 1. if (S = ∅
lse Chọn vj∈
f (vj được đá
lse { i ← skip
ig[i] = 0 then
 = S ∪ { vj →
e S = S ∪ {vj→
ay lại bước 1
ớc 2. if sig đư
 lp ∪ lp(vj); 
ay lại bước 1
 thuật toán 2,
ệt ở các bước
ệt một nút	v୨
oán sẽ đối sán
a đồ thị Gୱ. V
 đến các vị trí
huật toán 2, g
ần duyệt đồ th
đồ thị tối đa s
t đồ thị, gọi m
 tạp trong trườ
đồ thị chữ ký 
ợng trên đồ t
thị chữ ký Gୱ
 được băm th
hị chữ ký Gୱ.
ữ ký của cơ s
uy vấn chữ ký
ୱ 
ết đến các ch
t; S = {v}; 
 ) then retur
 S; S = S \ {v
nh dấu) then
(vj); 
right, vj→lef
left}; 
; 
ợc phủ bởi 
; 
 vì Gୱ đã tạo r
 tiếp theo. 
∈ S, thì v୨ sẽ
h chữ ký truy
ì vậy sau hữu
 của chữ ký tr
ọi n là số nút
ị sẽ là 2k, với
ẽ là ≈ n. Tuy 
 là chiều dài 
ng hợp này s
dựa trên tập t
Hình 2
hị chữ ký 
, quá trình tr
ành dạng chữ
 Kết quả của 
ở dữ liệu hướn
 sig trên đồ t
ữ ký giống nh
n lp; 
j}; 
 Qua bước 2
t}; 
sig(vj) then 
a trong thuật 
 được loại ra 
 vấn và chữ k
 hạn bước thu
uy vấn trong 
 đã được tạo 
 k ൌ 0, 1, 2, 
nhiên, trong đ
của mỗi chữ k
ẽ là Oሺn.mሻ.
in chữ ký ở ví
. Tạo đồ thị ch
uy vấn hướng
 ký theo cùng
quá trình tìm 
g đối tượng t
hị Gୱ được thự
au nhưng có 
; 
toán 1 là hữu 
khỏi tập S. Do
ý tại các nút.
ật toán sẽ cho
tập tin chữ ký
ra trong Gୱ, m
, ሾlogଶnሿ. Kh
ồ thị chữ ký 
ý, chi phí của
 dụ 3.2 được 
ữ ký 
 đối tượng ứn
 phương pháp
kiếm này là m
ương ứng. 
c hiện như sa
vị trí xuất hiệ
hạn nên tập S
 đó việc duyệ
Quá trình đối
 ra được kết 
. 
ỗi lần duyệt đ
i đó, chi phí 
Gୱ sẽ lần lượt
 thuật toán tạ
minh họa như
g với yêu cầ
 băm chữ ký 
ột danh sách
u: 
n khác nhau t
 là một tập hữ
t đồ thị sẽ kh
 sánh được th
quả là một da
ồ thị có thể đ
quá trình duy
 kiểm tra số b
o ra đồ thị ch
 sau: 
u truy vấn sẽ 
trên đồ thị Gୱ
 các con trỏ li
rong tập tin ch
u hạn chứa c
ông quay lại 
ực hiện trên m
nh sách lp gồ
i theo hai nh
ệt đồ thị để tìm
725 
it trên mỗi 
ữ ký Gୱ sẽ 
được thực 
, sau đó sẽ 
ên kết đến 
ữ ký. 
ác phần tử 
một nút sẽ 
ột số hữu 
m các con 
ánh của đồ 
 kiếm tối 
7
đ
s
D
đ
ứ
p
m
c
tư
n
tư
6
d
A
tư
n
26 
a sẽ là logଶn
ánh chữ ký tạ
o đó, độ lớn 
Một ví 
Xét tập
ồ thị được tìm
ng với s୯. Rõ
hép duyệt tập
Cấu trú
ột chữ ký trê
hữ ký sẽ khôn
ợng, chúng 
hiều đối tượn
ợng này sẽ t
4 bit, đó là sự
ưới dạng cấu 
. Một ví dụ
Để thực
ợng được đư
ày để cài đặt 
. Trong mỗi l
i các nút, giả 
chi phí của th
dụ về tìm kiếm
 tin chữ ký và
 kiếm. Để tìm
 ràng cách tì
 tin chữ ký sẽ
c đồ thị chữ k
n đồ thị được
g thể lưu trữ 
sẽ được lưu tr
g. Ứng với m
ạo ra một chữ
 tổ hợp các th
trúc một bảng
Hình
 về mô hình c
 nghiệm truy
a ra ở hình 5
CSDL hướng
TT 
1 
2 
3 
4 
5 
6 
7 
ần duyệt đồ t
sử chiều dài c
uật toán sẽ là 
 trên đồ thị c
 đồ thị chữ ký
 ra nút v, v 
m kiếm này h
 kiểm tra 8 ch
ý được lưu tr
 thực hiện dễ
trên bộ nhớ c
ữ và thực thi
ỗi lớp sẽ đư
 ký đối tượn
uộc tính tron
 băm gồm cá
 4. Mô hình cấ
ơ sở dữ liệu h
 vấn hướng đ
 đồng thời cũ
 đối tượng ở m
Lớp 1 
Truong
Truong
SinhVie
Khoa 
SinhVie
SinhVie
Chuong
hị sẽ kiểm tra
ủa mỗi chữ k
Oሺm. lognሻ.
hữ ký dựa trê
Hình 3. Tìm
 trên, giả sử 
được đánh dấ
iệu quả hơn v
ữ ký. 
IV. MÔ
ữ hoàn toàn b
 dàng. Tuy nh
hính mà phải 
 trên bộ nhớ 
ợc xây dựng 
g. Chữ ký của
g một đối tượ
c chữ ký của 
u trúc lưu trữ đ
ướng đối tượ
ối tượng trên
ng đưa ra nhữ
ức vật lý. 
Bản
Lớ
 Kh
 Sin
n Ch
Gi
n Nu
n Na
Trinh Ch
 TRUY 
 chữ ký tại cá
ý là m, chí ph
n hình 2 được
 kiếm trên đồ t
rằng s୯ ൌ 10
u hoặc skipሺv
iệc tìm kiếm
 HÌNH ỨNG
ên trong bộ n
iên, trong cơ
được lưu trữ 
ngoài. Cơ sở 
thành một cấ
 mỗi đối tượ
ng. Toàn bộ 
đối tượng để t
ồ thị chữ ký ch
ng 
 CSDL hướn
ng quan hệ t
g 1. Quan hệ c
p 2
oa 
hVien 
uongTrinh
angVien 
m 
uDe 
VẤN HƯỚNG Đ
c nút để thực
í quá trình tì
 minh họa nh
hị chữ ký 
11011 là chữ
ሻ ൌ 0 thì chữ
 tuần tự vì ch
 DỤNG 
hớ chính, tro
 sở dữ liệu cá
trên bộ nhớ ng
dữ liệu hướng
u trúc đồ thị 
ng được xây 
cơ sở dữ liệu 
hực hiện quá 
o cơ sở dữ liệu
g đối tượng. M
rên các lớp đ
ủa các lớp 
Qun hệ
Chứa trong
Kết tập 
Liên kết 
Liên kết 
Khái quát q
Khái quát q
Liên kết 
ỐI TƯỢNG DỰ
 hiện bước n
m kiếm trên đ
ư sau: 
 ký truy vấn, 
 ký của nút v
ỉ cần kiểm tra
ng trường hợ
c tập tin thườ
oài. Đối với 
 đối tượng c
chữ ký tìm k
dựng trong m
hướng đối tượ
trình truy vấn
 hướng đối tượ
ột ví dụ mô
ối tượng ở bả
uá 
uá 
A TRÊN ĐỒ TH
hảy bit và thự
ồ thị Gୱ sẽ là
lúc đó chỉ mộ
 sẽ được kiểm
 2 chữ ký, tr
p này, việc ch
ng rất lớn, vì
cơ sở dữ liệu 
ó nhiều lớp, m
iếm, đồng th
ô hình này có
ng sẽ được p
. 
ng 
 hình CSDL 
ng 1. Dựa trê
Ị CHỮ KÝ 
c hiện đối 
 2mlogଶn. 
t phần của 
 tra tương 
ong khi đó 
èn và xóa 
vậy đồ thị 
hướng đối 
ỗi lớp có 
ời mỗi đối 
 chiều dài 
hân hoạch 
hướng đối 
n mô hình 
Trần Minh Bảo, Trương Công Tuấn 727 
Hình 5. Một ví dụ mô hình cơ sở dữ liệu hướng đối tượng 
B. Xử lý truy vấn trên cơ sở dữ liệu hướng đối tượng 
Để thực hiện việc truy vấn một đối tượng trên CSDL hướng đối tượng, đầu tiên phải chuyển đổi cơ sở dữ liệu 
hướng đối tượng thành cấu trúc dữ liệu như trên, ta thực hiện như sau: 
Bước 1. Thuộc tính của đối tượng được băm thành chữ ký nhị phân và các thuộc tính tạo thành chữ ký đối tượng. 
Bước 2. Các chữ ký đối tượng của cùng một lớp sẽ tạo thành đồ thị chữ ký. 
Bước 3. Tạo danh sách đồ thị chữ ký tương ứng với từng lớp. 
Sau khi có cấu trúc dữ liệu để truy vấn, ta thực hiện quá trình truy vấn đối tượng trong cơ sở dữ liệu hướng đối tượng 
như sau: 
Bước 1. Mã hoá từ khóa cần truy vấn thành chữ ký nhị phân. 
Bước 2. Đối sánh chữ ký từ khóa để xác định thuộc lớp cần truy vấn. 
Bước 3. Thực hiện truy vấn chữ ký từ khóa trên đồ thị chữ ký tương ứng với các lớp đã xác định. 
V. KẾT LUẬN 
Bài báo đã đề xuất việc xây dựng đồ thị chữ ký để lưu trữ chữ ký đối tượng của CSDL hướng đối tượng và xây 
dựng thuật toán truy vấn đối tượng trên đồ thị chữ ký. Đồng thời dựa trên cấu trúc đồ thị chữ ký đã tạo, bài báo đã đưa 
ra một mô hình ứng dụng. Phương pháp này có thể áp dụng để truy vấn các đối tượng dữ liệu lớn như đối tượng dữ liệu 
ảnh, các đối tượng multimedia, các đối tượng trong hệ thống thông tin địa lý, 
VI. TÀI LIỆU THAM KHẢO 
[1] Yangjun Chen, Yibin Chen, “On the Signature Tree Construction and Analysis”, IEEE Trans. Knowl. Data Eng., 
18(9), 2006, 1207-1224. 
[2] Yangjun Chen, “Building Signature Trees into OODBs”, Journal of Information Science and Engineering, 20(2), 
2004, 275-304. 
[3] Yangjun Chen, Yibin Chen, “Signature File Hierarchies and Signature Graphs: a New Index Method for Object-
Oriented Databases”, Proceedings of the 2004 ACM symposium on Applied computing, Nicosia, Cyprus, 14-17 
March 2004, 724-728. 
[4] D. Dervos, Y. Manolopulos and P. Linardis, “Comparison of signature file models with superimposed coding”, J. 
of Information Processing Letters 65 (1998) 101 - 106. 
[5] C. Faloutsos, “Signature Files: Design and Performance Comparaison of Some Signature Extraction Methods”, 
ACM Sigmod Record, Volume 14, Issue 4, May 1985, pp. 63 – 82. 
[6] D. L. Lee, Y. M. Kim, G. Patel, “Efficient Signature File Methods for Text Retrieval”, IEEE Trans. Knowl. Data 
Eng., 7(3), 1995, 423-435. 
[7] W. C. Lee, D. L. Lee, “Signature File Methods for Indexing Object-Oriented Database systems”, Proceedings of 
the 2nd International Computer Science Conference, Hong Kong, 1992, 616-622. 
Truong
- Ten: Str
- DiaChi: Str
Khoa
- TenKhoa: Str
- ChuongTrinh: TenChuongTrinh[]
ChuongTrinh
- TenChuongTrinh: Str
- ChuDe: TenChuDe[]
ChuDe
- TenChuDe: Str
SinhVien
- TenSV: Str
- ChuongTrinh: Str
Nam
- GioiTinh: Str
Nu
- GioiTinh: Str
GiangVien
- TenGV: Str
- TenKhoa: Str
- ChuDe: TenChuDe[]
1..*
day
0..1
Tham gia day
0..1
1..*
gan cho
Thanh phan
Chua
1..*
gom
1..*
Co
1
Tham gia
728 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ 
[8] P. Mahatthanapiwat, “Flexible Searching for Graph Aggregation Hierarchy”, Proceedings of the World Congress 
on Engineering, 2010, London, UK, June 30-July 2, 2010, 405-409. 
[9] E. Tousidoua, P. Bozanis, Y. Manolopoulos, “Signature-based structures for objects with set-valued attributes”, 
Elsevier Science, Information Systems, 27(2), 2002, 93-121. 
OBJECT-ORIENTED QUERY PROCESSING BASED 
SIGNATURE BINARY GRAPH 
Tran Minh Bao, Truong Cong Tuan 
ABSTRACT - Indexing is always an important issue in the efficient information retrieval from the databases. For object-oriented 
databases, the use of signature files as a method of indexing has been recognized as a common approach in searching on object-
oriented databases. The objects of the class are encoded into the object signatures using hash functions and stored in a signature 
file. However, when a query arrives, the entire signature file must be scanned. So this method requires a high processing cost. To 
overcome this drawback, we propose a graph structure model constructed over signatures of objects for a class in an object-
oriented database, called a signature graph. We also suggest an algorithm to build the signature graph and query algorithm on 
signature graph, as well as an application of this method.