Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 27 Issue 3, September 2002

Searching for dependencies at multiple abstraction levels
Toon Calders, Raymond T. Ng, Jef Wijsen
Pages: 229-260
DOI: 10.1145/581751.581752
The notion of roll-up dependency (RUD) extends functional dependencies with generalization hierarchies. RUDs can be applied in OLAP and database design. The problem of discovering RUDs in large databases is at the center of this paper. An algorithm...

Fast incremental maintenance of approximate histograms
Phillip B. Gibbons, Yossi Matias, Viswanath Poosala
Pages: 261-298
DOI: 10.1145/581751.581753
Many commercial database systems maintain histograms to summarize the contents of large relations and permit efficient estimation of query result sizes for use in query optimizers. Delaying the propagation of database updates to the histogram often...

Cost models for overlapping and multiversion structures
Yufei Tao, Dimitris Papadias, Jun Zhang
Pages: 299-342
DOI: 10.1145/581751.581754
Overlapping and multiversion techniques are two popular frameworks that transform an ephemeral index into a multiple logical-tree structure in order to support versioning databases. Although both frameworks have produced numerous...