Die vind van funksionele afhanklikhede in data word gebruik in verskeie areas van data-analise: databasisbestuur, dataskoonmaak, databasis-omgekeerde ingenieurswese en data-eksplorasie. Ons het reeds oor die afhanklikhede self gepubliseer Anastasia Birillo en Nikita Bobrov. Hierdie keer deel Anastasia, 'n gegradueerde van die Rekenaarwetenskapsentrum vanjaar, die ontwikkeling van hierdie werk as deel van die navorsingswerk wat sy by die sentrum verdedig het.
Taakkeuse
Terwyl ek by die CS-sentrum studeer het, het ek begin om databasisse in diepte te bestudeer, naamlik die soeke na funksionele en verskilafhanklikhede. Hierdie onderwerp het verband gehou met die onderwerp van my kursuswerk by die universiteit, so terwyl ek aan die kursuswerk gewerk het, het ek artikels oor verskeie afhanklikhede in databasisse begin lees. Ek het 'n resensie oor hierdie area geskryf - een van my eerste in Engels en het dit by die SEIM-2017-konferensie ingedien. Ek was baie bly toe ek uitvind dat sy tog aanvaar is, en besluit om dieper in die onderwerp te delf. Die konsep self is nie nuut nie - dit het al in die 90's begin gebruik word, maar selfs nou word dit op baie gebiede gebruik.
Gedurende my tweede semester by die sentrum het ek 'n navorsingsprojek begin om algoritmes vir die vind van funksionele afhanklikhede te verbeter. Sy het daaraan gewerk saam met die St. Petersburg State University-student Nikita Bobrov by JetBrains Research.
Rekenkundige kompleksiteit van soeke na funksionele afhanklikhede
Die hoofprobleem is rekenaarkompleksiteit. Die aantal moontlike minimale en nie-triviale afhanklikhede word hierbo beperk deur die waarde Waar β aantal tabelkenmerke. Die werkstyd van die algoritmes hang nie net af van die aantal eienskappe nie, maar ook van die aantal rye. In die 90's kon federale wetsoekalgoritmes op 'n gewone rekenaar rekenaar datastelle verwerk wat tot 20 eienskappe en tienduisende rye in tot 'n paar uur bevat. Moderne algoritmes wat op multi-kern verwerkers loop, bespeur afhanklikhede vir datastelle wat bestaan ββuit honderde eienskappe (tot 200) en honderde duisende rye in ongeveer dieselfde tyd. Dit is egter nie genoeg nie: so 'n tyd is onaanvaarbaar vir die meeste werklike toepassings. Daarom het ons benaderings ontwikkel om bestaande algoritmes te bespoedig.
Kas skemas vir partisie kruisings
In die eerste deel van die werk het ons kasskemas ontwikkel vir 'n klas algoritmes wat die partisie-kruisingsmetode gebruik. 'n Partisie vir 'n kenmerk is 'n stel lyste, waar elke lys lynnommers bevat met dieselfde waardes vir 'n gegewe kenmerk. Elke so 'n lys word 'n groep genoem. Baie moderne algoritmes gebruik partisies om te bepaal of 'n afhanklikheid gehou word of nie, naamlik, hulle voldoen aan die lemma: Afhanklikheid gehou as . Hier 'n partisie word aangewys en die konsep van partisiegrootte word gebruik - die aantal trosse daarin. Algoritmes wat partisies gebruik, wanneer die afhanklikheid geskend word, voeg bykomende eienskappe aan die linkerkant van die afhanklikheid by, en herbereken dit dan, en voer die operasie van kruising van partisies uit. Hierdie operasie word spesialisasie in die artikels genoem. Maar ons het opgemerk dat partisies vir afhanklikhede wat eers na 'n paar rondes van spesialisasie behou sal word, aktief hergebruik kan word, wat die looptyd van die algoritmes aansienlik kan verminder, aangesien die kruisingsoperasie duur is.
Daarom het ons 'n heuristiek voorgestel wat gebaseer is op Shannon Entropy en Ginny Uncertainty, sowel as ons metrieke, wat ons Reverse Entropy genoem het. Dit is 'n effense wysiging van Shannon Entropy en neem toe namate die uniekheid van die datastel toeneem. Die voorgestelde heuristiek is soos volg:
Hier β graad van uniekheid van die onlangs berekende partisie En is die mediaan van die grade van uniekheid vir individuele eienskappe. Al drie metrieke wat hierbo beskryf is, is as 'n uniekheidsmaatstaf getoets. Jy kan ook sien dat daar twee wysigers in die heuristiek is. Die eerste dui aan hoe naby die huidige partisie aan die primΓͺre sleutel is en laat jou toe om daardie partisies wat ver van die potensiΓ«le sleutel af is, in 'n groter mate te kas. Die tweede wysiger laat jou toe om kasbesetting te monitor en moedig daardeur aan om meer partisies by die kas te voeg as daar vrye spasie beskikbaar is. Die suksesvolle oplossing van hierdie probleem het ons in staat gestel om die PYRO-algoritme met 10-40% te versnel, afhangend van die datastel. Dit is opmerklik dat die PYRO-algoritme die suksesvolste op hierdie gebied is.
In die onderstaande figuur kan jy die resultate sien van die toepassing van die voorgestelde heuristiek in vergelyking met 'n basiese munt-flip-kas-benadering. Die X-as is logaritmies.
'n Alternatiewe manier om partisies te stoor
Ons het toe 'n alternatiewe manier voorgestel om partisies te stoor. Partisies is 'n stel groepe, wat elkeen aantal tupels met identiese waardes vir sekere eienskappe stoor. Hierdie trosse kan lang rye van tupelgetalle bevat, byvoorbeeld as die data in 'n tabel georden is. Daarom het ons 'n kompressieskema vir die stoor van partisies voorgestel, naamlik intervalberging van waardes in groepe partisies:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Eerste interval}, underbrace{7, 8}_{Tweede interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{ondersteuning{$, 1, 5}_{Eerste~interval}, onderstreep{7, 8}_{Tweede~interval}, 10}}$$vertoon$$
Hierdie metode kon geheueverbruik tydens die werking van die TANE-algoritme van 1 tot 25% verminder. Die TANE-algoritme is 'n klassieke algoritme om na federale wette te soek; dit gebruik partisies tydens sy werk. As deel van die praktyk is die TANE-algoritme gekies, aangesien dit baie makliker was om intervalberging daarin te implementeer as byvoorbeeld in PYRO om te evalueer of die voorgestelde benadering werk. Die resultate wat verkry is, word in die figuur hieronder aangebied. Die X-as is logaritmies.
Konferensie ADBIS-2019
Op grond van die resultate van die navorsing het ek in September 2019 'n artikel gepubliseer by die 23ste Europese konferensie oor vooruitgang in databasisse en inligtingstelsels (ADBIS-2019). Tydens die aanbieding is kennis geneem van die werk deur Bernhard Thalheim, 'n betekenisvolle persoon op die gebied van databasisse. Die navorsingsresultate het die basis gevorm van my proefskrif by die meestersgraad in wiskunde en meganika aan die St. Petersburg State University, waartydens beide voorgestelde benaderings (kas en kompressie) in beide algoritmes geΓ―mplementeer is: TANE en PYRO. Verder het die resultate getoon dat die voorgestelde benaderings universeel is, aangesien op beide algoritmes, met beide benaderings, 'n beduidende vermindering in geheueverbruik waargeneem is, sowel as 'n beduidende vermindering in die bedryfstyd van die algoritmes.
Bron: will.com