高级数据库系统中基于语义的并发控制

This paper surveys the semantic-based concurrency control for advanced database systems, which aimed to eliminate the limitation of conventional concurrency control and to meet the requirements of advanced database applications. Covered in the paper are those approaches that using transaction semantic,that using abstract data type semantic, and that supporting for cooperation. The current situation and the future directions of the semantic-based concurrency control are also analysized.     

Concurrency Control of Single-Level Transaction in WHYMX Object-Oriented Database System

The data model of WHYMX complicates transaction management.Traditional locking method is not powerful enough to solve the new problem of concurrency control of WHYMX‘s transaction.This paper presents a number of concurrency control algorithms based on the extended locking method.     

A non-blocking locking method and performance evaluation on network of workstations

A network of workstation(NOW) can act as a single and scalable powerful computer by building a paralle and distributed computing platform on top of it.WAKASHI is such a platform system that supports persitent object management and makes full use of resources of NOW for high perforance transaction processing,One of the main difficulties to overcome is the bottleneck caused by concurrency control mechanism.Therefore,a non-bloking locking method is designed,by adopting several novel techniques to make it outperform the other typical locking methods such as 2PL:1) an SDG (Semantic Dependency Graph)based non-blocking locking protocol for fast transaction scheduling;2) a nmassively virtual memory based backup-page undo algorithm for fast restart;and 3) a multi-processor and multi-thread based transaction manager for fast execution.The new mechanisms have been implemented in WAKASHI and the performance comparison experiments have been implemented in WAKASHI and the performance comparison experiments with 2PL and DWDL have been done.The results show that the new method can outperform 2PL and DWDL under certain conditons.This is meaningful for choosing effective concurrency control mechanisms for improving transaction-rpocessing performance in NOW environments.     

Solving Lyapunov equation by quantum algorithm

Lyapunov equation is one of the most basic and important equations in control theory, which has various applications in, e.g., stability analysis and robust analysis of linear control systems. Inspired by the recent progresses of quantum algorithms, we find that solving Lyapunov equation can be exponentially accelerated by quantum algorithms rather than traditional classical algorithms. Our algorithm is more efficient especially when the system matrix is sparse and has a low condition number. The results presented in this paper open up new dimensions of research in controlling classical system by quantum information processors, which has rarely been considered in the existing literature.     

Intelligent optimal control system for ball mill grinding process

Operation aim of ball mill grinding process is to control grinding particle size and circulation load to ball mill into their objective limits respectively, while guaranteeing producing safely and stably. The grinding process is essentially a multi-input multi-output system (MIMO) with large inertia, strong coupling and uncertainty characteristics. Furthermore, being unable to monitor the particle size online in most of concentrator plants, it is difficult to realize the optimal control by adopting traditional control methods based on mathematical models. In this paper, an intelligent optimal control method with two-layer hierarchical construction is presented. Based on fuzzy and rule-based reasoning (RBR) algorithms, the intelligent optimal setting layer generates the loops setpoints of the basic control layer, and the latter can track their setpoints with decentralized PID algorithms. With the distributed control system (DCS) platform, the proposed control method has been built and implemented in a concentration plant in Gansu province, China. The industrial application indicates the validation and effectiveness of the proposed method.     

oodOPT: A semantics-based concurrency control framework for fully-replicated architecture

Concurrency control has always been one of the most important issues in the design of synchronous groupware systems with fully-replicated architecture,An ideal strategy should be able to support natural and flexible human-to-computer and human-to-human interactions while maintaining the consistency of the system.This paper summarizes previous researches on this topic and points out the deficiencies of the existing results.A novel semantics-based concurrency control framewokr oodOPT,is proposed.The main idea of the framework is to resulve conflicts by utilizing semantics of the operations and the accessed data frameworks is to resolve conflicts by utilizing semantics of the operations and the accessed data objects.With this approach,complexities in concurrency control are shifted completely from application developers to the framework.Conflicts among operations on objects with different semantics and the strategies resolving these conflicts are analyzed.After describing the algorithm in full detail.the discussion ends up with a comparison with other related work and some considerations for open problems.     

Output constrained IMC controllers in control systems of electromechanical actuators

Electromechanical actuators are widely used in many industrial applications. There are usually some constraints existing in a designed system. This paper proposes a simple method to design constrained controllers for electromechanical actuators. The controllers merge the ideas exploited in internal model control and model predictive control. They are designed using the standard control system structure with unity negative feedback. The structure of the controllers is relatively simple as well as the design process. The output constraint handling mechanism is based on prediction of the control plant behavior many time steps ahead. The mechanism increases control performance and safety of the control plant. The benefits offered by the proposed controllers have been demonstrated in real-life experiments carried out in control systems of two electromechanical actuators: a DC motor and an electrohydraulic actuator.     

Model-based tracking for agent-based control systems in the case of sensor failures

The study on artificial intelligence(AI) methods for tuning of particle accelerators has been reported in many literatures.This paper presents tuning method for agent-based control systems of transport lines in the case of sensor/actuator failures.The method uses model-based tracking concept to relax the demand on sensor data.The condition for successful operation of the stated scheme is derived,and the concept is demonstrated through simulation by applying it to the model of microtron,transport line-1 and booster of indus accelerator.The results show that this approach is very effective in transport line control during sensor/actuator failures.     

Nonlinear backstepping ship course controller

A ship, as an object of course control, is characterized by a nonlinear function describing the static maneuvering characteristics. The backstepping method is one of the methods that can be used during the designing process of a nonlinear course controller for ships. The method has been used for the purpose of designing two configurations of nonlinear controllers, which were then used to control the ship course. One of the configurations took dynamic characteristic of a steering gear into account during the designing stage. The parameters of the obtained nonlinear control structures have been tuned to optimise the operation of the control system. The optimisation process has been performed by means of genetic algorithms. The quality of operation of the designed control algorithms has been checked in simulation tests performed on the mathematical model of a tanker. The results of simulation experiments have been compared with the performance of the system containing a conventional proportional-derivative （PD） controller.     

一类欠驱动机械系统的动态及其稳定控制

Abstract The control of underactuated mechanical systems is very complex for the loss of its control inputs. The model of underactuated mechanical systems in a potential field is built with Lagrangian method and its structural properties are analyzed in detail. A stable control approach is proposed for the class of underactuated mechanical systems. This approach is applied to an unde ractuated double-pendulum-type overhead crane and the simulation results illustrate the correctness of dynamics analysis and validity of the proposed control algorithm.     

Towards a General Concurrency Control Algorithm for Database Systems

The concurrency control problem in database systems has been examined by many people and several concurrency control algorithms have been proposed. The most popular algorithms are two-phase locking and timestamp ordering. This paper shows that two-phase locking and timestamp ordering are special cases of a more general concurrency control algorithm. This general algorithm is described in detail and is proven to work correctly. We show that two-phase locking and timestamp ordering represent the two end points of a series of concurrency control algorithms. Each of them is a special case of the general algorithm proposed in this paper. Moreover, each of these special cases can be selected in advance, and can even be changed dynamically during execution.     

时标排序并发控制算法在移动分布式实时数据库中的应用分析

随着移动计算技术的发展,人们要求能够随时随地实时存取数据库的数据,这就导致了移动分布式实时数据库(MDRTDBS)的实现.移动实时应用的根本特性是其事务具有移动性和实时特性,数据具有定时特性.这对移动分布式实时数据库并发控制协议提出了新的挑战,目前这方面的研究还很少.对实时数据库的时标排序并发控制协议进行了分析,针对移动实时应用的特点对将它们应用到MDRTDBS的优缺点进行了阐述,提出了改进的方法.最后提出了新的适用于MDRTDBS的时标排序协议,并指出了未来的研究方向.     

Multidimensional Timestamp Protocols for Concurrency Control

We propose multidimensional timestamp protocols for concurrency control in database systems where each transaction is assigned a timestamp vector containing multiple elements. The timestamp vectors for two transactions can be equal if timestamp elements are assigned the same values. The serializability order among the transactions is determined by a topological sort of the corresponding timestamp vectors. The timestamp in our protocols is assigned dynamically and is not just based on the starting/finishing time as in conservative and optimistic timestamp methods. The concurrency control can be enforced based on more precise dependency information derived dynamically from the operations of the transactions. Several classes of logs have been identified based on the degree of concurrency or the number of logs accepted by a concurrency controller. The class recognized by our protocols is within D-serializable (DSR), and is different from all previously known classes such as two phase locking (2PL), strictly serializable (SSR), timestamp ordering (TO), which have been defined in literature. The protocols have been analyzed to study the complexity of recognition of logs. We briefly discuss the implementation of the concurrency control algorithm for the new class, and give a timestamp vector processing mechanism. The extension of the protocols for nested transaction and distributed database models has also been included.     

Analysis of the probability of transaction abort and throughput oftwo timestamp ordering algorithms for database systems

The author analyzes and compares the performance of two timestamp ordering concurrency control algorithms, namely, the basic and multiversion, for database systems. The multiversion algorithm improves the performance of the basic timestamp ordering algorithm by keeping multiple versions of data objects. The author discusses the performance enhancement in the multiversion algorithm over the basic algorithm. The author also discusses the storage overhead due to multiple versions of data objects in the multiversion algorithm. The exact performance model of these algorithms is so complex that it is impossible to find a closed-form solution. The author reduces the complexity of the analysis by analyzing a single transaction in isolation and reflects the presence of other transactions on the isolated transaction by the probability of conflict/abort. The analysis provides useful insight into the performance of these algorithms     

The partitioned synchronization rule for planar extendible partialorders

The partitioned synchronization rule is a technique for proving the correctness of concurrency control algorithms. Prior work has shown the applicability of the partitioned synchronization rule to hierarchically decomposed databases whose structure is restricted to semitrees. The principal contribution of the paper is a demonstration that the partitioned synchronization rule also applies to more general structures than semitrees, specifically, to any planar extendible partial order, a partial order which when extended with a least and a greatest element still remains planar. To demonstrate utility, the paper presents two applications of the partitioned synchronization rule. The first application shows correctness of a component based timestamp generation algorithm suitable for implementing a timestamp ordering concurrency control algorithm. The second application shows correctness of a snapshot algorithm for concurrency control in a replicated multilevel secure database; we choose this application to highlight that hierarchically decomposed databases and multilevel secure databases are structurally similar. In both cases, the correctness proofs via the partitioned synchronization rule are substantially simpler than corresponding direct proofs     

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     

数据广播环境下移动实时事务的有效并发控制

在无线数据广播环境下,从移动客户机到数据库服务器的上行带宽非常有限.传统的并发控制协议不适合这种不对称通讯环境.本文结合乐观并发控制协议和时标排序协议提出一种并发控制协议.只读事务满足弱一致性,包含所有更新事务和一个移动只读事务的可串行化图是非循环的.使用本文提出的并发控制协议,移动只读事务能够自主执行,移动更新事务能够较早地检测到数据冲突.模拟试验显示,我们提出的协议相对其它已经存在的并发控制协议来说,能够更好地满足事务截止期.     

Distributed optimistic concurrency control with reduced rollback

Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described which is particularly advantageous in a query-dominant environment. The drawbacks of the original optimistic concurrency control scheme, namely that inconsistent views may be seen by transactions (potentially causing unpredictable behavior) and that read-only transactions must be validated and may be rolled back, have been eliminated in the proposed algorithm. Read-only transactions execute in a completely asynchronous fashion and are therefore processed with very little overhead. Furthermore, the probability that read-write transactions are rolled back has been reduced by generalizing the validation algorithm. The effects of global transactions on local transaction processing are minimized. The algorithm is also free from dedlock and cascading rollback problems. Divyakant Agrawal is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Burroughs Limited, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include design of algorithms for concurrent systems, optimistic protocols and distributed systems. Arthur Bernstein is a Professor of Computer Science at the State University of New York at Stony Brook. His research is concerned with the design and verification of algorithms involving asynchronous activity and with languages for expressing such algorithms. Pankaj Gupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received M.S. degree in Electrical Engineering from SUNY at Stony Brook in 1982 and M.S. degree in Computer Science from SUNY at Stony Brook in 1985. His research interests include distributed systems, concurrency control, and databases. Soumitra Sengupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Consultancy Services, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include distributed algorithms, logic databases and concurrency control.This work was supported by the National Science Foundation under grant, DCR-8502161 and the Air Force Office of Scientific Research under grant AFOSR 810197     

索引时间戳：一种高效的文本索引系统设计方法

特征文件索引、时间戳排序技术是数据库技术研究方面的两个重要课题，前者通常用于支持文本数据的索引和检索操作，后者为实现数据库并发控制的两个基本方法之一。本文主要讨论面向文本数据库管理系统（ＦＩＭＳ）基于索引时间戳概念的文本对象索引模型的形式化描述、检索相关性计算及特征文件系统逻辑设计等问题。     

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

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