Models for test cost minimization in database migration

Caskurlu B, Subramani K, Acikalin UU, Velasquez A, Wojciechowski P. “Models for test cost minimization in database migration”

Abstract: Database migration is a ubiquitous need faced by enterprises that generate and use vast amounts of data. This is due to database software updates, or 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 due to 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 application uses. Additionally, we examine a variant of the problem in which all the parameters are constant, there are only two shifts, and each application calls at most two databases. 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 give experimental results for the adapted heuristic algorithms.