Content deleted Content added
→Duration: removed redundancy |
→Duration: Changed and merged headings to redistribute the information |
||
Line 3:
{{more citations needed|date=November 2012}}
In the fields of [[database]]s and [[transaction processing]] (transaction management), a '''schedule''' (or '''history''') of a system is an abstract model to describe [[Execution (computing)|execution]] of transactions running in the system. Often it is a ''list'' of operations (actions) ordered by time, performed by a set of [[Database transaction|transactions]] that are executed together in the system. If the order in time between certain operations is not determined by the system, then a ''[[partial order]]'' is used. Examples of such operations are requesting a read operation, reading, writing, aborting, [[Commit (data management)|committing]], requesting a [[Lock (computer science)|lock]], locking, etc. Not all transaction operation types should be included in a schedule, and typically only selected operation types (e.g., data access operations) are included, as needed to reason about and describe certain phenomena. Schedules and schedule properties are fundamental concepts in database [[concurrency control]] theory. A schedule describes the order of actions of the transactions as seen by the [[DBMS]].
Grid notation:
▲=== Notation ===
* '''Columns:''' The different transactions in the schedule.
* '''Rows:''' The time order of operations (a.k.a., actions).
Operations/actions:
* '''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.
Alternatively, a 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.
The following is an example of a schedule:
{| class="wikitable"
Line 68 ⟶ 67:
D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3
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. Real executed operations always have some duration.
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).
| |||