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 Ο (log n ).
Keywords
Computer sciencePredicate (mathematical logic)Concurrency controlConcurrencyTheoretical computer scienceProgramming languageDatabase transaction
Related Publications
The Grid file: A data structure designed to support proximity queries on spatial objects
Abstract : This document describes a technique for storing large sets of spatial objects so that proximity queries are handled efficiently as part of the accessing mechanism. Th...
Revolutionizing Supply Chain Management: Real-time Data Processing and Concurrency
In the contemporary business landscape, effective supply chain management (SCM) is paramount for organizations seeking to thrive amidst evolving market dynamics and heightened c...
BLAST+: architecture and applications
Abstract Background Sequence similarity searching is a very important bioinformatics task. While Basic Local Alignment Search Tool (BLAST) outperforms exact methods through its ...
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects
The problem of indexing multidimensional objects is considered. First, a classification of existing methods is given along with a discussion of the major issues involved in mult...
Mining sequential patterns
We are given a large database of customer transactions, where each transaction consists of customer-id, transaction time, and the items bought in the transaction. We introduce t...
Publication Info
- Year
- 1977
- Type
- article
- Volume
- 2
- Issue
- 3
- Pages
- 223-232
- Citations
- 18
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
18
OpenAlex
Cite This
K.C. Wong,
Murray Edelberg
(1977).
Interval hierarchies and their application to predicate files.
ACM Transactions on Database Systems
, 2
(3)
, 223-232.
https://doi.org/10.1145/320557.320562
Identifiers
- DOI
- 10.1145/320557.320562