In today's database management systems (DBMS), concurrency control is one of the main issues that draw a lot of attention. Concurrency control protocols prevent changes to the database made by one user to interfere with those made by another user. During last couple of decades, many new concurrency control mechanisms were introduced into the study of database management systems. Researchers have designed new concurrency control algorithms and examined their performances in comparison with well known concurrency control mechanisms, which are widely used in today's database management systems. The results reported to date, rather than being definitive, have tended to be quite contradictory [1]. The main cause of such findings is use of different assumptions and implications when defining a simulation model for database management systems. Different coding schemes and logical programmatic flows play another important role in obtaining questionable results. In this paper, rather than proposing yet another concurrency control algorithm, I will implement a standardized simulation model within windows application that can then be used by any researcher to test performance of his concurrency control protocol. I will implement Optimistic Concurrency control protocol to validate functionality of my application and compare it with two phase locking protocol.

M.Sc. (Computer Science) / Concurrency control is the problem that exists in a database management system when more than one transaction or application is executed simultaneously. If transactions or applications are executed sequentially there will- be no problem with the allocation of resources. It is however necessary to execute transactions concurrently to utilise computer and resource capacity to its maximum extent. It can lead to inconsistent data if this concurrent execution of transactions are not properly controlled. If this should happen the data would be of no more use to the users of a system. The thesis is divided in the following way. Chapter 1 gives background information on the concurrency control problem. In chapter 2 a couple of mechanisms for solving the concurrency control problem are studied briefly. Chapters 3 and 4 provides a more in depth study of two specific mechanisms namely two-phase locking and timestamps. 80th of these mechanisms have already been implemented in systems to. solve the concurrency control problem.- In chapter 5 a comparison is made of the two methods described in chapters 3 and 4. A third method for handling concurrency control is briefly described in chapter 6. This method hasn't received a lot of attention from researchers yet. And in the last chapter, chapter 7, the concurrency control method used in the SDD-1 system is studied in more detail. SDD-1 is a distributed database management system.

As demanded by applications such as GIS, CAD, ecology analysis, and space research, efficient spatial data access methods have attracted much research. Especially, moving object management and continuous spatial queries are becoming highlighted in the spatial database area. However, most of the existing spatial query processing approaches were designed for single-user environments, which may not ensure correctness and data consistency in multiple-user environments. This research focuses on designing efficient concurrent operations on spatial datasets. Current multidimensional data access methods can be categorized into two types: 1) pure multidimensional indexing structures such as the R-tree family and grid file; 2) linear spatial access methods, represented by the Space-Filling Curve (SFC) combined with B-trees. Concurrency control protocols have been designed for some pure multidimensional indexing structures, but none of them is suitable for variants of R-trees with object clipping, which are efficient in searching. On the other hand, there is no concurrency control protocol designed for linear spatial indexing structures, where the one-dimensional concurrency control protocols cannot be directly applied. Furthermore, the recently designed query processing approaches for moving objects have not been protected by any efficient concurrency control protocols. In this research, solutions for efficient concurrent access frameworks on both types of spatial indexing structures are provided, as well as for continuous query processing on moving objects, for multiple-user environments. These concurrent access frameworks can satisfy the concurrency control requirements, while providing outstanding performance for concurrent queries. Major contributions of this research include: (1) a new efficient spatial indexing approach with object clipping technique, ZR+-tree, that outperforms R-tree and R+-tree on searching; (2) a concurrency control protocol, GLIP, to provide high throughput and phantom update protection on spatial indexing with object clipping; (3) efficient concurrent operations for indices based on linear spatial access methods, which form up the CLAM protocol; (4) efficient concurrent continuous query processing on moving objects for both R-tree-based and linear spatial indexing frameworks; (5) a generic access framework, Disposable Index, for optimal location update and parallel search. / Ph. D.

The increasing power and decreasing cost of computers has resulted in them being applied in an ever widening area. In the world of Computer Aided Design it is now practicable to involve the machine in the earlier stages where a design is still speculative, as well as in the later stages where the computer's calculating ability becomes paramount. Research on database systems has not followed this trend, concentrating instead on commercial applications, with the result that there are very few systems targeted at the early stages of the design process. In this thesis we consider the design and implementation of the file manager for such a system, first of all from the point of view of a single designer working on an entire design, and then from the point of view of a team of designers, each working on a separate aspect of a design. We consider the functionality required of the type of system we are proposing, defining the terminology of experiments to describe it. Having ascertained our requirements we survey current database technology in order to determine to what extent it meets our requirements. We consider traditional concurrency control methods and conclude that they are incompatible with our requirements. We consider current data models and conclude that, with the exception of the persistent programming model, they are not appropriate in the context required, while the implementation of the persistent programming model provides transactions on data structures but not experiments. The implementation of experiments is considered. We examine a number of potential methods, deciding on differential files as the one most likely both to meet our requirements and to have the lowest overheads. Measurements conducted on both a preliminary and a full-scale implementation confirm that this is the case. There are, nevertheless, further gains in convenience and performance to be obtained by exploiting the capabilities of the hardware to the full; we discuss these in relation to virtual memory systems, with particular reference to the VAX/VMS environment. Turning to the case where several designers are each working on a (nearly) distinct part of a design, we consider how to detect conflicts between experiments. Basing our approach on optimistic concurrency control methods, we show how read and write sets may be used to determine those areas of the database where conflicts might arise. As an aside, we show how the methods we propose can be used in an alternative approach to optimistic concurrency control, giving a reduction in system overheads for certain applications. We consider implementation techniques, concluding that a differential files approach has significant advantages in maintaining write sets, while a two-level bitmap may be used to maintain read sets efficiently.

A possibility of a temporary disconnection of database service exists in many computing environments. It is a common need to permit a participating site to lag behind and re-initialize to full recovery. It is also necessary that active transactions view a globally consistent system state for ongoing operations. We present an algorithm for on-the-fly backup and site-initialization. The technique is non-blocking in the sense that failure and recovery procedures do not interfere with ordinary transactions. As a result the system can tolerate disconnection of services and reconnection of disconnected services, without incurring high overheads

Many activities are comprised of temporally dependent events that must be executed in a specific chronological order. Supportive software applications must preserve these temporal dependencies. Whenever the processing of this type of an application includes transactions submitted to a database that is shared with other such applications, the transaction concurrency control mechanisms within the database must also preserve the temporal dependencies. A basis for preserving temporal dependencies is established by using (within the applications and databases) real-time timestamps to identify and order events and transactions. The use of optimistic approaches to transaction concurrency control can be undesirable in such situations, as they allow incorrect results for database read operations. Although the incorrectness is detected prior to transaction committal and the corresponding transaction(s) restarted, the impact on the application or entity that submitted the transaction can be too costly. Three transaction concurrency control algorithms are proposed in this dissertation. These algorithms are based on timestamp ordering, and are designed to preserve temporal dependencies existing among data-dependent transactions. The algorithms produce execution schedules that are equivalent to temporally ordered serial schedules, where the temporal order is established by the transactions' start times. The algorithms provide this equivalence while supporting currency to the extent out-of-order commits and reads. With respect to the stated concern with optimistic approaches, two of the proposed algorithms are risk-free and return to read operations only committed data-item values. Risk with the third algorithm is greatly reduced by its conservative bias. All three algorithms avoid deadlock while providing risk-free or reduced-risk operation. The performance of the algorithms is determined analytically and with experimentation. Experiments are performed using functional database management system models that implement the proposed algorithms and the well-known Conservative Multiversion Timestamp Ordering algorithm.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / XML tornou-se um padrÃo amplamente utilizado na representaÃÃo e troca de dados entre aplicaÃÃes na Web. Com isso, grande volume desses dados està distribuÃdo na Web e armazenado em diversos meios de persistÃncia. SGBD relacionais que suportam XML fornecem tÃcnicas de controle de concorrÃncia para gerenciar esses dados. A estrutura dos dados XML, entretanto, dificulta a aplicaÃÃo dessas tÃcnicas. Trabalhos estÃo sendo propostos e fornecem gerenciamento de documentos XML. A maioria destes trabalhos, todavia, nÃo oferecem um controle de concorrÃncia eficiente para dados distribuÃdos. Outros trabalhos dÃo suporte ao controle distribuÃdo de dados XML, mas estes possuem protocolos com baixo grau de concorrÃncia e limitaÃÃes. Para prover um gerenciamento eficaz em ambientes distribuÃdos, este trabalho apresenta o DTX, como mecanismo para o controle de concorrÃncia distribuÃdo para dados XML, que leva em consideraÃÃo caracterÃsticas estruturais destes dados. O DTX visa a um gerenciamento eficaz de dados XML e contemplar as propriedades de isolamento e consistÃncia em transaÃÃes, utilizando um protocolo para controle de concorrÃncia multigranular que aumenta o paralelismo entre as transaÃÃes e possui uma estrutura otimizada para representaÃÃo dos dados. A soluÃÃo proposta possui uma arquitetura modular e flexÃvel, o que facilita sua integraÃÃo com diferentes estruturas de armazenamento XML, alÃm de poder ser estendido, adicionando novos recursos. Para validar o DTX, diversos testes foram feitos, comparando o DTX descrito neste trabalho com uma variaÃÃo do DTX, utilizando um protocolo de maior granulosidade, visando a simular as estratÃgias dos trabalhos relacionados. Os resultados obtidos atestam a eficÃcia do DTX, considerando diferentes aspectos em transaÃÃes distribuÃdas a dados XML, melhorando o desempenho, ou seja, o tempo de execuÃÃo destas transaÃÃes. / XML has become a widely used standard for data representation and exchange among Web applications. Consequently, a large volume of such data is distributed all over the Web and stored using several persistence methods. DBMSs provide concurrency control techniques to manage data. However, the structure of XML data makes it difficult to use these techniques. Projects are being proposed and they provide management of XML documents. Nevertheless, most of these projects do not provide efficient concurrency control mechanisms for distributed data. Some of them do provide support for distributed control of XML data, but use protocols that have limitations and offer low concurrency levels. In order to provide effective data management in distributed environments, we present DTX, a distributed concurrency control mechanism for XML data that takes into account its structural characteristics. DTX aims to provide effective management of XML data and contemplate properties such as isolation and consistency in transactions, using a multi-granular concurrency control protocol that increases parallelism among transactions and that has an optimized structure for data representation. DTX has a modular and flexible architecture, allowing for easy integration with any XML storage mechanisms. Moreover, DTX can be extended by adding new features to it. In order to evaluate DTX, several experiments were conducted comparing DTX as it is with a variation of DTX that uses a fine-grained protocol, in an attempt to simulate existing strategies in related work. Results confirm DTXâs effectiveness considering different aspects of distributed transactions on XML data, improving their performance, i.e., transaction execution time.

We present Roko, a system that allows parallelization of sequential C codes with a modest user intervention. The user exposes parallelism at the function level by annotating the code with pragmas. Roko defines only two pragmas: the parallel pragma is used to denote function calls that will be executed asynchronously, and the exposed pragma is used to describe data usage of the marked function calls. Architecturally, Roko consists of three components: a compiler that analyzes pragmas, a software environment that spreads the execution over multiple processors, and a hardware support that implements a novel synchronization scheme, versioning. We have designed, implemented and evaluated an FPGA-based prototype of Roko. Our experimental evaluation shows: (i) that few simple pragmas are all that is needed to expose parallelism in benchmark applications and (ii) that Roko can deliver good performance in terms of application speedup.

We present Roko, a system that allows parallelization of sequential C codes with a modest user intervention. The user exposes parallelism at the function level by annotating the code with pragmas. Roko defines only two pragmas: the parallel pragma is used to denote function calls that will be executed asynchronously, and the exposed pragma is used to describe data usage of the marked function calls. Architecturally, Roko consists of three components: a compiler that analyzes pragmas, a software environment that spreads the execution over multiple processors, and a hardware support that implements a novel synchronization scheme, versioning. We have designed, implemented and evaluated an FPGA-based prototype of Roko. Our experimental evaluation shows: (i) that few simple pragmas are all that is needed to expose parallelism in benchmark applications and (ii) that Roko can deliver good performance in terms of application speedup.

Transactional memory (TM) systems have gained considerable popularity in the last decade driven by the increased demand for tools that ease parallel programming. TM eliminates the need for user-locks that protect accesses to shared data. It offers performance close to that of fine-grain locking with the programming simplicity of coarse-grain locking. Today’s TM systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict occurs. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in applications with high contention because it increases the rate of aborts. We propose the use of a more relaxed concurrency control algorithm to provide better concurrency. This algorithm is based on the conflict-serializability (CS) model. Unlike 2PL, it allows some transactions to commit successfully even when they make conflicting accesses. We implement this algorithm both in a software TM system as well as in a simulator of a hardware TM system. Our evaluation using TM benchmarks shows that the algorithm improves the performance of applications with long transactions and high abort rates. Performance is improved by up to 299% in the software TM, and up to 66% in the hardware simulator. We argue that these improvements come with little additional complexity and require no changes to the transactional programming model. This makes our implementation feasible