Minimizing time-space cost for database version control
type: Item
instance of: scholarly article
title: Minimizing time-space cost for database version control
zbMATH Open document ID: 0682.68105
DOI: 10.1007/BF00259470
author: Lin Yu
author: Daniel J. Rosenkrantz
published in: Acta Informatica
publication date: 1990-01-01T00:00:00Z
review text: We introduce the concept of a version graph to model the problem of minimizing the combined cost of storage space and version regeneration time for database version control systems. We show that, in general, this problem and several of its variations are NP-complete. Several heuristics are developed, and performance guarantees for these heuristics are obtained. We also present linear time algorithms for special classes of version graphs; these special classes are likely to apply in many version control systems.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4117906
zbMATH Keywords: database version control
zbMATH Keywords: version graph
zbMATH Keywords: cost of storage space
zbMATH Keywords: NP- complete
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00259470
OpenAlex ID: W2006394074
Recommended article: Q3639043
Recommended article: Q4694688
Recommended article: Minimisation of the update response time in a distributed database system
Recommended article: Time-space tradeoffs for implementations of snapshots
description: scientific article; zbMATH DE number 4117906