Contact Information

Keywords

Project Award Information

• Award Number: 9221947
• Duration: 09/93 - 01/98
• Title: Transsaction Management in a Heterogeneous Database Environment

Project Summary

• Adapting to MDBS environments, existing techniques for ensuring database consistency based on the preservation of both transaction atomicity and serializability of schedules.
• Relaxing the requirement that transactions be atomic and schedules be serializable, and developing alternate correctness criteria for preserving database consistency in MDBS environments that exploit the semantics of transactions and integrity constraints.
• Investigate how to design a file management system in a loosely coupled network of heterogeneous workstations so that to ensure scalability and fast response time.

Goals, Objectives, And Targeted Activities

We plan also to continue the work on distributed file managers. Namely, we plan to develop concurrent access methods in such an environment that are fault-tolerant and guarantee a consistency of the data. We plan also to expand our system in such a way that it would be able to handle continuous multimedia applications.

In addition, as a part of cooperative effort, we continue to work on designing an experimental multidatabase system that would allow to verify multidatabase transaction management within SQL based database systems. It has been finally generally accepted that usage of the two phase commit protocol is not an acceptable alternative in multidatabases where data is distributed among WAN nodes. We will continue our work to find alternative protocols that guarantee a relaxed atomicity and semantic consistency in such multidatabase systems.

Indication Of Success

In (1) we reviewed the prototype multidatabase system ADDS. This is the most complete description of the system appeared so far. Different parts of the system have been described in other our papers. This paper mainly concentrated on describing the query optimizer in ADDS that is based on ideas implemented in ADDS. We also described our experiences with performance of the query optimizer. The value of these results lie in their implementation feasibility and in the incorporation of ideas from distributed homogeneous systems to a multidatabase environment.

In (2) we reviewed the state of the multidatabase transaction management research to date.

In (3) we described a prototype implementation of the ADDS multidatabase system that includes a transaction management system implementation based on our prior research on transaction management in multidatabases. Results obtained from the experiments with the prototype indicate the feasibility of our earlier research, as the prototype provided reasonably good transaction rates. However, it became clear that the transaction rates would deteriorate in high performance transaction models. The reason being that a requirement of serializability and atomicity within a multidatabase environment is too stringent for high performance transaction systems in a multidatabase environments and different transaction models must be found to guarantee consistency and atomicity in such environments.

Workflows are an alternative approach to the multidatabase transaction management since they provide both a novel transaction model as well as an alternative solution to serializable execution as a criteria of a correct execution. Workflows are widely used in industry as a substitute for transactions for interoperable data processing environments. This research was conducted in cooperation with with Prof. Schek, Vossen, and Vossen. We have organized a Dagsthul seminar on workflow management in 1996.

In (4) we develop a theory of concurrency control that guarantees both transaction atomicity and transaction consistency for arbitrary set of object operations. The major goal of this effort is to develop such a theory that would allow us to reason uniformly about multidatabase transactions, nested transactions, workflow transactions, and multilevel transactions with the purpose of proving atomicity and consistency of such transactions in a manner similar to that of classical concurrency control theory. At this point we are extending this work to multilevel transactions. The full version of the paper (4) was published as an invited paper in Theoretical Computer Science Journal 1997.

In (6,7) we substantially extended the work on distributed file structures that we started in the first year of this grant. We designed a family of various file management algorithms for a networks of workstations which we believe would be a prevalent distributed computing environment in the next few years. Our algorithms provide performance guarantees for input/output operations for distributed files and analyze its cost/performance behavior. The algorithms we designed are totally distributed and yet guarantee a consistent picture of the file by any client in such a distributed environment.

Project Impact

Publications (partial list)

1. Breitbart, Y., G., Reyes, T., ``An Overview of the ADDS System,'' Modern Database Systems: The Object Model, Interoperability, and Beyond Addison-Wesley 1995 (invited paper).
2. Breitbart, Y., Garcia-Molina, H., Silberschatz, A., ``Transaction Management in Multidatabases,'' Modern Database Systems: The Object Model, Interoperability, and Beyond editor Won Kim, Addison-Wesley 1995. (invited paper)
3. Y. Breitbart ``ADDS Transaction Management System,'' (invited paper) Proceedings of the Second International East/West Database Workshop, September 1994, Springer Verlag 1995.
4. R. Vingralek, H. Ye, Y. Breitbart, H.-J. Schek ``Unified Transaction Management for Semantically Rich Operations,'' Proceedings of International Conference on Database Theory, Prague, 1995
5. Breitbart, Y., Hunt III, H., Rosenkrantz, D., ``On the Size of Binary Decision Diagrams Representing Boolean Functions,'' Theoretical Computer Science, vol. 147, September, 1995
6. Y. Breitbart, R. Vingralek, G. Weikum, ``Load Control in Scalable File Structures,'' Distributed an Parallel Database Journal, 1996
7. R. Vingralek, Y. Breitbart, G. Weikum, ``SNOWBALL: Scalable Storage on Networks of Workstations with Balanced Load,'' Distributed and Parallel Database Journal, 1998
8. J. Shallit, Y. Breitbart Automaticity I: Properties of a Measure of Descriptional Complexity Journal of Computer and System Sciences, 1996
9. R. Rastogi, S. Mehrotra, Y. Breitbart, H. Korth, A. Silberschatz "On Correctness of non-serializable Executions", Journal of Computer and System Sciences, 1997
10. R. Vingralek, H. Hasse-Ye, Y. Breitbart, H.-J. Schek Unifying Concurrency Control And Recovery of Transactions with Semantically Rich Operations, Theoretical Computer Science, 190, 2, 1998