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

áo đề xuất p ữ dưới dạng c theo cấu trú 1 nhằm xác ree họa như sau và cây SD-tree hính, trong tr ơ sở dữ liệu lưu trữ trên dữ liệu hướn trúc cây SD- NG DỰA TRÊN g các nút lá c KÝ VÀ CÂY ữ liệu đơn gi i câu truy vấ , để vấn đề tr inh là cải thiệ so với độ phứ [4], nhưng th hương pháp cấu trúc cây S c phân cấp đ định chữ ký t : ường hợp này các tập tin thư bộ nhớ ngoài g đối tượng c tree, đồng thờ PHÂN CẤP T ho các bit 0. SD-TREE ản hơn và xây n mà vẫn đảm uy vấn được n thời gian tr c tạp thời gia ay thế cây ch kết hợp phân D-tree để tă ể tạo thuật lợ huộc lớp nào, , việc chèn v ờng rất lớn, . Đối với cơ ó nhiều lớp, m i mỗi đối tượ ẬP TIN dựng cấu bảo được tối ưu hơn uy vấn tốt n truy vấn ữ ký bằng cấp tập tin ng tốc quá i cho việc thuật toán à xóa một vì vậy cấu sở dữ liệu ỗi lớp có ng này sẽ Trần Minh Bảo, Trương Công Tuấn 735 tạo ra một chữ ký đố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. B. Xử lý truy vấn 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 cây SD-tree. Bước 3. Tạo phân cấp tập tin chữ ký trong đó mỗi tập tin là cây SD-tree. 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. Thực hiện truy vấn 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 cây SD-tree tương ứng với các lớp đã xác định. C. Đánh giá độ phức tạp 1. So sánh tìm kiếm theo phương pháp Yong và phân cấp tập tin chữ ký Để ước tính số đối tượng được truy cập trong một truy vấn sử dụng hai phương pháp khác nhau: (1) phương pháp Yong được đề xuất trong [15]; (2) tìm kiếm phân cấp theo kiểu trên xuống [4]. (1) Phương pháp Yong Phương pháp Yong, chữ ký của một đối tượng bị tham chiếu sẽ được lưu trữ trong đối tượng tham chiếu. Sau đó, có thể tiến hành kiểm tra thuộc tính đối với các chữ ký của chúng trước khi truy cập. Bằng cách này sẽ tiết kiệm được rất nhiều phép toán I/O. (2) Tìm kiếm phân cấp theo kiểu trên xuống Phương pháp này, có khả năng lọc mạnh mẽ hơn so với phương pháp Yong. Điều này là do mỗi sự kiểm tra đối với một nút trong một phân cấp chữ ký truy vấn, không chỉ thuộc tính liên quan đến nút hiện hành mà còn có một số thuộc tính khác các ảnh hưởng của chúng sẽ được đưa lên một số đường dẫn tới nút đó. Sử dụng phân cấp chữ ký truy vấn, có nhiều đối tượng trong lớp mục tiêu sẽ bị loại bỏ bằng cách kiểm tra tập tin chữ ký tương ứng, điều này dẫn tới giảm bớt đáng kể tổng số các đối tượng truy cập. Trong [4], cho thấy rằng có thể đạt được hiệu suất cao bằng phương pháp tìm kiếm phân cấp trên xuống từ quan điểm trừu tượng, phân cấp chữ ký truy vấn là một bộ lọc “toàn cục” trong khi đó thì kỹ thuật nhân bản được Yong phát triển có thể coi là bộ lọc “cục bộ”. Cả hai đều giúp giảm số đối tượng truy cập. 2. So sánh độ phức tạp thời gian của cây chữ ký và cây SD-tree (i) Phương pháp cây chữ ký Trong [13, 14], độ phức tạp thời gian chèn vào cây chữ ký là O(nF), n là số chữ ký của tập tin và F là độ dài của chữ ký bao gồm bit 0 và bit 1. Với cây chữ ký, chiều cao của cây bị giới hạn là O(log2n), n là số nút lá. Chi phí tìm kiếm cây chữ ký trung bình là O(λ.log2n), trong đó λ là số đường đã đi qua. (ii) Phương pháp cây SD-tree Trong [13, 14], cây SD-tree sử dụng như cấu trúc chỉ mục cho tập hợp các dữ liệu lớn, giá trị F nhỏ thì sẽ giảm thời gian xây dựng SD-tree. Độ phức tạp thời gian chèn bị giới hạn là O(n.m) trong đó n là số chữ ký trong tập tin và m là số bit 1 trong chữ ký cho trước. Một đặc tính hữu ích khác của SD-tree là với giá trị F lớn hơn, bằng cách biến đổi p, giá trị h, chiều cao của cây có thể được giữ ở mức nhỏ để thúc đẩy tìm kiếm nhanh hơn được giới hạn là O(logp(F/p-1)). Thời gian tìm kiếm cho một truy vấn với tập hợp bit ở vị trí thứ i sau cùng là tổng thời gian truy cập nút lá (Tli) và thời gian tìm kiếm nút chữ ký (Tsi ) được tính như sau: Ts=Tli+Tsi. Trong đó Tli không thay đổi cho tất cả các nút lá cho một cấu trúc cân bằng động như SD-tree và Tsi tăng khi giá trị của i tăng. Do vậy, thời gian tìm kiếm bị giới hạn là O(Tli+2i -1). So sánh độ phức tạp thời gian tìm kiếm của cây chữ ký là O(λ.log2n) và cây SD-tree là O(Tli+2i -1), rõ ràng là giá trị Tli rất nhỏ so với giá trị λ, đó là một lợi thế của cây SD-tree. V. KẾT LUẬN Trong bài báo này, chúng tôi đã đề xuất một kỹ thuật lập chỉ mục mới. Phương pháp tiếp cận này là kết hợp phân cấp tập tin chữ ký với cây SD-Tree. Để tối ưu hóa việc quét phân cấp đối tượng, dựa trên các phân cấp tập tin chữ ký để giảm bớt số nhánh cây. Tuy nhiên, do tập tin chữ ký chỉ làm việc với tư cách là bộ lọc phi chính xác, nó không thể bị sắp xếp hay tìm kiếm nhị phân nên không thể được dùng để tăng tốc quá trình quét tập tin chữ ký. Do đó, chúng tôi đề xuất xây dựng một cây SD-Tree trên tập tin chữ ký xuất hiện với tư cách là một nút trong phân cấp 736 TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN PHÂN CẤP TẬP TIN tập tin chữ ký. Kỹ thuật này có thể tránh phải tìm kiếm tuần tự giúp giảm đang kể thời gian cần thiết để tìm kiếm trên tập tin chữ ký. VI. TÀI LIỆU THAM KHẢO [1] Bertino, “Optimization of queries using nested indices”, in Proceedings of International Conference on Extending Database Technology, 1990, pp. 44-59. [2] Bertino and C. Guglielmani, “Optimization of object-oriented queries using path indices”, in 2nd International Workshop on Research Issues on Data Engineering: Transaction and Query Processing, 1992, pp. 140-149. [3] S. Choenni, E. Bertino, H. M. Blanken,and T. Chang, “On the selection of optimal index configuration in OO databases”, in Proceedings of 10th International Conference on Data Engineering, 1994, pp. 526-537. [4] Yangjun Chen, “Building Signature Trees into OODBs”, Journal of Information Science and Engineering, 20(2), 2004, 275-304. [5] Dervos, Y. Manolopoulos, and P. Linardis, “Comparison of signature file models with superimposed coding”, Journal of Information Processing Letters, Vol. 65, 1998, pp. 101-106. [6] R. Elmasri and S. B. Navathe, Fundamentals of Database Systems, Benjamin Cumming, California, 1989. [7] Fotouhi, T. G. Lee, and W. I. Grosky, “The generalized index model for object-oriented database systems”, in 10th Annual International Phonix Conference on Computers and Communication, 1991, pp. 302-308. [8] Y. Ishikawa, H. Kitagawa, and N. Ohbo, “Evaluation of signature files as set access facilities in OODBs”, in Procreedings of ACM SIGMOD International Conference on Management of Data, 1993, pp. 247-256. [9] W. Kim, K. C. Kim, and A. Dale, “Indexing Techniques for Object Oriented Databases”, Addison Wesley, 1989, pp. 371-394. [10] Kemper and G. Moerkotte, “Access support relations: an indexing method for object bases”, Information Systems, Vol. 17, 1992, pp. 117-145. [11] C. C. Low, B. C. Ooi, and H. Lu, “H-trees: a dynamic associative search index for OODB”, in Proceedings of 1992 ACM SIGMOD Conference on the Management of Data, 1992, pp. 134-143. [12] Sreenath and S. Seshadri, “The hcC-tree: an efficient index structure for object oriented database”, in Proceedings of International Conference on Very Large Database, 1994, pp. 203-213. [13] I.E. Shanthi, R. Nadarajan, “Applying SD-Tree for Object-Oriented Query Processing”, Informatica (Slovenia), 33(2), 2009, 169-179. [14] Ms. Ankita Thakur, Ms. Meena Chauhan, “Optimizing Search for Fast Query Retrieval in Object Oriented Databases Using Signature Declustering”, International Journal of Engineering Research and Development, 2012, pp. 46-50. [15] S. Yong, S. Lee, and H. J. Kim,“Applying signatures for forward traversal query processing in object-oriented databases”, in Proceedings of 10th International Conference on Data Engineering, 1994, pp. 518-525. OBJECT-ORIENTED QUERIES BASE ON SIGNATURE FILE HIERARCHY AND SD-TREE Tran Minh Bao, Truong Cong Tuan ABSTRACT – Direct query on objects in object-oriented database is time-consuming. Recently there are many studies focusing on resolving the problem by indexing on single class, class hierarchy or nested objects hierarchy. In this paper, we propose a new indexing approach by combining the signature files and SD-tree where signature files are organized in a hierarchy to quickly filter irrelevant data and each signature file is stored in a signature SD-tree to speed up signature scanning. This technique helps to reduce searching space, hence improves significantly time complexity of query.