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)

Paper ID: 838
Venue: PODS
Year: 1988
Pagerank: 5.093636e-05
Overall Rank: 13,148 | 9.80%
DOI: 10.1145/308386.308460

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Lin Yu (State University of New York at Albany)
2. Daniel J. Rosenkrantz (State University of New York at Albany)

BibTeX Citation

@inproceedings{yu_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Minimizing Time-Space Cost For Database Version Control (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/308386.308460},
        doi = {10.1145/308386.308460},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Yu, Lin and Rosenkrantz, Daniel J.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,114	Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications (Extended Abstract)	1990	PODS	5.093636e-05

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
59	Differential Files: Their Application To The Maintenance Of Large Data Bases	1976	SIGMOD	0.00040060625
988	Integration of Time Versions into a Relational Database System	1984	VLDB	0.00012809318

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,623	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
2	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
3	6,547	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
4	13,162	Temporal Relationships in Databases	1988	VLDB
5	5,076	A General Model for Version Management in Databases	1986	VLDB
6	7,236	On Merging Partitioned Databases	1983	SIGMOD
7	185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
8	1,349	Principles of Dataset Versioning: Exploring the Recreation/Storage Tradeoff	2015	VLDB
9	881	Meaningful Change Detection in Structured Data	1997	SIGMOD
10	2,675	Serialization Graph Algorithms for Multiversion Concurrency Control	1988	PODS