This section defines the kind of consistency our new mechanism provides.
We refer to the i version of object x as x. If a transaction creates a version x, we assume that it read x. Transaction T is said to directly depend on transaction U if it read x and U created version x; we also say that T has read from U. We say that T depends on U if there exist transactions V, V, V, where U is V and T is V and V directly depends on V, V directly depends on V, and so on.
A running transaction Q will view a consistent state if the following condition is satisfied:
If Q depends on T, it must observe the complete effects of T.
For example, suppose that T creates x and y. If Q reads x and also reads y, it must read y or a version of y that is later than y.
The same condition is used for providing consistent views for read-only transactions by Chan and Gray ; that paper proves that if the condition is satisfied, Q will observe a consistent snapshot of the database. Here we present a brief synopsis of the proof. Assume T, T, ... T is a prefix of the serialization history of the system, where T is the latest transaction whose updates have been observed by Q. Suppose Q only depends on transactions T, T, ... T and has missed the updates of transaction T. Since we are ensuring that the above condition is satisfied for Q, T's updates have no impact on T, T, ... T (they do not depend on T). If we consider a history in which we remove (all such) T from the set of committed transactions, there will be no change in the database state observed by Q. Since a transaction transforms the database from one consistent state to another and the output of each transaction in T, T, ... T is unaffected by the presence or absence of T, their combination must yield a consistent database state.
A transaction Q that views a consistent state is not necessarily serializable with all the committed transactions in the system. For example, suppose there are two objects x and y stored at servers X and Y respectively and suppose that transactions U and T run in parallel and commit and then Q reads x and y:
In this scenario, Q has observed the effects of T but missed the effects of U. To commit Q, we would need to serialize it both before U and after T, but since U is already serialized before T, this is impossible. The intuition why Q does not observe inconsistencies is that since T does not depend on U, its modifications must preserve system invariants regardless of what U does. A possible invariant that might be preserved is , where U stores the value of in and T increases .
This problem of transaction Q not being serializable can occur only when there is an anti-dependency: A transaction A anti-depends on B if A overwrites an object version that B has read. In this case, T anti-depends on U. Figure 1 shows a cycle that is formed in the dependency graph  for this schedule due to anti-dependencies.
Figure 1: A non-serializable transaction that has observed a consistent database state.
Lazy consistency is independent of causality : a transaction Q might observe the effects of T while missing the effects of T, where both T and T ran at the same client in order T; T. Our implementation guarantees causality for individual clients, which ensures that a client always observes the effects of all its previous committed transactions and the transactions they depended on. We believe such _local causality_ is good since it means code within a transaction can depend on invariants holding between objects observed directly and also results computed by its earlier transactions and stored in local variables. Causality is discussed further in Section 6.3, where we show the additional cost incurred over lazy consistency to support local causality. We also show what it would cost to support _global causality_, in which a client that observes the effects of transaction T of some other client also observes effects of all earlier transactions of that client (and the transactions they depended on). Note that locking ensures global causality for active transactions.