Overcoming Heterogeneity and Autonomy in Multidatabase Systems

Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham SilberschatzInf. Comput 2001 · DOI

Sure, here's a blog-style summary of the paper "Overcoming Heterogeneity and Autonomy in Multidatabase Systems":

TL;DR

This paper tackles the challenge of managing transactions across multiple independent and diverse database systems (multidatabase systems or MDBSs). It introduces a framework that allows users to execute transactions spanning these systems while ensuring data consistency and atomicity, even in the face of failures, without requiring modifications to the underlying local databases or compromising their autonomy.

What Problem Does This Paper Address?

Integrating multiple existing database systems, often from different organizations or with varying technologies, presents a significant challenge. These systems, known as multidatabase systems (MDBSs), are heterogeneous (using different concurrency control and recovery algorithms) and autonomous (maintaining local control). The core problem is ensuring that transactions spanning these diverse systems can be executed reliably, guaranteeing both serializability (transactions appear to execute in some serial order) and atomicity (transactions either complete fully or not at all), without forcing changes to the local databases or violating their autonomy. Traditional distributed database solutions like two-phase commit (2PC) are often unsuitable due to these constraints.

Methods

The paper proposes a framework that decomposes the problem into three subproblems: ensuring serializability of a global schedule (Ŝ), ensuring local schedules are M-serializable (multidatabase-serializable), and ensuring local schedules satisfy an order preservation property.

Key techniques include:

  • Serialization Functions: Mechanisms to determine the relative serialization order of global transactions at local sites, even with heterogeneous concurrency control protocols.
  • Redo Approach for Atomicity: Instead of 2PC, this approach uses a "redo" transaction to re-execute updates from aborted subtransactions, ensuring atomicity without requiring local DBMS participation in an atomic commit protocol. This preserves local autonomy.
  • M-Recoverability and M-Serializability: New concepts to characterize when consistency is preserved with the redo approach, considering the global view of transactions.
  • Order Preservation Property: A condition that servers must enforce to ensure that the serialization order of global transactions is consistent across sites.

The framework aims to overcome heterogeneity and autonomy issues by treating local DBMSs as "black boxes" that cannot be modified.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and model, using examples to illustrate concepts rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Decomposition is Key: The problem of failure-resilient transaction management in MDBSs can be effectively broken down into three manageable subproblems: serializability of a global schedule (Ŝ), M-serializability of local schedules, and order preservation.
  • Redo as an Autonomy-Preserving Atomicity Solution: The "redo" approach offers a viable alternative to 2PC for ensuring transaction atomicity in autonomous MDBS environments, avoiding the need for local DBMSs to enter a prepared state.
  • Global View vs. Local View: The distinction between how transactions appear locally (LV(Sj)) and globally (GV(Sj)) is crucial for understanding and ensuring consistency in MDBSs, especially when dealing with recovery mechanisms like redo.
  • M-Conflict Relation as a Generalization: The M-conflict relation provides a unified way to identify conflicts in the global view, even when local schedules are not strictly serializable in that view.

Key Results

The paper establishes a theoretical framework for achieving global serializability in MDBSs in the presence of failures. It demonstrates that by solving the three identified subproblems (ensuring serializability of Ŝ, M-serializability of local schedules, and order preservation), global serializability can be achieved. The framework is designed to work with autonomous local DBMSs without requiring modifications to their existing software.

Limitations and Future Work

  • Assumptions: The framework relies on certain assumptions about local DBMS interfaces (e.g., operation interface) and the ability to construct redo transactions. While some relaxations are discussed, these assumptions can limit applicability.
  • Complexity of Implementation: While the theoretical framework is presented, the practical implementation of mechanisms to ensure M-serializability and order preservation, especially with diverse local DBMSs, can be complex.
  • Study of Application Domains: The authors suggest that further study is needed to determine if a significant number of MDBS application domains fall within the boundaries where the proposed framework's restrictions are met.
  • Deadlock Detection: The paper explicitly states that it does not address deadlock detection in MDBS environments, which remains an open challenge.

Summary updated

BibTeX
@article{mehrotra2001overcoming,
  author = {Sharad Mehrotra and Rajeev Rastogi and Yuri Breitbart and Henry F. Korth and Abraham Silberschatz},
  title = {{Overcoming Heterogeneity and Autonomy in Multidatabase Systems}},
  journal = {Inf. Comput.},
  year = {2001},
  doi = {10.1006/inco.2001.3033},
}
Figure