Efficient Indexing for Constraint and Temporal Databases

摘要: We examine new I/O-efficient techniques for indexing problems in constraint and temporal data models. present algorithms these that are considerably simpler than previous solutions. Our solutions unique the sense they only use B+-trees rather special-purpose structures. Indexing many general models can be reduced to interval intersection. a algorithm this problem using query-time/space tradeoff, which achieves optimal query time O(logB n+t/B) I/O's linear space O(n/B) B+-trees. (Here, n is number of intervals, t intervals output query, B disk block size.) It easy update structure, but small worst-case bounds do not seem possible. Previous approaches have achieved fairly complex rely mostly on reducing intersection special cases two-dimensional search. Some them also handle updates n) amortized. becomes generalization management, where each object characterized by an key. There different ways querying objects, we achieve queries. These modification technique used problem. much other been achieving similar bounds.