ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS), Volume 9 Issue 3, Sept. 1984

SYSTEM/U: a database system based on the universal relation assumption
Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen van Gelder, Jeffrey D. Ullman
Pages: 331-347
DOI: 10.1145/1270.1209
System/U is a universal relation database system under development at Standford University which uses the language C on UNIX. The system is intended to test the use of the universal view, in which the entire database is seen as one relation....

Resolving the query inference problem using Steiner trees
Joseph A. Wald, Paul G. Sorenson
Pages: 348-368
DOI: 10.1145/1270.1275
The query inference problem is to translate a sentence of a query language into an unambiguous representation of a query. A query is represented as an expression over a set of query trees. A metric is introduced for measuring the complexity of a...

Recursive linear hashing
K Ramamohanarao, R Sacks-Davis
Pages: 369-391
DOI: 10.1145/1270.1285
A modification of linear hashing is proposed for which the conventional use of overflow records is avoided. Furthermore, an implementation of linear hashing is presented for which the amount of physical storage claimed is only fractionally more...

The average time until bucket overflow
Robert B. Cooper, Martin K. Solomon
Pages: 392-408
DOI: 10.1145/1270.318575
It is common for file structures to be divided into equal-length partitions, called buckets, into which records arrive for insertion and from which records are physically deleted. We give a simple algorithm which permits calculation of the...

On the selection of efficient record segmentations and backup strategies for large shared databases
Salvatore T. March, Gary D. Scudder
Pages: 409-438
DOI: 10.1145/1270.1481
In recent years the information processing requirements of business organizations have expanded tremendously. With this expansion, the design of databases to efficiently manage and protect business information has become critical. We analyze the...

Concurrency control in a dynamic search structure
Udi Manbar, Richard E. Ladner
Pages: 439-455
DOI: 10.1145/1270.318576
A design of a data structure and efficient algorithms for concurrent manipulations of a dynamic search structure by independent user processes is presented in this paper. The algorithms include updating data, inserting new elements, and deleting...

Optimism and consistency in partitioned distributed database systems
Susan B. Davidson
Pages: 456-481
DOI: 10.1145/1270.1499
A protocol for transaction processing during partition failures is presented which guarantees mutual consistency between copies of data-items after repair is completed. The protocol is “optimistic” in that transactions are processed...

On the optimal nesting order for computing N-relational joins
Toshihide Ibaraki, Tiko Kameda
Pages: 482-502
DOI: 10.1145/1270.1498
Using the nested loops method, this paper addresses the problem of minimizing the number of page fetches necessary to evaluate a given query to a relational database. We first propose a data structure whereby the number of page fetches required...