UB-Tree Indexing for Semantic Query Optimization of Range Queries
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.
[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)
[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)
@article{"International Journal of Information, Control and Computer Sciences:61738", author = "S. Housseno and A. Simonet and M. Simonet", title = "UB-Tree Indexing for Semantic Query Optimization of Range Queries", 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.", volume = "3", number = "11", pages = "2689-8", }
