Database transaction schedule: Difference between revisions

Revision as of 16:49, 15 February 2024

Revision as of 22:22, 17 February 2024

Line 6:

==Formal description==

A schedule describes the actions of the transactions as seen by the [[DBMS]].

=== Notation ===

Definitions:

* '''Columns:''' The different transactions in the schedule.

* '''Rows:''' The time order of operations.

* '''R(X):''' The corresponding transaction "reads" object X (i.e., it retrieves the data stored at X). This is done so that it can modify the data (e.g., X=X+4) during a "write" operation rather than merely overwrite it. When the schedule is represented as a list rather than a grid, the action is represented as <math>Ri(X)</math> where <math>i</math> is a number corresponding to a specific transaction.

* '''W(X):''' The corresponding transaction "writes" to object X (i.e., it modifies the data stored at X). When the schedule is represented as a list rather than a grid, the action is represented as <math>Wi(X) </math> where <math>i</math> is a number corresponding to a specific transaction.

* '''Com.:''' This represents a "commit" operation in which the corresponding transaction has successfully completed its preceding actions, and has made all its changes permanent in the database.

==== Example ====

The following is an example of a schedule:

{| class="wikitable"

Line 50 ⟶ 61:

|Com.

|}

In this example, the horizontalcolumns axis representsrepresent the different transactions in the schedule D. The vertical axis represents time order of operations. Schedule D consists of three transactions T1, T2, T3. First TheT1 scheduleReads describesand theWrites actionsto ofobject theX, transactionsand asthen seenCommits. byThen theT2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and [[DBMS]]Commits.

First T1 Reads and Writes to object X, and then Commits. Then T2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and Commits. This is an example of a ''serial'' schedule, i.e., sequential with no overlap in time because the actions of all three transactions are sequential, and the transactions are not interleaved in time.

The schedule D above can be written as a list in the following way:

Representing the schedule D above by a table (rather than a list) is just for the convenience of identifying each transaction's operations in a glance. This notation is used throughout the article below. A more common way in the technical literature for representing such schedule is by a list:

:::D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

=== Duration ===

Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as ''[[Atomicity (database systems)|atomic]]'', occurring at a point in time, without duration. When this is not satisfactory, start and end time-points and possibly other point events are specified (rarely). Real executed operations always have some duration and specified respective times of occurrence of events within them (e.g., "exact" times of beginning and completion), but for concurrency control reasoning usually only the precedence in time of the whole operations (without looking into the quite complex details of each operation) matters, i.e., which operation is before, or after another operation. Furthermore, in many cases, the before/after relationships between two specific operations do not matter and should not be specified, while being specified for other pairs of operations.

=== Order of actions ===

In general, operations of transactions in a schedule can interleave (i.e., transactions can be executed concurrently), while time orders between operations in each transaction remain unchanged as implied by the transaction's program. Since not always time orders between all operations of all transactions matter and need to be specified, a schedule is, in general, a ''[[partial order]]'' between operations rather than a ''[[total order]]'' (where order for each pair is determined, as in a list of operations). Also in the general case, each transaction may consist of several processes, and itself be properly represented by a partial order of operations, rather than a total order. Thus, in general, a schedule is a partial order of operations, containing ([[embedding]]) the partial orders of all its transactions.