View equivalence

Two histories that produce the same result are equivalent in computer science in connection with transaction systems .

Illustrative example

In order to be able to clearly imagine the most important terms of this article, the following example should serve:

In a library an index card system is used to manage the inventory of books. The following history could arise here:

1. Write "unknown" in the "Author" field of the "Treasure Island" map
2. Read the field "Year of publication" of the card "The Count of Monte Christo"
3. Write "Robert Louis Stevenson" in the "Author" field of the "Treasure Island" map

Operations 1 and 3 are conflicting because their order cannot be reversed without changing the result. A second history from the same operations - just in a different order - could look like this:

1. Read the field "Year of publication" of the card "The Count of Monte Christo"
2. Write "unknown" in the "Author" field of the "Treasure Island" map
3. Write "Robert Louis Stevenson" in the "Author" field of the "Treasure Island" map

These two histories are equivalent to views, because they lead to the same result: The year of publication of the Count of Monte Christo has been read and the “Author” field of the “Treasure Island” map says “Robert Louis Stevenson”. A history like the following would not be view equivalent to these two histories:

1. Read the field "Year of publication" of the card "The Count of Monte Christo"
2. Write "Robert Louis Stevenson" in the "Author" field of the "Treasure Island" map
3. Write "unknown" in the "Author" field of the "Treasure Island" map

The "reads from" relationship

A transaction A is said to read a data element x from another transaction B if A contains an operation that retrieves the exact value of x that B assigned to x.

The "last letter"

The last write of a data element x in a history H, noted as , is the operation in H that assigns a value to x for the last time. ${\displaystyle FIN_{H}[x]}$

Mathematical definition

In formulas :

Let H be a history of the set of transactions T, which includes the set of operations O, H 'a history of the set of transactions T', which includes the set of operations O '. H and H 'are called view equivalent if and only if:

1. T = T '
2. O = O '
3. ${\displaystyle \forall T_{1},T_{2}\in T;a_{1},a_{2}\not \in H:T_{2}\triangleright _{H}T_{1}\Leftrightarrow T_{2}\triangleright _{H'}T_{1}}$
4. ${\displaystyle \forall x:FIN_{H}[x]=FIN_{H'}[x]}$

In words:

Two histories are called view equivalent if and only if:

1. they include the same set of transactions,
2. they involve the same set of operations,
3. all operations from non-aborted transactions according to the read-from relationship are arranged in the same way in both histories and
4. their last writes are identical for all data elements.

View equivalence is noted as:

${\displaystyle H\equiv _{V}H'}$

Intended use

If two histories are view equivalent, this means that their execution leads to the same result. The view equivalence forms the basic condition for the view serializability of a history.