Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 4 Issue 3, Sept. 1979

On semantic issues connected with incomplete information databases
Witold Lipski, Jr.
Pages: 262-296
DOI: 10.1145/320083.320088
Various approaches to interpreting queries in a database with incomplete information are discussed. A simple model of a database is described, based on attributes which can take values in specified attribute domains. Information incompleteness...

The theory of joins in relational databases
A. V. Aho, C. Beeri, J. D. Ullman
Pages: 297-314
DOI: 10.1145/320083.320091
Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the...

Extendible hashing—a fast access method for dynamic files
Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong
Pages: 315-344
DOI: 10.1145/320083.320092
Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic...

Propeties of storage hierarchy systems with multiple page sizes and redundant data
Chat-Yu Lam, Stuart E. Madnick
Pages: 345-367
DOI: 10.1145/320083.320095
The need for high performance, highly reliable storage for very large on-line databases, coupled with rapid advances in storage device technology, has made the study of generalized storage hierarchies an important area of research....

Efficiently monitoring relational databases
O. Peter Buneman, Eric K. Clemons
Pages: 368-382
DOI: 10.1145/320083.320099
An alerter is a program which monitors a database and reports to some user or program when a specified condition occurs. It may be that the condition is a complicated expression involving several entities in the database; in this case the...

Heuristics for trie index minimization
Douglas Comer
Pages: 383-395
DOI: 10.1145/320083.320102
A trie is a digital search tree in which leaves correspond to records in a file. Searching proceeds from the root to a leaf, where the edge taken at each node depends on the value of an attribute in the query. Trie implementations have the...