It finen fan funksjonele ôfhinklikens yn gegevens wurdt brûkt yn ferskate gebieten fan gegevensanalyse: databasebehear, gegevensreiniging, reverse engineering fan database en gegevensferkenning. Wy hawwe al publisearre oer de ôfhinklikens sels Anastasia Birillo en Nikita Bobrov. Dizze kear dielt Anastasia, in ôfstudearre fan it Computer Science Center dit jier, de ûntwikkeling fan dit wurk as ûnderdiel fan it ûndersykswurk dat se yn it sintrum ferdigene.
Taak seleksje
Wylst ik studearre oan it CS-sintrum, begon ik databases yn 'e djipte te studearjen, nammentlik it sykjen nei funksjonele en ferskillenôfhinklikens. Dit ûnderwerp wie relatearre oan it ûnderwerp fan myn kursuswurk oan 'e universiteit, dus wylst ik oan' e kursus wurke, begon ik artikels te lêzen oer ferskate ôfhinklikens yn databases. Ik skreau in resinsje fan dit gebiet - ien fan myn earste yn it Ingelsk en yntsjinne it oan de SEIM-2017 konferinsje. Ik wie tige bliid doe't ik fûn út dat se nei alle gedachten waard akseptearre, en besletten om te ferdjipje djipper yn it ûnderwerp. It konsept sels is net nij - it begon te brûken yn 'e jierren '90, mar sels no wurdt it brûkt yn in protte gebieten.
Tidens myn twadde semester by it sintrum begon ik in ûndersyksprojekt om algoritmen te ferbetterjen foar it finen fan funksjonele ôfhinklikens. Se wurke der oan tegearre mei ôfstudearre studint Nikita Bobrov fan Sint Petersburg State University by JetBrains Research.
Computational kompleksiteit fan it sykjen nei funksjonele ôfhinklikens
It wichtichste probleem is komputaasje kompleksiteit. It oantal mooglike minimale en net-triviale ôfhinklikens wurdt hjirboppe beheind troch de wearde wêr - oantal tabel attributen. De wurktiid fan de algoritmen hinget net allinnich op it oantal attributen, mar ek op it oantal rigen. Yn 'e jierren '90 koene sykalgoritmen foar federale wet op in gewoane buroblêd PC gegevenssets ferwurkje mei maksimaal 20 attributen en tsientûzenen rigen yn maksimaal ferskate oeren. Moderne algoritmen dy't rinne op multi-core processors detectearje ôfhinklikens foar datasets besteande út hûnderten attributen (oant 200) en hûnderttûzenen rigen yn likernôch deselde tiid. Dit is lykwols net genôch: sa'n tiid is net akseptabel foar de measte echte applikaasjes. Dêrom hawwe wy oanpakken ûntwikkele om besteande algoritmen te fersnellen.
Caching skema's foar partition krusingen
Yn it earste diel fan it wurk, wy ûntwikkele caching skema's foar in klasse fan algoritmen dy't brûke de partition krusing metoade. In partysje foar in attribút is in set fan listen, wêrby't elke list rigelnûmers befettet mei deselde wearden foar in opjûne attribút. Elke sa'n list wurdt in kluster neamd. In protte moderne algoritmen brûke partysjes om te bepalen oft in ôfhinklikens hâlden wurdt of net, nammentlik, se hâlde har oan it lemma: Ofhinklikens holden as . Hjir in partition wurdt oanwiisd en it konsept fan partition grutte wurdt brûkt - it oantal klusters dêryn. Algoritmen dy't brûke partysjes, doe't de ôfhinklikens wurdt skeind, add ekstra attributen oan 'e linker kant fan' e ôfhinklikens, en dan recalculate it, it útfieren fan de operaasje fan krusing fan partysjes. Dizze operaasje wurdt spesjalisaasje neamd yn 'e artikels. Mar wy hawwe opmurken dat partysjes foar ôfhinklikens dy't allinnich wurde behâlden nei in pear rondes fan spesjalisaasje kinne wurde aktyf opnij brûkt, dat kin gâns ferminderje de rinnende tiid fan de algoritmen sûnt de krusing operaasje is djoer.
Dêrom hawwe wy in heuristyk foarsteld basearre op Shannon Entropy en Ginny Uncertainty, lykas ús metrysk, dy't wy Reverse Entropy neamden. It is in lichte wiziging fan Shannon Entropy en nimt ta as de eigenheid fan 'e dataset tanimt. De foarstelde heuristyk is as folget:
it is - graad fan unykheid fan 'e koartlyn berekkene partition en is de mediaan fan 'e graden fan unykheid foar yndividuele attributen. Alle trije hjirboppe beskreaune metriken waarden hifke as in unykensmetrik. Jo kinne ek merke dat d'r twa modifiers binne yn 'e heuristyk. De earste jout oan hoe ticht de aktuele partysje is by de primêre kaai en lit jo de partysjes dy't fier fan 'e potinsjele kaai binne, yn gruttere mjitte cache. De twadde modifikaasje lit jo de besetting fan cache kontrolearje en stimulearret dêrmei it tafoegjen fan mear partysjes oan it cache as frije romte beskikber is. De suksesfolle oplossing fan dit probleem koe ús it PYRO-algoritme mei 10-40% fersnelle, ôfhinklik fan de dataset. It is de muoite wurdich op te merken dat it PYRO-algoritme it meast súksesfol is yn dit gebiet.
Yn 'e ûndersteande figuer kinne jo de resultaten sjen fan it tapassen fan de foarstelde heuristyk yn ferliking mei in basis coin-flip caching oanpak. De X-as is logaritmysk.
In alternative manier om partysjes op te slaan
Wy hawwe doe in alternative manier foarsteld om partysjes op te slaan. Partitionen binne in set fan klusters, wêrfan elk oantallen tuples opslaan mei identike wearden foar bepaalde attributen. Dizze klusters kinne lange sekwinsjes fan tupelnûmers befetsje, bygelyks as de gegevens yn in tabel besteld binne. Dêrom hawwe wy in kompresjeskema foar it opslaan fan partysjes foarsteld, nammentlik ynterval opslach fan wearden yn klusters fan partysjes:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Earste ynterval}, underbrace{7, 8}_{Twadde ynterval}, 10}}\ downarrow{ Kompresje} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Dizze metoade wie by steat om te ferminderjen ûnthâld konsumpsje tidens de wurking fan de TANE algoritme fan 1 nei 25%. It TANE-algoritme is in klassyk algoritme foar it sykjen nei federale wetten; it brûkt partysjes tidens syn wurk. As ûnderdiel fan 'e praktyk waard it TANE-algoritme keazen, om't it folle makliker wie om yntervalopslach yn te fieren as bygelyks yn PYRO om te evaluearjen oft de foarstelde oanpak wurket. De resultaten krigen wurde presintearre yn 'e figuer hjirûnder. De X-as is logaritmysk.
Konferinsje ADBIS-2019
Op grûn fan de resultaten fan it ûndersyk publisearre ik yn septimber 2019 in artikel op de 23e Europeeske konferinsje oer foarútgong yn databases en ynformaasjesystemen (ADBIS-2019). By de presintaasje waard it wurk opmurken troch Bernhard Thalheim, in wichtich persoan op it mêd fan databanken. De ûndersyksresultaten foarmen de basis fan myn dissertaasje by de masterstitel yn wiskunde en meganika oan de Steatsuniversiteit fan Sint-Petersburg, wêrby't beide foarstelde oanpakken (caching en kompresje) yn beide algoritmen ymplementearre waarden: TANE en PYRO. Boppedat lieten de resultaten sjen dat de foarstelde oanpak universeel binne, om't op beide algoritmen, mei beide oanpakken, in signifikante fermindering fan ûnthâldferbrûk waard waarnommen, en ek in signifikante fermindering fan 'e wurktiid fan' e algoritmen.
Boarne: www.habr.com