Gjetja e varësive funksionale në të dhëna përdoret në fusha të ndryshme të analizës së të dhënave: menaxhimi i bazës së të dhënave, pastrimi i të dhënave, inxhinieria e kundërt e bazës së të dhënave dhe eksplorimi i të dhënave. Ne kemi publikuar tashmë për vetë varësitë Anastasia Birillo dhe Nikita Bobrov. Këtë herë Anastasia, e diplomuar në Qendrën e Shkencave Kompjuterike këtë vit, ndan zhvillimin e kësaj pune si pjesë e punës kërkimore që ajo mbrojti në qendër.
Zgjedhja e detyrës
Ndërsa studioja në qendrën CS, fillova të studioja në thellësi bazat e të dhënave, përkatësisht kërkimin e varësive funksionale dhe të ndryshimit. Kjo temë lidhej me temën e lëndës sime në universitet, kështu që ndërsa punoja në lëndën, fillova të lexoj artikuj për varësi të ndryshme në bazat e të dhënave. Unë shkrova një përmbledhje të kësaj fushe - një nga të parat e mia në anglisht dhe e dorëzoi atë në konferencën SEIM-2017. U gëzova shumë kur mora vesh se në fund të fundit ajo ishte pranuar dhe vendosa të thellohesha më thellë në temë. Vetë koncepti nuk është i ri - ai filloi të përdoret në vitet '90, por edhe tani përdoret në shumë fusha.
Gjatë semestrit tim të dytë në qendër, fillova një projekt kërkimor për të përmirësuar algoritmet për gjetjen e varësive funksionale. Ajo punoi për të së bashku me studenten e diplomuar në Universitetin Shtetëror të Shën Petersburgut, Nikita Bobrov në JetBrains Research.
Kompleksiteti llogaritës i kërkimit të varësive funksionale
Problemi kryesor është kompleksiteti llogaritës. Numri i varësive të mundshme minimale dhe jo të parëndësishme kufizohet më lart 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 e kërkimit të ligjit federal në një kompjuter desktop të rregullt mund të përpunonin grupe të dhënash që përmbajnë deri në 20 atribute dhe dhjetëra mijëra rreshta deri në 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 mjafton: një kohë e tillë është e papranueshme për shumicën e aplikacioneve të botës reale. Prandaj, ne kemi zhvilluar qasje për të përshpejtuar algoritmet ekzistuese.
Skemat e memorizimit për kryqëzimet e ndarjeve
NĂ« pjesĂ«n e parĂ« tĂ« punĂ«s, ne zhvilluam skemat e caching pĂ«r njĂ« klasĂ« algoritmesh qĂ« pĂ«rdorin metodĂ«n e kryqĂ«zimit tĂ« ndarjeve. NjĂ« ndarje pĂ«r njĂ« atribut Ă«shtĂ« njĂ« grup listash, ku secila listĂ« pĂ«rmban numra rreshtash me tĂ« njĂ«jtat vlera pĂ«r njĂ« atribut tĂ« caktuar. Ădo listĂ« e tillĂ« quhet njĂ« grup. ShumĂ« algoritme moderne pĂ«rdorin ndarje pĂ«r tĂ« pĂ«rcaktuar nĂ«se njĂ« varĂ«si mbahet apo jo, domethĂ«nĂ«, ata i pĂ«rmbahen lemĂ«s: VarĂ«sia 
mbahet nëse 
. këtu 
caktohet një ndarje dhe përdoret koncepti i madhësisë së ndarjes - numri i grupimeve në të. Algoritmet që përdorin ndarje, kur vartësia shkelet, shtojnë atribute shtesë në anën e majtë të varësisë dhe më pas e rillogaritin atë, duke kryer operacionin e kryqëzimit të ndarjeve. Ky operacion quhet specializim në artikuj. Por ne vumë re se ndarjet për varësitë që do të mbaheshin vetëm pas disa raundeve specializimi mund të ripërdoren në mënyrë aktive, gjë që mund të zvogëlojë ndjeshëm kohën e funksionimit të algoritmeve, pasi operacioni i kryqëzimit është i shtrenjtë.
Prandaj, ne propozuam njĂ« heuristik tĂ« bazuar nĂ« EntropinĂ« Shannon dhe PasigurinĂ« e Ginny, si dhe metrikĂ«n tonĂ«, tĂ« cilĂ«n e quajtĂ«m Entropi e kundĂ«rt. ĂshtĂ« njĂ« modifikim i lehtĂ« i Shannon Entropy dhe rritet me rritjen unike tĂ« grupit tĂ« tĂ« dhĂ«nave. Heuristika e propozuar Ă«shtĂ« si mĂ« poshtĂ«:
Këtu 
â shkalla e unike e ndarjes sĂ« llogaritur sĂ« fundmi 
Dhe 
Ă«shtĂ« mesatarja e shkallĂ«ve tĂ« veçantisĂ« pĂ«r atributet individuale. TĂ« tre metrikat e pĂ«rshkruara mĂ« sipĂ«r u testuan si metrikĂ« unike. Ju gjithashtu mund tĂ« vini re se ka dy modifikues nĂ« heuristik. E para tregon se sa afĂ«r Ă«shtĂ« ndarja aktuale me çelĂ«sin kryesor dhe ju lejon tĂ« ruani memorien nĂ« njĂ« masĂ« mĂ« tĂ« madhe ato ndarje qĂ« janĂ« larg çelĂ«sit tĂ« mundshĂ«m. Modifikuesi i dytĂ« ju lejon tĂ« monitoroni zĂ«nien e cache-it dhe nĂ« kĂ«tĂ« mĂ«nyrĂ« inkurajon shtimin e mĂ« shumĂ« ndarjeve nĂ« cache nĂ«se ka hapĂ«sirĂ« ââtĂ« lirĂ«. Zgjidhja e suksesshme e kĂ«tij problemi na lejoi tĂ« shpejtonim algoritmin PYRO me 10-40%, nĂ« varĂ«si tĂ« grupit tĂ« tĂ« dhĂ«nave. Vlen tĂ« theksohet se algoritmi PYRO Ă«shtĂ« mĂ« i suksesshmi nĂ« kĂ«tĂ« fushĂ«.
Në figurën më poshtë mund të shihni rezultatet e aplikimit të heuristikës së propozuar krahasuar me një qasje bazë të caching-ut me rrokullisje. Boshti X është logaritmik.
Një mënyrë alternative për të ruajtur ndarjet
Më pas propozuam një mënyrë alternative për të ruajtur ndarjet. Ndarjet janë një grup grupimesh, secila prej të cilave ruan një numër tuplesh me vlera identike për atribute të caktuara. Këto grupe mund të përmbajnë sekuenca të gjata të numrave të dyfishtë, për shembull nëse të dhënat në një tabelë janë të renditura. Prandaj, ne propozuam një skemë kompresimi për ruajtjen e ndarjeve, përkatësisht ruajtjen intervale të vlerave në grupet e ndarjeve:
$$display$$pi(X) = {{nënbrace{1, 2, 3, 4, 5}_{Intervali i parë}, underbrace{7, 8}_{Intervali i dytë}, 10}}\ downarrow{ Compression} \ pi(X) = {{nënbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Kjo metodë ishte në gjendje të zvogëlojë konsumin e kujtesës gjatë funksionimit të algoritmit TANE nga 1 në 25%. Algoritmi TANE është një algoritëm klasik për kërkimin e ligjeve federale; ai përdor ndarje gjatë punës së tij. Si pjesë e praktikës, u zgjodh algoritmi TANE, pasi ishte shumë më e lehtë të zbatohej ruajtja intervale në të 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 e mëposhtme. Boshti X është logaritmik.
Konferenca ADBIS-2019
Bazuar në rezultatet e hulumtimit, në shtator 2019 kam publikuar një artikull në Konferencën e 23-të Evropiane për Përparimet në Bazat e të Dhënave dhe Sistemet e Informacionit (ADBIS-2019). Gjatë prezantimit, puna u vu në dukje nga Bernhard Thalheim, një person i rëndësishëm në fushën e bazave të të dhënave. Rezultatet e hulumtimit formuan bazën e disertacionit tim në masterin në matematikë dhe mekanikë në Universitetin Shtetëror të Shën Petersburgut, gjatë të cilit të dyja qasjet e propozuara (caching dhe kompresim) u zbatuan në të dy algoritmet: TANE dhe PYRO. Për më tepër, rezultatet treguan se qasjet e propozuara janë universale, pasi në të dy algoritmet, me të dyja qasjet, u vu re një ulje e ndjeshme e konsumit të memories, si dhe një ulje e ndjeshme në kohën e funksionimit të algoritmeve.
Burimi: www.habr.com
