ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS), Volume 28 Issue 1, March 2003

Description logics for semantic query optimization in object-oriented database systems
Domenico Beneventano, Sonia Bergamaschi, Claudio Sartori
Pages: 1-50
DOI: 10.1145/762471.762472
Semantic query optimization uses semantic knowledge (i.e., integrity constraints) to transform a query into an equivalent one that may be answered more efficiently. This article proposes a general method for semantic query optimization in the...

A simple algorithm for finding frequent elements in streams and bags
Richard M. Karp, Scott Shenker, Christos H. Papadimitriou
Pages: 51-55
DOI: 10.1145/762471.762473
We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is an on-line algorithm, generalizing a...

Adaptive algorithms for set containment joins
Sergey Melnik, Hector Garcia-Molina
Pages: 56-99
DOI: 10.1145/762471.762474
A set containment join is a join between set-valued attributes of two relations, whose join condition is specified using the subset (⊆) operator. Set containment joins are deployed in many database applications, even those that do not support...