Manggihan kagumantungan fungsional dina data dipaké dina sagala rupa wewengkon analisis data: manajemén database, beberesih data, database reverse rékayasa jeung eksplorasi data. Kami parantos nyebarkeun ngeunaan katergantungan sorangan Anastasia Birillo jeung Nikita Bobrov. Waktos ieu, Anastasia, lulusan Pusat Élmu Komputer taun ieu, ngabagi pamekaran karya ieu salaku bagian tina karya panalungtikan anu anjeunna bela di pusat.
Pamilihan tugas
Nalika diajar di pusat CS, kuring mimiti diajar database sacara jero, nyaéta, milarian katergantungan fungsional sareng bédana. Topik ieu aya hubunganana sareng topik kursus kuring di universitas, janten nalika damel dina kursus, kuring ngamimitian maca tulisan ngeunaan sababaraha katergantungan dina pangkalan data. Kuring nulis ulasan ngeunaan daérah ieu - salah sahiji anu munggaran dina basa Inggris sarta dikintunkeun ka konferensi SEIM-2017. Abdi bagja pisan nalika kuring mendakan yén anjeunna katampi saatosna, sareng mutuskeun pikeun langkung jero kana topik éta. Konsep sorangan teu anyar - mimiti dipaké deui dina 90s, tapi malah ayeuna geus dipaké di loba wewengkon.
Salila semester kadua kuring di pusat, kuring ngamimitian proyek panalungtikan pikeun ningkatkeun algoritma pikeun milarian kagumantungan fungsional. Manehna dikeureuyeuh eta babarengan jeung St. Petersburg State University lulusan murid Nikita Bobrov di JetBrains Panalungtikan.
Pajeulitna komputasi pikeun milarian kagumantungan fungsional
Masalah utama nyaéta pajeulitna komputasi. Jumlah kamungkinan kagumantungan minimal sareng non-trivial diwatesan di luhur ku nilai dimana - Jumlah atribut tabel. Waktu operasi algoritma henteu ngan ukur gumantung kana jumlah atribut, tapi ogé dina jumlah barisan. Dina 90an, algoritma pilarian hukum féderal dina PC desktop biasa bisa ngolah susunan data ngandung nepi ka 20 atribut jeung puluhan rébu baris dina nepi ka sababaraha jam. Algoritma modern anu dijalankeun dina prosesor multi-inti ngadeteksi katergantungan pikeun set data anu diwangun ku ratusan atribut (nepi ka 200) sareng ratusan rébu baris dina waktos anu sami. Nanging, ieu henteu cekap: waktos sapertos kitu henteu tiasa ditampi pikeun kalolobaan aplikasi dunya nyata. Ku alatan éta, kami ngembangkeun pendekatan pikeun nyepetkeun algoritma anu aya.
Skéma cache pikeun intersections partisi
Dina bagian mimiti karya, kami ngembangkeun skéma cache pikeun kelas algoritma anu nganggo metode simpang partisi. Partisi pikeun atribut mangrupikeun sakumpulan daptar, dimana unggal daptar ngandung nomer garis kalayan nilai anu sami pikeun atribut anu dipasihkeun. Unggal daptar sapertos disebut klaster. Seueur algoritma modéren nganggo partisi pikeun nangtoskeun naha gumantungna dilaksanakeun atanapi henteu, nyaéta, aranjeunna taat kana lemma: Dependency dilaksanakeun lamun . Ieuh partisi ditunjuk sareng konsép ukuran partisi dianggo - jumlah klaster di jerona. Algoritma anu nganggo partisi, nalika kagumantungan dilanggar, tambahkeun atribut tambahan di sisi kénca dependensi, teras ngitung deui, ngalaksanakeun operasi simpang partisi. Operasi ieu disebut Spésialisasi dina artikel. Tapi kami perhatikeun yén partisi pikeun kagumantungan anu ngan bakal dipikagaduh saatos sababaraha spésialisasi tiasa dianggo deui sacara aktip, anu sacara signifikan tiasa ngirangan waktos ngajalankeun algoritma, sabab operasi simpang mahal.
Ku alatan éta, kami ngusulkeun heuristik dumasar kana Shannon Éntropi jeung Ginny kateupastian, kitu ogé métrik urang, nu urang disebut Reverse Entropy. Éta mangrupikeun modifikasi sakedik tina Shannon Entropy sareng ningkat nalika keunikan set data naék. Heuristik anu diusulkeun nyaéta kieu:
Ieu téh - darajat uniqueness tina partisi nembé diitung jeung mangrupa median tina darajat uniqueness pikeun atribut individu. Katiluna metrics ditétélakeun di luhur diuji salaku métrik uniqueness. Anjeun oge bisa perhatikeun yén aya dua modifiers dina heuristik. Kahiji nunjukkeun kumaha nutup partisi ayeuna ka konci primér sarta ngidinan Anjeun pikeun cache ka extent gede partisi anu jauh ti konci poténsial. Modifier kadua ngidinan Anjeun pikeun ngawas occupancy cache sarta kukituna nyorong nambahkeun partisi leuwih kana cache lamun spasi bébas sadia. Solusi suksés tina masalah ieu ngamungkinkeun urang pikeun nyepetkeun algoritma PYRO ku 10-40%, gumantung kana set data. Perhatos yén algoritma PYRO mangrupikeun anu paling suksés di daérah ieu.
Dina gambar di handap anjeun tiasa ningali hasil nerapkeun heuristik anu diajukeun dibandingkeun sareng pendekatan cache koin-flip dasar. Sumbu X nyaéta logaritmik.
Cara alternatif pikeun nyimpen partisi
Urang lajeng ngajukeun cara alternatif pikeun nyimpen partisi. Partisi mangrupikeun sakumpulan klaster, anu masing-masing nyimpen jumlah tuple kalayan nilai anu sami pikeun atribut anu tangtu. klaster ieu bisa ngandung runtuyan panjang angka tuple, contona lamun data dina tabél ieu maréntahkeun. Ku alatan éta, kami ngusulkeun skéma komprési pikeun nyimpen partisi, nyaéta neundeun interval nilai dina klaster partisi:
$$tampilan$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{interval kahiji}, underbrace{7, 8}_{interval kadua}, 10}}\ panah handap{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{Mimiti~interval}, underbrace{7, 8}_{second~interval}, 10}}$$display$$
Metoda ieu tiasa ngirangan pamakean mémori salami operasi algoritma TANE tina 1 dugi ka 25%. Algoritma TANE mangrupikeun algoritma klasik pikeun milarian hukum féderal; éta ngagunakeun partisi nalika dianggo. Salaku bagian tina prakna, Algoritma TANE dipilih, sabab éta langkung gampang pikeun nerapkeun panyimpenan interval di dinya tibatan, contona, dina PYRO pikeun ngevaluasi naha pendekatan anu diusulkeun tiasa dianggo. Hasil anu dicandak dipidangkeun dina gambar di handap ieu. Sumbu X nyaéta logaritmik.
Konférénsi ADBIS-2019
Dumasar kana hasil panalungtikan, dina bulan Séptémber 2019 kuring medalkeun artikel dina Konperénsi Éropa ka-23 ngeunaan Kamajuan dina Basis Data sareng Sistem Informasi (ADBIS-2019). Salila presentasi, karya ieu nyatet ku Bernhard Thalheim, hiji jalma signifikan dina widang database. Hasil panalungtikan dijadikeun dasar disertasi kuring di gelar master dina matématika jeung mékanika di St. Petersburg State University, salila duanana pendekatan diusulkeun (caching jeung komprési) dilaksanakeun dina duanana algoritma: TANE jeung PYRO. Sumawona, hasil nunjukkeun yén pendekatan anu diusulkeun universal, sabab dina duanana algoritma, kalayan duanana pendekatan, pangurangan anu signifikan dina konsumsi mémori diperhatoskeun, ogé pangurangan anu signifikan dina waktos operasi algoritma.
sumber: www.habr.com