Menemukan ketergantungan fungsional dalam data digunakan dalam berbagai bidang analisis data: manajemen basis data, pembersihan data, rekayasa balik basis data, dan eksplorasi data. Kami telah mempublikasikan tentang dependensi itu sendiri Anastasia Birillo dan Nikita Bobrov. Kali ini Anastasia, lulusan Pusat Ilmu Komputer tahun ini, menceritakan perkembangan karyanya sebagai bagian dari karya penelitian yang ia pertahankan di pusat tersebut.
Pemilihan tugas
Saat kuliah di CS center, saya mulai mempelajari database secara mendalam yaitu pencarian ketergantungan fungsional dan perbedaan. Topik ini terkait dengan topik tugas kuliah saya di universitas, jadi saat mengerjakan tugas kuliah, saya mulai membaca artikel tentang berbagai ketergantungan pada database. Saya menulis ulasan tentang area ini - salah satu ulasan pertama saya dalam bahasa Inggris dan menyerahkannya ke konferensi SEIM-2017. Saya sangat senang ketika mengetahui bahwa dia diterima, dan memutuskan untuk mempelajari topik ini lebih dalam. Konsepnya sendiri bukanlah hal baru - mulai digunakan pada tahun 90-an, namun hingga saat ini masih digunakan di banyak daerah.
Selama semester kedua saya di pusat tersebut, saya memulai proyek penelitian untuk meningkatkan algoritma untuk menemukan ketergantungan fungsional. Dia mengerjakannya bersama dengan mahasiswa pascasarjana Universitas Negeri St. Petersburg Nikita Bobrov di JetBrains Research.
Kompleksitas komputasi dalam mencari dependensi fungsional
Masalah utamanya adalah kompleksitas komputasi. Jumlah kemungkinan ketergantungan minimal dan non-sepele dibatasi di atas oleh nilainya Dimana β jumlah atribut tabel. Waktu pengoperasian algoritma tidak hanya bergantung pada jumlah atribut, tetapi juga pada jumlah baris. Pada tahun 90an, algoritma pencarian hukum federal pada PC desktop biasa dapat memproses kumpulan data yang berisi hingga 20 atribut dan puluhan ribu baris dalam waktu hingga beberapa jam. Algoritme modern yang berjalan pada prosesor multi-inti mendeteksi dependensi untuk kumpulan data yang terdiri dari ratusan atribut (hingga 200) dan ratusan ribu baris dalam waktu yang hampir bersamaan. Namun, ini belum 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 persimpangan partisi
Pada bagian pertama pekerjaan, kami mengembangkan skema caching untuk kelas algoritma yang menggunakan metode persimpangan partisi. Partisi untuk suatu atribut adalah sekumpulan daftar, di mana setiap daftar berisi nomor baris dengan nilai yang sama untuk atribut tertentu. Setiap daftar tersebut disebut cluster. Banyak algoritma modern yang menggunakan partisi untuk menentukan apakah suatu ketergantungan dipertahankan atau tidak, yaitu mengikuti lemma: Ketergantungan diadakan jika . Di sini sebuah partisi ditentukan dan konsep ukuran partisi digunakan - jumlah cluster di dalamnya. Algoritma yang menggunakan partisi, jika ketergantungan dilanggar, tambahkan atribut tambahan ke sisi kiri ketergantungan, lalu hitung ulang, lakukan operasi perpotongan partisi. Operasi ini disebut spesialisasi dalam artikel. Namun kami memperhatikan bahwa partisi untuk dependensi yang hanya akan dipertahankan setelah beberapa putaran spesialisasi dapat digunakan kembali secara aktif, yang secara signifikan dapat mengurangi waktu berjalannya algoritme, karena operasi persimpangan itu mahal.
Oleh karena itu, kami mengusulkan heuristik berdasarkan Entropi Shannon dan Ketidakpastian Ginny, serta metrik kami, yang kami sebut Entropi Terbalik. Ini adalah sedikit modifikasi dari Entropi Shannon dan meningkat seiring dengan meningkatnya keunikan kumpulan data. Heuristik yang diusulkan adalah sebagai berikut:
Di sini β tingkat keunikan partisi yang baru dihitung Dan adalah median derajat keunikan atribut individu. Ketiga metrik yang dijelaskan di atas diuji sebagai metrik keunikan. Anda juga dapat melihat bahwa ada dua pengubah dalam heuristik. Yang pertama menunjukkan seberapa dekat partisi saat ini dengan kunci utama dan memungkinkan Anda untuk melakukan cache ke tingkat yang lebih besar pada partisi yang jauh dari kunci potensial. Pengubah kedua memungkinkan Anda memantau penggunaan cache dan dengan demikian mendorong penambahan lebih banyak partisi ke cache jika ruang kosong tersedia. Solusi yang berhasil untuk masalah ini memungkinkan kami mempercepat algoritme PYRO sebesar 10-40%, bergantung pada kumpulan datanya. Perlu dicatat bahwa algoritma PYRO adalah yang paling sukses di bidang ini.
Pada gambar di bawah ini Anda dapat melihat hasil penerapan heuristik yang diusulkan dibandingkan dengan pendekatan dasar cache coin-flip. Sumbu X adalah logaritmik.
Cara alternatif untuk menyimpan partisi
Kami kemudian mengusulkan cara alternatif untuk menyimpan partisi. Partisi adalah sekumpulan cluster yang masing-masing menyimpan sejumlah tupel dengan nilai identik untuk atribut tertentu. Cluster ini mungkin berisi urutan nomor tupel yang panjang, misalnya jika data dalam tabel diurutkan. Oleh karena itu, kami mengusulkan skema kompresi untuk menyimpan partisi, yaitu penyimpanan interval nilai dalam kelompok partisi:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Interval pertama}, underbrace{7, 8}_{Interval kedua}, 10}}\ panah bawah{ Kompresi} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Metode ini mampu mengurangi konsumsi memori selama pengoperasian algoritma TANE dari 1 menjadi 25%. Algoritma TANE adalah algoritma klasik untuk mencari hukum federal, menggunakan partisi selama kerjanya. Sebagai bagian dari praktik, algoritme TANE dipilih karena lebih mudah mengimplementasikan penyimpanan interval di dalamnya daripada, misalnya, di PYRO untuk menilai apakah pendekatan yang diusulkan berhasil. Hasil yang diperoleh disajikan pada gambar di bawah ini. Sumbu X adalah logaritmik.
Konferensi ADBIS-2019
Berdasarkan hasil penelitian, pada bulan September 2019 saya menerbitkan sebuah artikel pada Konferensi Eropa tentang Kemajuan Basis Data dan Sistem Informasi ke-23 (ADBIS-2019). Selama presentasi, karya tersebut dicatat oleh Bernhard Thalheim, orang penting di bidang database. Hasil penelitian menjadi dasar disertasi saya di gelar master matematika dan mekanika di Universitas Negeri St. Petersburg, di mana kedua pendekatan yang diusulkan (caching dan kompresi) diimplementasikan dalam kedua algoritma: TANE dan PYRO. Selain itu, hasil menunjukkan bahwa pendekatan yang diusulkan bersifat universal, karena pada kedua algoritma, dengan kedua pendekatan tersebut, terjadi pengurangan konsumsi memori yang signifikan, serta pengurangan yang signifikan dalam waktu pengoperasian algoritma.
Sumber: www.habr.com