Indexing for Data Models with Constraints and Classes.

Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243

@inproceedings{DBLP:conf/pods/KanellakisRVV93,
  author    = {Paris C. Kanellakis and
               Sridhar Ramaswamy and
               Darren Erik Vengroff and
               Jeffrey Scott Vitter},
  title     = {Indexing for Data Models with Constraints and Classes},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {233-243},
  ee        = {http://doi.acm.org/10.1145/153850.153884, db/conf/pods/KanellakisRVV93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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(log_Bn+t/B) and has O(log_Bn+(log²_Bn)/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(log_Bn). 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(log₂c log_Bn + t/B) to O(log_B + log₂B).

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1052 KB]

Journal Version

Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. J. Comput. Syst. Sci. 52(3): 589-612(1996)

References

[BaM]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[ChT]: ...
[Cod]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)
[Com]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[IKO]: ...
[JaL]: Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119
[KKR]: Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313
[KKD]: ...
[KiL]: ...
[LOL]: Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143
[MaS]: David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182
[McC]: Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985)
[OSB]: Mark H. Overmars, Michiel H. M. Smid, Mark de Berg, Marc J. van Kreveld: Maintaining Range Trees in Secondary Memory. Part I: Partitions. Acta Inf. 27(5): 423-452(1989)
[Sama]: ...
[Samb]: Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[SlT]: Daniel Dominic Sleator, Robert Endre Tarjan: A Data Structure for Dynamic Trees. J. Comput. Syst. Sci. 26(3): 362-391(1983)
[SmO]: Michiel H. M. Smid, Mark H. Overmars: Maintaining Range Trees in Secondary Memory. Part II: Lower Bounds. Acta Inf. 27(5): 453-480(1989)
[Vit]: Jeffrey Scott Vitter: Efficient Memory Access in Large-Scale Computation. STACS 1991: 26-41
[ZdM]: Stanley B. Zdonik, David Maier (Eds.): Readings in Object-Oriented Database Systems. Morgan Kaufmann 1990, ISBN 1-55860-000-0