实时主动数据库有效性检查并发控制协议

在实时主动数据库中,事务不仅有时间约束,而且事务执行可能触发其它事务执行。传统并发控制协议不适应于实时主动数据库系统。该文研究了实时主动数据库事务执行模式,提出了有效性检查并发控制协议。协议使用动态调整串行次序策略,避免不必要的事务重启动。通过仿真模拟与HP2PL协议和OCC-TI-WAIT-50协议进行了比较。结果表明,该协议能有效地降低事务延误截止时间率和事务重启动率,性能优于HP2PL和OCC-TI-WAIT-50协议。     

Efficient execution of read-only transactions in replicatedmultiversion databases

Multiple versions of data are used in database systems to increase concurrency. The higher concurrency results since read-only transactions can be executed without any concurrency control overhead and, therefore, read-only transactions do not interfere with the execution of update transactions. Availability of data in a distributed environment is improved by data replication. We propose a protocol for managing data in a replicated multiversion environment, where execution of read-only transactions or queries becomes completely independent of the underlying concurrency control and replica control mechanisms, and the data availability for read-only transactions increases significantly since they can be executed as long as any one copy of the object is available in the system. In order to validate the feasibility of our approach, we developed a simple prototype to measure the performance improvement in the response times of queries. The results clearly establish the viability of the approach as a useful paradigm for the design of efficient and fault-tolerant distributed database systems     

Global scheduling for flexible transactions in heterogeneousdistributed database systems

A heterogeneous distributed database environment integrates a set of autonomous database systems to provide global database functions. A flexible transaction approach has been proposed for the heterogeneous distributed database environments. In such an environment, flexible transactions can increase the failure resilience of global transactions by allowing alternate (but in some sense equivalent) executions to be attempted when a local database system fails or some subtransactions of the global transaction abort. We study the impact of compensation, retry, and switching to alternative executions on global concurrency control for the execution of flexible transactions. We propose a new concurrency control criterion for the execution of flexible and local transactions, termed F-serializability, in the error-prone heterogeneous distributed database environments. We then present a scheduling protocol that ensures F-serializability on global schedules. We also demonstrate that this scheduler avoids unnecessary aborts and compensation     

A practical approach to the design of concurrency in object-oriented systems

Object-oriented software development methods deal with concurrency according to either the implicit concurrency model or the explicit concurrency model. In the implicit model, the objects themselves have concurrent execution capabilities whereas in the explicit model, objects are encapsulated inside processes, the latter providing concurrent execution capabilities. Both models have their advantages and disadvantages. In this paper, we propose applying the implicit model only while conducting object-oriented analysis and then switching over to the explicit model in the design phase. The implicit model naturally fits the analysis phase because the resulting models of the software system will be based on objects—the important concepts of the application—not the issues of how concurrency is implemented. A switch over to the explicit model in the design phase achieves smooth integration with already existing software consisting of processes—which is the main constraint in many industrial applications. This paper presents in detail a systematic solution for the switch over between the concurrency models that applies for soft real-time systems and demonstrates it by a simplified example from a real telecommunication project. Any object-oriented method not yet dealing with concurrency issues can easily integrate the solution. ©1997 John Wiley & Sons, Ltd.     

Concurrent behavior: A construct to specify the external behavior of objects in object databases

We present a linguistic construct to define concurrency control for the objects of an object database. This construct, calledconcurrent behavior, allows to define a concurrency control specification for each object type in the database; in a sense, it can be seen as a type extension. The concurrent behavior is composed by two parts: the first one, calledcommutativity specification, is a set of conditional rules, by which the programmer specifies when two methods do not conflict each other. The second part, the constraint specification, is a set of guarded regular expressions, calledconstraints, by which the programmer defines the allowed sequences of method calls. At each time during an actual execution, a subset of constraints may be active so limiting the external behavior of the object. A constraint becomesactive when its guard is verified, where a guard is composed of the occurrence of some method callm along with the verification of a boolean expression on the object state and the actual parameters ofm. A constraint dies when a string of the language corresponding to the regular expression has been recognized. While the commutativity specification is devoted to specify the way in which the external behavior of an object is influenced by the existence of concurrent transactions in the system, the constraint specification defines the behavior of the object, independently from the transactions. Since the two parts of the concurrent behavior are syntactically distinct and, moreover, each of them consists of a set of independent rules, modularity in specifying the objects is enhanced, with respect to a unique specification. We outline an implementation of the construct, which is based on a look-ahead policy: at each method execution, we foresee the admissible successive behaviors of the object, instead of checking the admission of each request at the time it is actually made.     

Applying semantic knowledge to real-time update of access control policies

Real-time update of access control policies, that is, updating policies while they are in effect and enforcing the changes immediately, is necessary for many security-critical applications. In this paper, we consider real-time update of access control policies in a database system. Updating policies while they are in effect can lead to potential security problems, such as, access to database objects by unauthorized users. In this paper, we propose several algorithms that not only prevent such security breaches but also ensure the correctness of execution. The algorithms differ from each other in the degree of concurrency provided and the semantic knowledge used. Of the algorithms presented, the most concurrency is achieved when transactions are decomposed into atomic steps. Once transactions are decomposed, the atomicity, consistency, and isolation properties no longer hold. Since the traditional transaction processing model can no longer be used to ensure the correctness of the execution, we use an alternate semantic-based transaction processing model. To ensure correct behavior, our model requires an application to satisfy a set of necessary properties, namely, semantic atomicity, consistent execution, sensitive transaction isolation, and policy-compliant. We show how one can verify an application statically to check for the existence of these properties.     

基于级联深度的主动实时乐观并发控制协议

主动实时数据库因结合了时间限制与主动机制而使系统事务的并发控制变得更为复杂。主动规则的引入使事务触发新的事务且在执行上具有多种耦合方式,传统的实时并发控制策略无法对具有复杂执行模式的事务进行有效调度,而基于主动数据库的并发控制机制也没有考虑事务的实时性问题。通过对事务不同耦合方式的实时要求及事务间冲突关系进行分析,提出了新的主动实时数据库乐观并发控制方法,对不同事务级联深度进行评估,结合事务执行的时间信息对冲突事务进行动态调整串行化顺序。理论分析与实验证明,能在保证事务可串行性的同时降低了不必要事务重启个数,更好地满足系统的实时性。     

Multi-level transaction model for semantic concurrency control in linear hash structures

In this paper, we present a version of the linear hash structure algorithm to increase concurrency using multi-level transaction model. We exploit the semantics of the linear hash operations at each level of transaction nesting to allow more concurrency. We implement each linear hash operation by a sequence of operations at lower level of abstraction. Each linear hash operation at leaf-level is a combination of search and read/write operations. We consider locks at both vertex (page) and key level (tuple) to further increase concurrency. As undo-based recovery is not possible with multi-level transactions, we use compensation-based undo to achieve atomicity. We have implemented our model using object-oriented technology and multithreading paradigm. In our implementation, linear hash operations such as find, insert, delete, split, and merge are implemented as methods and correspond to multi-level transactions.     

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 neural-based concurrency control algorithm for database systems

Concurrency control (CC) algorithms guarantee the correctness and consistency criteria for concurrent execution of a set of transactions in a database. A precondition that is seen in many CC algorithms is that the writeset (WS) and readset (RS) of transactions should be known before the transaction execution. However, in real operational environments, we know the WS and RS only for a fraction of transaction set before execution. However, optional knowledge about WS and RS of transactions is one of the advantages of the proposed CC algorithm in this paper. If the WS and RS are known before the transaction execution, the proposed algorithm will use them to improve the concurrency and performance. On the other hand, the concurrency control algorithms often use a specific static or dynamic equation in making decision about granting a lock or detection of the winner transaction. The proposed algorithm in this paper uses an adaptive resonance theory (ART)-based neural network for such a decision making. In this way, a parameter called health factor (HF) is defined for transactions that is used for comparing the transactions and detecting the winner one in accessing the database objects. HF is calculated using ART2 neural network. Experimental results show that the proposed neural-based CC (NCC) algorithm increases the level of concurrency by decreasing the number of aborts. The performance of proposed algorithm is compared with strict two-phase locking (S2PL) algorithm, which has been used in most commercial database systems. Simulation results show that the performance of proposed NCC algorithm, in terms of number of aborts, is better than S2PL algorithm in different transaction rates.     

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.     

Transaction decomposition using transaction semantics

Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. However, in a number of the newer and most challenging application areas, serializable execution may not be feasible.

? Serializable execution is generally implemented using a two-phase locking algorithm that locks items in the database to delay transactions that are in danger of performing in a non-serializable fashion. Such delays are unacceptable in high performance database systems that must process hundreds, and perhaps thousands, of transactions per second and in systems supporting long-running transactions.

? In systems in which data is distributed across a federated database, a global transaction is decomposed into a set of local subtransactions executed at a subset of the sites. Serializable execution in such systems not only incurs a performance penalty, but also requires the component systems to cooperate (for example in a two phase commit protocol), with a resulting loss of site autonomy. In many applications, the component systems either can not or will not agree to the required cooperation.

A number of models have recently been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. These models have the potential for improving performance since locks are released at the end of each step. Models of distributed transactions have also been proposed with the similarity that subtransactions correspond to steps. In most of this work serializability is no longer guaranteed. In this paper we propose a new, application-oriented, correctness criterion that utilizes transaction semantics. We treat transactions as programs whose semantics can be analyzed at design time. The effect of each transaction is specified using pre- and postconditions, and any schedule that preserves these conditions is permissible. Such schedules can produce database states that could not be reached by any serial execution. In addressing the issue of performance, we use transaction semantics to decompose transactions into steps and describe a concurrency control that controls step interleaving in such a way that assertions are preserved. The same model can be used to study the interleaving of subtransactions of concurrent distributed transactions.     

Concurrency control in distributed databases through time intervalsand short-term locks

A method for concurrency control in distributed database management systems that increases the level of concurrent execution of transactions, called ordering by serialization numbers (OSN), is proposed. The OSN method works in the certifier model and uses time-interval techniques in conjunction with short-term locks to provide serializability and prevent deadlocks. The scheduler is distributed, and the standard transaction execution policy is assumed, that is, the read and write operations are issued continuously during transaction execution. However, the write operations are copied into the database only when the transaction commits. The amount of concurrency provided by the OSN method is demonstrated by log classification. It is shown that the OSN method provides more concurrency than basic timestamp ordering and two-phase locking methods and handles successfully some logs which cannot be handled by any of the past methods. The complexity analysis of the algorithm indicates that the method works in a reasonable amount of time     

A Transaction Model to Improve Data Availability in Mobile Computing

We incorporate a prewrite operation before a write operation in a mobile transaction to improve data availability. A prewrite operation does not update the state of a data object but only makes visible the future value that the data object will have after the final commit of the transaction. Once a transaction reads all the values and declares all the prewrites, it can pre-commit at mobile host (MH) (computer connected to unreliable mobile communication network). The remaining transaction's execution (writes on database) is shifted to the mobile service station (MSS) (computer connected to the reliable fixed network). Writes on database consume time and resources and are therefore shifted to MSS and delayed. This reduces wireless network traffic congestion. Since the responsibility of expensive part of the transaction's execution is shifted to the MSS, it also reduces the computing expenses at mobile host. A pre-committed transaction's prewrite values are made visible both at mobile and at fixed database servers before the final commit of the transaction. Thus, it increases data availability during frequent disconnection common in mobile computing. Since a pre-committed transaction does not abort, no undo recovery needs to be performed in our model. A mobile host needs to cache only prewrite values of the data objects which take less memory, transmission time, energy and can be transmitted over low bandwidth. We have analysed various possible schedules of running transactions concurrently both at mobile and fixed database servers. We have discussed the concurrency control algorithm for our transaction model and proved that the concurrent execution of our transaction processing model produces only serializable schedules. Our performance study shows that our model increases throughput and decreases transaction-abort-ratio in comparison to other lock based schemes. We have briefly discussed the recovery issues and implementation of our model.     

A proof technique for concurrency control and recovery algorithms for replicated databases

A replicated database is a distributed database in which copies of some data items are stored redundantly at multiple sites. In such a system, an execution of transactions iscorrect if it is equivalent to a serial execution of those transactions on a one copy database. We show that in any serializable execution, if all transactions see the failures and recoveries of data item copies in a consistent order, then the execution is correct. We model this condition using a modified type of serialization graph, and show that if this graph is acyclic then the corresponding execution is correct. We demonstrate the value of this model by using it to prove the correctness of an algorithm for synchronizing access to a replicated database. Philip A. Bernstein is Professor of Information Technology at the Wang Institute of Graduate Studies. Previously, he was Vice President Software at Sequoia Systems, Associate at Harvard University, and a researcher at Computer Corporation of America, where he was codesigner of four distributed database systems. Professor Bernstein's research focuses on the theory and implementation of database systems and transaction processing systems. He is an Associate Editor of ACM Transactions on Database Systems, and on the editorial board of this journal. Nathan Goodman is a senior consulting engineer at Encore Computer Corporation. Previously he was with Sequoia Systems, where he developed a transaction processing system for a fault-tolerant multiprocessor computer. Prior to that he was with Computer Corporation of America, where he participated in the design of three distributed systems: SDD-1, the first relational distributed DBMS; Multibase, a system for querying relational and nonrelational distributed databases; and DDM, a distributed DBMS based on ADA. Dr. Goodman was a professor Computer Science at Harvard University and Boston University. He has done research on query optimization, concurrency control, and failure recovery.Research supported by the National Science Foundation, grant number MCS79-07762, and by the Office of Naval Research, contract number N00014-80-C-674.     

KRISHNA - An efficient concurrency control algorithm based on dynamic attributes of transactions and its performance

Concurrent transactions during their execution life acquire a number of attributes. We call them dynamic attributes of transactions. We have used them to develop a concurrency control mechanism, called KRISHNA, using a two-phase locking policy. To establish the usefulness of dynamic attributes in developing concurrency control mechanisms and to investigate the behaviour of KRISHNA we have studied their performance using a detailed simulation model. We show that KRISHNA outperforms a number of well-known concurrency control mechanisms based on a two-phase policy. We also show that the conflict-resolution policy of KRISHNA is comparatively more accurate in resolving conflicts, i.e., it selects the ‘right’ transaction for rolling back or blocking. We argue that implementing KRISHNA is not expensive compared to commonly used concurrency control mechanisms.     

Atomic RMI: A Distributed Transactional Memory Framework

This paper presents Atomic RMI, a distributed transactional memory framework that supports the control flow model of execution. Atomic RMI extends Java RMI with distributed transactions that can run on many Java virtual machines located on different network nodes. Our system employs SVA, a fully-pessimistic concurrency control algorithm that provides exclusive access to shared objects and supports rollback and fault tolerance. SVA is capable of achieving a relatively high level of parallelism by interweaving transactions that access the same objects and by making transactions that do not share objects independent of one another. It also allows any operations within transactions, including irrevocable ones, like system calls, and provides an unobtrusive API. Our evaluation shows that in most cases Atomic RMI performs better than fine grained mutual-exclusion and read/write locking mechanisms. Atomic RMI also performs better than an optimistic transactional memory in environments with high contention and a high ratio of write operations, while being competitive otherwise.     

大型实时数据库系统设计及并发控制调度

系统地分析了大型实时数据库系统的应用环境和功能需求，提出了企业大型实时数据库的体系结构、设计思路和实现方法，研究了实时主动数据库事务执行模式，提出了有效性检查并发控制协议。协议使用动态调整串行次序策略，避免不必要的事务重启动，并能有效降低事务延误截止时间。该实现方法在工程应用中取得了良好的效果。     

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.     

Autonomous objects: A natural model for complex applications

Object-oriented database systems are emerging as the next generation DBMSs for advanced applications, e.g., VLSI design, mechanical CAD/CAM, software engineering, etc. However, a close analysis indicates that the requirements imposed by these application domains cannot be met by an object-oriented model that relies purely onpassive objects. In this work we go beyond the conventionalsingle-thread-of-control paradigm of passive object models and propose a model ofactive objects which can autonomously initiate responses to environmental changes.Autonomous objects cooperate with each other by synchronous orasynchronous message passing—giving rise to themultiple-thread-of-control in such an environment. It is shown howevents—to which active objects react—can be incorporated into this model. We propose a nondeterministic computational model for the individual active objects that allows the autonomous reaction upon events. We show that this very sparse extension to an object-oriented model gives rise to several high-level features which can be controlled by events. The object-oriented paradigm allows one to isolate the rules according to which events are being raised. This leads to a potentially rather efficient execution model compared to existing relational concepts, which are typically globally-defined event trigger mechanisms.