Scheduler (database)

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

A (database) scheduler is used to manage read and write access (so-called operations ) to database objects. It ensures that no conflicts occur with concurrent transactions . Transactions are executed in parallel whenever possible in order to be able to use the system resources optimally or to complete them in a shorter time than if they are executed one after the other (serially). This is particularly important in the case of multi-user databases, since in such systems many database accesses can take place in a very short time, for example in the central server of a bank that administers the accounts of all branches.

In other words, the scheduler is the component of a DBMS which constructs the sequence (also called schedule or history ) of the data accesses on the database ( database operation ) in such a way that they obey a specific protocol . A scheduler also takes over the process control. He has the option to execute an operation immediately (i.e. pass it on to the data administrator), to delay it (usually implemented via a queue) in order to give the operations priority or to reject them (by aborting the associated transaction).

A scheduler must ensure the following properties of a schedule:

• Serializability
• Failure safety

Serializability

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)

In a serial schedule , the transactions contained are executed strictly one after the other. A serial schedule is therefore always correct, because the transactions cannot overlap. However, a serial schedule is also relatively inefficient, because a transaction always has to wait for the other transaction to be completed, so that parallelization cannot be used.

A schedule is said to be serializable if it is equivalent to a serial schedule. There are the following equivalence classes :

• Final-state serializability

Schedules are final-state-equivalent if their operations generate the same final state based on the same initial state. The global consistency after execution of all transactions involved is considered.
FSR (final state serializability) is the class of all final state serializable histories.

• View serializability

Schedules are equivalent to views if all transactions 'see' the same database status, i. H. if: Transactions read the same values they produce the same result. Both the global consistency after execution of all transactions involved and the local consistency after execution of each individual transaction are considered. VSR (view serializability) is the class of all view serializable histories. ${\displaystyle \Rightarrow }$

• Conflict serializability

Schedules are conflict-equivalent if incompatible operations are arranged in the same order.
CSR (conflict serializability) is the class of all conflict serializable histories.

• Commit serializability

CMFSR (commit final state serializability) is the class of all commit-final-state-serializable histories.

CMVSR (commit view serializability) is the class of all commit-view-serializable histories.

CMCSR (commit conflict serializability) is the class of all commit conflict serializable histories.

Failure safety

Failure-proofness of a schedule is the property that, if one or more transactions are aborted, this schedule behaves in the same way as a similar schedule that only contains the transactions that have not been aborted.

There are the following classes of schedules with regard to error safety:

• RC - recoverable. It is possible to continue processing the remaining schedules after an aborted transaction without inconsistencies.
• ACA - avoids cascading abort. Nested aborts are avoided by allowing transactions to only read from completed transactions.
• ST - strict schedules.
• RG - rigorous schedules.

Classification and Protocols

Schedulers can be divided into the following classes:

• Pessimistic / conservative schedulers. These schedulers attempt to detect and resolve conflicts between concurrent transaction operations during execution. They prefer to delay operations in the event of a conflict.
  • Interlocking Scheduler (Locking Scheduler) - The g o.. Criteria are achieved through locks .
    • 2PL - two-phase locking. Every transaction is divided into two phases. In the first phase, locks may only be requested and in the second phase these may only be released. A transaction is therefore not allowed to request a new lock after a data element has been released. The schedules issued are CSR.
      • C2PL - conservative 2PL. Here, all locks are generally requested at the start of each transaction.
      • S2PL - strict 2PL. All requested write locks are only released when the transaction is completed. It can be proven that such schedules are ST in addition to CSR.
      • SS2PL - strong 2PL. All locks are only released when the transaction is completed. It can be proven that such schedules correspond to class RG.
    • Tree locking protocols. Like 2PL, but especially for trees, taking advantage of their special characteristics.
      • WTL - write only tree locking
      • RWTL - read write tree locking
      • MGL - multiple granularity locking. The database objects are organized hierarchically in a tree. At the top is z. B. the database, including tables and below tuples. In order to obtain a lock at the bottom, at least one such lock must already exist on the nodes above. This is exactly the other way around when sharing. MGL-produced schedules are CSR.
  • Non-locking schedulers
    • TO - time ordering procedure. In order to avoid synchronization problems, time stamps are assigned for each transaction as soon as its first operation is received by the scheduler. Two strategies can be distinguished: wait-die and wound-wait
      • BTO - basic TO. Simple and aggressive implementation of TO. Operations are forwarded directly to the data administrator and transactions of operations that come too late are canceled.
    • SGT - Serialization Graph Tester
    • Generic exam
• Optimistic / aggressive scheduler. These schedulers postpone the conflict check by a so-called certifier to the commit time of a transaction. You carry out a transaction in three phases: Read phase (operations are carried out, write access takes place exclusively in the transient local work area), Validation phase (during commit, the transaction is validated by the certifier), Write phase (content of the transient local work area is transferred to the persistent Transferring database). Validation phase and write phase are uninterruptible, so they are always executed without interruption.
  • BOCC - backward oriented optimistic concurrency control .
  • FOCC - forward oriented optimistic concurrency control.
• Hybrid schedulers. You distribute the conflict checking over several components that can use different protocols.
  • Differentiation according to type of conflict (read-write / write-write conflict)
  • Subdivision of the data elements into disjoint subsets
  • Subdivision of the data elements according to their access pattern

In addition, there are multi-version schedulers which can save several versions for each written data element in order to avoid inconsistent reads. In addition to and depending on the protocol implemented, a multi-version scheduler must assign a specific version of the data element read to a read operation. A write operation normally creates a new version of the respective data element. Multi-version protocols are MVTO, MV2PL, MVSGT, ROMV (read only multi-version protocol).