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

BibTeX

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