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

Truy vấn hướng đối tượng . . .<br /> <br /> <br /> <br /> TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN<br /> ĐỒ THỊ CHỮ KÝ NHỊ PHÂN<br /> Trương Công Tuấn*, Trần Minh Bảo**<br /> <br /> TÓM TẮT<br /> Bài báo xây dựng một mô hình cấu trúc đồ thị để tổ chức lưu trữ chữ ký của các đối tượng<br /> trong cơ sở dữ liệu hướng đối tượng, trong đó các đối tượng được mã hóa và xây dựng dưới dạng<br /> một đồ thị chữ ký, từ đó xây dựng thuật toán để xử lý truy vấn trên đồ thị chữ ký và đề xuất mô<br /> hình ứng dụng.<br /> <br /> Từ khoá: hướng đối tượng cơ sở dữ liệu; cơ cấu chỉ số; chữ ký; tập tin chữ ký; đồ thị chữ ký<br /> <br /> <br /> OBJECT-ORIENTED QUERY PROCESSING BASED BINARY<br /> SIGNATURE GRAPH<br /> <br /> ABSTRACT<br /> In this paper, we construct a graph structure model to store object signatures in object-<br /> oriented databases, in which the objects are hash encoded and presented by a signature graph.<br /> Then we built an algorithm to process the query on signature graph and propose an application<br /> model.<br /> <br /> Keyword: Object-oriented database; index structure; signature; signature ile; signature graph.<br /> <br /> <br /> 1. ĐẶT VẤN ĐỀ tượng trên cây chữ ký SD-Tree [3], truy vấn<br /> Truy vấn trực tiếp trên các đối tượng trong đối tượng trong cơ sở dữ liệu hướng đối tượng<br /> cơ sở dữ liệu hướng đối tượng rất tốn kém chi dựa trên cấu trúc cây chữ ký đối tượng [2], xây<br /> phí lưu trữ dữ liệu trong quá trình truy vấn dựng cấu trúc tập tin chữ ký và cây chữ ký [8],<br /> và tốn nhiều thời gian để thực hiện truy vấn xây dựng cấu trúc đồ thị chữ ký dựa trên tập tin<br /> trên hệ thống dữ liệu thực. Bài toán đặt ra là chữ ký để truy vấn trong cơ sở dữ liệu hướng<br /> cần mô tả lại hệ thống dữ liệu đơn giản hơn đối tượng [9, 12], xây dựng cấu trúc cây chữ ký<br /> và xây dựng cấu trúc dữ liệu tương ứng để có để giảm không gian tìm kiếm dữ liệu [1, 2, 7,<br /> thể giảm không gian tìm kiếm trong quá trình 10], truy vấn dữ liệu trên tập tin văn bản bằng<br /> thực thi câu truy vấn mà vẫn đảm bảo được tập tin chữ ký tuần tự và tập tin chữ ký phân<br /> việc truy vấn được các đối tượng cần thiết. mảnh [4], tạo chỉ mục truy vấn cho các tập tin<br /> Các phương pháp truy vấn dựa trên chữ văn bản [5, 6], tạo cấu trúc cây chữ cân bằng<br /> ký nhị phân đã công bố như: truy vấn đối và thao tác trên cây chữ ký cân bằng [1, 8],…<br /> <br /> *<br /> PGS.TS. Trường Đại học Khoa học, Đại học Huế. E-Mail: tctuan_it_dept@yahoo.com<br /> **<br /> ThS. GV. Trường Đại học Công nghiệp Thực phẩm Tp.HCM. E-Mail: tmbaovn@gmail.com<br /> <br /> 59<br /> Tạp chí Kinh tế - Kỹ thuật<br /> <br /> Bài báo sẽ tiếp cận phương pháp tạo chữ giá trị thuộc tính. Chữ ký của một giá trị thuộc<br /> ký cho các đối tượng, từ đó xây dựng cấu trúc tính là một chuỗi bít được mã hóa bằng hàm<br /> đồ thị để tham chiếu đến cơ sở dữ liệu thực. băm, có độ dài với bít 1 và bít 0. Chữ ký đối<br /> Chữ ký nhỏ hơn rất nhiều so với đối tượng tượng được xây dựng bằng phép toán OR bít<br /> thực, khoảng từ 10% – 20% so với đối tượng cho tất cả các chữ ký của các giá trị thuộc tính<br /> [4, 5, 8]. Chữ ký của các đối tượng sẽ được của đối tượng [1].<br /> lưu trữ trong tập tin chữ ký và qua đó thực Các chữ ký đối tượng của một lớp được<br /> hiện phép truy vấn các đối tượng dựa trên tập lưu trữ trong một tập tin, gọi là tập tin chữ<br /> tin chữ ký này. Ngoài ra, để việc tìm kiếm ký. Tập tin chữ ký tuần tự SSF (Sequential<br /> hiệu quả hơn, cần xây dựng cấu trúc dữ liệu Signature File) gồm các chữ ký đối tượng<br /> lưu trữ tập tin chữ ký. Cấu trúc lưu trữ tập được lưu trữ tuần tự [1, 3, 8].<br /> tin chữ ký này có thể dưới dạng các tập tin Một câu truy vấn chỉ định các giá trị cần<br /> chữ ký tuần tự, các tập tin chữ ký phân mảnh, tìm kiếm cũng sẽ được mã hóa thành chữ ký<br /> cấu trúc cây chữ ký, cấu trúc dạng đồ thị chữ truy vấn giống như cách mã hóa chữ ký các<br /> ký,… các cấu trúc lưu trữ tập tin chữ ký sẽ giá trị thuộc tính của đối tượng. Lúc đó chữ<br /> làm giảm không gian tìm kiếm và tối ưu quá ký truy vấn được so sánh đối với mọi chữ ký<br /> trình truy vấn dữ liệu. đối tượng trong tập tin chữ ký. Có ba trường<br /> Bài báo mô tả lại hệ thống dữ liệu thực hợp có thể xảy ra:<br /> trở thành một cấu trúc dữ liệu tham chiếu có 1. Đối tượng phù hợp với câu truy vấn,<br /> không gian tìm kiếm nhỏ hơn để từ đó giảm nghĩa là đối với mọi tập bít trong chữ ký truy<br /> thời gian truy vấn dữ liệu và đồng thời cấu vấn sq, tập bít tương ứng trong chữ ký đối<br /> trúc dữ liệu tham chiếu trung gian này có thể tượng s cũng chính là nó, tức là sq ∧ s = sq;<br /> truy vấn ngược lại dữ liệu thực sự. Kết quả 2. Đối tượng không phù hợp với câu truy<br /> của bài báo sẽ tập trung vào việc xây dựng vấn, nghĩa là sq ∧ s ≠ sq ;<br /> cấu trúc lưu trữ tập tin chữ ký dưới dạng đồ 3. Chữ ký được đối sánh và cho ra một kết<br /> thị chữ ký và thuật toán truy vấn đối tượng quả phù hợp nhưng đối tượng không phù hợp<br /> trên đồ thị chữ ký đồng thời xây dựng mô với điều kiện tìm kiếm trong câu truy vấn.<br /> hình ứng dụng. Để loại ra trường hợp này, các đối tượng phải<br /> Phần đầu của bài báo sẽ giới thiệu khái được kiểm tra sau khi các chữ ký đối tượng<br /> quát về chữ ký cho các đối tượng; tiếp theo được đối sánh phù hợp.<br /> bài báo giới thiệu các khái niệm cơ bản về chữ Một ví dụ về chữ ký của đối tượng được<br /> ký và cấu trúc đồ thị chữ ký; sau đó bài báo minh họa như hình sau:<br /> thực hiện xây dựng đồ thị chữ ký và thuật toán<br /> truy vấn đối tượng trên đồ thị chữ ký đồng<br /> thời xây dựng mô hình ứng dụng; phần cuối<br /> cùng là kết luận.<br /> 2. CÁC KHÁI NIỆM CƠ SỞ<br /> 2.1. Chữ ký đối tượng<br /> Trong một cơ sở dữ liệu hướng đối tượng,<br /> mỗi đối tượng được biểu diễn bởi một tập các Hình 1. Một ví dụ về chữ ký của đối tượng.<br /> <br /> <br /> 60<br />  Truy vấn hướng đối tượng . . .<br /> <br /> 2.2. Đồ thị chữ ký tạp của việc tách nút là O(l3), với l là số chữ<br /> Định nghĩa 1. Một đồ thị chữ ký G đối ký trên một trang nút lá [11]. Để giải quyết<br /> với tập tin chữ ký S = s1.s2…sn, trong đó si≠ sj bài toán lưu trữ cơ sở dữ liệu hướng đối tượng<br /> (i≠j) và |sk| = m với k = 1,…, n, là một đồ thị và lưu trữ các đối tượng gần giống nhau trong<br /> G = (V, E) sao cho: cơ sở dữ liệu hướng đối tượng, cần phải xây<br /> 1. Mỗi nút v∈V có dạng (p, skip) với p là dựng một đồ thị chữ ký Gs có cấu trúc nhị<br /> con trỏ, trỏ đến chữ ký s trong S và skip là một phân nhưng vẫn có thể lưu trữ được danh sách<br /> số nguyên i không âm, gọi là bước nhảy bít. các chữ ký và cho phép truy ngược lại vị trí<br /> Nếu i > 0, bít thứ i của sq sẽ được kiểm tra khi của dữ liệu tương ứng, ta xây dựng một cấu<br /> tìm kiếm. Nếu i = 0, s sẽ được so sánh với sq. trúc Gs như sau:<br /> 2. Đặt e = (u,v)∈E. Lúc đó e được gán Định nghĩa 3. Đồ thị chữ ký Gs của lớp<br /> nhãn là 0 hoặc 1 và skip(u)>0. Đặt skip(u)=i. đối tượng có dạng: Gj (rj; v1,…, vn), với Gj mô<br /> Nếu e được gán nhãn là 0 và i>0 thì bít thứ i tả đồ thị chữ ký của lớp đối tượng thứ j, rj là<br /> của chữ ký được trỏ bởi p(v) là 0. Nếu e được nút gốc của đồ thị Gj và v1,…, vn là các nút của<br /> gán nhãn là 1 và i>0 thì bít thứ i của chữ ký đồ thị Gj. Mỗi nút u trong đồ thị Gj có dạng:<br /> được trỏ p(v) là 1. Một nút v với skip(u) = 0 < lp(u), skip (u) >, với lp(u) là danh sách các<br /> thì không có nút con. con trỏ tham chiếu đến các vị trí của chữ ký<br /> Định nghĩa 2. Cho S = s1.s2…sn là tập tin sig(u) trong tập tin chữ ký của lớp đối tượng<br /> chữ ký. Xét si (1 ≤ i ≤ n). Nếu tồn tại dãy và skip(u) là bước nhảy bít.<br /> j1,…, jh sao cho với mọi k ≠ i (1 ≤ k ≤n) ta có Ví dụ như hình vẽ sau đây minh họa tập<br /> si (j1,…, jh) ≠ sk (j1,…,jh), lúc đó ta nói si (j1,…, tin chữ ký và đồ thị chữ ký:<br /> jh) định danh chữ ký si hoặc si (j1,…,jh) là một<br /> định danh của si đối với S.<br /> 3. XÂY DỰNG ĐỒ THỊ CHỮ KÝ VÀ<br /> THUẬT TOÁN TRUY VẤN ĐỐI TƯỢNG<br /> 3.1. Cấu trúc đồ thị chữ ký<br /> Trong tập tin chữ ký có thể sẽ xuất hiện<br /> nhiều chữ ký giống nhau ứng với các đối<br /> tượng có nội dung giống nhau, quá trình truy Hình 2. Tập tin chữ ký và đồ thị chữ ký<br /> vấn cần tìm ra tất cả vị trí xuất hiện của đối Tại mỗi nút của đồ thị chữ ký sẽ lưu trữ<br /> tượng phù hợp. Đồ thị chữ ký G theo định danh sách con trỏ tham chiếu đến các chữ ký<br /> nghĩa 1 chỉ có thể lưu trữ các chữ ký đơn lẻ gần giống nhau nhưng có vị trí xuất hiện khác<br /> tại nút và cũng không thể lưu trữ được các nhau trong tập tin chữ ký.<br /> chữ ký giống nhau có tham chiếu đến các đối 3.2. Thuật toán tạo đồ thị chữ ký<br /> tượng trong cơ sở dữ liệu. Hơn nữa, việc lưu Thuật toán tạo ra đồ thị chữ ký được xây<br /> trữ danh sách các chữ ký có thể sử dụng cây dựng như sau:<br /> S-tree [3, 11] là dạng cây nhiều nhánh cân Vào: Lớp<br /> bằng tương tự như B+tree, tuy nhiên quá trình Ra: Đồ thị chữ ký<br /> tạo ra cây S-tree và xử lý quá trình tách nút để Phương pháp 1. Gen-Gs(lớp)<br /> cân bằng lại cây tương đối phức tạp, độ phức Begin<br /> <br /> <br /> 61<br /> Tạp chí Kinh tế - Kỹ thuật<br /> <br /> objs = {oj | oj∈ class, j = 1,…, n} Trong thuật toán tạo đồ thị chữ ký, vì mỗi<br /> Lp(root) = null; Sig1 = Hashing(o1); lớp là hữu hạn có đối tượng, đặt:<br /> Lp(root) = Lp(root) ∪ sig1; objs={oj| oj ∈ class, j = 1,…, n}<br /> root = ; Do đó, sẽ tạo được tập hữu hạn có chữ ký<br /> j = 2; đối tượng:<br /> Bước 1. Tạo chữ ký Sigj = Hashing(oj); Sig={sigj | sigj = Hashing (oj), j = 1,…, n}<br /> v ← root; Với mỗi giá trị j, thuật toán sẽ duyệt từ nút<br /> Qua bước 2; gốc của đồ thị Gs để đi tìm nút phù hợp, quá<br /> Bước 2. If (v không đánh dấu và skip trình này là hữu hạn vì số nút tạo ra trong đồ<br /> (root) ≠ 0) then Qua bước 3; thị Gs là hữu hạn. Nên thuật toán sẽ tìm được<br /> Else{i ← Skip(v) đánh dấu v; nút phù hợp để đưa chữ ký sigj vào hoặc tạo<br /> If (Sigv[i] = 1) then v = v→Right; ra một nút mới. Vì vậy, sau hữu hạn bước ứng<br /> Else v = v→Left; với giá trị của j = 1,…, n thì thuật toán cho kết<br /> Quay lại bước 2; } quả là một đồ thị chữ ký Gs với các nút trong<br /> Bước 3. u có dạng < lp(u), skip(u) >.<br /> If (Sigj = Sigv)then Gọi n là số đối tượng trong một lớp, khi<br /> { Lp(v) = Lp(v) ∪ Sigj; đó n=|objs|. Đồ thị chữ ký là dạng đồ thị chữ<br /> j ← j + 1; Quay lại bước 1; } ký và mỗi lần duyệt đồ thị chữ ký sẽ duyệt<br /> Else{o ← v; s=; Qua bước 4;} theo nhánh con bên trái hoặc nhánh bên phải,<br /> Bước 4. nên sẽ có 2(k-1) lần duyệt, với k ≈ 0,1,…, [log2<br /> Gọi k+1 là vị trí khác nhau đầu tiên giữa n]. Vì có n chữ ký lần lượt đưa vào đồ thị chữ<br /> Sigj và Sigv; ký Gs, nên số lần duyệt đồ thị tối đa sẽ là: ≈n.<br /> Thay thế nút v trở thành: Tuy nhiên, trong đồ thị chữ ký Gs sẽ lần lượt<br /> ; kiểm tra số bít trên mỗi chữ ký trong quá trình<br /> If (Sigj[k+1] = 1) then duyệt đồ thị, gọi m là chiều dài của mỗi chữ<br /> {v → Right = s; v → Left = o;} ký, chi phí của thuật toán tạo ra đồ thị chữ<br /> Else {v → Right = o; v → Left = s;} ký Gs sẽ là n.(2.m). Do đó, độ phức tạp trong<br /> j ← j + 1; Quay lại bước 1; trường hợp này sẽ là O(n.m).<br /> End.<br /> 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:<br /> <br /> <br /> <br /> <br /> Hình 3: Tạo đồ thị chữ ký<br /> 62<br />  Truy vấn hướng đối tượng . . .<br /> <br /> 3.3. Thuật toán truy vấn đối tượng trên sẽ không quay lại một nút sẽ đi qua. Thuật<br /> đồ thị chữ ký toán sẽ đối sánh chữ ký truy vấn và chữ ký<br /> Sau khi đã tạo ra đồ thị chữ ký Gs, quá tại các nút. Quá trình đối sánh được thực hiện<br /> trình truy vấn hướng đối tượng ứng với yêu trên một hữu hạn các nút của đồ thị Gs. Nên<br /> cầu truy vấn sẽ được thực hiện. Dữ liệu cần sau hữu hạn bước thuật toán sẽ cho ra được<br /> truy vấn sẽ được băm thành dạng chữ ký theo kết quả là một danh sách LP gồm các con trỏ<br /> cùng phương pháp băm chữ ký trên đồ thị Gs, tham chiếu đến các vị trí của chữ ký truy vấn<br /> sau đó sẽ tiến hành tìm kiếm trên đồ thị chữ trong tập tin chữ ký.<br /> ký Gs. Kết quả của quá trình tìm kiếm này là Trong phương pháp 2, gọi n là số nút đã<br /> một danh sách các con trỏ liên kết đến vị trí được tạo ra trong Gs, mỗi lần duyệt đồ thị có<br /> chữ ký trong tập tin chữ ký của cơ sở dữ liệu thể đi theo hai nhánh của đồ thị Gs nên số lần<br /> hướng đối tượng tương ứng. duyệt đồ thị sẽ là 2k, với k≈0,1,2,…,[log2n].<br /> Thuật toán truy vấn chữ ký sig trên đồ thị Khi đó, chi phí quá trình duyệt đồ thị để tìm<br /> Gs được thực hiện như sau: kiếm tối đa sẽ là log2n. Trong mỗi lần duyệt<br /> Vào: Chữ ký sig và đồ thị Gs đồ thị sẽ kiểm tra chữ ký tại các nút để thực<br /> Ra: Tập các con trỏ Lp liên kết đến các hiện bước nhảy bít và thực hiện đối sánh chữ<br /> chữ ký giống nhau nhưng có vị trí xuất hiện ký tại các nút, giả sử chiều dài của mỗi chữ ký<br /> khác nhau trong tập tin chữ ký. là m, chi phí quá trình tìm kiếm trên đồ thị Gs<br /> Phương pháp 2. Search-In-Gs(Gs, sig) sẽ là 2mlog2n. Do đó, độ lớn chi phí của thuật<br /> Begin toán sẽ là O(m.logn).<br /> Lp = ∅; v ← root; S = {v}; Một ví dụ về tìm kiếm trên đồ thị chữ ký<br /> Bước 1. If (S = ∅ ) then return Lp; dựa trên hình 2 được minh họa như sau:<br /> Else Chọn vj∈ S; S = S \ {vj};<br /> If (vj được đánh dấu) then Qua bước 2;<br /> Else { i ← Skip(vj);<br /> If sig[i] = 0 then<br /> S = S ∪ { vj →right, vj→left};<br /> Else S = S ∪ {vj→left};<br /> Quay lại bước 1;<br /> } Hình 4: Tìm kiếm trên đồ thị chữ ký<br /> Bước 2. If sig được phủ bởi Sig(vj) then<br /> Lp = Lp ∪ Lp(vj); Xét tập tin chữ ký và đồ thị chữ ký trên, giả<br /> Quay lại bước 1; sử rằng sq = 1011011 là chữ ký truy vấn, lúc<br /> End. đó chỉ một phần của đồ thị được tìm kiếm. Để<br /> Đối với phương pháp 2, vì Gs đã tạo ra tìm ra nút v, v được đánh dấu hoặc skip(v) =<br /> trong phương pháp 1 là hữu hạn nên tập S là 0 thì chữ ký của nút v sẽ được kiểm tra tương<br /> một tập hữu hạn chứa các phần tử vj sẽ được ứng với sq. Rõ ràng rằng cách tìm kiếm này<br /> duyệt ở các bước tiếp theo. hiệu quả hơn việc tìm kiếm tuần tự vì chỉ cần<br /> Khi duyệt một nút vj ∈S, thì vj sẽ được kiểm tra 2 chữ ký, trong khi đó phép duyệt tập<br /> loại ra khỏi tập S. Do đó việc duyệt đồ thị tin chữ ký sẽ kiểm tra 8 chữ ký.<br /> <br /> <br /> 63<br /> Tạp chí Kinh tế - Kỹ thuật<br /> <br /> 4. XÂY DỰNG MÔ HÌNH ỨNG DỤNG mỗi lớp có nhiều đối tượng. Ứng với mỗi lớp<br /> 4.1. Mô hình ứng dụng sẽ được xây dựng thành một cấu trúc đồ thị<br /> Cấu trúc đồ thị chữ ký được lưu trữ hoàn chữ ký tìm kiếm, đồng thời mỗi đối tượng này<br /> toàn bên trong bộ nhớ chính, trong trường sẽ tạo ra một chữ ký đối tượng. Chữ ký của<br /> hợp này, việc chèn và xóa một chữ ký trên đồ mỗi đối tượng được xây dựng trong mô hình<br /> thị được thực hiện dễ dàng. Tuy nhiên, trong này có chiều dài 128 bit, đó là sự tổ hợp các<br /> cơ sở dữ liệu các tập tin thường rất lớn, vì vậy thuộc tính trong một đối tượng. Toàn bộ cơ sở<br /> đồ thị chữ ký sẽ không thể lưu trữ trên bộ nhớ dữ liệu hướng đối tượng sẽ được phân hoạch<br /> chính mà phải được lưu trữ trên bộ nhớ ngoài. dưới dạng cấu trúc một bảng băm gồm các<br /> Đối với cơ sở dữ liệu hướng đối tượng, chúng chữ ký của đối tượng để thực hiện quá trình<br /> sẽ được lưu trữ và thực thi trên bộ nhớ ngoài. truy vấn.<br /> Cơ sở dữ liệu hướng đối tượng có nhiều lớp,<br /> <br /> <br /> <br /> <br /> 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<br /> <br /> 4.2. Một ví dụ về mô hình cơ sở dữ liệu đưa ra ở hình 6 đồng thời cũng đưa ra những<br /> hướng đối tượng quan hệ trên các lớp đối tượng bảng 1. Dựa<br /> Để thực nghiệm truy vấn hướng đối tượng trên mô hình này để thực nghiệm cài đặt cơ sở<br /> trên cơ sở dữ liệu hướng đối tượng. Một ví dụ dữ liệu hướng đối tượng ở mức vật lý.<br /> mô hình cơ sở dữ liệu hướng đối tượng được<br /> <br /> Bảng 1. Quan hệ các lớp<br /> <br /> S.No Class 1 Class 2 Relationship<br /> <br /> 1 University Dept Composition<br /> <br /> 2 University Student Aggregation<br /> <br /> 3 Student Programme Aggregation<br /> <br /> 4 Dept Instructor Aggregation<br /> <br /> 5 Student Male Generalization<br /> <br /> 6 Student Female Generalization<br /> <br /> 7 Programme Subject Aggregation<br /> <br /> <br /> <br /> 64<br />  Truy vấn hướng đối tượng . . .<br /> <br /> <br /> <br /> <br /> Hình 6: Một ví dụ mô hình cơ sở dữ liệu hướng đối tượng<br /> <br /> <br /> 4.3. Xử lý truy vấn trên cơ sở dữ liệu Bước 2. Đối sánh chữ ký từ khóa để xác<br /> hướng đối tượng định thuộc lớp cần truy vấn.<br /> Để thực hiện việc truy vấn một đối tượng Bước 3. Thực hiện truy vấn chữ ký từ<br /> trong cơ sở dữ liệu hướng đối tượng, đầu khóa trên đồ thị chữ ký tương ứng với các lớp<br /> tiên phải chuyển đổi cơ sở dữ liệu hướng đối đã xác định.<br /> tượng thành cấu trúc dữ liệu như trên, ta thực 5. KẾT LUẬN<br /> hiện như sau: Trong bài báo này, chúng tôi đã đề xuất<br /> Bước 1. Thuộc tính của đối tượng được thuật toán tạo đồ thị chữ ký để lưu trữ các<br /> băm thành chữ ký nhị phân và các thuộc tính chữ ký đối tượng của cơ sở dữ liệu hướng<br /> tạo thành chữ ký đối tượng. đối tượng và thuật toán truy vấn chữ ký đối<br /> Bước 2. Các chữ ký đối tượng của cùng tượng trên đồ thị chữ ký. Dựa trên cấu trúc đồ<br /> một lớp sẽ tạo thành đồ thị chữ ký. thị chữ ký đã tạo, bài báo tiến hành đề xuất<br /> Bước 3. Tạo danh sách đồ thị chữ ký mô hình ứng dụng cho cơ sở dữ liệu hướng<br /> tương ứng với từng lớp. đối tượng. Việc truy vấn trên đồ thị chữ ký<br /> Sau khi có cấu trúc dữ liệu để truy vấn, ta diễn ra tương đối nhanh, do đó có thể áp dụng<br /> thực hiện quá trình truy vấn đối tượng trong phương pháp này trong trường hợp truy vấn<br /> cơ sở dữ liệu hướng đối tượng như sau: các đối tượng dữ liệu lớn như đối tượng dữ<br /> Bước 1. Mã hoá từ khóa cần truy vấn liệu ảnh, các đối tượng multimedia, các đối<br /> thành chữ ký nhị phân. tượng trong hệ thống thông tin địa lý,…<br /> <br /> <br /> <br /> <br /> 65<br /> Tạp chí Kinh tế - Kỹ thuật<br /> <br /> TÀI LIỆU THAM KHẢO<br /> 1. Yangjun Chen, Yibin Chen, 2006,On the Signature Tree Construction and Analysis, IEEE Trans.<br /> Knowl. Data Eng., 18(9), 1207-1224.<br /> 2. Yangjun Chen, 2004, Building Signature Trees into OODBs, Journal of Information Science and<br /> Engineering, 20(2), 275-304.<br /> 3. I.E. Shanthi, R. Nadarajan, 2009, Applying SD-Tree for Object-Oriented Query Processing,<br /> Informatica (Slovenia), 33(2), 169-179.<br /> 4. D. L. Lee, Y. M. Kim, G. Patel, 1995, Eficient Signature File Methods for Text Retrieval, IEEE<br /> Trans. Knowl. Data Eng., 7(3), 423-435.<br /> 5. Walter W.Chang, Hans J. Schek, 1989, A signature Access Method for the Starburst Database<br /> System, Proceedings of the Fifteenth International Conference on Very Large Database, Amsterdam,<br /> 145-153.<br /> 6. W. C. Lee, D. L. Lee, 1992, Signature File Methods for Indexing Object-Oriented Database systems,<br /> Proceedings of the 2nd International Computer Science Conference, Hong Kong, 616-622.<br /> 7. Yangjun Chen, 2006, On the cost of searching signature trees, Science Direct, Information Processing<br /> Letters, 99(1), 19-26.<br /> 8. Yangjun Chen, 2002, Signature iles and signature trees, Elsevier Science, Journal Information<br /> Processing Letters, 82(4), 213-221.<br /> 9. Yangjun Chen, Yibin Chen, 2004, Signature File Hierarchies and Signature Graphs: a New<br /> Index Method for Object-Oriented Databases, Proceedings of the 2004 ACM symposium on<br /> Applied computing, Nicosia, Cyprus, 724-728.<br /> 10. E.Tousidoua, P. Bozanis, Y. Manolopoulos, 2002, Signature-basedstructuresforobjectswithset-<br /> valued attributes, Elsevier Science, Information Systems, 27(2), 93-121.<br /> 11. Y.Chen, 2005, On the Signature Trees and Balanced Signature Trees, Proceedings of the 21st<br /> International Conference on Data Engineering, IEEE Computer Society, Tokyo, Japan, 742-753.<br /> 12. P.Mahatthanapiwat, 2010, Flexible Searching for Graph Aggregation Hierarchy, Proceedings of the<br /> World Congress on Engineering 2010, London, UK, 405-409.<br /> <br /> <br /> <br /> <br /> 66<br />