Ang paghahanap ng mga functional dependencies sa datos ay ginagamit sa iba't ibang larangan ng pagsusuri ng datos: pamamahala ng database, paglilinis ng datos, reverse engineering ng database, at paggalugad ng datos. Nailathala na namin mismo ang tungkol sa mga dependencies. Sina Anastasia Birillo at Nikita Bobrov. Sa pagkakataong ito, ibinahagi ni Anastasia, isang nagtapos sa Computer Science Center ngayong taon, ang pag-unlad ng proyektong pananaliksik na ito, na kanyang ipinagtanggol sa sentro.
Pagpili ng gawain
Habang nag-aaral sa CS Center, sinimulan kong pag-aralan nang malaliman ang mga database, partikular na ang paghahanap ng mga functional at differential dependencies. Ang paksang ito ay may kaugnayan sa aking mga kurso sa unibersidad, kaya habang ginagawa ito, nagsimula akong magbasa ng mga artikulo tungkol sa iba't ibang dependencies sa mga database. Sumulat ako ng isang rebyu tungkol sa larangang ito—isa sa aking mga unang sa Ingles at isinumite ito sa kumperensya ng SEIM-2017. Tuwang-tuwa ako nang matanggap ito at nagpasya akong mas palalimin ang pag-aaral sa paksa. Ang konsepto mismo ay hindi na bago—ito ay umiral na mula pa noong dekada 90—ngunit ginagamit pa rin ito sa maraming larangan ngayon.
Sa aking ikalawang semestre sa sentro, sinimulan ko ang isang proyektong pananaliksik upang mapabuti ang mga algorithm para sa paghahanap ng mga functional dependencies. Pinagtulungan ko ito kasama si Nikita Bobrov, isang graduate student sa St. Petersburg State University, sa JetBrains Research.
Komplikasyon sa komputasyon ng paghahanap para sa mga functional dependencies
Ang pangunahing problema ay ang pagiging kumplikado ng pagkalkula. Ang bilang ng mga posibleng minimal at hindi-trivial na dependency ay limitado mula sa itaas ng 
Saan 
— ang bilang ng mga katangian ng talahanayan. Ang oras ng pagpapatakbo ng mga algorithm ay hindi lamang nakasalalay sa bilang ng mga katangian kundi pati na rin sa bilang ng mga hilera. Noong dekada 90, ang mga algorithm para sa pagtukoy ng pederal na batas sa isang karaniwang desktop PC ay maaaring magproseso ng mga dataset na naglalaman ng hanggang 20 katangian at sampu-sampung libong hilera nang hanggang ilang oras. Ang mga modernong algorithm na tumatakbo sa mga multi-core processor ay nakakakita ng mga dependency para sa mga dataset na binubuo ng daan-daang katangian (hanggang 200) at daan-daang libong hilera sa halos parehong oras. Gayunpaman, hindi ito sapat: ang ganitong oras ay hindi katanggap-tanggap para sa karamihan ng mga aplikasyon sa totoong mundo. Samakatuwid, bumuo kami ng mga pamamaraan upang mapabilis ang mga umiiral na algorithm.
Mga scheme ng pag-cache para sa interseksyon ng partisyon
Sa unang bahagi ng papel, bumuo kami ng mga caching scheme para sa isang klase ng mga algorithm gamit ang partition intersection method. Ang partition para sa isang attribute ay isang set ng mga listahan, kung saan ang bawat listahan ay naglalaman ng mga numero ng row na may parehong mga halaga para sa ibinigay na attribute. Ang bawat naturang listahan ay tinatawag na cluster. Maraming modernong algorithm ang gumagamit ng mga partition upang matukoy kung ang isang dependency ay nagpapatuloy, ibig sabihin, sumusunod sila sa sumusunod na lemma: Dependency 
ay pinapanatili kung 
. Dito 
Ang isang partisyon ay minamarkahan ng , at ang konsepto ng laki ng partisyon—ang bilang ng mga kumpol sa loob nito—ang ginagamit. Ang mga algorithm na gumagamit ng mga partisyon ay nagdaragdag ng mga karagdagang katangian sa kaliwang bahagi ng dependency kapag ang isang dependency ay nilabag, pagkatapos ay muling kinakalkula ito sa pamamagitan ng pagsasagawa ng isang operasyon ng interseksyon ng partisyon. Ang operasyong ito ay tinutukoy sa mga artikulo bilang espesyalisasyon. Gayunpaman, napansin namin na ang mga partisyon para sa mga dependency na mananatili lamang pagkatapos ng ilang round ng espesyalisasyon ay maaaring aktibong gamitin muli, na maaaring makabuluhang bawasan ang oras ng pagpapatakbo ng mga algorithm, dahil ang operasyon ng interseksyon ay magastos.
Samakatuwid, nagpanukala kami ng isang heuristic batay sa Shannon entropy at Gini uncertainty, pati na rin ang aming sariling metric, na tinatawag naming Inverse Entropy. Ito ay isang bahagyang pagbabago sa Shannon entropy at tumataas habang tumataas ang pagiging natatangi ng dataset. Ang iminungkahing heuristic ay ang mga sumusunod:
Dito 
— ang antas ng pagiging natatangi ng kamakailang kinalkulang partisyon 
At 
ay ang median ng mga antas ng pagiging natatangi para sa mga indibidwal na katangian. Ang lahat ng tatlong sukatan na inilarawan sa itaas ay sinubukan bilang mga sukatan ng pagiging natatangi. Mapapansin din na ang heuristic ay may kasamang dalawang modifier. Ang una ay nagpapahiwatig kung gaano kalapit ang kasalukuyang partisyon sa pangunahing susi at nagbibigay-daan para sa mas malaking pag-cache ng mga partisyon na mas malayo mula sa kandidatong susi. Sinusubaybayan ng pangalawang modifier ang okupasyon ng cache, sa gayon ay hinihikayat ang pagdaragdag ng higit pang mga partisyon sa cache kapag may magagamit na espasyo. Ang matagumpay na paglutas ng problemang ito ay nagbigay-daan sa algorithm ng PYRO na bumilis ng 10-40% depende sa dataset. Mahalagang tandaan na ang algorithm ng PYRO ang pinakamatagumpay sa lugar na ito.
Ang pigura sa ibaba ay nagpapakita ng mga resulta ng paglalapat ng iminungkahing heuristic kumpara sa baseline caching approach batay sa coin flips. Ang x-axis ay logarithmic.
Isang alternatibong paraan upang mag-imbak ng mga partisyon
Pagkatapos ay iminungkahi namin ang isang alternatibong pamamaraan para sa pag-iimbak ng mga partisyon. Ang mga partisyon ay isang hanay ng mga kumpol, na ang bawat isa ay nag-iimbak ng mga numero ng tuple na may magkaparehong mga halaga para sa ilang partikular na katangian. Ang mga kumpol na ito ay maaaring maglaman ng mahahabang pagkakasunud-sunod ng mga numero ng tuple, halimbawa, kung ang data sa isang talahanayan ay nakaayos. Samakatuwid, iminungkahi namin ang isang pamamaraan ng compression para sa pag-iimbak ng mga partisyon, lalo na, ang interval storage ng mga halaga sa mga kumpol ng partisyon:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Unang~interval}, underbrace{7, 8}_{Pangalawang~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, 5}_{Unang~interval}, underbrace{7, 8}_{Pangalawang~interval}, 10}}$$display$$
Nagawa ng pamamaraang ito na mabawasan ang pagkonsumo ng memorya habang isinasagawa ang algorithm ng TANE ng 1 hanggang 25%. Ang algorithm ng TANE ay isang klasikong algorithm para sa paghahanap ng mga logical zone; gumagamit ito ng mga partisyon habang ginagamit ito. Para sa mga praktikal na layunin, pinili ang algorithm ng TANE dahil ang pagpapatupad ng interval storage ay mas madali kaysa, halimbawa, sa PYRO upang suriin ang posibilidad ng iminungkahing pamamaraan. Ang mga resulta ay ipinapakita sa pigura sa ibaba. Ang x-axis ay logarithmic.
Kumperensya ng ADBIS-2019
Batay sa mga resulta ng pananaliksik, naglathala ako ng isang artikulo noong Setyembre 2019. Sa ika-23 European Conference on Advances in Databases and Information Systems (ADBIS-2019), ang gawa ay kinilala ni Bernhard Thalheim, isang kilalang pigura sa larangan ng mga database. Ang mga resulta ng pananaliksik ang naging batayan ng aking disertasyon para sa programang Master sa Faculty of Mathematics and Mechanics sa St. Petersburg State University, kung saan ang parehong iminungkahing pamamaraan (caching at compression) ay ipinatupad sa parehong algorithm: TANE at PYRO. Ipinakita ng mga resulta na ang mga iminungkahing pamamaraan ay unibersal, dahil ang parehong algorithm ay nagpakita ng isang makabuluhang pagbawas sa pagkonsumo ng memorya at isang makabuluhang pagbawas sa oras ng pagpapatupad.
Pinagmulan: www.habr.com
