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

Намирането на функционални зависимости в данните се използва в различни области на анализ на данни: управление на база данни, почистване на данни, обратно инженерство на база данни и изследване на данни. За самите зависимости вече сме публикували Статия Анастасия Бирило и Никита Бобров. Този път Анастасия, възпитаник на Центъра по компютърни науки тази година, споделя развитието на тази работа като част от изследователската работа, която е защитила в центъра.

Избор на задача

Докато учех в 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}}$$показване$$

Този метод успя да намали консумацията на памет по време на работа на алгоритъма TANE от 1 до 25%. Алгоритъмът TANE е класически алгоритъм за търсене на федерални закони, той използва дялове по време на своята работа. Като част от практиката беше избран алгоритъмът TANE, тъй като беше много по-лесно да се приложи интервално съхранение в него, отколкото например в PYRO, за да се оцени дали предложеният подход работи. Получените резултати са представени на фигурата по-долу. Оста X е логаритмична.

Конференция ADBIS-2019

Въз основа на резултатите от изследването през септември 2019 г. публикувах статия Интелигентно кеширане за ефективно откриване на функционални зависимости на 23-та Европейска конференция за напредъка в базите данни и информационните системи (ADBIS-2019). По време на презентацията работата беше отбелязана от Бернхард Талхайм, значима личност в областта на базите данни. Резултатите от изследването бяха в основата на моята магистърска степен по математика и механика в Държавния университет в Санкт Петербург, по време на която и двата предложени подхода (кеширане и компресия) бяха внедрени в двата алгоритма: TANE и PYRO. Освен това резултатите показаха, че предложените подходи са универсални, тъй като и при двата алгоритъма и при двата подхода се наблюдава значително намаляване на потреблението на памет, както и значително намаляване на времето за работа на алгоритмите.

Източник: www.habr.com