Truy vấn hướng đối tượng dựa trên phân cấp tập tin chữ ký và cây Sd-Tree

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.000213 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN PHÂN CẤP TẬP TIN CHỮ KÝ VÀ CÂY SD-TREE Trần Minh Bảo1, Trương Công Tuấn2 1, 2 Trường Đại học Khoa học, Đại học Huế tmbaovn@gmail.com, tctuan_it_dept@yahoo.com TÓM TẮT - 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. Gần đây, có nhiều nghiên cứu tập trung vào việc giải quyết vấn đề đó bằng cách xây dựng các chỉ mục trên các lớp đơn, phân cấp lớp, hoặc phân cấp đối tượng lồng nhau. Trong bài báo này, chúng tôi sẽ đề xuất một phương pháp lập chỉ mục mới. Phương pháp này dựa trên kỹ thuật sử dụng tập tin chữ ký và cây SD-tree trong đó các tập tin chữ ký được tổ chức theo phân cấp để nhanh chóng lọc dữ liệu không thích hợp và mỗi tập tin chữ ký được lưu theo cấu trúc cây SD-tree nhằm tăng tốc độ quét chữ ký. Kỹ thuật này giúp giảm đáng kể không gian tìm kiếm và do đó sẽ cải thiện đáng kể độ phức tạp thời gian truy vấn. Từ khóa - Hệ thống cơ sở dữ liệu hướng đối tượng, chỉ mục, tập tin chữ ký, cây SD-Tree, truy vấn hướng đối tượng. I. MỞ ĐẦU 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 và tốn nhiều thời gian để thực hiệ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. Để giảm không gian truy vấn dữ liệu, các kỹ thuật chỉ mục sử dùng đánh giá truy vấn trong CSDL được đề xuất trong [6] đã được phát triển dựa trên cơ chế thăng bằng cây nhị phân thêm vào một số tính chất đặc biệt để giảm việc cân bằng cây hoặc để tối thiểu hóa các truy cập vào tập tin dữ liệu. Các kỹ thuật này đã được phát triển tiếp nhằm tăng tốc truy vấn trong các CSDL hướng đối tượng [10, 11, 12]. Ý tưởng chính ở đây là mỗi cây SD-tree trên một lớp trong phân cấp lớp vẫn được duy trì nhưng các chỉ mục sẽ được lồng ghép với nhau bằng mối quan hệ lớp con – lớp mục tiêu. Ngoài các chỉ mục theo cấu trúc phân cấp thừa kế còn có rất nhiều các phương pháp lập chỉ mục dùng cho truy vấn thuộc tính lồng nhau đã được đề xuất [1, 2, 3, 7, 9]. Thay vì tập trung vào phân cấp thừa kế các lớp, các nhà nghiên cứu khác đã khám phá ra sự phân cấp tổng hợp các lớp và đề xuất các cấu trúc lập chỉ mục khác nhau theo các thuộc tính lồng nhau [1, 2, 7, 9] 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. Để 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ý, Trong đó, chi phí lưu trữ của tập tin chữ ký phân mảnh lại gấp đôi tập tin chữ ký tuần tự và chi phí cập nhật của tập tin chữ ký phân mảnh cũng gấp ba lần tập tin chữ ký tuần tự hoặc nhiều hơn [8]. Ưu điểm cơ bản của phương pháp tập tin chữ ký tuần tự nằm ở hiệu quả xử lý chèn và truy vấn mới lên các phần của từ. Tuy nhiên, khi so sánh với lập chỉ mục dựa trên cấu trúc cây thì các tập tin chữ ký liên tiếp lại bị hai nhược điểm, thứ nhất không thể được dùng để đánh giá các truy vấn phạm vi và thứ hai đối với mỗi truy vấn được xử lý thì toàn bộ tập tin chữ ký cần phải được quét làm tăng chi phí xử lý I/O. Trong bài báo này, chúng tôi sẽ cố gắng cải thiện vấn đề thứ hai đến một mức độ nào đó. Đầu tiên, chúng tôi tổ chức các tập tin chữ ký tuần tự sang cấu trúc phân cấp dùng để giảm bớt không gian tìm kiếm trong quá trình đánh giá truy vấn. Tiếp theo, chúng tôi lưu trữ tập tin chữ ký dưới dạng cây SD-tree, nhằm tiến hành quét chỉ một tập tin chữ ký đơn nhất. Nếu tập tin chữ ký có kích thước lớn thì khối lượng thời gian tiết kiệm được bằng phương pháp này là rất đáng kể. Cây SD-tree được xây dựng dựa trên tập tin chữ ký. Do đó, nó có thể tăng tốc quá trình xác định vị trí chữ ký trong một tập tin chữ ký. Tuy nhiên, trong cây SD-tree, mỗi đường dẫn sẽ tương ứng với một định danh chữ ký có thể dùng để xác định duy nhất chữ ký tương ứng với nó trong tập tin chữ ký. Cách này giúp nhanh chóng tìm ra một tập hợp các chữ ký phù hợp với chữ ký truy vấn. Bài báo này được tổ chức như sau. Trong phần II, chúng tôi đưa ra một số kiến thức cơ sở. Tại phần III, chúng tôi sẽ giới thiệu cấu trúc dữ liệu và thuật toán truy vấn. Phần IV đề xuất phương pháp kết hợp phân cấp tập tin chữ ký và cây SD-tree. Cuối cùng, phần V sẽ đưa ra một kết luận. II. MỘT SỐ KHÁI NIỆM CƠ SỞ A. Chữ ký thuộc tính 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. Cho trước một giá trị thuộc tính, ví dụ chữ “truong”, phân giải nó thành một chuỗi các bộ ba chữ cái như sau: “tru”, “ruo”, “uon” và “ong”. Sau đó, dùng hàm băm h, ánh xạ một bộ ba thành một số nguyên k với ý nghĩa là bit thứ k trong chuỗi sẽ được đặt giá trị 1. 730 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN PHÂN CẤP TẬP TIN Ví dụ, giả sử có h(tru) = 2, h(ruo) = 7, h(uon) = 10, and h(ong) = 11. Sau đó thiết lập một chuỗi bit: 010 000 100 110 làm chữ ký cho từ. B. Chữ ký đối tượng, tập tin chữ ký 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ụ 1. Xét một đối tượng có các giá trị thuộc tính lần lượt là “truong”, “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. C. 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: (i) Đối tượng phù hợp với truy vấn, nghĩa là đối với mọi bit trong chữ ký truy vấn ݏ௤, bit tương ứng trong chữ ký đối tượng s cũng chính là nó, tức là ݏ௤ ∧ ݏ ൌ ݏ௤, đối tượng thực sự chứa từ truy vấn; (ii) Đối tượng không phù hợp với câu truy vấn, nghĩa là ݏ௤ ∧ ݏ ് ݏ௤; (iii) 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 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. Ví dụ 2. Ví dụ này minh họa việc truy vấn đối với chữ ký đối tượng ở ví dụ 1: Truy vấn Chữ ký truy vấn Kết quả truong 010 000 100 110 thành công binh 011 000 100 100 không thành công duong 110 100 100 000 thành công nhưng không phù hợp Nhận xét: Việc so sánh chữ ký truy vấn sq với chữ ký đối tượng s là loại đối sánh không chính xác. Nghĩa là, chữ ký truy vấn sq phù hợp chữ ký s nếu mọi bit 1 trong sq, các bit tương ứng trong s cũng là bit 1. Tuy nhiên, đối với mọi bit 0 trong sq thì không quan trọng bit tương ứng trong s là 0 hay 1. III. CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN TRUY VẤN A. Truy vấn trong cơ sở dữ liệu hướng đối tượng Trong các hệ thống CSDL hướng đối tượng, một thực thể sẽ được biểu diễn dưới dạng đối tượng bao gồm các phương thức và thuộc tính. Các đối tượng có cùng tập thuộc tính và phương thức được nhóm lại với nhau trong cùng một lớp. Nếu một lớp C có một thuộc tính phức hợp với miền C' thì sẽ thiết lập quan hệ giữa C và C'. Quan hệ này được gọi là mối quan hệ tổng hợp. Khi dùng mũi tên kết nối các lớp này để biểu diễn mối quan hệ tổng hợp thì một phân cấp tổng hợp có thể được xây dựng để hiển thị cấu trúc lồng nhau của các lớp. Ví dụ 3. Một ví dụ về hệ thống phân cấp đối tượng lồng nhau được minh họa như sau: Hình 1. Một ví dụ về hệ thống phân cấp đối tượng lồng nhau SinhVien - HoTen: char - Truong: Truong - NganhHoc: NganhHoc - NoiSinh: char - GioiTinh: byte - ThanNhan: ThanNhan Truong - Khoa: Khoa - TenTruong: char - DiaChiTruong: char Khoa - TenKhoa: char - DiaChiKhoa: char NganhHoc - MonHoc: MonHoc - TenNganh: char MonHoc - TenMon: char - SoTC: int ThanNhan - HoTen: char - NoiSinh: char - GioiTinh: byte Ttr th d t T c đ c tr t V d c đ th c t Đ c c rần Minh Bảo, T Nếu đố ong o’ còn o Trong C uộc tính. Thu Ví dụ 4 iễn như sau: Select S Where And Sin Nếu kh iên, hệ thống iếp đó hệ thố ủa trường. Cu ược trả về. B. Phân 1. Phân Mục đí hữ ký không ánh được việ ập tin chữ ký (i) Chữ k phức (ii) Chữ k phức (iii) Giả sử có mộ (iv) Gọi S thì cũ í dụ 5. Chữ k Xét lớp ựng bằng phư ủa o và s(o) k ược tạo ra th uộc tính phứ ho đối tượng ập tin chữ ký 2. Thuậ ịnh nghĩa 1: ó dạng: <giá ây truy vấn, k rương Công Tuấn i tượng o đượ ’ sẽ được gọi l SDL hướng ộc tính này c . Truy vấn “ inhVien SinhVien.Noi hVien.Truon ông có cấu trú phải tìm kiếm ng sẽ tìm các ối cùng, nhữ cấp tập tin c cấp tập tin c ch của việc sử phù hợp với c c truy cập kh của nó như sa ý của đối tượ hợp của nó. ý của thuộc hợp là chữ ký C là ký hiệu t mục <osig, i và Sj là hai t ng ngầm định ý và phân cấ “Khoa” trong ơng pháp nh ý hiệu chữ k eo cùng cách c hợp là chữ k của lớp “Truo mà có thể xây t toán truy v (Cây truy vấ trị toán tử thu ý hiệu là Qt. c tham chiếu à các đối tượn đối tượng, điề ó thể là thuộc tìm tất cả các Sinh = “Bến g.Khoa.TenK c chỉ mục th tất cả các đố đối tượng trư ng sinh viên c hữ ký và thu hữ ký dụng tập tin hữ ký truy vấ ông cần thiết u: ng được tạo tính nguyên t của đối tượn lớp với o1, .. oid> trong S. ập tin chữ ký có một mũi t p tập tin chữ H phân cấp lớp ư trong hình 2 ý của o. Đối v thức như đối ý của đối tượ ng” và đối tư dựng cho m ấn dựa trên t n) Gọi ݌ଵ ∧ ݌ ộc tính>. Lú là một thuộc g cha của o. u kiện tìm ki tính lồng nha sinh viên sin Tre” hoa = “Công ì truy vấn nói i tượng trong ờng có tham ó nơi sinh ở ật toán truy chữ ký là để n sẽ đảm bảo vào các đối tư ra bằng cách hủy được tạo g mà nó tham ., ol là các đối tương ứng liê ên từ Si đến S ký được minh ình 2. Chữ ký không các th (a), trong đó ới lớp các th với lớp chỉ c ng mà nó tha ợng o của lớ ột cơ sở dữ liệ ập tin chữ ký ଶ ∧ ݌௞ là đ c đó, tất cả cá tính của đối ếm trong truy u của lớp mụ h ở Bến Tre nghệ Thông trên có thể đư lớp “SinhVien chiếu là sinh “Bến Tre” và vấn lọc ra hầu h rằng đối tượn ợng này. Đố xếp chồng cá ra bằng cách chiếu. tượng của lớ n kết với các j. họa như sau và phân cấp tậ uộc tính phứ mỗi s(o, x) k uộc tính phức ác thuộc tính m chiếu được p “Khoa” là g u được hiển t iều kiện tìm k c đường dẫn x tượng o’, thì vấn được biể c tiêu. của Khoa Cô tin” ợc đánh giá t ” và lọc ra cá viên có nơi s thuộc khoa “ ết các đối tượ g liên quan v i với phân cấp c chữ ký của băm các giá p đó; tồn tại m lớp Ci và Cj. : p tin chữ ký c hợp tại hình ý hiệu chữ k hợp thì chữ nguyên thủy. minh họa ở h iá trị thuộc tí hị trong hình iếm trong tru uất hiện trong sau đó o đượ u diễn dưới d ng nghệ thôn heo trình tự t c đối tượng c inh ở “Bến Tr Công nghệ T ng không đủ ới chữ ký này tổng hợp, có tất cả các thu trị thuộc tính ột tập tin chữ Nếu tồn tại m 1. Chữ ký củ ý được tạo ra ký của các đố Sự khác biệt ình 2(b). Tron nh của “Khoa 1 được minh y vấn Q, tron điều kiện tìm c coi là được ạng một tổ h g tin” có thể rên xuống nh ó nơi sinh ở e” và kiểm tr hông tin” của điều kiện, ng sẽ bị bỏ qua thể xây dựng ộc tính nguy ; chữ ký của ký S mà oi ( ột mũi tên từ a đối tượng o cho giá trị th i tượng trong duy nhất là c g hình 2 (b), ” của o’. Mộ họa ở hình 2( g đó mỗi pi là kiếm sẽ tạo 731 lồng nhau ợp của các được biểu ư sau. Đầu “Bến Tre”. a tên khoa trường sẽ hĩa là một . Do đó sẽ phân cấp ên thủy và thuộc tính i = 1, ..., l) Ci đến Cj, được xây uộc tính x đó có thể hữ ký của o’ ký hiệu t phân cấp c). một vị từ thành một 732 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN PHÂN CẤP TẬP TIN Ví dụ 6. Cây truy vấn được minh họa như sau: Hình 3. Cây truy vấn Định nghĩa 2: (Cây chữ ký truy vấn) Gọi p1.p2 ... .pn là một đường dẫn trong cây truy vấn Qt. Gọi <pi ... .pn giá trị toán tử> là một vị từ xuất hiện trong điều kiện tìm kiếm của Q. Lúc đó, chữ ký của pn là svalue. Chữ ký của một nút không phải nút lá Qt được tạo bằng phép toán logic OR cho các chữ ký của các nút con của nó. Cây chữ ký truy vấn được ký hiệu là Q(s,t). Vi dụ 7. Cây chữ ký truy vấn được minh họa như sau: Hình 4. Cây chữ ký truy vấn Sử dụng cây chữ ký truy vấn để giảm bớt không gian tìm kiếm. Phương pháp này, cần có hai cấu trúc ngăn xếp (stack) để điều khiển việc quét ưu tiên chiều sâu của các cấu trúc cây: stackq đối với Q(s,t) và stackc đối với phân cấp lớp. Trong stackq, mỗi thành phần là một chữ ký trong khi trong stackc, mỗi thành phần là một tập các đối tượng thuộc về cùng một lớp có thể tiếp cận được bằng cách quét phân cấp lớp. Thuật toán 1. [4] Tìm kiếm phân cấp theo kiểu trên xuống; Vào: Một truy vấn đối tượng Q; Ra: Một tập các OIDs thỏa mãn truy vấn. Phương pháp: Bước 1. Tính toán phân cấp chữ ký truy vấn Q(s,t) đối với Q. Bước 2. Đưa chữ ký gốc của Q(s,t) vào stackq; đẩy tập OID đối tượng của lớp mục tiêu vào stackc. Bước 3. Nếu stackq không rỗng, sq ← lấy ra stackq; ngược lại chuyển sang (Bước 7). Bước 4. S ← lấy stackc; với mỗi oidi E S, nếu chữ ký của nó osigi không so sánh với sq, thì loại ra khỏi S; đưa S vào Sresult. Bước 5. Gọi C là lớp các đối tượng của S; gọi C1, ..., Ck là các lớp con của C; sau đó phân chia tập OID của các đối tượng được tham chiếu bởi S vào S1, ..., Sk sao cho Si thuộc Ci; đẩy S1, ..., Sk vào stackc; đẩy các nút con của sq vào stackq. Bước 6. Chuyển đến (Bước 3). Bước 7. Đối với mỗi đối tượng lá, kiểm tra phù hợp nhưng không đúng. Kỹ thuật này giúp đạt được tối ưu hóa khi thực hiện bước (4). Tại bước này, một số đối tượng được lọc bằng cách sử dụng chữ ký tương ứng trong cây chữ ký truy vấn. Trong bước (5), các đối tượng được tham chiếu và các chữ ký của nút con của cây chữ ký truy vấn được tương ứng đưa vào stackc và stackq. Trong bước (7), thực hiện việc kiểm tra nhằm lẫn. SinhVien NoiSinh Truong Khoa TenKhoa SinhVien 110 110 100 110 NoiSinh 100 110 000 100 Truong 010 000 100 110 Khoa 010 000 100 110 TenKhoa 010 000 100 110 Bến Tre 100 110 000 100 Công nghệ Thông tin 010 000 100 110 TV tr v c “ k n “ c d t V b x c V tr t d t đ k v T c rần Minh Bảo, T í dụ 8. Giả ong hình 1 th Khi cả ấn, các chữ k hữ ký đầu tiê Truong” đượ hông phù hợp ó tham chiếu tìm kiếm trên C. Cây S 1. Tổng q Kỹ thuậ hữ ký). Trong ụng phương ích lũy trong m í dụ 9. Cây c Để xử l it 1 tại vị trí i ét sự xuất hiệ hữ ký của nút í dụ 10. Cho ị nút được so ạo thành cho anh sách chữ ố 0110010001 ơn. Tương iếm chữ ký c ị trí 11. Như 2. Thuật huật toán sau ác thuật toán rương Công Tuấn sử rằng một p uộc dạng đượ hai chữ ký đầ ý được tham n của “Truon c tham chiếu với chữ ký t sẽ không bị k xuống” vì tro D-tree uát về cấu tr t tạo chỉ mục công việc n pháp này cho ột nút đơn. hữ ký SD-tre ý một chữ ký trong Sq sẽ tì n cuối cùng c lá thứ i được Sq = 011001 sánh với vị t Sq bằng cách ký lưu trữ bi 0. Do đó, kh tự, chúng tôi ó trọng lượng vậy nút có giá toán truy vấn đây phác thả đều đến trực hần của phân c mô tả trong u của tập tin chiếu bởi chú g” được tham bởi chữ ký ương ứng tro iểm tra (xem ng “tìm kiếm úc SD-tree trong hệ thố ày, các vị trí một chữ ký Việc truy vấn e được minh truy vấn Sq: m thấy với sự ủa bit 0 tại v truy cập từ g 000101. Để t rí các bit của sử dụng vị trí t 1 dưới dạng ông kể tới m sử dụng SD-t trên 50%. B trị là 11 sẽ đ trên cây SD o các bước tì tiếp các nút c cấp tập tin c hình 5: Hình 5. Min chữ ký cho “ ng trong tập chiếu bởi ch thứ hai trong ng cây chữ ký minh họa tại trên xuống” p ng CSDL hướ của bit 0 và b truy vấn cho , con đường t họa như sau: Hình 6. (1) Đối với c tạo thành tiề ị trí i trong Sq ốc và tất cả c ìm tất cả các Sq. Sự xuất hi của bit 1 là 0 gom cụm và ẫu bit của Sq, ree để mô tả ây giờ, giả sử ược tìm kiếm -tree m kiếm chữ k hữ ký hồi đáp hữ ký được x h họa quá trình SinhVien” phù tin chữ ký ch ữ ký đầu tiên “SinhVien”. truy vấn. Vì phần màu xá hải tiến hành ng đối tượng it 1 trong chữ sẵn thì tất cả ìm kiếm tối ư Cây chữ ký SD hữ ký có trọn n tố trung gia sẽ tìm thấy v ác chữ ký với chữ ký khớp ện cuối cùng 1100100010. tất cả chữ ký tất cả các chữ bit 0 dưới dạn rằng Sq= 01 trong danh s ý khớp với ch lại 1 cuối cùn ây dựng cho truy vấn hợp với chữ o “Truong” sẽ trong “Sinh Có thể thấy r vậy tất cả cá m trong hình kiểm tra tất c ở đây bằng c ký được phâ các chữ ký t u được tính to -tree g lượng dưới n (B); (2) Đố ới sự tạo thà tiền tố (B) đư với Sq, cây SD của 1 trong S Một nút với g trong danh s ký trùng khớ g gom cụm. 1101110101. ách chữ ký lư ữ ký truy vấn g từ gốc. một CSDL v ký tương ứn được kiểm t Vien” trong k ằng chữ ký c chữ ký của 5). Việc này l ả các chữ ký ách sử dụng n bổ qua mộ rùng khớp đề án để đẩy nh 50% xét sự x i với chữ ký c nh tiền tố trun ợc truy vấn. -tree được x q là ở vị trí 12 iá trị khóa là ách chữ ký đ p đều được tr Điều này giúp Sự xuất hiện u trữ bit 0 dư cho trước Sq ới sơ đồ được g trong cây c ra bổ sung. G hi chữ ký thứ thứ hai trong đối tượng “K à tối ưu khi s đối tượng củ cây SD-tree t tập hợp các u có thể đượ anh toàn bộ q uất hiện cuố ó trọng lượng g gian (B). S ét kỹ từ gốc . Tiền tố nhị 12 được truy ược kiểm tra ả về trong m cải thiện thờ cuối cùng của ới dạng gom . Trong quá t 733 minh họa hữ ký truy iả sử rằng hai trong “Truong” hoa” được o sánh với a “Khoa”. (Phân cụm nút lá. Sử c truy vấn uá trình. i cùng của trên 50% au đó, nút và các giá phân được cập trong giá trị tiền ột truy cập i gian tìm bit 0 là ở cụm. rình F← 0 7 T V R P B B B B B B B tr v c h tr c c tr th 2 V V c tr h n 34 huật toán 2. ào: Chữ ký t a: Danh sách hương pháp ước 1. Tính ước 2. Nếu ước 3. Nếu ước 4. Truy ước 5. So sá ước 6. Nếu ước 7. Nếu A. Mô h Để cải úc dữ liệu tư iệc truy vấn đ ần kết hợp ph ơn. Từ [13], ên cây chữ k ây SD-tree để Dựa trê hữ ký và cây ình quét tập ực hiện kỹ th xác định chín í dụ 11. Tạo í dụ 12. Kết Cấu trú hữ ký trên câ úc dữ liệu sẽ ướng đối tượ hiều đối tượn [14] Tìm kiế ruy vấn. các chữ ký k : trọng lượng c trọng lượng c không thì tìm cập nút lá. nh tiền tố của tìm thấy thì đ không thì báo IV. PHƯƠ ình cấu trúc thiện thời gian ơng ứng để có ược các đối t ân cấp tập tin độ phức tạp th ý. Do đó, chú cải thiện thờ n cơ sở lý thu SD-tree như tin chữ ký; (2 uật lọc theo t h xác chữ ký cây SD-tree đ hợp phân cấp c dữ liệu đượ y SD-tree đượ không thể lư ng, được lưu g. Ứng với m m(Sq) hớp