Security aware database migration planning

In the age of Big Data, many companies work with a huge amount of data. Database migration is an important problem faced by companies dealing with big data. Not only is migration a costly procedure, it involves serious security risks as well. Due to the quality-of-service requirements, it is often not possible to migrate all databases at once. Therefore, companies prefer to perform database migration in multiple short time intervals called shifts. For some institutions, the primary focus is on reducing the cost of the migration operation, which manifests itself in application testing. For other institutions, minimizing security risks is the most important goal, especially if the data involved is of a sensitive nature. In the literature, the database migration problem has been studied from a test cost minimization perspective. This thesis focuses on an orthogonal measure, i.e., security risk minimization. The security risk is associated with the number of shifts needed to complete the migration task. Ideally, the migration should be completed in as few shifts as possible, so that the risk of data exposure is minimized. In this thesis, a formal framework for studying the database migration problem from the perspective of security risk minimization is provided. The framework consists of 24 models and it is designed so that it can take the different needs of the companies into account. The computational complexity of 23 of the 24 models is established. 16 of the models in the framework are NP-hard, and 7 of the models can be solved in polynomial time. Moreover, it is proven that 2 of the NP-hard models admit an asymptotic fully polynomial time approximation scheme while 12 of the NP-hard models does not admit a polynomial time approximation scheme. For the NP-hard models, several constructive heuristic and local search algorithms are designed, and memetic algorithms that employ these algorithms are developed. The memetic algorithms use 2 problem-specific crossover and 2 mutation operators. These memetic algorithms produce solutions that are within 10% in 95% of the instances and solve 72.1% of the instances optimally under 8 seconds. Furthermore, developed algorithms produce solutions that are within 7% in 95% of the instances and solve 74.5% of the instances optimally under 82 seconds.