History (transaction processing)

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:44, December 4, 2011 (CET)

A history (which corresponds to a complete schedule , see section Schedule and Schuffle Product ) is used in computer science in the field of database theory to describe an execution plan for the parallel execution of several transactions (see also transaction system ), which specifies the order in which the transaction operations are executed. The possible types of transaction operations include read and write operations, and the scheduling operations Commit (successful completion of the transaction) and Abort (termination of the transaction). The history is therefore a designation for the execution order of all operations of the parallel executed transactions.

Schedule and shuffle product

The term schedule should also be mentioned in connection with history. A schedule is a so-called prefix of a history. In this context, the prefix means: the first to the nth element of the history. A complete schedule therefore corresponds to a history. A (formal) example of a schedule would be:

The following elements are given:

${\displaystyle x,y,z}$: Data objects in a database

${\displaystyle T_{i}}$: a transaction executed in parallel ${\displaystyle n}$

${\displaystyle R_{i}(x)}$: Read operation of the transaction on the object ${\displaystyle i}$ ${\displaystyle x}$

${\displaystyle W_{i}(x)}$: Write operation of the transaction on the object ${\displaystyle i}$ ${\displaystyle x}$

${\displaystyle C_{i}}$: Commit operation of the transaction (successful completion of the transaction) ${\displaystyle i}$

${\displaystyle A_{i}}$: Abort operation of the transaction (termination of the transaction) ${\displaystyle i}$

${\displaystyle H_{i}}$: one of i possible histories for up to ${\displaystyle T_{1}}$ ${\displaystyle T_{n}}$

${\displaystyle S_{i}(H_{i})}$: a schedule of history ${\displaystyle H_{i}}$

For the parallel execution of 3 transactions ( ) one of the possible histories ( ), with its write operations ( ) and read operations ( ) on the objects ( ) and the associated commit operations ( ) and abort operations ( ), looks like this: ${\displaystyle T_{1},T_{2},T_{3}}$ ${\displaystyle H_{1}}$ ${\displaystyle W_{i}()}$ ${\displaystyle R_{i}()}$ ${\displaystyle x,y,z}$ ${\displaystyle C_{i}}$ ${\displaystyle A_{i}}$

history ${\displaystyle H_{1}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2},W_{1}(x),C_{1}}$

A possible schedule ( ), in this case the complete schedule, for this history would be: ${\displaystyle S_{1}}$

Schedule ${\displaystyle S_{1}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2},W_{1}(x),C_{1}}$

Another possible schedule ( ) (incomplete) for this history would be: ${\displaystyle S_{2}}$

Schedule ${\displaystyle S_{2}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2}}$

Another possible schedule ( ) (incomplete) for this history would be: ${\displaystyle S_{3}}$

Schedule ${\displaystyle S_{3}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3}}$

There are of course other histories for the parallel execution of the three transactions, e.g. B. if we simply postpone the two operations of the third transaction:

history ${\displaystyle H_{2}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),W_{2}(y),C_{2},W_{1}(x),C_{1},R_{3}(y),A_{3}}$

The set of all possible combinations of read and write operations, but without the commit and abort operations, is called the shuffle product . If we take our second history ( ) as the basis, then the element ( ) from the set of shuffle products ( ) would be: ${\displaystyle H_{2}}$ ${\displaystyle S_{2}}$ ${\displaystyle S}$

${\displaystyle S_{2}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),W_{2}(y),W_{1}(x),R_{3}(y)}$

A closer look reveals that the combination of read and write operations remains the same, but the commit and cancel operations have been removed.

Serial and non / serializable histories, correctness criterion "serializability"

In addition to the representation of certain execution sequences of the operations, histories serve to define (and are the basis for checking) the serializability of these execution sequences.

Imagine the following transactions on an account:

1. ${\displaystyle T_{1}}$: Withdraw 100, - € from account no. 777980.
2. ${\displaystyle T_{2}}$: Pay 52, - € into account no. 777980.

${\displaystyle T_{1}}$comprises a read operation to read in the account balance and a write operation to modify the account balance. Same goes for . A total of four operations have to be carried out for these two transactions. A history now defines the order in which these operations are processed. The most obvious solution would be to execute the transactions one after the other (" serially "), for example all operations from and then all operations from . Such a history is called a serial history . ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

A problem arises when the serial execution of transactions is inefficient. For example, when a whole series of transactions has to wait because the first transaction is waiting for user input. In some cases the strict sequential execution is not necessary at all, e.g. B. when the transactions work on completely different data objects, or only perform read operations. In this case, we get a low transaction throughput rate (completed transactions per unit of time). In order to increase the transaction throughput, histories are also permitted in transaction systems in which several transactions are so-called "active" at the same time. Active means that a transaction can start executing before the current transactions are completed, and operations on subsequent transactions can be performed before the current transactions are completed. Such a concurrent history is correct if it delivers the same results as a serial history. ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$

Formally, a correctness criterion serializability can be defined for the concurrent execution of transactions: A history can be serialized if it is equivalent to a serial history . The order of the transactions in is then called the serialization order. It is important that the relative order of conflicting operations (e.g. two write operations) in the history corresponds to the serialization order of the associated transactions. Conflicting operation means that two operations in different transactions access the same data object and at least one of the operations involved is a write operation. ${\displaystyle H}$ ${\displaystyle H'}$ ${\displaystyle H'}$ ${\displaystyle H}$

Totally and partially ordered histories

Since the order does not matter for some operations, histories define i. A. No total order on all operations, but only a partial order, which primarily determines the relative order of conflicting operations. Such partial orders can be represented with the help of a directed graph:

${\displaystyle {\begin{matrix}r_{1}[x]&\rightarrow &w_{1}[x]&&r_{1}[x]&\rightarrow &c_{1}&\rightarrow &c_{2}\\&&\downarrow &\nearrow \\r_{2}[y]&\rightarrow &w_{2}[x]\end{matrix}}}$

In the history presented here, a read operation of the transaction on an object is recorded as , while a write operation from to is recorded as . The arrows indicate the relative order of conflicting operations. The history shown here cannot be serialized. ${\displaystyle T_{1}}$ ${\displaystyle x}$ ${\displaystyle r_{1}[x]}$ ${\displaystyle T_{1}}$ ${\displaystyle x}$ ${\displaystyle w_{1}[x]}$

Individual evidence

1. ^ Theo Härder and Erhard Rahm: Database systems, concepts and techniques of implementation , 2nd edition (2001), page 413
2. ↑ Theo Härder and Erhard Rahm: Database systems, concepts and techniques of implementation , 2nd edition (2001)

literature

• Alfons Kemper, André Eickler: Database systems . Oldenbourg , 2004, ISBN 3-486-25706-4 .
• Theo Härder, Erhard Rahm: Database systems, concepts and implementation techniques . Springer , Berlin 2001, ISBN 3-540-42133-5 .