Ang paghahanap ng mga functional na dependency sa data ay ginagamit sa iba't ibang bahagi ng pagsusuri ng data: pamamahala ng database, paglilinis ng data, reverse engineering ng database at paggalugad ng data. Nai-publish na namin ang tungkol sa mga dependency mismo Anastasia Birillo at Nikita Bobrov. Sa pagkakataong ito, ibinahagi ni Anastasia, isang nagtapos ng Computer Science Center ngayong taon, ang pagbuo ng gawaing ito bilang bahagi ng gawaing pananaliksik na kanyang ipinagtanggol sa sentro.
Pagpili ng gawain
Habang nag-aaral sa CS center, nagsimula akong mag-aral ng mga database nang malalim, ibig sabihin, ang paghahanap para sa functional at difference dependencies. Ang paksang ito ay nauugnay sa paksa ng aking coursework sa unibersidad, kaya habang nagtatrabaho sa coursework, nagsimula akong magbasa ng mga artikulo tungkol sa iba't ibang dependency sa mga database. Sumulat ako ng pagsusuri sa lugar na ito - isa sa aking una sa Ingles at isinumite ito sa kumperensya ng SEIM-2017. Tuwang-tuwa ako noong nalaman kong tinanggap siya, at nagpasya akong mag-dede deep sa paksa. Ang konsepto mismo ay hindi bago - nagsimula itong gamitin noong 90s, ngunit kahit ngayon ay ginagamit ito sa maraming lugar.
Sa aking ikalawang semestre sa center, nagsimula ako ng isang proyekto sa pananaliksik upang mapabuti ang mga algorithm para sa paghahanap ng mga functional na dependency. Pinagtrabaho niya ito kasama ang nagtapos na estudyante ng St. Petersburg State University na si Nikita Bobrov sa JetBrains Research.
Computational complexity ng paghahanap ng functional dependencies
Ang pangunahing problema ay computational complexity. Ang bilang ng posibleng minimal at hindi trivial na mga dependency ay limitado sa itaas ng halaga Saan β bilang ng mga katangian ng talahanayan. Ang oras ng pagpapatakbo ng mga algorithm ay nakasalalay hindi lamang sa bilang ng mga katangian, kundi pati na rin sa bilang ng mga hilera. Noong dekada 90, ang mga algorithm sa paghahanap ng batas ng pederal sa isang regular na desktop PC ay maaaring magproseso ng mga set ng data na naglalaman ng hanggang 20 attribute at sampu-sampung libong row sa loob ng ilang oras. Nakikita ng mga modernong algorithm na tumatakbo sa mga multi-core na processor ang mga dependency para sa mga set ng data na binubuo ng daan-daang attribute (hanggang 200) at daan-daang libong row sa humigit-kumulang sa parehong oras. Gayunpaman, hindi ito sapat: ang ganitong oras ay hindi katanggap-tanggap para sa karamihan ng mga real-world na application. Samakatuwid, bumuo kami ng mga diskarte upang mapabilis ang mga umiiral na algorithm.
Mga scheme ng pag-cache para sa mga intersection ng partition
Sa unang bahagi ng trabaho, bumuo kami ng mga caching scheme para sa isang klase ng mga algorithm na gumagamit ng partition intersection method. Ang partition para sa isang attribute ay isang set ng mga listahan, kung saan ang bawat listahan ay naglalaman ng mga line number na may parehong mga value para sa isang naibigay na attribute. Ang bawat naturang listahan ay tinatawag na isang kumpol. Maraming mga modernong algorithm ang gumagamit ng mga partisyon upang matukoy kung ang isang dependency ay gaganapin o hindi, ibig sabihin, sila ay sumusunod sa lemma: Dependency gaganapin kung . Dito ang isang partisyon ay itinalaga at ang konsepto ng laki ng partisyon ay ginagamit - ang bilang ng mga kumpol sa loob nito. Ang mga algorithm na gumagamit ng mga partisyon, kapag ang dependency ay nilabag, magdagdag ng mga karagdagang katangian sa kaliwang bahagi ng dependency, at pagkatapos ay muling kalkulahin ito, na isinasagawa ang operasyon ng intersection ng mga partisyon. Ang operasyong ito ay tinatawag na espesyalisasyon sa mga artikulo. Ngunit napansin namin na ang mga partisyon para sa mga dependency na pananatilihin lamang pagkatapos ng ilang round ng espesyalisasyon ay maaaring aktibong magamit muli, na maaaring makabuluhang bawasan ang oras ng pagtakbo ng mga algorithm, dahil mahal ang operasyon ng intersection.
Samakatuwid, iminungkahi namin ang isang heuristic batay sa Shannon Entropy at Ginny Uncertainty, pati na rin ang aming sukatan, na tinawag naming Reverse Entropy. Ito ay isang bahagyang pagbabago ng Shannon Entropy at tumataas habang tumataas ang pagiging natatangi ng set ng data. Ang iminungkahing heuristic ay ang mga sumusunod:
Dito β antas ng pagiging natatangi ng kamakailang kinakalkula na partisyon At ay ang median ng mga antas ng pagiging natatangi para sa mga indibidwal na katangian. Lahat ng tatlong sukatan na inilarawan sa itaas ay sinubukan bilang isang sukatan ng pagiging natatangi. Mapapansin mo rin na mayroong dalawang modifier sa heuristic. Ang una ay nagpapahiwatig kung gaano kalapit ang kasalukuyang partition sa pangunahing key at nagbibigay-daan sa iyo na i-cache sa mas malaking lawak ang mga partisyon na malayo sa potensyal na key. Ang pangalawang modifier ay nagbibigay-daan sa iyo na subaybayan ang cache occupancy at sa gayon ay hinihikayat ang pagdaragdag ng higit pang mga partisyon sa cache kung may available na libreng espasyo. Ang matagumpay na solusyon ng problemang ito ay nagbigay-daan sa amin na pabilisin ang PYRO algorithm ng 10-40%, depende sa dataset. Kapansin-pansin na ang PYRO algorithm ay ang pinakamatagumpay sa lugar na ito.
Sa figure sa ibaba makikita mo ang mga resulta ng paglalapat ng iminungkahing heuristic kumpara sa isang pangunahing diskarte sa pag-cache ng coin-flip. Ang X axis ay logarithmic.
Isang alternatibong paraan upang mag-imbak ng mga partisyon
Pagkatapos ay iminungkahi namin ang isang alternatibong paraan upang mag-imbak ng mga partisyon. Ang mga partisyon ay isang hanay ng mga kumpol, na ang bawat isa ay nag-iimbak ng mga bilang ng mga tuple na may magkaparehong halaga para sa ilang partikular na katangian. Ang mga cluster na ito ay maaaring maglaman ng mahabang pagkakasunud-sunod ng mga numero ng tuple, halimbawa kung ang data sa isang talahanayan ay nakaayos. Samakatuwid, iminungkahi namin ang isang scheme ng compression para sa pag-iimbak ng mga partisyon, lalo na ang pag-iimbak ng pagitan ng mga halaga sa mga kumpol ng mga partisyon:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7, 8}_{Second interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Ang pamamaraang ito ay nagawang bawasan ang pagkonsumo ng memorya sa panahon ng pagpapatakbo ng TANE algorithm mula 1 hanggang 25%. Ang TANE algorithm ay isang klasikong algorithm para sa paghahanap ng mga pederal na batas; gumagamit ito ng mga partisyon sa panahon ng trabaho nito. Bilang bahagi ng pagsasanay, napili ang algorithm ng TANE, dahil mas madaling ipatupad ang pag-iimbak ng agwat dito kaysa, halimbawa, sa PYRO upang masuri kung gumagana ang iminungkahing diskarte. Ang mga resulta na nakuha ay ipinakita sa figure sa ibaba. Ang X axis ay logarithmic.
Conference ADBIS-2019
Batay sa mga resulta ng pananaliksik, noong Setyembre 2019 naglathala ako ng isang artikulo sa 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Sa panahon ng pagtatanghal, ang gawain ay napansin ni Bernhard Thalheim, isang makabuluhang tao sa larangan ng mga database. Ang mga resulta ng pananaliksik ay naging batayan ng aking disertasyon sa master's degree sa matematika at mekanika sa St. Petersburg State University, kung saan ang parehong mga iminungkahing diskarte (caching at compression) ay ipinatupad sa parehong mga algorithm: TANE at PYRO. Bukod dito, ipinakita ng mga resulta na ang mga iminungkahing diskarte ay pangkalahatan, dahil sa parehong mga algorithm, na may parehong mga diskarte, isang makabuluhang pagbawas sa pagkonsumo ng memorya ay naobserbahan, pati na rin ang isang makabuluhang pagbawas sa oras ng pagpapatakbo ng mga algorithm.
Pinagmulan: www.habr.com