ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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}
}
BibTeX

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).

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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

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 BibTeX

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) BibTeX

References

[BaM]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[ChT]
...
[Cod]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Com]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[IKO]
...
[JaL]
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
[KKR]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[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 BibTeX
[MaS]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 BibTeX
[McC]
Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985) BibTeX
[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) BibTeX
[Sama]
...
[Samb]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX
[SlT]
Daniel Dominic Sleator, Robert Endre Tarjan: A Data Structure for Dynamic Trees. J. Comput. Syst. Sci. 26(3): 362-391(1983) BibTeX
[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) BibTeX
[Vit]
Jeffrey Scott Vitter: Efficient Memory Access in Large-Scale Computation. STACS 1991: 26-41 BibTeX
[ZdM]
Stanley B. Zdonik, David Maier (Eds.): Readings in Object-Oriented Database Systems. Morgan Kaufmann 1990, ISBN 1-55860-000-0
BibTeX

Referenced by

  1. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  2. Himanshu Gupta, Divesh Srivastava: The Data Warehouse of Newsgroups. ICDT 1999: 471-488
  3. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Indexing Constraint Databases by Using a Dual Representation. ICDE 1999: 618-627
  4. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Approximation Techniques for Indexing Two-Dimensional Constraint Databases. DASFAA 1999: 213-220
  5. Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998)
  6. Vassilis J. Tsotras, Christian S. Jensen, Richard T. Snodgrass: An Extensible Notation for Spatiotemporal Index Queries. SIGMOD Record 27(1): 47-53(1998)
  7. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  8. Jeffrey Scott Vitter: External Memory Algorithms. PODS 1998: 119-128
  9. Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51
  10. Elias Koutsoupias, David Scot Taylor: Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998: 52-58
  11. Thomas A. Mück, Martin L. Polaschek: A Configrable Type Hierarchy Index for OODB. VLDB J. 6(4): 312-332(1997)
  12. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256
  13. Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431
  14. Thomas A. Mück, Martin L. Polaschek: The Multikey Type Index for Persistent Object Sets. ICDE 1997: 22-31
  15. Thomas A. Mück, Martin L. Polaschek: Optimal Type Hierarchy Linearization for Queries in OODB. DASFAA 1997: 225-234
  16. Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
  17. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  18. Serge Abiteboul, Gabriel M. Kuper, Harry G. Mairson, Alexander A. Shvartsman, Moshe Y. Vardi: In Memoriam Paris C. Kanellakis. ACM Comput. Surv. 28(1): 3-15(1996)
  19. Stéphane Grumbach, Jianwen Su: Towards Practical Constraint Databases. PODS 1996: 28-39
  20. Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150
  21. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  22. Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65
  23. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  24. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  25. Stéphane Grumbach, Zoé Lacroix: Computing Queries on Linear Constraint Databases. DBPL 1995: 11
  26. Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35
  27. Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300
  28. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:08 2009