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,929 | Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications (Extended Abstract) | 1990 | PODS | 4.1905499e-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.00077553033 |
| 738 | Integration of Time Versions into a Relational Database System | 1984 | VLDB | 0.000173732 |
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.4765914e-05 |
| 4,189 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3681294e-05 |
| 6,697 | Optimal Splitters for Temporal and Multi-version Databases | 2013 | SIGMOD | 4.9538866e-05 |
| 12,976 | Temporal Relationships in Databases | 1988 | VLDB | 4.1905499e-05 |
| 5,167 | A General Model for Version Management in Databases | 1986 | VLDB | 5.6463857e-05 |
| 5,977 | On Merging Partitioned Databases | 1983 | SIGMOD | 5.2434005e-05 |
| 268 | A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification | 2005 | SIGMOD | 0.00029739054 |
| 1,565 | Principles of Dataset Versioning: Exploring the Recreation/Storage Tradeoff | 2015 | VLDB | 0.00011336478 |
| 724 | Meaningful Change Detection in Structured Data | 1997 | SIGMOD | 0.00017477352 |
| 1,619 | Serialization Graph Algorithms for Multiversion Concurrency Control | 1988 | PODS | 0.00011114085 |