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

h 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ý, vì mỗi 
lớp là hữu hạn có đối tượng, đặt:
objs={oj| oj ∈ class, j = 1,, n}
Do đó, sẽ tạo được tập hữu hạn có chữ ký 
đối tượng:
Sig={sigj | sigj = Hashing (oj), 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ị Gs để đ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ị Gs là hữu hạn. Nên thuật toán sẽ tìm được 
nút phù hợp để đưa chữ ký sigj vào hoặc tạo 
ra một nút mới. Vì vậy, 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ý Gs với các nút trong 
u có dạng .
Gọi n là số đối tượng trong một lớp, khi 
đó n=|objs|. Đồ thị chữ ký là dạng đồ thị chữ 
ký và 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ó 2(k-1) lần duyệt, với k ≈ 0,1,, [log2 
n]. Vì có n chữ ký lần lượt đưa vào đồ thị chữ 
ký Gs, nên số lần duyệt đồ thị tối đa sẽ là: ≈n. 
Tuy nhiên, trong đồ thị chữ ký Gs sẽ lần lượt 
kiểm tra số bít trên mỗi chữ ký trong quá trình 
duyệt đồ thị, gọi m là chiều dài của mỗi chữ 
ký, chi phí của thuật toán tạo ra đồ thị chữ 
ký Gs sẽ là n.(2.m). Do đó, độ phức tạp trong 
trường hợp này sẽ là O(n.m).
Một ví dụ về tạo đồ thị chữ ký dựa trên tập tin chữ ký hình 2(a) được minh họa như sau:
Hình 3: Tạo đồ thị chữ ký
63
Truy vấn hướng đối tượng . . .
3.3. Thuật toán truy vấn đối tượng trên 
đồ thị chữ ký 
Sau khi đã tạo ra đồ thị chữ ký Gs, quá 
trình truy vấn hướng đối tượng ứng với yêu 
cầu truy vấn sẽ được thực hiện. Dữ liệu cần 
truy vấn sẽ được bĕm thành dạng chữ ký theo 
cùng phương pháp bĕm chữ ký trên đồ thị Gs, 
sau đó sẽ tiến hành tìm kiếm trên đồ thị chữ 
ký Gs. Kết quả của quá trình tìm kiếm này là 
một danh sách các con trỏ liên kết đến vị trí 
chữ ký trong tập tin chữ ký của cơ sở dữ liệu 
hướng đối tượng tương ứng.
Thuật toán truy vấn chữ ký sig trên đồ thị 
Gs được thực hiện như sau:
Vào: Chữ ký sig và đồ thị Gs
Ra: Tập các con trỏ Lp liên kết đến các 
chữ ký giống nhau nhưng có vị trí xuất hiện 
khác nhau trong tập tin chữ ký.
Phương pháp 2. Search-In-Gs(Gs, sig)
Begin
Lp = ∅; v ← root; S = {v};
Bước 1. If (S = ∅ ) then return Lp;
 Else Chọn vj∈ S; S = S \ {vj};
 If (vj được đánh dấu) then Qua bước 2;
 Else { i ← Skip(vj);
If sig[i] = 0 then 
 S = S ∪ { vj →right, vj→left};
 Else S = S ∪ {vj→left};
Quay lại bước 1;
 }
Bước 2. If sig được phủ bởi Sig(vj) then 
Lp = Lp ∪ Lp(vj); 
Quay lại bước 1;
End.
Đối với phương pháp 2, vì Gs đã tạo ra 
trong phương pháp 1 là hữu hạn nên tập S là 
một tập hữu hạn chứa các phần tử vj sẽ được 
duyệt ở các bước tiếp theo.
Khi duyệt một nút vj ∈S, thì vj sẽ được 
loại ra khỏi tập S. Do đó việc duyệt đồ thị 
sẽ không quay lại một nút sẽ đi qua. Thuật 
toán sẽ đối sánh chữ ký truy vấn và chữ ký 
tại các nút. Quá trình đối sánh được thực hiện 
trên một hữu hạn các nút của đồ thị Gs. Nên 
sau hữu hạn bước thuật toán sẽ cho ra được 
kết quả là một danh sách LP gồm các con trỏ 
tham chiếu đến các vị trí của chữ ký truy vấn 
trong tập tin chữ ký.
Trong phương pháp 2, gọi n là số nút đã 
được tạo ra trong Gs, mỗi lần duyệt đồ thị có 
thể đi theo hai nhánh của đồ thị Gs nên số lần 
duyệt đồ thị sẽ là 2k, với k≈0,1,2,,[log2n]. 
Khi đó, chi phí quá trình duyệt đồ thị để tìm 
kiếm tối đa sẽ là log2n. Trong mỗi lần duyệt 
đồ thị sẽ kiểm tra chữ ký tại các nút để thực 
hiện bước nhảy bít và thực hiện đối sánh chữ 
ký tại các nút, giả sử chiều dài của mỗi chữ ký 
là m, chi phí quá trình tìm kiếm trên đồ thị Gs 
sẽ là 2mlog2n. Do đó, độ lớn chi phí của thuật 
toán sẽ là O(m.logn).
Một ví dụ về tìm kiếm trên đồ thị chữ ký 
dựa trên hình 2 được minh họa như sau:
Hình 4: Tìm kiếm trên đồ thị chữ ký
Xét tập tin chữ ký và đồ thị chữ ký trên, giả 
sử rằng sq = 1011011 là chữ ký truy vấn, lúc 
đó chỉ một phần của đồ thị được tìm kiếm. Để 
tìm ra nút v, v được đánh dấu hoặc skip(v) = 
0 thì chữ ký của nút v sẽ được kiểm tra tương 
ứng với sq. Rõ ràng rằng cách tìm kiếm này 
hiệu quả hơn việc tìm kiếm tuần tự vì chỉ cần 
kiểm tra 2 chữ ký, trong khi đó phép duyệt tập 
tin chữ ký sẽ kiểm tra 8 chữ ký.
64
Tạp chí Kinh tế - Kỹ thuật
4. XÂY DỰNG MÔ HÌNH ỨNG DỤNG
4.1. Mô hình ứng dụng 
Cấu trúc đồ thị chữ ký được lưu trữ hoàn 
toàn bên trong bộ nhớ chính, trong trường 
hợp này, việc chèn và xóa một chữ ký trên đồ 
thị được thực hiện dễ dàng. Tuy nhiên, trong 
cơ sở dữ liệu các tập tin thường rất lớn, vì vậy 
đồ thị chữ ký sẽ không thể lưu trữ trên bộ nhớ 
chính mà phải được lưu trữ trên bộ nhớ ngoài. 
Đối với cơ sở dữ liệu hướng đối tượng, chúng 
sẽ được lưu trữ và thực thi trên bộ nhớ ngoài. 
Cơ sở dữ liệu hướng đối tượng có nhiều lớp, 
mỗi lớp có nhiều đối tượng. Ứng với mỗi lớp 
sẽ được xây dựng thành một cấu trúc đồ thị 
chữ ký tìm kiếm, đồng thời mỗi đối tượng này 
sẽ tạo ra một chữ ký đối tượng. Chữ ký của 
mỗi đối tượng được xây dựng trong mô hình 
này có chiều dài 128 bit, đó là sự tổ hợp các 
thuộc tính trong một đối tượng. Toàn bộ cơ sở 
dữ liệu hướng đối tượng sẽ được phân hoạch 
dưới dạng cấu trúc một bảng bĕm gồm các 
chữ ký của đối tượng để thực hiện quá trình 
truy vấn.
Hình 5: Mô hình cấu trúc lưu trữ đồ thị chữ ký cho cơ sở dữ liệu hướng đối tượng
 4.2. Một ví dụ về mô hình cơ sở dữ liệu 
hướng đối tượng
Để thực nghiệm truy vấn hướng đối tượng 
trên cơ sở dữ liệu hướng đối tượng. Một ví dụ 
mô hình cơ sở dữ liệu hướng đối tượng được 
đưa ra ở hình 6 đồng thời cũng đưa ra những 
quan hệ trên các lớp đối tượng bảng 1. Dựa 
trên mô hình này để thực nghiệm cài đặt cơ sở 
dữ liệu hướng đối tượng ở mức vật lý. 
Bảng 1. Quan hệ các lớp
S.No Class 1 Class 2 Relationship
1 University Dept Composition
2 University Student Aggregation
3 Student Programme Aggregation
4 Dept Instructor Aggregation
5 Student Male Generalization
6 Student Female Generalization
7 Programme Subject Aggregation
65
Truy vấn hướng đối tượng . . .
 4.3. 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 
trong cơ sở dữ liệu 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.
5. KẾT LUẬN
Trong bài báo này, chúng tôi đã đề xuất 
thuật toán tạo đồ thị chữ ký để lưu trữ các 
chữ ký đối tượng của cơ sở dữ liệu hướng 
đối tượng và thuật toán truy vấn chữ ký đối 
tượng trên đồ thị chữ ký. Dựa trên cấu trúc đồ 
thị chữ ký đã tạo, bài báo tiến hành đề xuất 
mô hình ứng dụng cho cơ sở dữ liệu hướng 
đối tượng. Việc truy vấn trên đồ thị chữ ký 
diễn ra tương đối nhanh, do đó có thể áp dụng 
phương pháp này trong trường hợp 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ý,
Hình 6: Một ví dụ mô hình cơ sở dữ liệu hướng đối tượng 
66
Tạp chí Kinh tế - Kỹ thuật
TÀI LIỆU THAM KHẢO
1. Yangjun Chen, Yibin Chen, 2006,On the Signature Tree Construction and Analysis, IEEE Trans. 
Knowl. Data Eng., 18(9), 1207-1224.
2. Yangjun Chen, 2004, Building Signature Trees into OODBs, Journal of Information Science and 
Engineering, 20(2), 275-304.
3. I.E. Shanthi, R. Nadarajan, 2009, Applying SD-Tree for Object-Oriented Query Processing, 
Informatica (Slovenia), 33(2), 169-179.
4. D. L. Lee, Y. M. Kim, G. Patel, 1995, Eficient Signature File Methods for Text Retrieval, IEEE 
Trans. Knowl. Data Eng., 7(3), 423-435.
5. Walter W.Chang, Hans J. Schek, 1989, A signature Access Method for the Starburst Database 
System, Proceedings of the Fifteenth International Conference on Very Large Database, Amsterdam, 
145-153.
6. W. C. Lee, D. L. Lee, 1992, Signature File Methods for Indexing Object-Oriented Database systems, 
Proceedings of the 2nd International Computer Science Conference, Hong Kong, 616-622.
7. Yangjun Chen, 2006, On the cost of searching signature trees, Science Direct, Information Processing 
Letters, 99(1), 19-26.
8. Yangjun Chen, 2002, Signature iles and signature trees, Elsevier Science, Journal Information 
Processing Letters, 82(4), 213-221.
9. Yangjun Chen, Yibin Chen, 2004, 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, 724-728.
10. E.Tousidoua, P. Bozanis, Y. Manolopoulos, 2002, Signature-basedstructuresforobjectswithset-
valued attributes, Elsevier Science, Information Systems, 27(2), 93-121.
11. Y.Chen, 2005, On the Signature Trees and Balanced Signature Trees, Proceedings of the 21st 
International Conference on Data Engineering, IEEE Computer Society, Tokyo, Japan, 742-753.
12. P.Mahatthanapiwat, 2010, Flexible Searching for Graph Aggregation Hierarchy, Proceedings of the 
World Congress on Engineering 2010, London, UK, 405-409.