Наоѓањето функционални зависности во податоците се користи во различни области на анализа на податоци: управување со бази на податоци, чистење на податоци, обратно инженерство на бази на податоци и истражување на податоци. За самите зависности веќе објавивме Анастасија Бирило и Никита Бобров. Овој пат, Анастасија, дипломирана на овогодинешниот Центар за компјутерски науки, го споделува развојот на оваа работа како дел од истражувачката работа што таа ја бранеше во центарот.
Избор на задача
Додека студирав во CS центарот, почнав длабински да ги проучувам базите на податоци, имено, потрагата по функционални и различни зависности. Оваа тема беше поврзана со темата на моите предмети на универзитетот, па додека работев на предметите, почнав да читам написи за различни зависности во базите на податоци. Напишав преглед на оваа област - еден од моите први на англиски јазик и го достави на конференцијата SEIM-2017. Бев многу среќен кога дознав дека сепак е прифатена и решив да навлезам подлабоко во темата. Самиот концепт не е нов - почна да се користи уште во 90-тите, но дури и сега се користи во многу области.
За време на мојот втор семестар во центарот, започнав истражувачки проект за подобрување на алгоритмите за наоѓање функционални зависности. Таа работеше на тоа заедно со дипломираниот студент на Државниот универзитет во Санкт Петербург Никита Бобров во JetBrains Research.
Пресметувачка сложеност на пребарувањето за функционални зависности
Главниот проблем е комплексноста на компјутерите. Бројот на можни минимални и нетривијални зависности е ограничен погоре со вредноста 
каде 
— број на атрибути на табелата. Времето на работа на алгоритмите не зависи само од бројот на атрибути, туку и од бројот на редови. Во 90-тите, алгоритмите за пребарување на федералните закони на обичен десктоп компјутер можеа да обработуваат множества на податоци што содржат до 20 атрибути и десетици илјади редови до неколку часа. Современите алгоритми кои работат на процесори со повеќе јадра детектираат зависност за множества на податоци што се состојат од стотици атрибути (до 200) и стотици илјади редови во приближно исто време. Сепак, ова не е доволно: таквото време е неприфатливо за повеќето апликации од реалниот свет. Затоа, развивме пристапи за забрзување на постоечките алгоритми.
Кеширање шеми за пресеци на партиции
Во првиот дел од работата, развивме шеми за кеширање за класа на алгоритми кои користат метод на пресек на партиции. Партиција за атрибут е збир на списоци, каде што секоја листа содржи броеви на линии со исти вредности за даден атрибут. Секоја таква листа се нарекува кластер. Многу современи алгоритми користат партиции за да утврдат дали постои зависност или не, имено, тие се придржуваат до лемата: Зависност 
одржана доколку 
. Еве 
се означува партиција и се користи концептот за големина на партицијата - бројот на кластери во неа. Алгоритмите кои користат партиции, кога зависноста е нарушена, додаваат дополнителни атрибути на левата страна на зависноста, а потоа ја пресметуваат повторно, извршувајќи ја операцијата на пресек на партиции. Оваа операција се нарекува специјализација во статиите. Но, забележавме дека партициите за зависности кои би се задржале само по неколку рунди специјализација може активно да се користат, што може значително да го намали времето на работа на алгоритмите, бидејќи операцијата на вкрстување е скапа.
Затоа, предложивме хеуристика заснована на Шенонова ентропија и Џини несигурност, како и нашата метрика, која ја нарековме обратна ентропија. Тоа е мала модификација на ентропијата на Шенон и се зголемува како што се зголемува уникатноста на множеството податоци. Предложената хеуристика е како што следува:
Тука 
— степен на уникатност на неодамна пресметаната партиција 
И 
е медијана на степените на уникатност за поединечни атрибути. Сите три метрики опишани погоре беа тестирани како метрика за уникатност. Можете исто така да забележите дека има два модификатори во хеуристиката. Првата означува колку тековната партиција е блиску до примарниот клуч и ви овозможува да ги кеширате во поголема мера оние партиции кои се далеку од потенцијалниот клуч. Вториот модификатор ви овозможува да ја следите зафатеноста на кешот и на тој начин поттикнува додавање на повеќе партиции во кешот доколку има слободен простор. Успешното решение на овој проблем ни овозможи да го забрзаме алгоритмот PYRO за 10-40%, во зависност од базата на податоци. Вреди да се напомене дека алгоритмот PYRO е најуспешен во оваа област.
На сликата подолу можете да ги видите резултатите од примената на предложената хеуристика во споредба со основниот пристап за кеширање со превртување на монети. Оската X е логаритамска.
Алтернативен начин за складирање на партиции
Потоа предложивме алтернативен начин за складирање на партиции. Партициите се збир на кластери, од кои секоја складира бројни торки со идентични вредности за одредени атрибути. Овие кластери може да содржат долги секвенци од тократни броеви, на пример ако податоците во табела се подредени. Затоа, предложивме шема за компресија за складирање на партиции, имено интервално складирање на вредности во кластери на партиции:
$$display$$pi(X) = {{подграда{1, 2, 3, 4, 5}_{Прв интервал}, подзаград{7, 8}_{Втор интервал}, 10}}\ надолу{ Компресија} \ pi(X) = {{подграда{$, 1, 5}_{Прв~интервал}, подзаград{7, 8}_{Втор~интервал}, 10}}$$display$$
Овој метод успеа да ја намали потрошувачката на меморија за време на работата на алгоритмот TANE од 1 до 25%. Алгоритмот TANE е класичен алгоритам за пребарување на федерални закони што користи партиции за време на својата работа. Како дел од практиката, беше избран алгоритмот TANE, бидејќи беше многу полесно да се имплементира интервално складирање во него отколку, на пример, во PYRO за да се оцени дали предложениот пристап функционира. Добиените резултати се претставени на сликата подолу. Оската X е логаритамска.
Конференција АДБИС-2019
Врз основа на резултатите од истражувањето, во септември 2019 година објавив статија на 23-та Европска конференција за напредок во базите на податоци и информациските системи (ADBIS-2019). За време на презентацијата, работата ја забележа Бернхард Талхајм, значајна личност во областа на базите на податоци. Резултатите од истражувањето ја формираа основата на мојата дисертација на магистерски студии по математика и механика на Државниот универзитет во Санкт Петербург, при што двата предложени пристапи (кеширање и компресија) беа имплементирани во двата алгоритми: TANE и PYRO. Дополнително, резултатите покажаа дека предложените пристапи се универзални, бидејќи и на двата алгоритми, со двата пристапа, забележано е значително намалување на потрошувачката на меморија, како и значително намалување на времето на работа на алгоритмите.
Извор: www.habr.com
