Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 9 Issue 2, June 1984

Implications of certain assumptions in database performance evauation
S. Christodoulakis
Pages: 163-186
DOI: 10.1145/329.318578
The assumptions of uniformity and independence of attribute values in a file, uniformity of queries, constant number of records per block, and random placement of qualifying records among the blocks of a file are frequently used in database...

Logical, internal, and physical reference behavior in CODASYL database systems
Wolfgang Effelsberg, Mary E. S. Loomis
Pages: 187-213
DOI: 10.1145/329.331
This work investigates one aspect of the performance of CODASYL database systems: the data reference behavior. We introduce a model of database traversals at three levels: the logical, internal, and physical levels. The mapping between the...

A parallel pipelined relational query processor
Won Kim, Daniel Gajski, David J. Kuck
Pages: 214-235
DOI: 10.1145/329.332
This paper presents the design of a relational query processor. The query processor consists of only four processing PIPEs and a number of random-access memory modules. Each PIPE processes tuples of relations in a bit-serial, tuple-parallel...

Algorithms for trie compaction
M. Al-Suwaiyel, E Horowitz
Pages: 243-263
DOI: 10.1145/329.295
The trie data structure has many properties which make it especially attractive for representing large files of data. These properties include fast retrieval time, quick unsuccessful search determination, and finding the longest match to a given...

Database states and their tableaux
Alberto O. Mendelzon
Pages: 264-282
DOI: 10.1145/329.318579
Recent work considers a database state to satisfy a set of dependencies if there exists a satisfying universal relation whose projections contain each of the relations in the state. Such relations are called weak instances for...

On the foundations of the universal relation model
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi
Pages: 283-308
DOI: 10.1145/329.318580
The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the...

An extension of conflict-free multivalued dependency sets
Hirofumi Katsuno
Pages: 309-326
DOI: 10.1145/329.354
Several researchers (Beeri, Bernstein, Chiu, Fagin, Goodman, Maier, Mendelzon, Ullman, and Yannakakis) have introduced a special class of database schemes, called acyclic or tree schemes. Beeri et al. have shown...