UB-Tree Indexing for Semantic Query Optimization of Range Queries

Authors: S. Housseno, A. Simonet, M. Simonet

Abstract:

Semantic query optimization consists in restricting the search space in order to reduce the set of objects of interest for a query. This paper presents an indexing method based on UB-trees and a static analysis of the constraints associated to the views of the database and to any constraint expressed on attributes. The result of the static analysis is a partitioning of the object space into disjoint blocks. Through Space Filling Curve (SFC) techniques, each fragment (block) of the partition is assigned a unique identifier, enabling the efficient indexing of fragments by UB-trees. The search space corresponding to a range query is restricted to a subset of the blocks of the partition. This approach has been developed in the context of a KB-DBMS but it can be applied to any relational system.

Keywords: Index, Range query, UB-tree, Space Filling Curve, Query optimization, Views, Database, Integrity Constraint, Classification.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079716

References:

[1] Bayer, R.: The universal B-Tree for multi-dimensional Indexing: General Concepts. In World-Wide Computing and its Applications -97 (WWCA-97), Lecture Notes on Computer Science. Springer Verlag, Tsukuba, Japan (1997)
[2] Markl, V.: Processing Relational Queries using a Multidimensional Access Technique. PhD thesis, DISDBIS, Band 59, Infix Verlag (1999)
[3] Bayer, R., McCreight, E.: Organization and Maintenance of large ordered Indexes. In Acta Informatica 1, pp. 173--189 (1972)
[4] Ramsak , F.: The BUB-Tree. In Proceedings of 28rd VLDB International Conference on Very Large Data Bases, VLDB 2002, Hong Kong, China (2002)
[5] Orenstein, J.A., Merrett, T.H.: A Class of Data Structures for Associative Searching. In Proceedings of the Third ACM SIGACT-SIGMOD Symposium on PODS, April 2-4, pp. 181-- 190. ACM (1984)
[6] Sagan, H.: Space-Filling Curves, Springer; 1 edition (September 2, 1994), ISBN-10: 0387942653, ISBN-13: 978-0387942650
[7] Otoo, E. J.: A Mapping Function for the Directory of a Multidimensional Extendible Hashing, Proceedings of the 10th International Conference on Very Large Data Bases(VLDB), pp. 493--506, San Francisco, CA, USA (1984)
[8] Berchtold, S., Keim, D. A.., Kriegel, H.: The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB), pp. 28ÔÇö39, India (1996)
[9] Böhm, C., Berchtold, S., Keim, D.A.: Searching in highdimensional spaces: index structures for improving the performance of multimedia databases, ACM Comput. Surv. 33 (3), pp. 322-373, (2001)
[10] Skopal, T., KrátkÛ, M., PokornÛ, J., Snášel, V.: A new range query algorithm for universal B-trees, Information Systems, Vol. 31, Issue 6, pp. 489 - 511, (September 2006)
[11] Peano, G.: Sur une courbe qui remplit toute une aire plaine, Mathematishe Annalen, 36, pp. 157ÔÇö160, (1890)
[12] Hilbert, D.: Ueber die stetige Abbildung einer Line auf ein Flächenstück, Mathematische Annalen, 38: pp. 459-460, (1891)
[13] Simonet, A., Simonet, M.: OSIRIS : an Object-Oriented system Unifying Databases and Knowledge bases, KBKS-95 : Towards Very Large Knowledge Bases, Enschede, The Netherlands, pp. 217--227, N. Mars Ed., IOS Press, (1995)
[14] Stanat, D., McAllister, D. : Discrete Mathematics in Computer Science, Prentice Hall (1977)
[15] Yu, C.: High-Dimensional Indexing: Transformational Approaches to High-Dimensional Range and Similarity Searches, Springer (2002)
[16] Simonet, A., Simonet, M.: Objects with Views and Constraints : from Databases to Knowledge Bases, Object-Oriented Information Systems OOIS'94, Springer Verlag, pp. 182--197, London (1994)
[17] Bertino, E., Chin, O.B., Sacks-Davis, R., Tan, K., Zobel, J., Shidlovsky, B., Andronico, D.: Indexing Techniques for Advanced Database Systems. Kluwer Academic (1997)
[18] Tamminen, M., Sulonen, R.: The excell method for efficient geometric access to data, Annual ACM IEEE Design Automation Conference, Proceedings of the 19th conference on Design automation, pp. 345--351 (1982)
[19] Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Trans. Database Syst, vol. 9(1), pp. 38--71 (1984)
[20] Samet, H.: Foundations of Multidimensional and Metric Data Structures, ISBN-10: 0123694469, ISBN-13: 978-0123694461, Morgan Kaufmann (2006)
[21] Guttman, A. : R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, SIGMOD 84, pp. 47ÔÇö57, Boston, Massachusetts (1984)
[22] Mokbel, M. F., Aref, W. G., Kamel, I.: Performance of multidimensional space-filling curves, Geographic Information Systems, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, pp.149 - 154 McLean, Virginia, USA (2002)