Kërkimi i varësive funksionale në të dhëna përdoret në drejtime të ndryshme të analizës së të dhënave: menaxhimi i bazave të dhënash, pastrimi i të dhënave, inxhinieria e prapë e bazave të dhënash dhe eksplorimi i të dhënave. Për vetë varësitë, ne kemi publikuar tashmë Anastasija Birillo dhe Nikita Bobrov. Këtë herë Anastasija — e diplomuara e këtij viti nga Qendra e Shkencave Kompjuterike — ndan zhvillimin e këtij projekti në kuadër të NIR-it, të cilin ajo e mbrojti në qendër.
Zgjedhja e detyrës
Gjatë studimeve në Qendrën CS fillova të studioj thellësisht bazat e të dhënave, sidomos kërkimin e varësive funksionale dhe diferenciale. Kjo temë ishte e lidhur me temën e punës sime të kursit në universitet, kështu që gjatë punës mbi punën e kursit fillova të lexoj artikuj mbi varësi të ndryshme në bazat e të dhënave. Nga ajo shkrova një përmbledhje të kësaj fushe — një nga punimet e mia të para në gjuhën angleze dhe e dorëzova në konferencën SEIM-2017. Isha shumë e lumtur kur mësova se ajo ishte pranuar, dhe vendosa të thellohem në temë. Koncepti vetë nuk është i ri — ai filloi të aplikohej që në vitet '90, por edhe tani gjen aplikim në shumë fusha.
Në semestrin e dytë të studimeve në qendër, fillova një projekt kërkimor për përmirësimin e algoritmeve të gjetjes së varësive funksionale. Punova mbi të së bashku me studentin e doktoratës nga SPbGU, Nikita Bobrov, në bazën e JetBrains Research.
Kërkimi i varësive funksionale dhe kompleksiteti i llogaritjes
Problemi kryesor është kompleksiteti i llogaritjes. Numri i varësive minimale dhe jo triviale të mundshme është i kufizuar nga vlera 
, ku 
— numri i atributeve të tabelës. Koha e funksionimit të algoritmeve varet jo vetëm nga numri i atributeve, por edhe nga numri i rreshtave. Në vitet '90, algoritmet për gjetjen e varësive funksionale në një PC të zakonshëm mund të përpunonin grupe të dhënash që përmbanin deri në 20 atribute dhe dhjetëra mijëra rreshta, për disa orë. Algoritmet moderne, që funksionojnë në procesorë me shumë bërthama, zbulojnë varësi për grupe të dhënash që përbëhen nga qindra atribute (deri në 200) dhe qindra mijëra rreshta, përafërsisht në të njëjtën kohë. Megjithatë, kjo nuk është e mjaftueshme: kjo kohë është e papranueshme për shumicën e aplikacioneve reale. Prandaj, ne po zhvillonim qasje për të përshpejtuar algoritmet ekzistuese.
Skematiket e keshtjellave për ndërprerjen e pjesëve
Në pjesën e parë të punës, ne zhvilluam skemat e keshtjellave për klasën e algoritmeve që përdorin metodën e ndërprerjes së pjesëve. Një pjesë për atributin përfaqëson një grup listash, ku çdo listë përmban numra rreshtash me vlera të njëjta për këtë atribut. Çdo listë e tillë quhet klaster. Shumë algoritme moderne përdorin pjesët për të përcaktuar nëse mbahen varësitë apo jo, konkretisht ndjekin lemmën: Varësia 
mbahet nëse 
. Këtu 
pjesa shënohet dhe përdoret koncepti i madhësisë së pjesës - numri i klastereve në të. Algoritmet që përdorin pjesë, në rast të shkeljes së varësisë, shtojnë atribute të tjera në anën e majtë të varësisë, pas së cilës ribëjnë atë duke kryer operacionin e ndërveprimit të pjesëve. Ky operacion në artikuj quhet specializim. Por ne vërejtëm se pjesët për varësitë, të cilat do të mbahen vetëm pas disa raundesh specializimi, mund të ri-përdoren aktivisht, çka mund të reduktojë ndjeshëm kohën e funksionimit të algorithmeve, pasi operacioni i ndërveprimit është i shtrenjtë.
Prandaj ne ofruam një heuristikë të bazuar në Entropinë e Shannon-it dhe paqartësinë e Gini-it, si dhe metrikën tonë, të cilën e quajti Obstruksion Entropia. Ajo është një modifikim i vogël i Entropisë së Shannon-it dhe rritet ndërsa rritet unikësia e grumbullit të të dhënave. Heuristika e propozuar duket si më poshtë:
Këtu 
— shkalla e unikësisë së pjesës së sapo llogaritur 
, dhe 
është një mediane e shkallës së veçantë të unikësisë për atributet e veçanta. Si metrikë unikësie janë provuar të tre metrikat e përshkruara më sipër. Gjithashtu, mund të vërehet se në heuristikë ka dy modifikatorë. Modifikatori i parë tregojnë sa afër është partitimi aktual me çelësin primar dhe lejon ruajtjen më të madhe të atyre partitimeve që janë larg çelësit potencial. Modifikatori i dytë lejon ndjekjen e përdorimit të caches dhe kështu nxit shtimin e më shumë partitimeve në cache kur ka hapësirë të lirë. Zgjidhja e suksesshme e këtij problemi ka lejuar përshpejtimin e algoritmit PYRO me 10-40% në varësi të datasets. Vlen të theksohet se algoritmi PYRO është më i suksesshmi në këtë fushë.
Në pamjen më poshtë mund të shihni rezultatet e aplikimit të heuristikës së propozuar krahasuar me qasjen bazë të caches, e cila është e bazuar në hedhjen e një monedhe. E vertikala X është logaritmike.
Një mënyrë alternative për ruajtjen e partitimeve
Më pas ofruam një mënyrë alternative për ruajtjen e particioneve. Particionet përbëjnë një grup klasterësh, në secilin prej të cilëve ruhet numrat e tupleve me vlera të njëjta për atributet e caktuara. Këta klasterë mund të përmbajnë sekonda të gjata numrash të tupleve, për shembull, nëse të dhënat në tabelë janë të renditura. Prandaj, ofruam një skemë kompresimi për ruajtjen e particioneve, pëkatësisht ruajtjen intervale të vlerave në klasterët e particioneve:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Intervali~i~Parë}, underbrace{7, 8}_{Intervali~i~Dytë}, 10}}\ downarrow{Kompresimi}\ pi(X) = {{underbrace{$, 1, 5}_{Intervali~i~Parë}, underbrace{7, 8}_{Intervali~i~Dytë}, 10}}$$display$$
Ky metod arriti të reduktojë konsumimin e memories gjatë punës së algoritmit TANE nga 1 deri në 25%. Algoritmi TANE është një algoritëm klasik për gjetjen e FQ, ai përdor partitë gjatë punës së tij. Në kuadrin e praktikës, ishte zgjedhur pikërisht algoritmi TANE, pasi implementimi i ruajtjes intervale në të ishte ndjeshëm më i lehtë, sesa për shembull, në PYRO, për të vlerësuar nëse qasja e propozuar funksionon. Rezultatet e marra janë paraqitur në figurën më poshtë. Eksi X është logaritmike.
Konferenca ADBIS-2019
Sip ligjit të hulumtimit të bërë në Shtator 2019, unë prezantova një artikull në konferencën 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Gjatë prezantimit, puna u vlerësua nga Bernhard Thalheim, një figurë e rëndësishme në fushën e bazave të të dhënave. Rezultatet e hulumtimit ishin baza e disertacionit tim në masterin e matematikës dhe mekanikës në SPbGU, gjatë të cilit të dy qasjet e propozuara (kashimi dhe kompresimi) u implementuan në të dy algoritmet: TANE dhe PYRO. Në këtë mënyrë, rezultatet treguan se qasjet e propozuara janë universale, pasi të dy algoritmet për të dy qasjet treguan një reduktim të dukshëm të memories së konsumuar, si dhe një ulje të konsiderueshme të kohës së ekzekutimit të algoritmeve.
Burimi: habr.com
