KĂ«rkimi i varĂ«sive funksionale nĂ« tĂ« dhĂ«na zbatohet nĂ« drejtim tĂ« ndryshĂ«m tĂ« analizĂ«s sĂ« tĂ« dhĂ«nave: menaxhimi i bazave tĂ« tĂ« dhĂ«nave, pastrimi i tĂ« dhĂ«nave, inxhinieria revers e bazave tĂ« tĂ« dhĂ«nave dhe eksplorimi i tĂ« dhĂ«nave. Ne tashmĂ« kemi publikuar pĂ«r vetĂ« varĂ«sitĂ«. Anastasia Birillo dhe Nikita Bobrov. KĂ«tĂ« herĂ«, Anastasia â njĂ« diplomante e QendrĂ«s pĂ«r Shkencat e Kompjuterit tĂ« kĂ«tij viti â ndan zhvillimin e kĂ«tij punimi brenda NIR, qĂ« ajo e mbrojti nĂ« qendĂ«r.
Zgjedhja e detyrës
GjatĂ« studimeve nĂ« qendrĂ«n CS, fillova tĂ« studioj nĂ« thellĂ«si bazat e tĂ« dhĂ«nave, nĂ« veçanti, kĂ«rkimin e varĂ«sive funksionale dhe diferenciale. Kjo temĂ« ishte e lidhur me temĂ«n e kursit tim nĂ« universitet, kĂ«shtu qĂ« gjatĂ« punĂ«s mbi kursin fillova tĂ« lexoj artikuj pĂ«r varĂ«si tĂ« ndryshme nĂ« bazat e tĂ« dhĂ«nave. Kam shkruar njĂ« pĂ«rmbledhje tĂ« kĂ«saj fushe â njĂ« nga punimet e mia tĂ« para. nĂ« gjuhĂ«n angleze dhe e dĂ«rgova nĂ« konferencĂ«n SEIM-2017. Ishte njĂ« kĂ«naqĂ«si e madhe kur mĂ«sova se ishte pranuar, dhe vendosa tĂ« thellohem nĂ« temĂ«. Koncepti vetĂ« nuk Ă«shtĂ« i ri â u aplikua pĂ«r herĂ« tĂ« parĂ« nĂ« vitet '90, por ende gjen pĂ«rdorim 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ë kërkimit të varësive funksionale. Punova mbi të sëbashku me doktorantin e SPbGU, Nikita Bobrov, në bazën e JetBrains Research.
Kostoja kompjuterike e kërkimit të varësive funksionale.
Problemi kryesor â kostoja kompjuterike. Numri maksimal i varĂ«sive minimale dhe jo-triviale Ă«shtĂ« i kufizuar me vlerĂ«n 
index 
â numri i atributeve tĂ« tabelĂ«s. Koha e ekzekutimit tĂ« algoritmeve varet jo vetĂ«m nga numri i atributeve, por edhe nga numri i rreshtave. NĂ« vitet '90, algoritmet pĂ«r kĂ«rkimin 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 dhjetra mijĂ«ra rreshta, pĂ«r disa orĂ«. Algoritmet moderne, qĂ« punojnĂ« nĂ« procesorĂ« me shumĂ« bĂ«rthama, zbulojnĂ« varĂ«si pĂ«r grupe tĂ« dhĂ«nash qĂ« pĂ«rmbajnĂ« qindra atribute (deri nĂ« 200) dhe qindra mijĂ«ra rreshta, afĂ«rsisht nĂ« tĂ« njĂ«jtin kohĂ«. MegjithatĂ«, kjo nuk Ă«shtĂ« e mjaftueshme: njĂ« kohĂ« e tillĂ« Ă«shtĂ« e papranueshme pĂ«r shumicĂ«n e aplikacioneve reale. Prandaj, ne zhvilluam qasje pĂ«r tĂ« pĂ«rshpejtuar algoritmet ekzistuese.
Skemat e ruajtjes për ndërprerjen e particioneve.
NĂ« pjesĂ«n e parĂ« tĂ« punĂ«s, ne zhvilluam skemat e caching pĂ«r klasĂ«n e algoritmeve qĂ« pĂ«rdorin metodĂ«n e ndĂ«rprerjes sĂ« particioneve. NjĂ« particion pĂ«r njĂ« atribut pĂ«rfaqĂ«son njĂ« grup listash, ku secila listĂ« pĂ«rmban numrat e rreshtave me vlera tĂ« njĂ«jta pĂ«r kĂ«tĂ« atribut. Ădo listĂ« e tillĂ« quhet klaster. ShumĂ« algoritme bashkĂ«kohore pĂ«rdorin partitĂ« pĂ«r tĂ« pĂ«rcaktuar nĂ«se mbahen varĂ«si apo jo, dhe ata specifikojnĂ« lemĂ«n: VarĂ«sia 
ruhet nëse 
. Këtu 
përcaktohet particioni dhe përdoret koncepti i madhësisë së particionit - numri i klastereve në të. Algoritmet që përdorin partitë, kur varësia është shkelur, shtojnë atributet shtesë në pjesën e majtë të varësisë, pas së cilës e ripërcaktojnë atë duke kryer operacionin e ndërprerjes së particioneve. Ky operacion në artikuj quhet specializim. Por ne vërejtem se partitë për varësi që do të mbahen vetëm pas disa raundesh specializimi, mund të përdoren aktivisht, çka mund të reduktojë ndjeshëm kohën e punës së algoritmeve, pasi operacioni i ndërprerjes është i shtrenjtë.
Prandaj ne propozoi një heuristikë, e cila bazohet në Entropinë e Shannon-it dhe pasigurinë e Ginny-t, si dhe në metrikën tonë që e quam Entropi e Kundërt. Ajo është një modifikim i vogël i Entropisë së Shannon-it dhe rritet ndërsa rritet unikësia e grupit të dhënave. Heuristika e propozuar duket si më poshtë:
Këtu 
â niveli i unikĂ«sisĂ« sĂ« particionit qĂ« sapo Ă«shtĂ« llogaritur 
, ndërsa 
është një metrikë mediane për shkallën e unikateve për atribute të veçanta. Si metrikë unikate janë provuar të tre metrikat e përmendura më lart. Gjithashtu, mund të vihet re se në heuristikë ka dy modifikatorë. I pari tregon se sa afër është ndarja aktuale me çelësin primar dhe lejon që të cache-ojmë më shumë ato ndarjet që janë larg çelësit potencial. Modifikatori i dytë lejon të monitorohet ngarkesa e cache-it dhe kështu inkurajon shtimin e më shumë ndarjesh në cache kur ka hapësirë të lirë. Zgjidhja e suksesshme e këtij problemi ka lejuar të përshpejtohet algoritmi PYRO me 10-40% varësisht nga dataset-i. Duhet vlerësuar se algoritmi PYRO është më i suksesshmi në këtë fushë.
Në diagramin më poshtë mund të shihni rezultatet e aplikimit të heuristikës së propozuar në krahasim me qasjen bazë të cache-it, e cila bazohet në hedhjen e një monedhe. Osi X është logaritmik.
Mënyra alternative e ruajtjes së ndarjeve
Thenë ne propozuam një mënyrë alternative për ruajtjen e ndarjeve. Ndarjet përfaqësojnë një grup klasteresh, ku secili përmban numrat e tuple-ve me vlera të njëjta për atribute të caktuara. Këta klasterë mund të përmbajnë sekuenca të gjata numrash të tuple-ve, për shembull, nëse të dhënat në tabelë janë të renditura. Prandaj, ne propozuam një skemë kompresimi për ruajtjen e ndarjeve, e cila është ruajtja intervalore e vlerave në klasterët e ndarjeve:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Intervalli~e~parë}, underbrace{7, 8}_{Intervalli~i~dytë}, 10}}\ downarrow{Kompresimi}\ pi(X) = {{underbrace{$, 1, 5}_{Intervalli~e~parë}, underbrace{7, 8}_{Intervalli~i~dytë}, 10}}$$display$$
Kjo metodë arriti të zvogëlojë konsumimin e memories gjatë punës së algoritmit TANE nga 1 deri në 25%. Algoritmi TANE është një algoritëm klasik për zbuluar FD-të, ai përdor ndarjet gjatë procesit të tij. Për praktikën, u zgjodh konkretisht algoritmi TANE, pasi implementimi i ruajtjes intervalore ishte shumë më i lehtë se, për shembull, në PYRO, për të vlerësuar nëse qasja e propozuar funksionon. Rezultatet e marra paraqiten në diagramin më poshtë. Osi X është logaritmik.
Konferenca ADBIS-2019
Sipas rezultatave të studimit në Shtator 2019, unë kam prezantuar një artikull në konferencën 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Gjatë fjalës së tij, punimin e përmendi Bernhard Thalheim, një personazh i rëndësishëm në fushën e bazave të të dhënave. Rezultatet e kërkimeve shërbyen si bazë për disertacionin tim në masterin e matematikës dhe mekanikës në SPbGU, gjatë të cilit të dy qasjet e sugjeruara (kapja në cache dhe kompresimi) u implementuan në të dy algoritmet: TANE dhe PYRO. Në këtë rast, rezultatet treguan se qasjet e propozuara janë universale, pasi në të dy algoritmet me të dy qasjet u vërejt një reduktim të dukshëm të memories së përdorur, si dhe një reduktim të ndjeshëm të kohës së ekzekutimit të algoritmeve.
Burimi: habr.com
