Database transaction schedule: Difference between revisions

Revision as of 01:36, 26 February 2024

Revision as of 03:10, 26 February 2024

Line 16:

* '''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.

Alternatively, the schedule can be represented with a ''[[acyclic directed graph|directed acyclic graph]]'' (or DAG) in which there is an arc (i.e., [[directed edge]]) between each ''[[ordered pair]]'' of operations.

==== Example ====

Line 72 ⟶ 73:

=== Order of actions ===

Operations of transactions in a schedule can interleave (i.e., transactions can be executed [[Concurrency (computer science)|concurrently]]), but time orders between operations in each transaction must remain unchanged. The schedule is in ''[[partial order]]'' when the operations of transactions in a schedule interleave (i.e., when the schedule is conflict-serializable but not serial). The schedule is in ''[[partial order|total order]]'' when the operations of transactions in a schedule do not interleave (i.e., when the schedule is serial).

Time-order between two operations can be represented by an ''[[ordered pair]]'' of these operations (e.g., the existence of a pair (OP1, OP2) means that OP1 is always before OP2), and a schedule in the general case is a [[set (mathematics)|set]] of such ordered pairs. Such a set, a schedule, is a [[partial order]] which can be represented by an ''[[acyclic directed graph]]'' (or ''directed acyclic graph'', DAG) with operations as nodes and time-order as a [[directed edge]] (no cycles are allowed since a cycle means that a first (any) operation on a cycle can be both before and after (any) another second operation on the cycle, which contradicts our perception of [[Time]]). In many cases, a graphical representation of such a graph is used to demonstrate a schedule.

'''Comment:''' Since a list of operations (and the table notation used in this article) always represents a total order between operations, schedules that are not a total order cannot be represented by a list (but always can be represented by a DAG).

==Types of schedule==