TL;DR
This paper introduces PRISM, a workbench that automates and streamlines the complex process of database schema evolution. It addresses the significant challenges DBAs face in predicting schema change impacts, rewriting queries, and migrating data, particularly in dynamic environments like Wikipedia.
What Problem Does This Paper Address?
Database schemas, the blueprints of data organization, are not static. They need to evolve to accommodate new requirements, data types, or business logic. This "schema evolution" is a critical but notoriously difficult task for Database Administrators (DBAs). Traditional systems have largely solved the problem of physical data independence (hiding storage details) but have struggled with logical data independence (hiding structural changes).
When a schema changes, it can have a ripple effect:
- Data Integrity: Changes can break existing data or lead to its loss.
- Application Maintenance: Queries and applications that rely on the old schema will likely fail, requiring extensive and costly rewriting.
- Downtime: The process of evolving a schema and migrating data often necessitates taking the database offline, which is unacceptable for many modern web applications.
This problem is amplified in "Web Information Systems" like Wikipedia, where collaboration leads to frequent schema changes, and downtime is highly undesirable. The paper highlights a DBA's dilemma: the fear of schema changes due to the unknown cost and complexity, leading to a reluctance to upgrade. PRISM aims to bridge this gap by providing tools to predict impacts, automate query rewriting, and manage data migration gracefully.
Methods
PRISM's core innovation lies in its Schema Modification Operators (SMOs). These are atomic, intuitive operations that allow DBAs to express schema changes concisely. PRISM enhances existing SMO concepts by:
- Functions for Conversions: Allowing data type and semantic conversions within SMOs.
- Logical Mappings: Translating SMOs into formal logical representations called Disjunctive Embedded Dependencies (DEDs). This allows for rigorous analysis and query rewriting.
- Invertibility: Developing mechanisms to find "quasi-inverses" for SMOs, enabling the system to reverse schema changes and support legacy queries.
- Automated Query Rewriting: Leveraging a chase-and-backchase engine (MARS) to automatically translate queries written for an old schema version to work on a new schema version.
- Data Migration Scripts & Views: Generating SQL scripts for data migration and SQL views to support legacy queries without modifying applications.
- Documentation: Automatically recording the schema evolution history for provenance, flashbacks, and historical queries.
The system guides the DBA through an iterative process: design schema changes using SMOs, predict and evaluate impacts, generate migration scripts, and finally deploy.
Datasets
The primary dataset used for evaluation is the schema evolution history of Wikipedia. This dataset, derived from the work in [8], includes over 170 schema versions and associated data. The authors also mention using data from other Web Information Systems like MediaWiki, Joomla!, Zen Cart, and TikiWiki for design and refinement.
Key Insights and Ideas
- SMOs as a Bridge: The concept of atomic Schema Modification Operators (SMOs) is crucial. They provide a high-level, intuitive way for DBAs to express complex changes, abstracting away low-level SQL details.
- Formal Mappings are Key: Translating SMOs into formal logical representations (DEDs) unlocks powerful capabilities for analysis, query rewriting, and proving properties like information preservation.
- Invertibility is Practical: The notion of "quasi-inverses" for schema evolution operations is a practical approach to supporting legacy queries and enabling rollbacks, even when perfect inverses don't exist.
- Automation Reduces DBA Burden: The system automates many tedious and error-prone tasks (query rewriting, migration script generation), freeing up DBAs to focus on higher-level design decisions.
- Wikipedia as a Realistic Testbed: Using Wikipedia's extensive and complex schema evolution history demonstrates PRISM's ability to handle real-world, large-scale challenges.
Key Results
- High Automation Rate: PRISM automatically handles 97.2% of schema evolution steps in their experiments.
- Query Support: The system automatically supports a significant percentage of queries: 74% in the worst case, compared to only 16% that would work without any intervention.
- Performance: While manually rewritten queries sometimes outperform PRISM's automatically generated ones (due to implicit knowledge not fed into the system), PRISM's rewritten queries are significantly better than original queries on new schemas. The system also offers reasonable design-time performance for view generation and DED composition.
- Scalability: The system was tested against the entire Wikipedia schema evolution history (170+ versions), demonstrating its capability to handle long-term evolution.
Limitations and Future Work
- Integrity Constraints: While PRISM uses integrity constraints to optimize query rewriting and disambiguate inverses, its support is currently limited and ad-hoc. Future work aims to fully integrate integrity constraint management.
- Update Management: The paper acknowledges that update management is a significant area for future work, building upon PRISM's foundations.
- Manual Rework: In a small percentage of cases (2.8%), DBAs still need to manually rework some queries. The system aims to highlight these cases for the DBA.
- Implicit Knowledge: The performance gap between manual and automatic rewrites sometimes stems from DBAs using implicit knowledge not captured by the system. Future work includes better integration of integrity constraints.
- Temporal Queries: The authors plan to support rich temporal queries over the recorded schema evolution history.
- Automatic SMO Mining: Investigating automatic approaches for deriving SMOs from SQL logs is an ongoing research direction.
Summary updated