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.