Managing and querying transaction-time databases under schema evolution

Hyun Jin Moon, Carlo Curino, Alin Deutsch, Chien-Yi Hou, Carlo ZanioloPVLDB 2008 · DOI

TL;DR

This paper introduces PRIMA, a system that allows users to query historical data from databases that have undergone schema evolution, as if the database schema had never changed. It achieves this by representing database history and schema evolution in XML and using query reformulation techniques to translate user queries from the current schema to the appropriate historical schema versions.

What Problem Does This Paper Address?

Managing and querying historical data in databases is challenging, especially when the database schema itself evolves over time. Traditional approaches often involve migrating old data to the new schema, which can lead to loss of historical accuracy and is computationally expensive. Collaborative web systems like Wikipedia, with their frequent schema changes and need to preserve history, highlight this problem. The core challenge is to enable users to query historical data using a familiar schema (either the current one or a chosen historical one) without requiring them to understand the complex evolution of the schema over time. This involves both efficiently storing historical data and effectively answering queries against it, even across numerous schema versions.

Methods

PRIMA tackles this problem with two key innovations:

  1. Unified Representation (MV-document): The system represents the entire history of both the database content and its schema evolution in a single XML document called an MV-document. This document uses a temporally grouped data model, making it amenable to standard XQuery for historical queries.
  2. Transparent Schema Evolution and Query Reformulation: PRIMA makes schema evolution transparent to the user. Users write queries against a schema version of their choice (typically the current one). The system then automatically reformulates these queries into equivalent queries that can be executed against the historical data stored under its original schema versions. This is achieved through:
  3. Schema Modification Operators (SMOs): These operators describe schema changes (e.g., adding columns, renaming tables).
  4. XML Integrity Constraints (XICs): SMOs are translated into XICs, which act as mappings between schema versions.
  5. Query Analysis and Taxonomy: A query taxonomy categorizes input queries based on source versions, number of tables, and join types. This analysis helps in selecting the most efficient reformulation strategy.
  6. Query Reformulation Engine (MARS): A chase-based engine uses the XICs to rewrite queries.
  7. Optimization Techniques: SMO pruning and compression are employed to handle a large number of schema versions efficiently.

Datasets

  • Synthetic Employee Database: A synthetic dataset based on an employee database schema evolution example (Table 1 in the paper) was used for initial testing and demonstration.
  • MediaWiki Schema Evolution History: Real-world data from the MediaWiki (the software behind Wikipedia) schema evolution history was used to test the system's scalability and practical completeness. This dataset involved 171 schema versions over 4.5 years.

Key Insights and Ideas

  • XML as a Unifying Force: Representing both data history and schema evolution in XML elegantly solves the problem of managing disparate historical versions. XQuery's power then allows for sophisticated temporal queries.
  • Query Reformulation is Key: Instead of costly data migration, query reformulation offers a practical and efficient way to bridge the gap between user queries and historical data under evolving schemas.
  • Query Taxonomy for Efficiency: Classifying queries based on their characteristics (source versions, joins) is crucial for selecting the most efficient reformulation strategy, leading to significant performance gains.
  • Transparency is User-Centric: The ability for users to query using a familiar schema without needing to understand the underlying schema evolution is a major usability improvement.

Key Results

  • Usability Improvement: PRIMA significantly reduces user effort for query writing, saving up to 75% or more compared to manual approaches.
  • Performance Gains: The query reformulation approach, especially when combined with query analysis and optimization, drastically reduces query execution time compared to baseline methods that attempt to answer queries across all versions without analysis.
  • Scalability: The system demonstrates practical scalability, handling the complex MediaWiki schema evolution history with optimized query reformulation times, even across hundreds of schema versions. The optimization techniques (SMO pruning and compression) were shown to be highly effective, reducing the number of effective SMOs used for reformulation.

Limitations and Future Work

  • Performance Dependency on XQuery Engine: The current performance of PRIMA is limited by the underlying XQuery engine. The authors suggest exploring RDBMS-backed storage and query execution for further improvements.
  • Future Work: The authors plan to explore building a highly efficient and scalable transaction-time DBMS that natively supports schema evolution, potentially by integrating their approach into an RDBMS.

Summary updated

BibTeX
@article{moon2008managing,
  author = {Hyun Jin Moon and Carlo Curino and Alin Deutsch and Chien-Yi Hou and Carlo Zaniolo},
  title = {{Managing and querying transaction-time databases under schema evolution}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453952},
}
Figure