Indexing for Data Models with Constraints and Classes

✍ Scribed by Paris Kanellakis; Sridhar Ramaswamy; Darren E. Vengroff; Jeffrey Scott Vitter

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 829 KB
• Volume: 52
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0043

✦ Synopsis

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 generated 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 two-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 two-dimensional range searching. Based on this observation, we first identify a simple algorithm with good worst-case performance, query IÂO time O(log 2 c log B n+tÂB), update IÂO time O(log 2 c log B n) and space O((nÂB) log 2 c) 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).