Models for Test Cost Minimization in Database Migration

Bugra Caskurlu (), K. Subramani (), Utku Umur Acikalin (), Alvaro Velasquez () and Piotr Wojciechowski ()
Additional contact information
Bugra Caskurlu: Computer Engineering Department, TOBB University of Economics and Technology, Ankara 06560, Turkey
K. Subramani: Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, West Virginia 06510
Utku Umur Acikalin: Computer Engineering Department, TOBB University of Economics and Technology, Ankara 06560, Turkey
Alvaro Velasquez: Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309
Piotr Wojciechowski: Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, West Virginia 06510

INFORMS Journal on Computing, 2025, vol. 37, issue 2, 249-269

Abstract: Database migration is a ubiquitous need faced by enterprises that generate and use vast amounts of data. This is because of database software updates, or it is from changes to hardware, project standards, and other business factors. Migrating a large collection of databases is a way more challenging task than migrating a single database because of the presence of additional constraints. These constraints include capacities of shifts and sizes of databases. In this paper, we present a comprehensive framework that can be used to model database migration problems of different enterprises with customized constraints by appropriately instantiating the parameters of the framework. These parameters are the size of each database, the size of each shift, and the cost of testing each application. Each of these parameters can be either constant or arbitrary. Additionally, the cost of testing an application can be proportional to the number of databases that the application uses. We establish the computational complexities of a number of instantiations of this framework. We present fixed-parameter intractability results for various relevant parameters of the database migration problem. We also provide approximability and inapproximability results as well as lower bounds for the running time of any exact algorithm for the database migration problem. We show that the database migration problem is equivalent to a variation of the classical hypergraph partitioning problem. Our theoretical results also imply new theoretical results for the hypergraph partitioning problem that are interesting in their own right. Finally, we adapt heuristic algorithms devised for the hypergraph partitioning problem to the database migration problem, and we also give experimental results for the adapted heuristics.

Keywords: database migration; hypergraph partitioning; inapproximability; fixed-parameter tractability (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0021 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:2:p:249-269

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().