Tez (Yüksek Lisans Tezi)--TOBB ETÜ Fen Bilimleri Enstitüsü Ağustos 2022

İçinde bulunduğumuz Büyük Veri çağında birçok firma devasa boyutlarda verilerle çalışmaktadır. Veritabanı göçü, büyük veri üstüne çalışan firmalar için önemli bir problemdir. Veritabanı göçünün, servis kalitesi gereksinimleri nedeniyle tek seferde gerçekleştirilmesi çoğu zaman mümkün değildir. Bu yüzden, firmalar veritabanı göçünü parti adı verilen birden çok kısa zaman aralığında gerçekleştirmeyi tercih etmektedirler. Veritabanı göçü maliyetli bir işlem olmasının yanı sıra ciddi güvenlik riskleri de içermektedir. Bu nedenle, veri göçü işleminde, bazı firmalar uygulama testlerinden kaynaklanan maliyeti düşürmeyi amaçlarken, göç ettirilecek verinin gizli veya hassas bilgiler içerdiği durumlarda firmalar güvenlik risklerini azaltmayı amaçlamaktadırlar. Literatürde veritabanı göçü planlaması problemi uygulama test maliyetinin azaltılması yönünden ele alınmıştır. Bu çalışma ise uygulama test maliyetine ortogonal bir metrik olan güvenlik riskinin azaltılmasına odaklanmaktadır. Veri ne kadar uzun süre erişme açık kalırsa, o kadar büyük bir güvenlik ihlal riski oluşturmaktadır. Dolayısıyla bu tezde ele alınan veritabanı göçü planlaması probleminde güvenlik riski göçün tamamlanması gereken parti sayısıyla ilişkilendirilmektedir. Buna bağlı olarak, güvenlik riskinin minimize edilmesi için veri göçü en az sayıda parti kullanılarak tamamlanmalıdır. Bu çalışmada veritabanı göçü planlaması probleminin güvenlik riskinin minimize edilmesi yönünden ele alınması için teorik bir problem çatısı tanımlanmaktadır. Bu çatı firmaların farklı ihtiyaçları göz önünde bulundurularak tasarlanmıştır ve toplamda 24 farklı modelden oluşmaktadır. Tanımlanan çatıdaki 24 problem modelinden 23 tanesinin hesaplama karmaşıklığı tespit edilmiştir. Bu modellerin 16 tanesinin NP-zor olduğu, 7 tanesinin ise polinom zamanda çözülebildiği tespit edilmiştir. Ayrıca NP-zor modellerden 2 tanesinin asimptotik tamamen polinom zamanlı yakınsama şemasına sahip olduğu, 12 tanesinin ise polinom zamanlı yakınsama şemasına sahip olmadığı ispatlanmıştır. NP-zor modeller için kurucu sezgisel algoritmalar, yerel arama algoritmaları ve bunları kullanan memetik algoritmalar geliştirilmektedir. Geliştirilen memetik algoritmalar problem spesifik 2 çaprazlama ve 2 mutasyon operatörü kullanmaktadır. Geliştirilen memetik algoritmalar 8 saniyeden az bir sürede, örneklerin %95'inde optimalden en fazla %10 uzaklıkta çözümler bulmakta ve örneklerin 72,1'ini optimal çözmektedir. Ayrıca, memetik algoritmalar 82 saniyeden kısa bir sürede, örneklerin %95'inde optimalden en fazla %7 uzaklıkta çözümler bulmakta ve örneklerin 74,5'ini optimal çözmektedir.

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.