Minimizing Time-Space Cost For Database Version Control (extended abstract)
Summary: Introduces a "version graph" model for minimizing space vs. regeneration (time) cost in database version control and shows the general optimization and variants are NP-complete. Proposes heuristics with worst-case guarantees and exact algorithms: linear-time for trees, single-cycle, or max-degree-2 graphs, and O(n^3) for uniform edge lengths. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Lin Yu
- 2. Daniel J. Rosenkrantz
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,919 | Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications (Extended Abstract) | 1990 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 32 | Differential Files: Their Application To The Maintenance Of Large Data Bases | 1976 | SIGMOD | 0.00077486306 |
| 740 | Integration of Time Versions into a Relational Database System | 1984 | VLDB | 0.00017373475 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,630 | A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition | 2022 | VLDB | 4.480887e-05 |
| 4,194 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3697822e-05 |
| 6,694 | Optimal Splitters for Temporal and Multi-version Databases | 2013 | SIGMOD | 4.9586454e-05 |
| 12,966 | Temporal Relationships in Databases | 1988 | VLDB | 4.1945683e-05 |
| 5,168 | A General Model for Version Management in Databases | 1986 | VLDB | 5.6518215e-05 |
| 5,970 | On Merging Partitioned Databases | 1983 | SIGMOD | 5.2481582e-05 |
| 265 | A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification | 2005 | SIGMOD | 0.00029763412 |
| 1,565 | Principles of Dataset Versioning: Exploring the Recreation/Storage Tradeoff | 2015 | VLDB | 0.00011345567 |
| 728 | Meaningful Change Detection in Structured Data | 1997 | SIGMOD | 0.00017494982 |
| 1,621 | Serialization Graph Algorithms for Multiversion Concurrency Control | 1988 | PODS | 0.00011109354 |