Indexing for data models with constraints and classes (extended abstract)

ABSTRACT

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and from object-oriented programming (e.g., objects are organized in class hierarchies). Let n be the size of the database, c the number of classes, B the secondary storage page size, and t the size of the output of a query. Indexing by one attribute in the constraint data model (for a fairly general type of constraints) is equivalent to external dynamic interval management, which is a special case of external dynamic 2-dimensional range searching. We present a semi-dynamic data structure for this problem which has optimal worst-case space O(n/B) pages and optimal query I/O time O(logBn+t/B) and has O(logBn+(log2Bn)/B) amortized insert I/O time. If the order of the insertions is random then the expected number of I/O operations needed to perform insertions is reduced to O(logBn). Indexing by one attribute and by class name in an object-oriented model, where objects are organized as a forest hierarchy of classes, is also a special case of external dynamic 2-dimensional range searching. Based on this observation we first identify a simple algorithm with good worst-case performance for the class indexing problem. Using the forest structure of the class hierarchy and techniques from the constraint indexing problem, we improve its query I/O time from O(log2c logBn + t/B) to O(logB + log2B).

REFERENCES

• BaM: R. Bayer and E. McCreight, "Organization of Large Ordered Indexes," A cta Informatica 1 (1972), 173-189.
• ChT: Y.-J. C'hiang and R. Tamassia, "Dynamic Algorithms in Computational Geometry," Proceedings of IEEE, Special Issue on Computational Geometry 80(9)(1992), 362-381.
• Cod: 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]
• Com: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• IKO: Ch. Icking , R. Klein , Th. Ottmann, Priority search trees in secondary memory (extended abstract), Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.84-93, July 1988, Kloster Banz/Staffelstein, Germany
• JaL: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• KKR: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• KKD: 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]
• KiL: Won Kim , Frederick H. Lochovsky, Object-oriented concepts, databases, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1989
• LOL: 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
• MaS: 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
• McC: E. M. McCreight, "Priority Search Trees," SIAM Journal of Computing 14(2)(May 1985), 257-276.
• OSB: 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]
• Sama: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Samb: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SlT: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• SmO: 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]
• Vit: Jeffrey Scott Vitter, Efficient memory access in large-scale computation (invited paper), Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.26-41, February 1991, Hamburg, Germany
• ZdM: 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.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data description languages (DDL)
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Languages