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.     

Multiserialization of iterated transactions

The usual criterion of serializability considered in data base systems in order to control the accesses to shared informations by concurrent transactions is generalized in two directions: the transactions can be arbitrarily often iterated, as processes in an operating system, and the notion of serialization is extended in order to control behaviours of concurrent transactions with respect to several independent criteria of serializability. For transaction systems controlled under multiple criteria of serializability, a characterization of deadlock freedom is given. This characterization is shown to be applicable to any mutual exclusion problem.     

基于分布式事务流的动态可串行调度算法

针对分布式数据库中发生待处理的事务流提出一种动态可串行调度算法。通过执行此算法,能够高效地处理源源不断的事务流,使之尽可能串行调度地执行,从而提高并发度,以及分布式数据库各站点的并行处理度。     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

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.     

Concurrency control in mobile distributed real-time database systems

This paper presents DMVOCC-2PLV (Distributed Multiversion Optimistic Concurrency Control with Two-Phase Local Validation) protocol for processing mobile distributed real-time transactions in mobile broadcast environments. In DMVOCC-2PLV protocol, transaction validation is performed at two levels: local validation and global validation. Local validation of transactions is performed in two phases: local pre-validation and local final validation. At the MHs (Mobile Hosts), all mobile transactions perform local pre-validation of transactions by using a backward validation mechanism. The local pre-validation process is carried out against committed transactions at the server in the last broadcast cycle. Such an early data conflict detection feature can save processing and communication resources. Transactions that survive in local pre-validation must be submitted to the server for local final validation. In global validation distributed update transactions have to check to ensure distributed serializability in all participants. The protocol can eliminate conflicts between mobile read-only and mobile update transactions, and resolve data conflicts flexibly using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly reduced. The tolerance of mobile transactions of disconnections from the broadcast channel is increased. The results of simulation experiment show that the new protocol proposed offers better performance in terms of miss rate, restart rate, commit rate and throughput.     

The group paradigm for concurrency control protocols

The authors propose a paradigm for developing, describing, and proving the correctness of concurrency control protocols for replicated databases in the presence of failures or communication restrictions. The approach used is to hierarchically divide the problem of achieving one-copy serializability by introducing the notion of a `group' that is a higher level of abstraction than transactions. Instead of dealing with the overall problem, the paradigm breaks it into two simpler ones: (1) a local policy for each group that ensures a total order of all transactions in that group; and (2) a global policy that ensures a correct serialization of all groups. The paradigm is used to demonstrate the similarities between several concurrency control protocols by comparing the way they achieve correctness     

移动广播环境中实时事务处理性能研究

提出了移动广播环境中MVOCC-DA-2PV(Multiversion Optimistic Concurrency Control with Dynamic Adjustment of serialization order using Two-Phase Validation)并发控制协议。移动实时事务处理分两阶段进行。第一阶段在移动主机(MobileHosts,MHs)上处理,第二阶段在服务器上处理。移动主机(MHs)上所有移动事务执行部分向后有效性确认,与在服务器提交事务进行有效性确认。如果移动事务通过MH上部分有效性确认,提交到服务器进行最终有效性确认。如此早地检测数据冲突,节省了处理和通信资源。协议消除了移动只读事务和移动更新事务的冲突,使用多版本动态调整串行次序技术,避免了不必要的事务重启动。降低了移动只读事务的响应时间。通过模拟仿真,对MVOCC-DA-2PV协议进行了性能测试,并与PVTO和HP2PL进行了比较。实验结果表明MVOCC-DA-2PV并发控制协议要优于其它协议。     

Concurrent Certifications by Intervals of Timestamps in Distributed Database Systems

This paper introduces, as an optimistic concurrency control method, a new certification method by means of intervals of timestamps, usable in a distributed database system. The main advantage of this method is that it allows a chronological commit order which differs from the serialization one (thus avoiding rejections or delays of transactions which occur in usual certification methods or in classical locking or timestamping ones). The use of the dependency graph permits both classifying this method among existing ones and proving it. The certification protocol is first presented under the hypothesis that transactions' certifications are processed in the same order on all the concerned sites; it is then extended to allow concurrent certifications of transactions.     

On rigorous transaction scheduling

The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined. This class of transaction management mechanisms is important, because it simplifies transaction management in a multidatabase system environment. The notion of analogous execution and serialization orders of transactions is defined and the concept of strongly recoverable and rigorous execution schedules is introduced. It is then proven that rigorous schedulers always produce analogous execution and serialization orders. It is shown that the systems using the rigorous scheduling can be naturally incorporated in hierarchical transaction management mechanisms. It is proven that several previously proposed multidatabase transaction management mechanisms guarantee global serializability only if all participating databases systems produce rigorous schedules     

Selective dynamic serialization for reducing energy consumption in hardware transactional memory systems

In the search for new paradigms to simplify multithreaded programming, Transactional Memory (TM) is currently being advocated as a promising alternative to deadlock-prone lock-based synchronization. In this way, future many-core CMP architectures may need to provide hardware support for TM. On the other hand, power dissipation constitutes a first class consideration in multicore processor designs. In this work, we propose Selective Dynamic Serialization (SDS) as a new technique to improve energy consumption without degrading performance in applications with conflicting transactions by avoiding wasted work due to aborted transactions. Our proposal, which is implemented on top of a hardware transactional memory (HTM) system with an eager conflict management policy, detects and serializes conflicting transactions dynamically (at run-time). In its simplest form, in case of conflict, one transaction is allowed to continue whilst the rest are completely stalled. Once the executing transaction has finished, it wakes up several of the stalling transactions. More elaborated implementations of SDS try to delay this behavior until serialization of transactions is profitable, achieving the best trade-off between performance, energy savings and network traffic. SDS implementations differ from each other in the condition that triggers the serialization mode. We have evaluated several SDS schemes using GEMS, a full-system simulator implementing the LogTM-SE Eager–Eager HTM system, and several benchmarks from the STAMP suite. Results for a 16-core CMP show that SDS obtains reductions of 6 % on average in energy consumption (more than 20 % in high contention scenarios) in a wide range of benchmarks without affecting, on average, execution time. At the same time, network traffic level is also reduced by 22 %.     

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

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

BLAST-SSAHA Hybridization for Credit Card Fraud Detection

A phenomenal growth in the number of credit card transactions, especially for online purchases, has recently led to a substantial rise in fraudulent activities. Implementation of efficient fraud detection systems has thus become imperative for all credit card issuing banks to minimize their losses. In real life, fraudulent transactions are interspersed with genuine transactions and simple pattern matching is not often sufficient to detect them accurately. Thus, there is a need for combining both anomaly detection as well as misuse detection techniques. In this paper, we propose to use two-stage sequence alignment in which a profile analyzer (PA) first determines the similarity of an incoming sequence of transactions on a given credit card with the genuine cardholder's past spending sequences. The unusual transactions traced by the profile analyzer are next passed on to a deviation analyzer (DA) for possible alignment with past fraudulent behavior. The final decision about the nature of a transaction is taken on the basis of the observations by these two analyzers. In order to achieve online response time for both PA and DA, we suggest a new approach for combining two sequence alignment algorithms BLAST and SSAHA.     

Discovering admissibleWeb services with uncertain QoS

Open and dynamic environments lead to inherent uncertainty of Web service QoS (Quality of Service), and the QoS-aware service selection problem can be looked upon as a decision problem under uncertainty. We use an empirical distribution function to describe the uncertainty of scores obtained from historical transactions. We then propose an approach to discovering the admissible set of services including alternative services that are not dominated by any other alternatives according to the expected utility criterion. Stochastic dominance (SD) rules are used to compare two services with uncertain scores regardless of the distribution form of their uncertain scores. By using the properties of SD rules, an algorithm is developed to reduce the number of SD tests, by which the admissible services can be reported progressively. We prove that the proposed algorithm can be run on partitioned or incremental alternative services. Moreover, we achieve some useful theoretical conclusions for correct pruning of unnecessary calculations and comparisons in each SD test, by which the efficiency of the SD tests can be improved. We make a comprehensive experimental study using real datasets to evaluate the effectiveness, efficiency, and scalability of the proposed algorithm.     

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

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

Using tickets to enforce the serializability of multidatabasetransactions

To enforce global serializability in a multidatabase environment the multidatabase transaction manager must take into account the indirect (transitive) conflicts between multidatabase transactions caused by local transactions. Such conflicts are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these difficulties, we propose to incorporate additional data manipulation operations in the subtransactions of each multidatabase transaction. We show that if these operations create direct conflicts between subtransactions at each participating local database system, indirect conflicts can be resolved even if the multidatabase system is not aware of their existence. Based on this approach, we introduce optimistic and conservative multidatabase transaction management methods that require the local database systems to ensure only local serializability. The proposed methods do not violate the autonomy of the local database systems and guarantee global serializability by preventing multidatabase transactions from being serialized in different ways at the participating database systems. Refinements of these methods are also proposed for multidatabase environments where the participating database systems allow schedules that are cascadeless or transactions have analogous execution and serialization orders. In particular, we show that forced local conflicts can be eliminated in rigorous local systems, local cascadelessness simplifies the design of a global scheduler, and that local strictness offers no significant advantages over cascadelessness     

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.     

移动计算环境中实时嵌套事务并发控制协议的研究

提出了移动计算环境中多版本乐观并发控制协议(MultiversionOptimisticConcurrencyControl,MVOCC)处理移动实时嵌套事务.协议消除了只读事务和更新事务之间冲突,通过动态调整事务串行次序,避免不必要的事务重启动.只读事务在移动主机处理,只读事务的响应时间大大改善.事务有效性检查分两级局部有效性检查和全局有效性检查.局部有效性检查在移动主机进行.通过局部有效性检查的事务提交到服务器进行全局有效性检查.如此早地检测数据冲突,节省了处理和通信资源.通过模拟仿真,对协议进行了性能测试,并与OCC-TI-WAIT50和HP2PL协议进行了比较.实验结果表明该协议要优于其它协议.协议不但能有效地降低事务的重启动率和延误截止时间率,而且改善只读事物的响应时间.     

Optimal Design of Object-Oriented Databases in Automatic Information-Control Systems. II. Models and Methods of Design of Optimal Logical Structures for Object-Oriented Databases

Part II is devoted to the formulation of the problem and models and methods of design of optimal logical structures for object-oriented databases used in designing automatic information control systems. The effectiveness criteria used for the problem design are defined by the minimal total time of utilization of databases and service of a given set of user inquires and transactions, minimal total time of implementation of a set of inquires and transactions over the database. Design problems are formulated as nonlinear integer programming problems and effective exact and heuristic algorithms are developed to solve them.     

移动广播环境中有效处理实时只读事务

提出了移动广播环境中有效处理实时只读事务的方法。给出了多种多版本广播磁盘组织。采用多版本机制，实现移动只读事务无阻塞提交。通过乐观方法，消除移动只读事务和移动更新事务的冲突。使用多版本动态调整串行次序技术，避免了不必要的事务重启动。在移动主机上如果移动只读事务通过向后有效性确认，则可提交，不需要提交到服务器处理，降低移动只读事务的响应时间。通过模拟仿真对提出的方法进行了性能测试,实验结果表明新方法要优于其他协议。