Partial order, total order, and version order in transaction histories

Question

In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]:

A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the operations (e.g., read, write, abort, commit) of those transactions, and (2) a version order, $\ll$, that is a total order on committed object versions.

---

The author gives a comment on "the partial order of events" (Page 36):

"For convenience, we will present history events in our examples as a total order that is consistent with the partial order. Furthermore, wherever possible in our examples, we make this total order be consistent with the real-time ordering of events in a database system."

Question 1: Why can we present the partial order of events as a total order of them? Because a partial order may imply multiple total orders consistent with it, which one to choose? Does the choice matter for later definitions and theorems?

---

Some comments on "the total version order" (Page 36) are as follows:

[Added (01-10-2015)] "The version order in a history $H$ can be different from the order of write or commit events in $H$. This flexibility is needed to allow certain optimistic and multi-version implementations where it is possible that a version $x_i$ is placed before version $x_j$ in the version order even though $x_i$ is installed in the committed state after $x_j$ is installed."

And,

"The system chooses the version order for each object."

Question 2: What does it mean for the database system to choose the version order? And how? Is this implementation-dependent?

---

[1] Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions by Atul Adya, 1999

Answer 1

for what it concerns Question 1:

there is a theoretical result from 1930 [1] that states that

any partial order $S$ can be extended to a total order $S'$ which contains $S$.

This result is known as the "Order Extension Principle"; the proof of this result uses the Axiom of Choice (I am not aware whether there is an alternative proof that does not use it). The paper is written in French, but you can find a proof at https://www.proofwiki.org/wiki/Order-Extension_Principle.

When Adya states that he chooses the real-time order of events, the best guess is that he assumes an implementation of the database; in this case, every history $H$ corresponds to an execution of the database, where events are totally ordered; such an order is the real-time order. More specifically, by requiring that the partial order $<$ in a history $H$ is extended by the real-time (total) order, Adya imposes that whenever $e_1 < e_2$ in $H$, then the instant of time $t_1$ at which the event $e_1$ takes place (in the execution of the database that leads to $H$) is less than the instant of time $t_2$ at which $e_2$ takes place. Choosing the real-time order of events to extend the partial order of a history $H$ is needed if one wants to prove the correctness of an abstract specification (i.e. set of properties that a history has to satisfy) with respect to a given specification.

Let's turn to Question 2:

in this case it seems to me that Adya wants to stress the fact that he allows the implementation of a database to access a version of an object which precedes (in the version order) the latest version installed. In practice, choosing an earlier version of an object could be either the result of the database not being able to access such a version (e.g. the lost update anomaly in causal consistency), or the user explicitly requesting to access an older version of an object (e.g. accessing an older version of a revision in a SVN repository).

Hope this helps, Andrea Cerone.

[1] Edward Szpilrajn - sur l'extension de l'ordre partiel