Serializability

As serializable is called in transaction systems has a history that leads to the same result as a serial history over the same transactions. A distinction Conflict serializability, Sichtenserialisierbarkeit and 1- serializability; without the addition is under serializability usually the Conflict serializability understood.

Illustrative example

To be able to imagine vividly the key terms of this article is intended to serve the following example:

Conflict serializability

To verify the equivalence of the histories of conflict equivalence is used here. The terms of the Conflict serializability denominated in formulas:

In words:

The commit completed projection of a history contains only those transactions that are completed by Commit ( so do not be aborted). This projection is explained in the article history closer.

Conflict serializability can be tested using a Serialisierbarkeitsgraphen: Is the resulting graph acyclic, so the tested history is serializable.

Sichtenserialisierbarkeit

Here the view equivalence is used to check the equivalence. The terms of the Sichtenserialisierbarkeit loud - similar to above - in formulas:

In words:

Sichtenserialisierbarkeit can be tested with the aid of a polygraph: Is the resulting graph acyclic, so the tested history is sichtenserialisierbar.

Relationship between conflict and Sichtenserialisierbarkeit

The set of all histories konfliktserialisierbaren forms a proper subset of the set of all sichtenserialisierbaren histories. Histories that are konfliktserialisierbar, are therefore automatically also sichtenserialisierbar. Sichtenserialisierbarkeit is theoretically the more effective form of serializability, because it allows more concurrency and thus better performance than Conflict serializability. The problem is that the test on Sichtenserialisierbarkeit with a polygraph is NP-complete, so extremely long takes. Thus, a utilization of Sichtenserialisierbarkeit is practically impossible.

1- serializability

The 1- serializability is a specialization of Sichtenserialisierbarkeit on More versions histories. In formulas:

In words:

In principle, the equivalence relation used for this purpose is the same as the perspective of equivalence, the special properties of the multi - version histories make but checking the equality of the last letter fell. The test whether two more versions histories are view equivalent, is simplified.

1- serializability can be tested with the help of a multi - versions Serialisierbarkeitsgraphen: Is the resulting graph acyclic, so the tested history is 1- serializable.

Comparison between views and 1- serializability

Only ordinary ( Einversionen ) histories can be sichtenserialisierbar while More versions histories can be 1- serializable exclusively. The basic meaning of both terms is - you can see the shape of the history from - the same: "If I run only the operations that affect the result visible, and in the correct order, the result is correct." So both properties confirm the correctness of the verified history. Both properties are rarely used in practice because the check on the associated graphs takes an extremely long time.

• Database Theory