Interval Hierarchies and Their Application to Predicate Files.

Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977)

@article{DBLP:journals/tods/WongE77,
  author    = {Kai C. Wong and
               Murray Edelberg},
  title     = {Interval Hierarchies and Their Application to Predicate Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {2},
  number    = {3},
  year      = {1977},
  pages     = {223-232},
  ee        = {http://doi.acm.org/10.1145/320557.320562, db/journals/tods/WongE77.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Predicates are used extensively in modern database systems for purposes ranging from user specification of associative accesses to data, to user-invisible system control functions such as concurrency control and data distribution. Collections of predicates, or predicate files, must be maintained and accessed efficiently. This paper describes a dynamic index, called an interval hierarchy, which supports several important retrieval operations on files of simple conjunctive predicates. Search and maintenance algorithms for interval hierarchies are given. For a file of n predicates, typical of the kind expected in practice, these algorithms require time equal to O(log n).

Copyright © 1977 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Conference Abstract

Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files (Abstract). SIGMOD Conference 1977: 168 BibTeX

References

[1]: Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[2]: Kapali P. Eswaran: Aspects of a Trigger Subsystem in an Integrated Data Base System. ICSE 1976: 243-250 BibTeX
[3]: Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[4]: Kapali P. Eswaran, Donald D. Chamberlin: Functional Specifications of Subsystem for Database Integrity. VLDB 1975: 48-68 BibTeX
[5]: Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX

Referenced by

Dennis Shasha, François Llirbat, Eric Simon, Patrick Valduriez: Transaction Chopping: Algorithms and Performance Studies. ACM Trans. Database Syst. 20(3): 325-363(1995)
Dennis Shasha, Eric Simon, Patrick Valduriez: Simple Rational Guidance for Chopping Up Transactions. SIGMOD Conference 1992: 298-307
David Eichmann, D. Alton: A Polymorphic Relational Algebra and Its Optimization. ICDE 1991: 680-689
Wojtek Kozaczynski, Leszek Lilien: An Extended Entity-Relationship (E²R) Database Specification and its Automatic Verification and Transformation into the Logical Relational Design. ER 1987: 533-549
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
E. O. Onuegbe, H. C. Du: A Locking Scheme for Associative Retrieval. ICDE 1986: 574-579
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72
Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]