Menemukan ketergantungan fungsional dalam data digunakan di berbagai bidang analisis data: manajemen basis data, pembersihan data, rekayasa balik basis data, dan eksplorasi data. Kami telah menerbitkan artikel tentang ketergantungan itu sendiri. Anastasia Birillo dan Nikita Bobrov. Kali ini, Anastasia, lulusan Pusat Ilmu Komputer tahun ini, berbagi tentang pengembangan proyek penelitian ini, yang ia pertahankan di pusat tersebut.
Pemilihan tugas
Saat belajar di CS Center, saya mulai mempelajari basis data secara mendalam, khususnya, menemukan dependensi fungsional dan diferensial. Topik ini terkait dengan tugas kuliah saya, jadi sambil mengerjakannya, saya mulai membaca artikel tentang berbagai dependensi dalam basis data. Saya menulis ulasan tentang bidang ini—salah satu karya pertama saya. Saya menulis makalah tersebut dalam bahasa Inggris dan mengirimkannya ke konferensi SEIM-2017. Saya sangat senang ketika makalah tersebut diterima dan memutuskan untuk mempelajari topik ini lebih dalam. Konsep itu sendiri bukanlah hal baru—sudah ada sejak tahun 90-an—tetapi masih banyak diterapkan di berbagai bidang hingga saat ini.
Pada semester kedua saya di pusat penelitian tersebut, saya memulai sebuah proyek penelitian untuk meningkatkan algoritma dalam menemukan ketergantungan fungsional. Saya mengerjakannya bersama Nikita Bobrov, seorang mahasiswa pascasarjana di Universitas Negeri St. Petersburg, di JetBrains Research.
Kompleksitas komputasi dalam mencari ketergantungan fungsional
Masalah utamanya adalah kompleksitas komputasi. Jumlah kemungkinan ketergantungan minimal dan non-trivial dibatasi dari atas oleh 
Dimana 
— jumlah atribut tabel. Waktu eksekusi algoritma tidak hanya bergantung pada jumlah atribut tetapi juga pada jumlah baris. Pada tahun 90-an, algoritma untuk mendeteksi hukum federal pada PC desktop biasa dapat memproses dataset yang berisi hingga 20 atribut dan puluhan ribu baris hingga beberapa jam. Algoritma modern yang berjalan pada prosesor multi-core mendeteksi dependensi untuk dataset yang terdiri dari ratusan atribut (hingga 200) dan ratusan ribu baris dalam waktu yang hampir sama. Namun, ini tidak cukup: waktu seperti itu tidak dapat diterima untuk sebagian besar aplikasi dunia nyata. Oleh karena itu, kami mengembangkan pendekatan untuk mempercepat algoritma yang ada.
Skema caching untuk irisan partisi
Pada bagian pertama makalah ini, kami mengembangkan skema caching untuk kelas algoritma menggunakan metode irisan partisi. Partisi untuk suatu atribut adalah himpunan daftar, di mana setiap daftar berisi nomor baris dengan nilai yang sama untuk atribut yang diberikan. Setiap daftar tersebut disebut klaster. Banyak algoritma modern menggunakan partisi untuk menentukan apakah suatu ketergantungan berlaku, yaitu, mereka mematuhi lemma berikut: Ketergantungan 
dipertahankan jika 
. Di sini 
Partisi dilambangkan dengan , dan konsep ukuran partisi—jumlah klaster di dalamnya—digunakan. Algoritma yang menggunakan partisi menambahkan atribut tambahan ke sisi kiri dependensi ketika suatu dependensi dilanggar, kemudian menghitung ulang dengan melakukan operasi irisan partisi. Operasi ini disebut dalam artikel sebagai spesialisasi. Namun, kami telah mencatat bahwa partisi untuk dependensi yang hanya akan dipertahankan setelah beberapa putaran spesialisasi dapat digunakan kembali secara aktif, yang dapat secara signifikan mengurangi waktu eksekusi algoritma, karena operasi irisan itu mahal.
Oleh karena itu, kami mengusulkan heuristik berdasarkan entropi Shannon dan ketidakpastian Gini, serta metrik kami sendiri, yang kami sebut Entropi Balik. Ini adalah sedikit modifikasi dari entropi Shannon dan meningkat seiring dengan meningkatnya keunikan dataset. Heuristik yang diusulkan adalah sebagai berikut:
Di sini 
— tingkat keunikan partisi yang baru saja dihitung 
Dan 
adalah median dari derajat keunikan untuk atribut individual. Ketiga metrik yang dijelaskan di atas diuji sebagai metrik keunikan. Perlu juga dicatat bahwa heuristik tersebut mencakup dua pengubah. Yang pertama menunjukkan seberapa dekat partisi saat ini dengan kunci utama dan memungkinkan caching yang lebih besar untuk partisi yang lebih jauh dari kunci kandidat. Pengubah kedua memantau okupansi cache, sehingga mendorong penambahan lebih banyak partisi ke cache ketika ruang tersedia. Keberhasilan dalam memecahkan masalah ini memungkinkan algoritma PYRO untuk berakselerasi sebesar 10-40% tergantung pada dataset. Perlu dicatat bahwa algoritma PYRO adalah yang paling sukses di bidang ini.
Gambar di bawah ini menunjukkan hasil penerapan heuristik yang diusulkan dibandingkan dengan pendekatan caching dasar berdasarkan lemparan koin. Sumbu x menggunakan skala logaritmik.
Cara alternatif untuk menyimpan partisi
Kemudian, kami mengusulkan metode alternatif untuk menyimpan partisi. Partisi adalah sekumpulan klaster, yang masing-masing menyimpan angka tupel dengan nilai identik untuk atribut tertentu. Klaster ini dapat berisi urutan angka tupel yang panjang, misalnya, jika data dalam tabel diurutkan. Oleh karena itu, kami mengusulkan skema kompresi untuk menyimpan partisi, yaitu, penyimpanan interval nilai dalam klaster partisi:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Interval~Pertama}, underbrace{7, 8}_{Interval~Kedua}, 10}}\ downarrow{Kompresi}\ pi(X) = {{underbrace{$, 1, 5}_{Interval~Pertama}, underbrace{7, 8}_{Interval~Kedua}, 10}}$$display$$
Metode ini mampu mengurangi konsumsi memori selama eksekusi algoritma TANE sebesar 1 hingga 25%. Algoritma TANE adalah algoritma klasik untuk mencari zona logis; algoritma ini menggunakan partisi selama operasinya. Untuk tujuan praktis, algoritma TANE dipilih karena implementasi penyimpanan interval jauh lebih mudah daripada, misalnya, di PYRO untuk mengevaluasi kelayakan pendekatan yang diusulkan. Hasilnya disajikan pada gambar di bawah ini. Sumbu x adalah logaritmik.
Konferensi ADBIS-2019
Berdasarkan hasil penelitian tersebut, saya menerbitkan sebuah artikel pada bulan September 2019. Pada Konferensi Eropa ke-23 tentang Kemajuan dalam Basis Data dan Sistem Informasi (ADBIS-2019), karya ini diakui oleh Bernhard Thalheim, seorang tokoh terkemuka di bidang basis data. Hasil penelitian tersebut menjadi dasar disertasi saya untuk program Magister di Fakultas Matematika dan Mekanika di Universitas Negeri St. Petersburg, di mana kedua pendekatan yang diusulkan (caching dan kompresi) diimplementasikan dalam kedua algoritma: TANE dan PYRO. Hasilnya menunjukkan bahwa pendekatan yang diusulkan bersifat universal, karena kedua algoritma tersebut menunjukkan pengurangan konsumsi memori yang signifikan dan pengurangan waktu eksekusi yang signifikan.
Sumber: www.habr.com
