Indexing for Data Models with Constraints and Classes

P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter.  ``Indexing for Data Models with Constraints and Classes,'' Journal of Computer and System Sciences, 52(3), 1996, 589-612. An earlier version appeared in Proceedings of the 12th Annual ACM Symposium on Principles of Database Systems (PODS '93), Washington, D. C, May 1993.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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 page size on secondary storage, and t the size of the output of a query. (1) Indexing by one attribute in many constraint data models 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 that has worst-case space O(n/B) pages, query I/O time $O(\log_B n + t/B)$ and $O(\log_B n + (\log_B n)^2/B)$ amortized insert I/O time. Note that, for the static version of this problem, this is the first worst-case optimal solution. (2) 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, query I/O time $O(\log_2c\log_Bn + t/B)$, update I/O time $O(\log_2c\log_Bn)$ and space $O((n/B)\log_2c)$ pages 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 to $O(\log_B n + t/B + \log_2 B)$.