Mencari kebergantungan fungsian dalam data digunakan dalam pelbagai bidang analisis data: pengurusan pangkalan data, pembersihan data, kejuruteraan terbalik pangkalan data dan penerokaan data. Kami telah pun menerbitkan tentang kebergantungan itu sendiri. Anastasia Birillo dan Nikita Bobrov. Kali ini, Anastasia, graduan Pusat Sains Komputer tahun ini, berkongsi perkembangan projek penyelidikan ini, yang dipertahankannya di pusat tersebut.
Pemilihan tugas
Semasa belajar di Pusat CS, saya mula mengkaji pangkalan data secara mendalam, khususnya, mencari kebergantungan fungsian dan pembezaan. Topik ini berkaitan dengan kerja kursus universiti saya, jadi semasa mengusahakannya, saya mula membaca artikel tentang pelbagai kebergantungan dalam pangkalan data. Saya menulis ulasan tentang bidang ini—salah satu ulasan pertama saya dalam Bahasa Inggeris dan menyerahkannya ke persidangan SEIM-2017. Saya teruja apabila ia diterima dan memutuskan untuk mendalami topik tersebut. Konsep itu sendiri bukanlah sesuatu yang baharu—ia telah wujud sejak tahun 90-an—tetapi ia masih menemui aplikasi dalam pelbagai bidang hari ini.
Pada semester kedua saya di pusat tersebut, saya memulakan projek penyelidikan untuk menambah baik algoritma bagi mencari kebergantungan fungsian. Saya telah mengusahakannya bersama Nikita Bobrov, seorang pelajar siswazah di Universiti Negeri St. Petersburg, di JetBrains Research.
Kerumitan pengiraan untuk mencari kebergantungan fungsian
Masalah utama ialah kerumitan pengiraan. Bilangan kebergantungan minimum dan bukan remeh yang mungkin dihadkan dari atas oleh 
Jika 
— bilangan atribut jadual. Masa operasi algoritma bukan sahaja bergantung pada bilangan atribut tetapi juga pada bilangan baris. Pada tahun 90-an, algoritma untuk mengesan undang-undang persekutuan pada PC desktop biasa boleh memproses set data yang mengandungi sehingga 20 atribut dan puluhan ribu baris sehingga beberapa jam. Algoritma moden yang berjalan pada pemproses berbilang teras mengesan kebergantungan untuk set data yang terdiri daripada ratusan atribut (sehingga 200) dan ratusan ribu baris dalam masa yang lebih kurang sama. Walau bagaimanapun, ini tidak mencukupi: masa sedemikian tidak boleh diterima untuk kebanyakan aplikasi dunia sebenar. Oleh itu, kami membangunkan pendekatan untuk mempercepatkan algoritma sedia ada.
Skim caching untuk persimpangan partition
Dalam bahagian pertama kertas kerja ini, kami telah membangunkan skema caching untuk kelas algoritma menggunakan kaedah persilangan partition. Partition untuk atribut ialah satu set senarai, di mana setiap senarai mengandungi nombor baris dengan nilai yang sama untuk atribut yang diberikan. Setiap senarai sedemikian dipanggil kluster. Banyak algoritma moden menggunakan partition untuk menentukan sama ada sesuatu kebergantungan itu berlaku, iaitu, ia mematuhi lema berikut: Kebergantungan 
dikekalkan jika 
. Di sini 
Partition dilambangkan dengan , dan konsep saiz partition—bilangan kluster di dalamnya—digunakan. Algoritma yang menggunakan partition menambah atribut tambahan di sebelah kiri kebergantungan apabila kebergantungan dilanggar, kemudian mengiranya semula dengan melakukan operasi persilangan partition. Operasi ini dirujuk dalam artikel sebagai pengkhususan. Walau bagaimanapun, kami telah menyatakan bahawa partition untuk kebergantungan yang hanya akan dikekalkan selepas beberapa pusingan pengkhususan boleh digunakan semula secara aktif, yang boleh mengurangkan masa operasi algoritma dengan ketara, kerana operasi persilangan adalah mahal.
Oleh itu, kami mencadangkan heuristik berdasarkan entropi Shannon dan ketidakpastian Gini, serta metrik kami sendiri, yang kami panggil Entropi Songsang. Ia merupakan sedikit pengubahsuaian entropi Shannon dan meningkat apabila keunikan set data meningkat. Heuristik yang dicadangkan adalah seperti berikut:
ia adalah 
— tahap keunikan partisi yang baru dikira 
Dan 
ialah median bagi darjah keunikan untuk atribut individu. Ketiga-tiga metrik yang diterangkan di atas telah diuji sebagai metrik keunikan. Ia juga boleh diperhatikan bahawa heuristik merangkumi dua pengubah suai. Yang pertama menunjukkan sejauh mana jarak partition semasa dengan kunci utama dan membolehkan caching partition yang lebih besar lebih jauh daripada kunci calon. Pengubah suai kedua memantau penghunian cache, sekali gus menggalakkan penambahan lebih banyak partition pada cache apabila ruang tersedia. Penyelesaian masalah ini dengan jayanya membolehkan algoritma PYRO memecut sebanyak 10-40% bergantung pada set data. Perlu diingatkan bahawa algoritma PYRO adalah yang paling berjaya dalam bidang ini.
Rajah di bawah menunjukkan keputusan penggunaan heuristik yang dicadangkan berbanding pendekatan penyimpanan asas berdasarkan lambungan syiling. Paksi-x adalah logaritma.
Cara alternatif untuk menyimpan partition
Kemudian, kami mencadangkan kaedah alternatif untuk menyimpan partition. Partition ialah satu set kluster, yang setiap satunya menyimpan nombor tuple dengan nilai yang sama untuk atribut tertentu. Kluster ini boleh mengandungi jujukan nombor tuple yang panjang, contohnya, jika data dalam jadual disusun. Oleh itu, kami mencadangkan skema pemampatan untuk menyimpan partition, iaitu penyimpanan nilai selang masa dalam kluster partition:
$$paparan$$pi(X) = {{pendakap bawah{1, 2, 3, 4, 5}_{Selang~pertama}, pendakap bawah{7, 8}_{Selang~kedua}, 10}}\ panah bawah{Mampatan}\ pi(X) = {{pendakap bawah{$, 1, 5}_{Selang~pertama}, pendakap bawah{7, 8}_{Selang~kedua}, 10}}$$paparan$$
Kaedah ini dapat mengurangkan penggunaan memori semasa pelaksanaan algoritma TANE sebanyak 1 hingga 25%. Algoritma TANE ialah algoritma klasik untuk mencari zon logik; ia menggunakan partition semasa operasinya. Untuk tujuan praktikal, algoritma TANE dipilih kerana pelaksanaan storan selang masa adalah jauh lebih mudah berbanding, sebagai contoh, dalam PYRO untuk menilai kebolehlaksanaan pendekatan yang dicadangkan. Keputusan ditunjukkan dalam rajah di bawah. Paksi-x ialah logaritma.
Persidangan ADBIS-2019
Berdasarkan hasil kajian, saya telah menerbitkan sebuah artikel pada September 2019. Pada Persidangan Eropah ke-23 mengenai Kemajuan dalam Pangkalan Data dan Sistem Maklumat (ADBIS-2019), hasil kerja ini telah diiktiraf oleh Bernhard Thalheim, seorang tokoh terkemuka dalam bidang pangkalan data. Hasil penyelidikan ini menjadi asas disertasi saya untuk program Sarjana di Fakulti Matematik dan Mekanik di Universiti Negeri St. Petersburg, di mana kedua-dua pendekatan yang dicadangkan (caching dan compression) telah dilaksanakan dalam kedua-dua algoritma: TANE dan PYRO. Keputusan menunjukkan bahawa pendekatan yang dicadangkan adalah universal, kerana kedua-dua algoritma menunjukkan pengurangan yang ketara dalam penggunaan memori dan pengurangan yang ketara dalam masa pelaksanaan.
Sumber: www.habr.com
