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<br /> DOI: 10.15625/vap.2015.000212<br /> <br /> TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ<br /> Trần Minh Bảo1, Trương Công Tuấn2<br /> 1, 2<br /> Trường Đại học Khoa học, Đại học Huế<br /> tmbaovn@gmail.com, tctuan_it_dept@yahoo.com<br /> 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ữ<br /> 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<br /> 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ữ<br /> 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<br /> 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ô<br /> 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<br /> đề 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<br /> pháp này.<br /> Từ khóa - Truy vấn hướng đối tượng, chữ ký đối tượng, tập tin chữ ký, đồ thị chữ ký.<br /> <br /> I. MỞ ĐẦU<br /> 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<br /> 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<br /> 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<br /> 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<br /> đố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<br /> 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<br /> 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<br /> thấy trong nhiều công trình nghiên cứu [1] [2] [3] [8] [9].<br /> 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<br /> 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<br /> 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.<br /> 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ữ<br /> 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<br /> 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.<br /> II. MỘT SỐ KHÁI NIỆM CƠ SỞ<br /> 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 đủ<br /> hơn có thể xem trong [1] [2].<br /> A. Chữ ký đối tượng, tập tin chữ ký<br /> 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ý<br /> 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<br /> 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<br /> đối tượng:<br /> 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<br /> các đối tượng này là:<br /> 010 000 100 110<br /> 100 010 010 100<br /> 110 100 011 000<br /> 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<br /> logic OR.<br /> 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.<br /> B. Chữ ký truy vấn<br /> 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<br /> đố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ẽ<br /> 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<br /> có thể xảy ra:<br /> <br /> Trần Minh Bảo, T<br /> T<br /> Trương Công Tuấn<br /> n<br /> <br /> 723<br /> <br /> (1) Đối tư<br /> ượng phù hợp với truy vấn, nghĩa là đối với mọi bit tro chữ ký tru vấn<br /> p<br /> ,<br /> ong<br /> uy<br /> đối tư<br /> ượng s cũng ch<br /> hính là nó, tức là<br /> c<br /> <br /> ∧ =<br /> <br /> , bit tương ứng tro chữ ký<br /> ong<br /> <br /> , đối tượng th sự chứa từ truy vấn;<br /> hực<br /> ừ<br /> <br /> (2) Đối tư<br /> ượng không p hợp với câ truy vấn, ng là<br /> phù<br /> âu<br /> ghĩa<br /> <br /> ∧<br /> <br /> ≠<br /> <br /> ;<br /> <br /> (3) Chữ k được đối sá và cho ra một kết quả phù hợp nhưn đối tượng k<br /> ký<br /> ánh<br /> p<br /> ng<br /> không phù hợp với điều kiện tìm kiếm<br /> p<br /> n<br /> trong truy vấn. Để loại ra trườn hợp này, các đối tượng phải được kiể tra sau kh các chữ ký đối tượng<br /> ể<br /> ng<br /> ểm<br /> hi<br /> được đối sánh phù hợp.<br /> Ví dụ 2.2. Ví dụ này minh h việc truy vấn đối với ch ký đối tượn ở ví dụ 1.1 :<br /> V<br /> họa<br /> hữ<br /> ng<br /> T<br /> Truy vấn<br /> <br /> Chữ ký tr vấn<br /> ruy<br /> <br /> Kết quả<br /> <br /> D<br /> Dung<br /> <br /> 010 000 100 110<br /> <br /> thành công<br /> g<br /> <br /> B<br /> Binh<br /> <br /> 011 000 100 100<br /> <br /> không thàn công<br /> ành<br /> <br /> D<br /> Duong<br /> <br /> 110 100 100 000<br /> <br /> thành công nhưng khôn phù hợp<br /> g<br /> ng<br /> <br /> xét:<br /> ánh<br /> uy<br /> với chữ ký đối tư<br /> ượng s là loại đối sánh khô chính xác. Nghĩa là,<br /> i<br /> ông<br /> Nhận x Việc so sá chữ ký tru vấn<br /> chữ ký truy vấ<br /> c<br /> ấn phù hợp chữ ký s nếu mọi bit 1 tron<br /> ng , các bit tương ứng tro s cũng là b 1. Tuy nhiên, đối với<br /> ong<br /> bit<br /> mọi bit 0 trong thì không quan trọng bi tương ứng trong s là 0 hay 1.<br /> m<br /> g<br /> g<br /> it<br /> y<br /> III.<br /> <br /> ĐỒ THỊ CHỮ KÝ VÀ THUẬT TOÁ<br /> C<br /> T<br /> ÁN<br /> <br /> A. Đồ thị chữ ký<br /> A<br /> ữ<br /> Để tìm một chữ ký đ tượng tron tập tin chữ ký có phù hợ với chữ ký truy vấn, ta c phải quét một tập tin<br /> đối<br /> ng<br /> ợp<br /> cần<br /> m<br /> chữ ký đó. Nế tập tin là lớ thì thời gia để tìm kiếm trên một tập tin như vậy là đáng kể. Ý tưởng trước tiên để cải<br /> c<br /> ếu<br /> ớn<br /> an<br /> m<br /> p<br /> th quá trình này là sắp xế tập tin chữ ký và sau đó sử dụng việc tìm kiếm nhị p<br /> hiện<br /> h<br /> ếp<br /> t<br /> phân. Tuy nhi điều này không thực<br /> iên,<br /> k<br /> hiện được do v đối sánh t<br /> h<br /> việc<br /> trên tập tin ch ký là một đố sánh không chính xác. Ta xem ví dụ sa đây:<br /> hữ<br /> ối<br /> g<br /> a<br /> au<br /> Ví dụ 3.1. Xem tập tin chữ k đã được sắ xếp gồm 3 chữ ký đối tượ<br /> V<br /> m<br /> ký<br /> ắp<br /> c<br /> ợng:<br /> 010 0<br /> 000 100 110<br /> 100 0<br /> 010 010 100<br /> 010 1<br /> 100 011 000<br /> Giả sử chữ ký truy v s là 000 010 010 100. Nó phù hợp với chữ ký 10 010 010 10 Tuy nhiên nếu ta sử<br /> vấn<br /> v<br /> 00<br /> 00.<br /> n,<br /> dụng tìm kiếm nhị phân thì chữ ký 100 0<br /> d<br /> m<br /> 010 010 100 không thể tìm thấy. Mặt khá trong tập t chữ ký có thể sẽ xuất<br /> k<br /> ác,<br /> tin<br /> hiện nhiều chữ ký giống nhau ứng với cá đối tượng có nội dung giống nhau, quá trình truy vấ cần tìm ra tất cả vị trí<br /> h<br /> ữ<br /> ác<br /> á<br /> ấn<br /> t<br /> xuất hiện của đ tượng phù hợp. Vì lý do này, ta sẽ tổ chức tập tin chữ ký thành một đồ thị, gọ là đồ thị chữ ký nhằm<br /> x<br /> đối<br /> ù<br /> o<br /> ổ<br /> c<br /> ọi<br /> lư trữ được d<br /> ưu<br /> danh sách các c ký và cho phép truy ngược lại vị trí của dữ liệu tươ ứng. Ta c định nghĩa sau:<br /> chữ<br /> o<br /> c<br /> ơng<br /> có<br /> s<br /> Định nghĩa 3.1. Đồ thị chữ ký G đối với tập tin chữ ký S là một đồ thị có hướng G = (V, E) sa cho:<br /> Đ<br /> i<br /> ý<br /> ao<br /> 1.<br /> <br /> 2.<br /> <br /> Mỗi n u ∈ V có d<br /> nút<br /> dạng lp u , skip u , vớ lp u là dan sách các co trỏ tham chi đến các vị trí của chữ<br /> ới<br /> nh<br /> on<br /> iếu<br /> ký sig u trong tập tin chữ ký S v skip u là một số nguyên i không âm, gọi là bước n<br /> g<br /> p<br /> và<br /> ,<br /> nhảy nhảy bit. Nếu i 0,<br /> bit thứ i của chữ ký truy vấn s sẽ được kiểm tr khi tìm kiếm Nếu i 0, s u sẽ được so sánh với s .<br /> ứ<br /> ý<br /> ẽ<br /> ra<br /> m.<br /> sig<br /> c<br /> Đặt e<br /> u, v ∈ E Lúc đó e đư gán nhãn là 0 hoặc 1 và skip u<br /> E.<br /> ược<br /> v<br /> 0. Đặt skip u<br /> i. Nếu e được gán<br /> e<br /> nhãn là 0 và i 0 thì bit thứ i c chữ ký được trỏ bởi lp v là 0. Nếu e được gán nh là 1 và i 0 thì bit<br /> của<br /> hãn<br /> ược<br /> là<br /> 0 thì không có nút con.<br /> g<br /> thứ i của chữ ký đư trỏ lp v l 1. Một nút v với skip u<br /> <br /> Ví dụ 3.2. Hìn vẽ sau min họa một tập tin chữ ký và đồ thị chữ ký của nó:<br /> V<br /> nh<br /> nh<br /> p<br /> à<br /> ý<br /> <br /> Hìn 1. Minh họa tập tin chữ ký và đồ thị chữ ký<br /> nh<br /> a<br /> <br /> 724<br /> <br /> TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN ĐỒ THỊ CHỮ KÝ<br /> <br /> B. Thuật toán<br /> 1. Thuật toán tạo đồ thị chữ ký<br /> 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:<br /> Vào: Lớp đối tượng<br /> Ra: Đồ thị chữ ký<br /> Phương pháp:<br /> Begin<br /> objs = {oj | oj∈ class, j = 1,…, n}<br /> lp(root) = null; sig1 = Hashing(o1);<br /> lp(root) = lp(root) ∪ sig1;<br /> root = ;<br /> j = 2;<br /> Bước 1. Tạo chữ ký sigj = Hashing(oj);<br /> v ← root;<br /> Qua bước 2;<br /> Bước 2. if (v không đánh dấu và skip(root) ≠ 0 ) then Qua bước 3;<br /> else{i ← skip(v) đánh dấu v;<br /> if (sigv[i] = 1) then v = v→right;<br /> else v = v→left;<br /> Quay lại bước 2; }<br /> Bước 3.<br /> if (sigj = sigv) then<br /> { lp(v) = lp(v) ∪ sigj;<br /> j ← j + 1; Quay lại bước 1; }<br /> else{o ← v; s=; Qua bước 4;}<br /> Bước 4.<br /> Gọi k+1 là vị trí khác nhau đầu tiên giữa sigj và sigv;<br /> Thay thế nút v trở thành:<br /> ;<br /> if (sigj[k+1] = 1) then<br /> {v → right = s; v → left = o;}<br /> else {v → right = o; v → left = s;}<br /> j ← j + 1; Quay lại bước 1;<br /> End.<br /> 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:<br /> objs<br /> <br /> o o ∈ class, j<br /> <br /> 1, … , n <br /> <br /> Do đó, sẽ tạo được tập hữu hạn có n chữ ký đối tượng:<br /> sig sig<br /> <br /> Sig<br /> <br /> Hashing o , j<br /> <br /> 1, … , n<br /> <br /> 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ì<br /> 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<br /> 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<br /> với các nút u có dạng lp u , skip u .<br /> 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<br /> ( k −1 )<br /> lần duyệt, với k 0, 1, … , log n . Vì có n chữ ký lần lượt đưa vào đồ thị<br /> trái hoặc nhánh bên phải, nên sẽ có 2<br /> k<br /> <br /> ∑2<br /> i =0<br /> <br /> i<br /> <br /> Trần Minh Bảo, T<br /> T<br /> Trương Công Tuấn<br /> n<br /> <br /> 725<br /> <br /> chữ ký G , nên số lần duyệt đồ thị tối đa s là ≈ n. Tuy nhiên, trong đồ thị chữ ký G sẽ lần lượt kiểm tra số bit trên mỗi<br /> c<br /> n<br /> sẽ<br /> đ<br /> t<br /> b<br /> chữ ký trong q trình duyệ đồ thị, gọi m là chiều dài của mỗi chữ ký, chi phí của thuật toán tạ ra đồ thị ch ký G sẽ<br /> c<br /> quá<br /> ệt<br /> k<br /> a<br /> ạo<br /> hữ<br /> là n. 2. m . Do đó, độ phức tạp trong trườ hợp này sẽ là O n. m .<br /> c<br /> ờng<br /> s<br /> Ví dụ 3.3. Một ví dụ về tạo đồ thị chữ ký dựa trên tập tin chữ ký ở ví dụ 3.2 được minh họa như sau:<br /> V<br /> t<br /> í<br /> ư<br /> <br /> Hình 2. Tạo đồ thị ch ký<br /> 2<br /> hữ<br /> <br /> 2. Thuật toán truy vấn đối tư<br /> 2<br /> ượng trên đồ t chữ ký<br /> thị<br /> i<br /> g<br /> ng<br /> ầu<br /> Sau khi đã tạo ra đồ thị chữ ký G , quá trình truy vấn hướng đối tượng ứn với yêu cầ truy vấn sẽ được thực<br /> hiện. Dữ liệu c truy vấn sẽ được băm th<br /> h<br /> cần<br /> ẽ<br /> hành dạng chữ ký theo cùng phương pháp băm chữ ký trên đồ thị G , sau đó sẽ<br /> ữ<br /> g<br /> p<br /> tiến hành tìm k<br /> kiếm trên đồ t chữ ký G . Kết quả của quá trình tìm kiếm này là m danh sách các con trỏ li kết đến<br /> thị<br /> một<br /> h<br /> iên<br /> vị trí chữ ký tr<br /> v<br /> rong tập tin ch ký của cơ sở dữ liệu hướn đối tượng tương ứng.<br /> hữ<br /> ng<br /> t<br /> Thuật toán 2: Thuật toán tr vấn chữ ký sig trên đồ thị G được thự hiện như sa<br /> T<br /> :<br /> ruy<br /> ý<br /> ực<br /> au:<br /> Vào: Chữ ký s và đồ thị G<br /> V<br /> sig<br /> Ra: Tập các co trỏ lp liên k đến các ch ký giống nh nhưng có vị trí xuất hiệ khác nhau t<br /> R<br /> on<br /> kết<br /> hữ<br /> hau<br /> ện<br /> trong tập tin ch ký.<br /> hữ<br /> Phương pháp<br /> P<br /> p:<br /> Begin<br /> ot;<br /> lp = ∅; v ← roo S = {v};<br /> Bư 1. if (S = ∅ ) then retur lp;<br /> ước<br /> rn<br /> else<br /> e Chọn vj∈ S; S = S \ {vj};<br /> v<br /> if<br /> i (vj được đá dấu) then Qua bước 2;<br /> ánh<br /> n<br /> 2<br /> else<br /> e { i ← skip j);<br /> p(v<br /> if s<br /> sig[i] = 0 then<br /> n<br /> S = S ∪ { vj →right, vj→lef<br /> ft};<br /> else S = S ∪ {vj→left};<br /> Qu lại bước 1<br /> uay<br /> 1;<br /> }<br /> ước<br /> ược<br /> Bư 2. if sig đư phủ bởi sig(vj) then<br /> lp = lp ∪ lp(vj);<br /> Qu lại bước 1<br /> uay<br /> 1;<br /> End.<br /> Đối với thuật toán 2, vì G đã tạo r trong thuật toán 1 là hữu hạn nên tập S là một tập hữ hạn chứa các phần tử<br /> i<br /> ,<br /> ra<br /> ữu<br /> c<br /> v sẽ được duy ở các bước tiếp theo.<br /> yệt<br /> c<br /> Khi duy một nút v ∈ S, thì v sẽ được loại ra khỏi tập S. Do đó việc duyệ đồ thị sẽ kh<br /> yệt<br /> ẽ<br /> o<br /> ệt<br /> hông quay lại một nút sẽ<br /> đi qua. Thuật t<br /> đ<br /> toán sẽ đối sán chữ ký truy vấn và chữ ký tại các nút. Quá trình đối sánh được th hiện trên một số hữu<br /> nh<br /> y<br /> k<br /> i<br /> hực<br /> m<br /> hạn các nút củ đồ thị G . V vậy sau hữu hạn bước thu toán sẽ cho ra được kết quả là một da sách lp gồ các con<br /> h<br /> ủa<br /> Vì<br /> u<br /> uật<br /> o<br /> anh<br /> ồm<br /> tr tham chiếu đến các vị trí của chữ ký tr vấn trong tập tin chữ ký<br /> rỏ<br /> u<br /> í<br /> ruy<br /> ý.<br /> Trong t<br /> thuật toán 2, g n là số nút đã được tạo ra trong G , mỗi lần duyệt đ thị có thể đ theo hai nhánh của đồ<br /> gọi<br /> t<br /> m<br /> đồ<br /> đi<br /> th G nên số lần duyệt đồ th sẽ là 2k, với k 0, 1, 2, … , log n . Kh đó, chi phí quá trình duy đồ thị để tìm kiếm tối<br /> hị<br /> hị<br /> hi<br /> yệt<br /> m<br /> i<br /> <br /> 726<br /> 7<br /> <br /> TRUY VẤN HƯỚNG Đ TƯỢNG DỰ TRÊN ĐỒ TH CHỮ KÝ<br /> ĐỐI<br /> ỰA<br /> HỊ<br /> <br /> đa sẽ là log n. Trong mỗi l duyệt đồ t sẽ kiểm tra chữ ký tại cá nút để thực hiện bước n<br /> đ<br /> lần<br /> thị<br /> a<br /> ác<br /> c<br /> nhảy bit và thự hiện đối<br /> ực<br /> sánh chữ ký tạ các nút, giả sử chiều dài c mỗi chữ ký là m, chí ph quá trình tì kiếm trên đ thị G sẽ là 2mlog n.<br /> s<br /> ại<br /> của<br /> k<br /> hí<br /> ìm<br /> đồ<br /> à<br /> Do đó, độ lớn chi phí của th toán sẽ là O m. logn .<br /> D<br /> huật<br /> Một ví dụ về tìm kiếm trên đồ thị c ký dựa trê hình 2 được minh họa nh sau:<br /> m<br /> chữ<br /> ên<br /> c<br /> hư<br /> <br /> Hình 3. Tìm kiếm trên đồ thị chữ ký<br /> m<br /> t<br /> <br /> Xét tập tin chữ ký và đồ thị chữ ký trên, giả sử rằng s<br /> p<br /> à<br /> ý<br /> 1011011 là chữ ký truy vấn, lúc đó chỉ mộ phần của<br /> ữ<br /> ột<br /> 0 thì chữ ký của nút v sẽ được kiểm tra tương<br /> đồ thị được tìm kiếm. Để tìm ra nút v, v được đánh dấ hoặc skip v<br /> đ<br /> m<br /> m<br /> ấu<br /> ữ<br /> m<br /> ứng với s . Rõ ràng cách tìm kiếm này h<br /> ứ<br /> õ<br /> 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 đó<br /> v<br /> m<br /> hỉ<br /> a<br /> phép duyệt tập tin chữ ký sẽ kiểm tra 8 ch ký.<br /> p<br /> p<br /> ẽ<br /> hữ<br /> IV.<br /> <br /> Ô<br /> G<br /> MÔ HÌNH ỨNG DỤNG<br /> <br /> Cấu trú đồ thị chữ k được lưu tr hoàn toàn bên trong bộ nhớ chính, tro trường hợ này, việc ch và xóa<br /> úc<br /> ký<br /> rữ<br /> b<br /> n<br /> ong<br /> ợp<br /> hèn<br /> một chữ ký trê đồ thị được thực hiện dễ dàng. Tuy nh<br /> m<br /> ên<br /> c<br /> ễ<br /> hiên, trong cơ sở dữ liệu cá tập tin thườ rất lớn, vì vậy đồ thị<br /> ơ<br /> ác<br /> ờng<br /> chữ ký sẽ khôn thể lưu trữ trên bộ nhớ c<br /> c<br /> ng<br /> chính mà phải được lưu trữ trên bộ nhớ ng<br /> ngoài. Đối với cơ sở dữ liệu hướng đối<br /> g<br /> tư<br /> ượ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ó<br /> rữ<br /> i<br /> có<br /> m<br /> nhiều đối tượn Ứng với m lớp sẽ đư xây dựng thành một cấ trúc đồ thị chữ ký tìm k<br /> n<br /> ng.<br /> mỗi<br /> ược<br /> ấu<br /> kiếm, đồng thời mỗi đối<br /> tư<br /> ượng này sẽ t ra một chữ ký đối tượn Chữ ký của mỗi đối tượ được xây dựng trong m hình này có chiều dài<br /> tạo<br /> ữ<br /> ng.<br /> a<br /> ợng<br /> mô<br /> ó<br /> 64 bit, đó là sự tổ hợp các th<br /> 6<br /> ự<br /> huộc tính tron một đối tượ Toàn bộ cơ sở dữ liệu hướng đối tượ sẽ được phân hoạch<br /> ng<br /> ợng.<br /> ợng<br /> p<br /> dưới dạng cấu trúc một bảng băm gồm cá chữ ký của đối tượng để thực hiện quá trình truy vấn<br /> d<br /> g<br /> ác<br /> t<br /> n.<br /> <br /> Hình 4. Mô hình cấ trúc lưu trữ đồ thị chữ ký ch cơ sở dữ liệu hướng đối tượ<br /> h<br /> ấu<br /> đ<br /> ho<br /> u<br /> ợng<br /> <br /> A. Một ví dụ về mô hình c sở dữ liệu h<br /> A<br /> cơ<br /> hướng đối tượ<br /> ợng<br /> Để thực nghiệm truy vấn hướng đ tượng trên CSDL hướn đối tượng. M ví dụ mô hình CSDL hướng đối<br /> c<br /> y<br /> đối<br /> n<br /> ng<br /> Một<br /> ô<br /> tư<br /> ượng được đư ra ở hình 5 đồng thời cũ đưa ra nhữ quan hệ trên các lớp đ tượng ở bả 1. Dựa trê mô hình<br /> ưa<br /> ũng<br /> ững<br /> t<br /> đối<br /> ảng<br /> ên<br /> này để cài đặt CSDL hướng đối tượng ở m vật lý.<br /> n<br /> g<br /> mức<br /> Bản 1. Quan hệ của các lớp<br /> ng<br /> c<br /> <br /> TT<br /> <br /> Lớp 1<br /> <br /> Lớ 2<br /> ớp<br /> <br /> Qu n hệ<br /> <br /> 1<br /> <br /> Truong<br /> g<br /> <br /> Kh<br /> hoa<br /> <br /> Chứa trong<br /> g<br /> <br /> 2<br /> <br /> Truong<br /> g<br /> <br /> Sin<br /> nhVien<br /> <br /> Kết tập<br /> <br /> 3<br /> <br /> en<br /> SinhVie<br /> <br /> Ch<br /> huongTrinh<br /> <br /> Liên kết<br /> <br /> 4<br /> <br /> Khoa<br /> <br /> GiangVien<br /> <br /> Liên kết<br /> <br /> 5<br /> <br /> en<br /> SinhVie<br /> <br /> Nu<br /> u<br /> <br /> Khái quát q<br /> quá<br /> <br /> 6<br /> <br /> SinhVie<br /> en<br /> <br /> Na<br /> am<br /> <br /> Khái quát q<br /> quá<br /> <br /> 7<br /> <br /> Chuong<br /> gTrinh<br /> <br /> Ch<br /> huDe<br /> <br /> Liên kết<br /> <br />