OODB indexing by class-division

ABSTRACT

Indexing a class hierarchy, in order to efficiently search or update the objects of a class according to a (range of) value(s) of an attribute, impacts OODB performance heavily. For this indexing problem, most systems use the class hierarchy index (CH) technique of [15] implemented using B⁺-trees. Other techniques, such as those of [14, 18,31], can lead to improved average-case performance but involve the implementation of new data-structures. As a special form of external dynamic two-dimensional range searching, this OODB indexing problem is solvable within reasonable worst-case bounds [12]. Based on this insight, we have developed a technique, called indexing by class-division (CD), which we believe can be used as a practical alternative to CH. We present an optimized implementation and experimental validation of CD's average-case performance. The main advantages of the CD technique are: (1) CD is an extension of CH that provides a significant speed-up over CH for a wide spectrum of range queries--this speed-up is at least linear in the number of classes queried for uniform data and larger otherwise; and (2) CD queries, updates and concurrent use are implementable using existing B⁺-tree technology. The basic idea of class-division involves a time-space tradeoff and CD requires some space and update overhead in comparison to CH. In practice, this overhead is a small factor (2 to 3) and, in worst-case, is bounded by the depth of the hierarchy and the logarithm of its size.

REFERENCES

• 1: François Bancilhon , Claude Delobel , Paris Kanellakis, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 2: R. Bayer and E. M cCreight, "Organization of Large Ordered Indexes," Acta In}ormatica 1 (1972), 173-189.
• 3: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 4: E. Bertino , W. Kim, Indexing Techniques for Queries on Nested Objects, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.196-214, June 1989 [doi>10.1109/69.87960]
• 5: B. Chazelle and L. J. Guibas, "Fractional Cascading: i. A Data Structuring Technique," Algorithmical (1986), 133-162.
• 6: Y.-J. Chiang and R. Tamassia, "Dynamic Algorithms in Computational Geometry," Proceedings of IEEE, Special Issue on Computational Geometry 80(9) (1992), 362-381.
• 7: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 8: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 9: Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
• 10: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: Yoshiharu Ishikawa , Hiroyuki Kitagawa , Nobuo Ohbo, Evaluation of signature files as set access facilities in OODBs, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.247-256, May 25-28, 1993, Washington, D.C., United States
• 12: Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
• 13: Alfons Kemper , Guido Moerkotte, Access support in object bases, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.364-374, May 23-26, 1990, Atlantic City, New Jersey, United States
• 14: Christoph Kilger , Guido Moerkotte, Indexing Multiple Sets, Proceedings of the 20th International Conference on Very Large Data Bases, p.180-191, September 12-15, 1994
• 15: Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989 [doi>10.1145/63320.66510]
• 16: Won Kim , F. H. Lochovsky, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989
• 17: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 18: Chee Chin Low , Beng Chin Ooi , Hongjun Lu, H-trees: a dynamic associative search index for OODB, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.134-143, June 02-05, 1992, San Diego, California, United States
• 19: David Maier , Jacob Stein, Indexing in an object-oriented DBMS, Proceedings on the 1986 international workshop on Object-oriented database systems, p.171-182, September 23-26, 1986, Pacific Grove, California, United States
• 20: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 21: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 22: Mark H. Overmars , Mark T. de Berg , Marc J. van Kreveld , Michiel H. M. Smid, Maintaining range trees in secondary memory. Part I: partitions, Acta Informatica, v.27 n.5, p.423-452, 1990 [doi>10.1007/BF00289018]
• 23: Sridhar Ramaswamy, Indexing for data models with classes and constraints, Brown University, Providence, RI, 1996
• 24: Sridhar Ramaswamy , Paris C. Kanellakis, OODB Indexing by Class-Division, Brown University, Providence, RI, 1995
• 25: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 26: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 27: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 28: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 29: M. Seltzer, K. Bostic, and O. Yigit, The Berkeley DB code, available by ftp from ftp.cs.berkeley.edu as ucb/4bsd/db.tar.Z .
• 30: Michiel H. M. Smid , Mark H. Overmars, Maintaining range trees in secondary memory. Part II: lower bounds, Acta Informatica, v.27 n.5, p.453-480, 1990 [doi>10.1007/BF00289019]
• 31: B. Sreenath , S. Seshadri, The hcC-tree: An Efficient Index Structure for Object Oriented Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.203-213, September 12-15, 1994
• 32: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• 33: Stanley B. Zdonik , David Maier, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Design, Experimentation, Performance, Verification