MDTF: A Most Dependent Transactions First Priority Assignment Heuristic

MDTF: A Most Dependent Transactions First Priority Assignment Heuristic

DOI: 10.4018/978-1-7998-3473-1.ch054
(Individual Chapters)
No Current Special Offers


The Equal slack (EQS) heuristic is one of the widely used priority assignment heuristics. However, it severely suffers from the problems of intensive data contention, deadlock, and cyclic restart. To overcome some of the above problems, this chapter proposes a Most Dependent Transaction First (MDTF) priority heuristic that injects the size of dependent transactions of all directly competing transactions (that have requested access to the conflicting data item) in their priority computation. The MDTF heuristic efficiently reduces the data contentions among concurrently executing cohorts; and thus, it reduces the wastage of the system resources. This dynamic cohort priority assignment heuristic reduces the data contention considerably by utilizing the information about the dependency size of cohort(s). Doing this will make it easy for a currently executing cohort to better assess the level of data contention with absolutely no extra communication and time overhead. Such detailed dependency information is very useful to efficiently assign priorities to the cohorts.
Chapter Preview


In recent years, considering the ever-growing challenging and complex requirements of target users, several advanced real-time based applications are developed by utilizing the database framework and scheduling aspects of time-constrained databases (Shanker, Misra, & Sarje, 2006a). The transaction processing techniques were first studied from the real-time perspective in real time database system (RTDBS). The RTDBS is simply a database system which works up on real time transaction (RTT).

The RTTs are associated with deadlines. They may be categorized as soft, firm and hard based on the consequences of their deadline misses. The soft RTT’s deadline miss means the result will have lesser value (positive but diminishing); the firm RTT’s deadline miss means the result will have no value (zero value), and the hard RTT’s deadline miss means the result may be catastrophic (negative value). Therefore, the soft/firm/ hard RTTs must be completed without missing their deadline to make sure the meeting of the objectives of executing it. This discussion makes one point very much clear that deadline computation of RTTs (priority assignment of RTTs) should be performed in a customized fashion considering the nature of the application to get the best possible outcome.

Several protocols were developed to improve overall RTDBS performance. Then, it is realized that most of the real-life problems related to the database are distributed in nature. For instance, a balance transfer transaction between users of two different banks. To incorporate all these requirements, a more advanced research area called distributed real time database system (DRTDBS) is evolved. The DRTDBS may be defined as a collection of a finite number of time-constrained distributed database systems (Pandey & Shanker, 2016) (Pandey & Shanker, 2018c) connected through a network. In DRTDBS, a distributed RTT is generated at the parent site. The coordinator of this transaction is then tasked to coordinate and perform changes at multiple sites atomically. In contrary to the traditional databases, the correctness of the result in DRTDBS based application depends on two things: logical computation performed, and the time when the result is produced & disseminated. Although the result produced is functionally right, it may lead to tragic repercussions, be unusable, or has less value if it is not produced in time (Shanker, Misra, & Sarje, 2001). To make it easy for understanding, a complete list of acronyms with their meaning is presented below in Table 1.

Table 1.
Table of Acronyms
RTDBSReal Time Database System
RTTReal Time Transaction
DRTDBSDistributed Real Time Database System
RTSReal Time System
EDFEarliest Deadline First
AEDAdaptive Earliest Deadline
AEVDAdaptive Earliest Virtual Deadline
AAPAdaptive Access Parameter
UDUltimate Deadline
EDEffective Deadline
EQSEqual Slack
SSSlack-time Slice
EQFEqual Flexibility
PSSProportional Slack-time Slice
NLNumber of Locks
MNLModified Number of Locks
MDTFMost Dependent Transactions First

Key Terms in this Chapter

Hard Distributed Real-Time Transaction (Hard DRTT): The hard DRTT must be finished before its deadline; otherwise, it may lead to potentially catastrophic consequence.

Soft Distributed Real-Time Transaction (Soft DRTT): The soft DRTT is not killed/aborted in case of its deadline miss because the result has some value (obviously degrading) even after the deadline miss.

Priority Assignment Heuristic: Act as a base for all other DRTT processing components, i.e. concurrency control and commit processing; therefore, largely affects the DRTDBS performance.

Earliest Deadline First (EDF): As per the EDF heuristic, priority of a task is inversely proportional to its deadline. So, the highest priority is assigned to the task with the earliest deadline.

Distributed Real-Time Database System (DRTDBS): The DRTDBS consists of multiple data sites that are connected through an underlying computer network specifically used to run applications based on distributed real-time transactions.

Real-Time Commit Protocols: Ensure that either all the effects of the DRTT persist or none of them irrespective of any such failure.

Firm Distributed Real-Time Transaction (Firm DRTT): The firm DRTT is killed in case it misses its deadline because its outcome has no value after deadline miss.

Complete Chapter List

Search this Book: