ACM Transactions on Database Systems · 1994 · 68 citations · 39 references
ComputingComputer ScienceComputer SystemsDatabasesDistributed SystemsFormal MethodsConcurrency ControlData ReplicationDistributed TransactionsTransaction ManagementIntegrity ConstraintsSerializabilityTransaction ProcessingTransactions
Databases are replicated to improve performance and availability. The notion of correctness that has commonly been adopted for concurrent access by transactions to shared, possibly replicated, data is serializability. However, serializability may be impractical in high-performance applications since it imposes too stringent a restriction on concurrency. When serializability is relaxed, the integrity constraints describing the data may be violated. By allowing bounded violations of the integrity constraints, however, we are able to increase the concurrency of transactions that execute in a replicated environment. In this article, we introduce the notion of an N-ignorant transaction, which is a transaction that may be ignorant of the results of at most N prior transactions, which is a transaction that may be ignorant of the results of at most N prior transactions. A system in which all transactions are N-ignorant can have an N + 1-fold increase in concurrency over serializable systems, at the expense of bounded violations of its integrity constraints. We present algorithms for implementing replicated databases in N-ignorant systems. We then provide constructive methods for calculating the reachable states in such systems, given the value of N , so that one may assess the maximum liability that is incurred in allowing constraint violation. Finally, we generalize the notion of N-ignorance to a matrix of ignorance for the purpose of higher concurrency.
39
David Jefferson · ACM Transactions on Programming Languages and Systems · 1985 · 2.4K citations · Full text
The notions of consistency and predicate locks in a database system
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie et al. · Communications of the ACM · 1976 · 2K citations · Full text
Andrew Birrell, Roy Levin, Michael Schroeder et al. · Communications of the ACM · 1982 · 447 citations · Full text