ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS), Volume 15 Issue 2, June 1990

Explaining ambiguity in a formal query language
Joseph A. Wald, Paul G. Sorenson
Pages: 125-161
DOI: 10.1145/78922.78923
The problem of generating reasonable natural language-like responses to queries formulated in nonnavigational query languages with logical data independence is addressed. An extended ER model, the Entity-Relationship-Involvement model, is...

Logic-based approach to semantic query optimization
Upen S. Chakravarthy, John Grant, Jack Minker
Pages: 162-207
DOI: 10.1145/78922.78924
The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described...

A linear-time probabilistic counting algorithm for database applications
Kyu-Young Whang, Brad T. Vander-Zanden, Howard M. Taylor
Pages: 208-229
DOI: 10.1145/78922.78925
We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm has O(q) time complexity, where q is the number of values including...

Dynamic voting algorithms for maintaining the consistency of a replicated database
S. Jajodia, David Mutchler
Pages: 230-280
DOI: 10.1145/78922.78926
There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they...

The five color concurrency control protocol: non-two-phase locking in general databases
Partha Dasgupta, Zvi M. Kedem
Pages: 281-307
DOI: 10.1145/78922.78927
Concurrency control protocols based on two-phase locking are a popular family of locking protocols that preserve serializability in general (unstructured) database systems. A concurrency control algorithm (for databases with no inherent...