A multi-granularity locking model for concurrency control inobject-oriented database systems

A locking model adopting a multi-granularity approach is proposed for concurrency control in object-oriented database systems. The model is motivated by a desire to provide high concurrency and low locking overhead in accessing objects. Locking in schemas and locking in instances are developed separately and then are integrated. Schema changes and composite objects are also taken into account. A dual queue scheme for efficient scheduling of lock requests is developed. The model consists of a rich set of lock modes, a compatibility matrix, and a locking protocol. Characteristic query examples on single class, class lattice, and composite objects are used to illustrate the comparison between the ORION model and the proposed model. It is shown that our locking model has indeed made some improvements and is suitable for concurrency control in object-oriented databases     

A non-two-phase locking protocol for global concurrency control indistributed heterogeneous database systems

A concurrency control method is proposed for global transactions in a distributed heterogeneous database system. This method is applicable when the database sites are interconnected in a rooted tree fashion. It guarantees deadlock freedom in addition to serializability. A general architecture of a heterogeneous system is given. The global transaction manager (GTM) decomposes the global transactions initiated at a site and the subtransactions received from other sites into smaller subtransactions, some of which are sent to the GTMs of the other sites, and those remaining, called g-local transactions, are to be executed by the local transaction manager (LTM) at that site. A concurrency control mechanism ensures serializability among: the local transactions (including the g-local transactions of the global ones) at each site, the global transactions and the global and local transactions together     

A transaction model and multiversion concurrency control for mobile database systems

Transaction management on Mobile Database Systems (MDS) has to cope with a number of constraints such as limited bandwidth, low processing power, unreliable communication, and mobility etc. As a result of these constraints, traditional concurrency control mechanisms are unable to manage transactional activities to maintain availability. Innovative transaction execution schemes and concurrency control mechanisms are therefore required to exploit the full potential of MDS. In this paper, we report our investigation on a multi-versions transaction processing approach and a deadlock-free concurrency control mechanism based on multiversion two-phase locking scheme integrated with a timestamp approach. We study the behavior of the proposed model with a simulation study in a MDS environment. We have compared our schemes using a reference model to argue that such a performance comparison helps to show the superiority of our model over others. Experimental results demonstrate that our model provide significantly higher throughput by improving degree of concurrency, by reducing transaction wait time, and by minimizing restarts and aborts.     

Optimistic priority-based concurrency control protocol for firm real-time database systems

This paper presents an optimistic priority-based concurrency control protocol that schedules active transactions accessing firm deadline real-time database systems. This protocol combines the forward and backward validation processes in order to control concurrent transactions with different priorities more effectively. For a transaction in the validation phase, it can be committed successfully if the serialization order is adjusted in favour of the transactions with higher priority and aborted otherwise. Thus, this protocol establishes a priority ordering technique whereby a serialization order is selected and transaction execution is forced to obey this order. This priority-based protocol addresses the problem of satisfying data consistency, with the goal being to increase the number of transactions that commit by their deadlines. In addition, for desirable real-time conflict resolution, this protocol intends to meet more deadlines of higher priority transactions then lower priority transactions.     

Evaluation of concurrency control strategies for mixed soft real-time database systems

Previous research in real-time concurrency control mainly focuses on the schedulability guarantee of hard real-time transactions and the reduction of the miss rate of soft real-time transactions. Although many new database applications have significant response time requirements, not much work has been done in the joint scheduling of traditional non-real-time transactions and soft real-time transactions. In this paper, we study the concurrency control problems in mixed soft real-time database systems, in which both non-real-time and soft real-time transactions exist simultaneously. The objectives are to identify the cost and the performance tradeoff in the design of cost-effective and practical real-time concurrency control protocols, and to evaluate their performance under different real-time and non-real-time supports. In particular, we are interested in studying the impacts of different scheduling approaches for soft real-time transactions on the performance of non-real-time transactions. Instead of proposing yet another completely new real-time concurrency control protocol, our objective is to design an efficient integrated concurrency control method based on existing techniques. We propose several methods to integrate the well-known two phase locking and optimistic concurrency control with the aims to meet the deadline requirements of soft real-time transactions and, at the same time, to minimize the impact on the performance of non-real-time transactions. We have conducted a series of experiments based on a sanitized version of stock trading systems to evaluate the performance of both soft real-time and non-real-time transactions under different real-time supports in the system.     

A generic simulation model for evaluating concurrency control protocols in native XML database systems

In this paper we propose a generic simulation model, named XSM, with which researchers can construct standard platforms and evaluate their proposed concurrency control protocols for native XDBMSs. The system environment, the performance metrics, and the protocol rules of various types of XML protocols are all considered by the model. To facilitate the implementation of XSM, the state diagrams, the sequence diagrams, the component diagram, and the class diagram of XSM are depicted using UML 2.0 notations. We also show a simulation platform constructed from XSM to fairly and comprehensively evaluate the performance of various XML protocols.     

Optimistic versus pessimistic concurrency control mechanisms in database management systems

Concurrency control mechanisms are necessary to preserve database integrity in a multi-user environment. Two kinds of concurrency control mechanisms are considered in this paper, namely optimistic and pessimistic ones. Optimistic concurrency control is based on the idea of conflicts and transaction restart while pessimistic concurrency control uses locking as the basic serialization mechanism. Analytic and simulation models of both mechanisms were developed in order to compare them as far as transaction response time is concerned. These results take into consideration parameters such as transaction arrival rate, number of database resources accessed per transaction, size of the database, system processing rate and degree of multiprogramming.     

A concurrency control model for PDM systems

In today's manufacturing environment, enterprises having work groups geographically dispersed are not uncommon. A product data management (PDM) system is therefore required for controlling the distribution and maintaining the integrity of the product data throughout its entire lifecycle; the efficiency of a PDM system is greatly affected by the concurrency control method it adopts. The paper proposes a concurrent control model for PDM that can also caters for version management and product architecture. The paper discusses how granularity and versioning are being embedded into a lock-based concurrency control model. The concurrent accessibility of an example product data is explained to illustrate the adjustability according to the actions taken by the users and the architecture of the corresponding entities.     

Cautious transaction schedulers for database concurrency control

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed     

On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

一种新的实时数据库的乐观并发控制协议

针对一些并发控制协议中由于过多的事务重启动造成资源浪费,提出了一种新的乐观并发控制协议(Optimistic Concurrency Control),通过向后调整不严重冲突事务的动态串行化顺序,许多不必要的事务重启动可以避免。在一个事务的读阶段不用记录事务冲突和串行化限制,各种优先级冲突解决方法可以很方便地加入到该协议中,根据需要选择使用了优先级-中止-50机制。     

An intelligent hybrid optimistic/pessimistic concurrency control algorithm for centralized database systems using modified GSA-optimized ART neural model

Concurrency control is the activity of synchronizing operations issued by concurrent executing transactions on a shared database. The aim of this control is to provide an execution that has the same effect as a serial (non-interleaved) one. The optimistic concurrency control technique allows the transactions to execute without synchronization, relying on commit-time validation to ensure serializability. Effectiveness of the optimistic techniques depends on the conflict rate of transactions. Since different systems have various patterns of conflict and the patterns may also change over time, so applying the optimistic scheme to the entire system results in degradation of performance. In this paper, a novel algorithm is proposed that dynamically selects the optimistic or pessimistic approach based on the value of conflict rate. The proposed algorithm uses an adaptive resonance theory–based neural network in making decision for granting a lock or detection of the winner transaction. In addition, the parameters of this neural network are optimized by a modified gravitational search algorithm. On the other hand, in the real operational environments we know the writeset (WS) and readset (RS) only for a fraction of transactions set before execution. So, the proposed algorithm is designed based on optional knowledge about WS and RS of transactions. Experimental results show that the proposed hybrid concurrency control algorithm results in more than 35 % reduction in the number of aborts in high-transaction rates as compared to strict two-phase locking algorithm that is used in many commercial database systems. This improvement is 13 % as compared to pure-pessimistic approach and is more than 31 % as compared to pure-optimistic approach.     

Evolving a model of transaction management with embedded concurrency control for mobile database systems

Transactions within a mobile database management system face many restrictions. These cannot afford unlimited delays or participate in multiple retry attempts for execution. The proposed embedded concurrency control (ECC) techniques provide support on three counts, namely—to enhance concurrency, to overcome problems due to heterogeneity, and to allocate priority to transactions that originate from mobile hosts. These proposed ECC techniques can be used to enhance the server capabilities within a mobile database management system. Adoption of the techniques can be beneficial in general, and for other special cases of transaction management in distributed real-time database management systems. The proposed model can be applied to other similar problems related to synchronization, such as the generation of a backup copy of an operational database system.     

Fuzzy neural-based control for nonlinear time-varying delay systems.

In this paper, a partially known nonlinear dynamic system with time-varying delays of the input and state is approximated by N fuzzy-based linear subsystems described by a state-space model with average delay. To shape the response of the closed-loop system, a set of fuzzy reference models is established. Similarly, the same fuzzy sets of the system rule are employed to design a fuzzy neural-based control. The proposed control contains a radial-basis function neural network to learn the uncertainties caused by the approximation error of the fuzzy model (e.g., time-varying delays and parameter variations) and the interactions resulting from the other subsystems. As the norm of the switching surface is inside of a defined set, the learning law starts; in this situation, the proposed method is an adaptive control possessing an extra compensation of uncertainties. As it is outside of the other set, which is smaller than the aforementioned set, the learning law stops; under this circumstance, the proposed method becomes a robust control without the compensation of uncertainties. A transition between robust control and adaptive control is also assigned to smooth the possible discontinuity of the control input. No assumption about the upper bound of the time-varying delays for the state and the input is required. However, two time-average delays are needed to simplify the controller design: 1) the stabilized conditions for every transformed delay-free subsystem must be satisfied; and 2) the learning uncertainties must be relatively bounded. The stability of the overall system is verified by Lyapunov stability theory. Simulations as compared with a linear transformed state feedback with integration control are also arranged to consolidate the usefulness of the proposed control.     

一种多粒度锁的事务并发控制算法

研究了一种基于多粒度锁的并发控制算法,包括其多粒度锁锁、锁表数据结构及锁操作的算法步骤。算法可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。在验证算法有效性时,通过测试类对内存数据库记录的插入速度、索引查找的速度、记录的删除速度三方面的性能进行了测试,结果表明,事务并发控制优化算法对内存数据库性能的提升是有效可行的。     

A theory of global concurrency control in multidatabase systems

This article presents a theoretical basis for global concurrency control to maintain global serializability in multidatabase systems. Three correctness criteria are formulated that utilize the intrinsic characteristics of global transactions to determine the serialization order of global subtransactions at each local site. In particular, two new types of serializability, chain-conflicting serializability and sharing serializability, are proposed and hybrid serializability, which combines these two basic criteria, is discussed. These criteria offer the advantage of imposing no restrictions on local sites other than local serializability while retaining global serializability. The graph testing techniques of the three criteria are provided as guidance for global transaction scheduling. In addition, an optimal property of global transactions for determinating the serialization order of global subtransactions at local sites is formulated. This property defines the upper limit on global serializability in multidatabase systems.     

Dynamic priority ceilings: A concurrency control protocol for real-time systems

Real-time systems have stringent deadline requirements for their tasks. To meet the requirements, a real-time system must use scheduling algorithms that ensure a predictable response even in the face of mutually exclusive accesses to critical sections. We present a concurrency control protocol for systems using the earliest deadline first scheduling algorithm. The protocol specifies a dynamic priority ceiling for each critical section which is the earliest deadline of jobs which are currently in or will enter the critical section. Jobs trying to enter a critical section will be blocked if they do not have a priority higher than the priority ceiling of any critical section which is in use. We show that the protocol prevents both deadlock and chained blocking. The schedulability condition and implementation issues of the protocol are also discussed.     

A model for database allocation incorporating a concurrency controlmechanism

The impact of incorporating a specific concurrency control mechanism (CCM) into the file allocation problem (FAP) is discussed. Depending on the specific CCM use, the communication flows in a network will vary. To allocate data optimally, one must identify the exact communication flows in the network. It is this aspect that has been ignored in past research on the FAP. A linear mixed-integer programming model formulated for the FAP is given. The model incorporates the WRITE LOCKS ALL-READ LOCKS ONE mechanism for concurrency control. A special algorithm based on the implicit representation of variable upper bounds is developed to solve the model. Detailed analysis for various configurations of a network is performed. Several potential applications for the model are identified     

Modeling selected real-time database concurrency control protocols in Uppaal

Real-time database management systems (RTDBMS) are recently subject of an intensive research. Model checking algorithms and verification tools are of great concern as well. In this paper, we show some possibilities of using a verification tool Uppaal on some variants of pessimistic and optimistic concurrency control protocols used in real-time database management systems. We present some possible models of such protocols expressed as nets of timed automata, which are a modeling language of Uppaal. M. Kot acknowledges the support by the Czech Ministry of Education, Grant No. 1M0567.