Serializability

The articles serializability , scheduler (database) and history (transaction processing) overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Albing 10:22, December 4, 2011 (CET)

The term serializability comes from the database theory of computer science. In transaction systems there is an execution plan for the parallel execution of several transactions. The plan is also called the history and indicates the order in which the individual operations of the transaction are carried out. A history is referred to as serializable if it leads to the same result as a successively ( serially ) executed history of the same transactions .

A distinction is made between conflict serializability , view serializability and 1-serializability . If the term serializability is used alone, it is usually understood as conflict serializability.

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. A history or an execution sequence could be:

1. Check the last entry in the "loaned to" field on the "Moby Dick" card.
2. Write “Hans Meier” in the “loaned to” field on the “Moby Dick” card.
3. Delete the last entry in the "Return on" field on the "Moby Dick" card.
4. Write “15. March 2003 ”in the“ Return on ”field on the“ Moby Dick ”card.

Two transactions are mixed here. Transaction A is a return process and is:

A.1: Check the last entry in the "loaned to" field on the "Moby Dick" card.

A.2: Delete the last entry in the "Return on" field on the "Moby Dick" card.

Transaction B is a borrowing process and reads:

B.1: Write “Hans Meier” in the “loaned to” field on the “Moby Dick” card.

B.2: Write “15. March 2003 ”in the“ Return on ”field on the“ Moby Dick ”card.

Operations A.1 and B.1 are conflicting, as are operations A.2 and B.2; if they were carried out in reversed order, the result of the history would be an incomprehensible mess. One reason is: Operations A.1 and A.2 each refer to the last entry. However, which is the last entry is determined by operations B.1 or B.2. If B.1 (B.2) is carried out before A.1 (A.2), a new entry for "Hans Meier" is added. This entry is now the last in the list, but no longer corresponds to the last borrower, but to the new one. Thus the wrong entry is checked off or deleted.

With the help of the conflict serializability, we can check the history to see whether these conflicting operations are carried out in the correct order. The view serializability, on the other hand, tells us that the result of the history is the same as if we had only performed the ultimately visible operations of the transactions in the correct order.

The 1-serializability is an extension of the term to multi-version histories. The use of a multi-version history in this example would mean that each time a book card is changed, a new card is created and the old card is kept at the same time. Operations then become possible such as:

"Read the" Author "field on the" Moby Dick "map in the map version of March 17, 1993".

All forms of serializability guarantee that the result of a history is correct.

Conflict serializability

To check the equivalence of the histories, the conflict equivalence is used here . The conditions of conflict serializability are in formulas :

Let H be a history, C (H) the committed projection of H. H is called conflict serializable if and only if:

${\displaystyle \exists }$ serial history ${\displaystyle H_{s}:C(H)\equiv H_{s}}$

In words:

A history H is called conflict serializable if and only if there is a serial history to which the committed projection of H is conflict-equivalent.

The commit-completed projection of a history only contains those transactions that are completed by means of a commit (i.e. not canceled). This projection is explained in more detail in the article History .

Conflict serializability can be tested with the help of a serializability graph: If the resulting graph is acyclic (circle-free), the tested history can be serialized.

View serializability

The view equivalence is used to check the equivalence . The conditions of the view serializability are - analogous to the above - in formulas:

Let H be a history, C (H) the commit-completed projection of H. H is called view serializable if and only if:

${\displaystyle \exists }$ serial history ${\displaystyle H_{s}:C(H)\equiv _{V}H_{s}}$

In words:

A history H is called view serializable if and only if there is a serial history to which the committed projection of H is view equivalent.

Visual serializability can be tested with the help of a polygraph : If the resulting graph is acyclic, the tested history can be visualized.

Relationship between conflict and view serializability

The set of all conflict serializable histories forms a real subset of the set of all view serializable histories. Histories that can be serialized to conflict are therefore automatically serializable. In theory, view serializability is the more effective form of serializability, because it enables more concurrency and thus better performance than conflict serializability. The problem with this is that the test for visual serializability with a polygraph is NP-complete , i.e. it takes an extremely long time. This means that it is practically impossible to use the view serializability.

1 serializability

The 1-serializability is a specialization of the view serializability on multi-version histories. In formulas:

Be a multi-version history, the commit-completed projection of . is called 1-serializable if and only if: ${\displaystyle H_{MV}}$ ${\displaystyle C(H_{MV})}$ ${\displaystyle H_{MV}}$ ${\displaystyle H_{MV}}$

${\displaystyle \exists }$ 1-serial multi-version history ${\displaystyle H_{1s,MV}:C(H_{MV})\equiv _{V}H_{1s,MV}}$

In words:

A multi-version history is called 1-serializable if and only if there is a 1-serial multi- version history to which the commit-completed projection of views is equivalent. ${\displaystyle H_{MV}}$ ${\displaystyle H_{MV}}$

In principle, the equivalence relation used for this is identical to the view equivalence , but the special properties of the multi-version histories make checking the equality of the last letter superfluous. This simplifies the test of whether two multi-version histories are view equivalent.

1-serializability can be tested with the help of a multi-version serializability graph: If the resulting graph is acyclic, the tested history is 1-serializable.

Comparison between viewability and 1-serializability

Only ordinary (one-version) histories can be view-serializable, while multi-version histories can only be 1-serializable. The basic meaning of both terms is - apart from the form of the history - identical: "If I only perform those operations that visibly influence the result, and that in the correct order, the result is correct". Both properties therefore confirm the correctness of the checked history. Both properties are rarely used in practice, as checking the associated graphs takes an extremely long time.