Ефикасно пронађите функционалне зависности у базама података

Проналажење функционалних зависности у подацима се користи у различитим областима анализе података: управљање базом података, чишћење података, обрнути инжењеринг базе података и истраживање података. О самим зависностима смо већ објавили статью Анастасиа Бирилло и Никита Бобров. Овог пута Анастасија, дипломац овогодишњег Центра за рачунарске науке, дели развој овог рада у оквиру истраживачког рада који је одбранила у центру.

Избор задатака

Док сам студирао у ЦС центру, почео сам дубље да проучавам базе података, односно потрагу за функционалним и разликама зависности. Ова тема је била везана за тему мог курса на универзитету, тако да сам током рада на курсу почео да читам чланке о разним зависностима у базама података. Написао сам рецензију ове области - једну од мојих првих чланци на енглеском језику и предао на конференцију СЕИМ-2017. Био сам веома срећан када сам сазнао да је ипак примљена и одлучио да се дубље удубим у тему. Сам концепт није нов - почео је да се користи још 90-их година, али чак и сада се користи у многим областима.

Током мог другог семестра у центру, започео сам истраживачки пројекат за побољшање алгоритама за проналажење функционалних зависности. Радила је на томе заједно са дипломираним студентом Државног универзитета Санкт Петербурга Никитом Бобровом у ЈетБраинс Ресеарцх-у.

Рачунска сложеност тражења функционалних зависности

Главни проблем је сложеност рачунара. Број могућих минималних и нетривијалних зависности изнад је ограничен вредношћу Где — број атрибута табеле. Време рада алгоритама зависи не само од броја атрибута, већ и од броја редова. Током 90-их, алгоритми за претрагу федералног закона на обичном десктоп рачунару могли су да обрађују скупове података који садрже до 20 атрибута и десетине хиљада редова у року од неколико сати. Савремени алгоритми који раде на вишејезгарним процесорима откривају зависности за скупове података који се састоје од стотина атрибута (до 200) и стотина хиљада редова у приближно истом времену. Међутим, ово није довољно: такво време је неприхватљиво за већину апликација у стварном свету. Стога смо развили приступе за убрзање постојећих алгоритама.

Шеме кеширања за пресеке партиција

У првом делу рада развили смо шеме кеширања за класу алгоритама који користе метод пресека партиција. Партиција за атрибут је скуп листа, где свака листа садржи бројеве редова са истим вредностима за дати атрибут. Свака таква листа назива се кластер. Многи савремени алгоритми користе партиције да би утврдили да ли се зависност одржава или не, наиме, придржавају се леме: Зависност одржан ако . Ево означава се партиција и користи се концепт величине партиције – број кластера у њој. Алгоритми који користе партиције, када је зависност нарушена, додају додатне атрибуте на леву страну зависности, а затим је поново израчунавају, изводећи операцију пресека партиција. Ова операција се назива специјализација у чланцима. Али приметили смо да се партиције за зависности које би се задржале тек након неколико рунди специјализације могу активно поново користити, што може значајно смањити време рада алгоритама, пошто је операција укрштања скупа.

Стога смо предложили хеуристику засновану на Шенон Ентропији и Џини несигурности, као и нашој метрици, коју смо назвали Реверзна Ентропија. То је мала модификација Шенонове ентропије и повећава се како се повећава јединственост скупа података. Предложена хеуристика је следећа:

Овде — степен јединствености недавно израчунате партиције И је медијана степена јединствености за појединачне атрибуте. Све три горе описане метрике су тестиране као метрика јединствености. Такође можете приметити да постоје два модификатора у хеуристици. Први показује колико је тренутна партиција блиска примарном кључу и омогућава вам да у већој мери кеширате оне партиције које су далеко од потенцијалног кључа. Други модификатор вам омогућава да надгледате заузетост кеша и на тај начин подстиче додавање више партиција у кеш ако је слободан простор доступан. Успешно решење овог проблема нам је омогућило да убрзамо ПИРО алгоритам за 10-40%, у зависности од скупа података. Вреди напоменути да је ПИРО алгоритам најуспешнији у овој области.

На слици испод можете видети резултате примене предложене хеуристике у поређењу са основним приступом кеширања за бацање новчића. Кс оса је логаритамска.

Алтернативни начин складиштења партиција

Затим смо предложили алтернативни начин складиштења партиција. Партиције су скуп кластера, од којих сваки складишти бројеве торки са идентичним вредностима за одређене атрибуте. Ови кластери могу да садрже дуге низове бројева торки, на пример ако су подаци у табели поређани. Због тога смо предложили шему компресије за складиштење партиција, односно интервално складиштење вредности у кластерима партиција:

$$дисплаи$$пи(Кс) = {{подграда{1, 2, 3, 4, 5}_{Први интервал}, доња витица{7, 8}_{Други интервал}, 10}}\ доле{ компресија} \ пи(Кс) = {{подграда{$, 1, 5}_{први~интервал}, доња~интервал{7, 8}_{други~интервал}, 10}}$$приказ$$

Овај метод је успео да смањи потрошњу меморије током рада алгоритма ТАНЕ са 1 на 25%. ТАНЕ алгоритам је класичан алгоритам за тражење федералних закона током свог рада; Као део праксе изабран је ТАНЕ алгоритам, пошто је у њему било много лакше имплементирати интервално складиштење него, на пример, у ПИРО како би се проценило да ли предложени приступ функционише. Добијени резултати су приказани на доњој слици. Кс оса је логаритамска.

Конференција АДБИС-2019

На основу резултата истраживања, у септембру 2019. објавио сам чланак Паметно кеширање за ефикасно откривање функционалних зависности на 23. Европској конференцији о напретку у базама података и информационим системима (АДБИС-2019). Током презентације, рад је забележио Бернхард Тхалхеим, значајна личност у области база података. Резултати истраживања су чинили основу моје дисертације на мастер студијама математике и механике на Државном универзитету у Санкт Петербургу, током које су оба предложена приступа (кеширање и компресија) имплементирана у оба алгоритма: ТАНЕ и ПИРО. Штавише, резултати су показали да су предложени приступи универзални, будући да је на оба алгоритма, код оба приступа, уочено значајно смањење потрошње меморије, као и значајно смањење времена рада алгоритама.

Извор: ввв.хабр.цом