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

59 Truy vấn hướng đối tượng . . . TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ NHỊ PHÂN Trương Công Tuấn*, Trần Minh Bảo** TÓM TẮT 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 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 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ô hình ứng dụng. 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ý OBJECT-ORIENTED QUERY PROCESSING BASED BINARY SIGNATURE GRAPH ABSTRACT In this paper, we construct a graph structure model to store object signatures in object- oriented databases, in which the objects are hash encoded and presented by a signature graph. Then we built an algorithm to process the query on signature graph and propose an application model. Keyword: Object-oriented database; index structure; signature; signature ile; signature graph. * PGS.TS. Trường Đại học Khoa học, Đại học Huế. E-Mail: tctuan_it_dept@yahoo.com ** ThS. GV. Trường Đại học Công nghiệp Thực phẩm Tp.HCM. E-Mail: tmbaovn@gmail.com 1. ĐẶT VẤN ĐỀ Truy vấn trực tiếp trên các đối tượng trong cơ sở dữ liệu hướng đối tượng rất tốn kém chi phí lưu trữ dữ liệu trong quá trình truy vấn và tốn nhiều thời gian để thực hiện truy vấn trên hệ thống dữ liệu thực. Bài toán đặt ra là cần mô tả lại hệ thống dữ liệu đơn giản hơn và xây dựng cấu trúc dữ liệu tương ứng để có thể giảm không gian tìm kiếm trong quá trình thực thi câu truy vấn mà vẫn đảm bảo được việc truy vấn được các đối tượng cần thiết. Các phương pháp truy vấn dựa trên chữ ký nhị phân đã công bố như: truy vấn đối tượng trên cây chữ ký SD-Tree [3], truy vấn đối tượng trong cơ sở dữ liệu hướng đối tượng dựa trên cấu trúc cây chữ ký đối tượng [2], xây dựng cấu trúc tập tin chữ ký và cây chữ ký [8], xây dựng cấu trúc đồ thị chữ ký dựa trên tập tin chữ ký để truy vấn trong cơ sở dữ liệu hướng đối tượng [9, 12], xây dựng cấu trúc cây chữ ký để giảm không gian tìm kiếm dữ liệu [1, 2, 7, 10], truy vấn dữ liệu trên tập tin vĕn bản bằng tập tin chữ ký tuần tự và tập tin chữ ký phân mảnh [4], tạo chỉ mục truy vấn cho các tập tin vĕn bản [5, 6], tạo cấu trúc cây chữ cân bằng và thao tác trên cây chữ ký cân bằng [1, 8], 60 Tạp chí Kinh tế - Kỹ thuật Bài báo sẽ tiếp cận phương pháp tạo chữ ký cho các đối tượng, từ đó xây dựng cấu trúc đồ thị để tham chiếu đến cơ sở dữ liệu thực. Chữ ký nhỏ hơn rất nhiều so với đối tượng thực, khoảng từ 10% – 20% so với đối tượng [4, 5, 8]. Chữ ký của các đối tượng sẽ được lưu trữ trong tập tin chữ ký và qua đó thực hiện phép truy vấn các đối tượng dựa trên tập tin chữ ký này. Ngoài ra, để việc tìm kiếm hiệu quả hơn, cần xây dựng cấu trúc dữ liệu lưu trữ tập tin chữ ký. Cấu trúc lưu trữ tập tin chữ ký này có thể dưới dạng các tập tin chữ ký tuần tự, các tập tin chữ ký phân mảnh, cấu trúc cây chữ ký, cấu trúc dạng đồ thị chữ ký, các cấu trúc lưu trữ tập tin chữ ký sẽ làm giảm không gian tìm kiếm và tối ưu quá trình truy vấn dữ liệu. Bài báo mô tả lại hệ thống dữ liệu thực trở thành một cấu trúc dữ liệu tham chiếu có không gian tìm kiếm nhỏ hơn để từ đó giảm thời gian truy vấn dữ liệu và đồng thời cấu trúc dữ liệu tham chiếu trung gian này có thể truy vấn ngược lại dữ liệu thực sự. Kết quả của bài báo sẽ tập trung vào việc xây dựng cấu trúc lưu trữ tập tin chữ ký dưới 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 đầu của bài báo sẽ giới thiệu khái quát về chữ ký cho các đối tượng; tiếp theo bài báo giới thiệu các khái niệm cơ bản về chữ ký và cấu trúc đồ thị chữ ký; sau đó bài báo thực hiện 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ùng là kết luận. 2. CÁC KHÁI NIỆM CƠ SỞ 2.1. Chữ ký đối tượng Trong một cơ sở dữ liệu hướng đối tượng, mỗi đối tượng được biểu diễn bởi một tập các giá trị thuộc tính. Chữ ký của một giá trị thuộc tính là một chuỗi bít được mã hóa bằng hàm bĕm, có độ dài với bít 1 và bít 0. Chữ ký đối tượng được xây dựng bằng phép toán OR bít cho tất cả các chữ ký của các giá trị thuộc tính của đối tượng [1]. 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ý. Tập tin chữ ký tuần tự SSF (Sequential Signature File) gồm các chữ ký đối tượng được lưu trữ tuần tự [1, 3, 8]. Một câu truy vấn chỉ định các giá trị cần tìm kiếm cũng sẽ được mã hóa thành chữ ký truy vấn giống như cách mã hóa chữ ký các giá trị thuộc tính của đối tượng. 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: 1. Đối tượng phù hợp với câu truy vấn, nghĩa là đối với mọi tập bít trong chữ ký truy vấn sq, tập bít tương ứng trong chữ ký đối tượng s cũng chính là nó, tức là sq ∧ s = sq; 2. Đối tượng không phù hợp với câu truy vấn, nghĩa là sq ∧ s ≠ sq ; 3. Chữ ký được đối sánh và cho ra một kết quả phù hợp nhưng đối tượng không phù hợp với điều kiện tìm kiếm trong câu truy vấn. Để loại ra trường hợp này, các đối tượng phải được kiểm tra sau khi các chữ ký đối tượng được đối sánh phù hợp. Một ví dụ về chữ ký của đối tượng được minh họa như hình sau: Hình 1. Một ví dụ về chữ ký của đối tượng. 61 Truy vấn hướng đối tượng . . . 2.2. Đồ thị chữ ký Định nghĩa 1. Một đồ thị chữ ký G đối với tập tin chữ ký S = s 1 .s2sn, trong đó si≠ sj (i≠j) và |sk| = m với k = 1,, n, là một đồ thị G = (V, E) sao cho: 1. Mỗi nút v∈V có dạng (p, skip) với p là con trỏ, trỏ đến chữ ký s trong S và skip là một số nguyên i không âm, gọi là bước nhảy bít. Nếu i > 0, bít thứ i của sq sẽ được kiểm tra khi tìm kiếm. Nếu i = 0, s sẽ được so sánh với sq. 2. Đặt e = (u,v)∈E. Lúc đó e được gán nhãn là 0 hoặc 1 và skip(u)>0. Đặt skip(u)=i. Nếu e được gán nhãn là 0 và i>0 thì bít thứ i của chữ ký được trỏ bởi p(v) là 0. Nếu e được gán nhãn là 1 và i>0 thì bít thứ i của chữ ký được trỏ p(v) là 1. Một nút v với skip(u) = 0 thì không có nút con. Định nghĩa 2. Cho S = s 1 .s2sn là tập tin chữ ký. Xét si (1 ≤ i ≤ n). Nếu tồn tại dãy j 1 ,, jh sao cho với mọi k ≠ i (1 ≤ k ≤n) ta có si (j1,, jh) ≠ sk (j1,,jh), lúc đó ta nói si (j1,, jh) định danh chữ ký si hoặc si (j1,,jh) là một định danh của si đối với S. 3. XÂY DỰNG ĐỒ THỊ CHỮ KÝ VÀ THUẬT TOÁN TRUY VẤN ĐỐI TƯỢNG 3.1. Cấu trúc đồ thị chữ ký Trong tập tin chữ ký có thể sẽ xuất hiện nhiều chữ ký giống nhau ứng với các đối tượng có nội dung giống nhau, quá trình truy vấn cần tìm ra tất cả vị trí xuất hiện của đối tượng phù hợp. Đồ thị chữ ký G theo định nghĩa 1 chỉ có thể lưu trữ các chữ ký đơn lẻ tại nút và cũng không thể lưu trữ được các chữ ký giống nhau có tham chiếu đến các đối tượng trong cơ sở dữ liệu. Hơn nữa, việc lưu trữ danh sách các chữ ký có thể sử dụng cây S-tree [3, 11] là dạng cây nhiều nhánh cân bằng tương tự như B+tree, tuy nhiên quá trình tạo ra cây S-tree và xử lý quá trình tách nút để cân bằng lại cây tương đối phức tạp, độ phức tạp của việc tách nút là O(l3), với l là số chữ ký trên một trang nút lá [11]. Để giải quyết bài toán lưu trữ cơ sở dữ liệu hướng đối tượng và lưu trữ các đối tượng gần giống nhau trong cơ sở dữ liệu hướng đối tượng, cần phải xây dựng một đồ thị chữ ký Gs có cấu trúc nhị phân nhưng vẫn có thể lưu trữ được danh sách các chữ ký và cho phép truy ngược lại vị trí của dữ liệu tương ứng, ta xây dựng một cấu trúc Gs như sau: Định nghĩa 3. Đồ thị chữ ký Gs của lớp đối tượng có dạng: Gj (rj; v1,, vn), với Gj mô tả đồ thị chữ ký của lớp đối tượng thứ j, rj là nút gốc của đồ thị Gj và v1,, vn là các nút của đồ thị Gj. Mỗi nút u trong đồ thị Gj có dạng: , với lp(u) là danh sách các con trỏ tham chiếu đến các vị trí của chữ ký sig(u) trong tập tin chữ ký của lớp đối tượng và skip(u) là bước nhảy bít. Ví dụ như hình vẽ sau đây minh họa tập tin chữ ký và đồ thị chữ ký: Hình 2. Tập tin chữ ký và đồ thị chữ ký Tại mỗi nút của đồ thị chữ ký sẽ lưu trữ danh sách con trỏ tham chiếu đến các chữ ký gần giống nhau nhưng có vị trí xuất hiện khác nhau trong tập tin chữ ký. 3.2. Thuật toán tạo đồ thị chữ ký Thuật toán tạo ra đồ thị chữ ký được xây dựng như sau: Vào: Lớp Ra: Đồ thị chữ ký Phương pháp 1. Gen-Gs(lớp) Begin 62 Tạp chí Kinh tế - Kỹ thuật objs = {oj | oj∈ class, j = 1,, n} Lp(root) = null; Sig 1 = Hashing(o 1 ); Lp(root) = Lp(root) ∪ sig 1 ; 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ý, 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.