Conflict Equivalence

Conflict equivalent are computer science related to transaction systems , two histories , the conflicting operations in the same sequence order.

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. Read the "Author" field on the "Treasure Island" map

2. Read the "Year of publication" field on the "The Count of Monte Christo" card

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 "Year of publication" field on the "The Count of Monte Christo" card

2. Read the "Author" field on the "Treasure Island" map

3. Write “Robert Louis Stevenson” in the “Author” field of the “Treasure Island” map

These two histories are conflict-equivalent, because the conflicting operations "Read the" Author "field of the" Treasure Island "map" "and" Write "Robert Louis Stevenson" in the "Author" field of the "Treasure Island" map "are used in both histories in processed in the same order. A history like the following would not be conflict-equivalent to these two histories:

1. Read the "Year of publication" field on the "The Count of Monte Christo" card

2. Write “Robert Louis Stevenson” in the “Author” field of the “Treasure Island” map

3. Read the "Author" field on the "Treasure Island" map

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 conflict-equivalent if and only if:

1. T = T '
2. O = O '
3. ${\displaystyle \forall o_{1}\in T_{1}\in T,o_{2}\in T_{2}\in T;o_{1}\not \|o_{2};a_{1},a_{2}\not \in H:o_{1}<_{H}o_{2}\Rightarrow o_{1}<_{H'}o_{2}}$

In words:

Two histories are called conflict equivalent if and only if:

1. they include the same set of transactions,
2. they involve the same set of operations and
3. conflicting operations from transactions that have not been aborted are arranged identically in both histories.

Conflict equivalence is noted as:

${\displaystyle H\equiv H'}$

Intended use

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