New Results on Test-Cost Minimization in Database Migration

Abstract

An important ubiquitous task in modern cloud systems is the migration of databases from one location to another. In practical settings, the databases are migrated in several shifts in order to meet the quality of service requirements of the end-users [18]. Once a batch of databases is migrated in a shift, the applications that depend on the databases on that shift are to be immediately tested [8]. Testing an application is a costly procedure [25] and the number of times an application is to be tested throughout the migration process varies greatly depending on the migration schedule. An interesting algorithmic challenge is to find a schedule that minimizes the total testing cost of all the applications. This problem, referred to as the capacity constrained database migration (CCDM) problem, is known to be NP-hard and fixed-parameter intractable for various relevant parameters [24]. In this paper, we provide new approximability and inapproximability results as well as new conditional lower bounds for the running time of any exact algorithm for the CCDM problem. Also, we adapt heuristic algorithms devised for the Hypergraph Partitioning problem to the CCDM problem and give extensive experimental results. © 2021, Springer Nature Switzerland AG.