Consistency Models

A pathological ordering of transactions in a database is an ordering that satisfies the serializability requirement, but is not a realistic or desirable ordering.

The serializability requirement states that all possible executions of a set of transactions are equivalent to some serial execution of the same transactions. This means that the order in which the transactions are executed does not matter, as long as the final state of the database is the same.

However, the serializability requirement does not rule out all possible orderings of transactions. For example, a database could always return the empty state for any reads, by appearing to execute those reads at time 0. This is a pathological ordering, because it is not a realistic or desirable ordering of transactions.

Another example of a pathological ordering is to discard write-only transactions by reordering them to execute at the very end of the history, after any reads. This is also not a realistic or desirable ordering, because it can lead to inconsistencies in the database.

Finally, increments can also be discarded, assuming the result of the increment is never observed. This is another example of a pathological ordering, because it can lead to incorrect data being returned to users.

Most database implementations do not take advantage of these optimization opportunities, because they would lead to pathological orderings. Instead, database implementations typically use a variety of techniques to ensure that transactions are executed in a fair and predictable order.

Here are some of the techniques that database implementations use to ensure that transactions are executed in a fair and predictable order:

<aside> 💡 数据库避免病态排序的常用方法：锁、时间戳、2PC

</aside>

• Locking: Locking prevents concurrent transactions from modifying the same data at the same time. This helps to ensure that transactions are executed in a serializable order.
• Timestamping: Timestamping assigns a unique timestamp to each transaction. This timestamp can be used to order transactions in a fair and predictable way.
• Two-phase commit: Two-phase commit is a protocol that ensures that all or none of the changes made by a transaction are committed to the database. This helps to prevent inconsistencies in the database.

By using these techniques, database implementations can ensure that transactions are executed in a fair and predictable order, and that pathological orderings are avoided.

To answer your question more directly, a pathological ordering is an ordering of transactions that satisfies the serializability requirement, but is not realistic or desirable. It is an ordering that could theoretically be executed by a database, but would lead to unexpected or incorrect results.