Пошук функцыянальных залежнасцяў у дадзеных ужываецца ў розных кірунках аналізу дадзеных: кіраванне базамі дадзеных, ачыстка дадзеных, рэверс-інжынірынг баз дадзеных і экспларацыя дадзеных. Пра самі залежнасці мы ўжо публікавалі Анастасіі Бірыла і Мікіты Баброва. У гэты раз Анастасія – выпускніца Computer Science Center гэтага года – дзеліцца развіццём гэтай працы ў рамках НДР, якую яна абараніла ў цэнтры.
выбар задачы
Падчас навучання ў CS цэнтры я пачала паглыблена вывучаць базы дадзеных, а менавіта пошук функцыянальных і рознасных залежнасцяў. Гэтая тэма была звязана з тэмай маёй курсавой ва ўніверсітэце, так што падчас працы над курсавой я пачала чытаць артыкулы пра розныя залежнасці ў базах дадзеных. Я напісала агляд гэтай галіне - адну з першых сваіх. на англійскай мове і падала яе на канферэнцыю SEIM-2017. Я была вельмі рада, калі даведалася, што яе ўсё ж прынялі, і вырашыла паглыбіцца ў тэму. Сама канцэпцыя не новая - яе пачалі ўжываць яшчэ ў 90х гадах, але і цяпер яна знаходзіць прымяненне ў многіх галінах.
У другім семестры навучання ў цэнтры я пачала навукова-даследчы праект па паляпшэнні алгарытмаў пошуку функцыянальных залежнасцяў. Працавала над ім разам з аспірантам СПбДУ Мікітам Бабровым на базе JetBrains Research.
Вылічальная працаёмкасць пошуку функцыянальных залежнасцяў
Асноўная праблема - вылічальная працаёмкасць. Лік магчымых мінімальных і нетрывіяльных залежнасцяў абмежавана зверху значэннем , Дзе - Лік атрыбутаў табліцы. Час працы алгарытмаў залежыць не толькі ад колькасці атрыбутаў, але і ад колькасці радкоў. У 90-х гадах алгарытмы па пошуку ФЗ на звычайным настольным ПК маглі апрацоўваць наборы дадзеных, якія змяшчаюць да 20 атрыбутаў і дзясяткі тысяч радкоў, да некалькіх гадзін. Сучасныя алгарытмы, якія працуюць на шмат'ядравых працэсарах, выяўляюць залежнасці для набораў дадзеных, якія складаюцца з сотняў атрыбутаў (да 200) і сотняў тысяч радкоў, прыкладна за той жа час. Тым не менш гэтага недастаткова: такі час непрымальны для большасці рэальных дадаткаў. Таму мы распрацоўвалі падыходы для паскарэння існуючых алгарытмаў.
Схемы кэшавання для перасячэння партыцый
У першай частцы працы мы распрацавалі схемы кэшавання для класа алгарытмаў, якія выкарыстоўваюць метад перасячэння партыцый. Партыцыя для атрыбута ўяўляе сабой набор спісаў, дзе кожны спіс утрымоўвае нумары радкоў з аднолькавымі значэннямі для дадзенага атрыбута. Кожны такі спіс называецца кластар. Многія сучасныя алгарытмы выкарыстоўваюць партыцыі для вызначэння, утрымліваецца залежнасць ці не, а менавіта прытрымліваюцца лемы: Залежнасць утрымліваецца, калі . Тут пазначаецца партыцыя і выкарыстоўваецца паняцце памер партіціі - колькасць кластараў у ёй. Алгарытмы, якія выкарыстоўваюць партіціі, пры парушэнні залежнасці дадаюць дадатковыя атрыбуты ў левую частку залежнасці, пасля чаго пералічваюць яе, вырабляючы аперацыю скрыжавання партыцый. Такая аперацыя ў артыкулах называецца спецыялізацыяй. Але мы заўважылі, што партыцыі для залежнасцяў, якія будуць утрыманыя толькі пасля некалькіх раўндаў спецыялізацыі, могуць быць актыўна перавыкарыстаны, што можа істотна скараціць час працы алгарытмаў, бо аперацыя скрыжавання з'яўляецца дарогай.
Таму мы прапанавалі эўрыстыку, заснаваную на Энтрапіі Шэнана і нявызначанасці Джыні, а таксама нашай метрыцы, якую мы назвалі Зваротная Энтрапія. Яна з'яўляецца нязначнай мадыфікацыяй Энтрапіі Шэнана і расце па меры таго, як расце унікальнасць набору дадзеных. Прапанаваная эўрыстыка выглядае наступным чынам:
Тут - ступень унікальнасці нядаўна вылічанай партіціі , А з'яўляецца медыянай ступеняў унікальнасці для асобных атрыбутаў. У якасці метрыкі ўнікальнасці былі апрабаваны ўсе тры метрыкі, апісаныя вышэй. Таксама можна заўважыць, што ў эўрыстыкі прысутнічаюць два мадыфікатара. Першы паказвае, наколькі блізкая бягучая партыцыя да першаснага ключа і дазваляе ў большай ступені кэшаваць тыя партіціі, якія далёкія ад патэнцыйнага ключа. Другі мадыфікатар дазваляе адсочваць занятасць кэша і тым самым стымулюе даданне большай колькасці партыцый у кэш пры наяўнасці вольнага месца. Паспяховае рашэнне гэтай задачы дазволіла паскорыць алгарытм PYRO на 10-40% працэнтаў у залежнасці ад датасета. Варта адзначыць, што алгарытм PYRO з'яўляецца найболей паспяховым у гэтай вобласці.
На малюнку ніжэй можна ўбачыць вынікі прымянення прапанаванай эўрыстыкі ў параўнанні з базавым падыходам па кэшаванні, заснаваным на падкідванні манеткі. Вось X лагарыфмічная.
Альтэрнатыўны спосаб захоўвання партыцый
Потым мы прапанавалі альтэрнатыўны спосаб захоўвання партыцый. Партыцыі ўяўляюць сабой набор кластараў, у кожным з якіх захоўваюцца нумары картэжаў з аднолькавымі значэннямі па пэўных атрыбутах. Гэтыя кластары могуць утрымоўваць доўгія паслядоўнасці нумароў картэжаў, напрыклад, калі ў табліцы дадзеныя спарадкаваны. Таму мы прапанавалі схему сціску для захоўвання партыцый, а менавіта інтэрвальнае захоўванне значэнняў у кластарах партыцый:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Першы~інтэрвал}, underbrace{7, 8}_{Другі~інтэрвал}, 10}}\ downarrow{ Сціск}\ pi(X) = {{underbrace{$, 1, 5}_{Першы~інтэрвал}, underbrace{7, 8}_{Другі~інтэрвал}, 10}}$$display$$
Гэты метад змог скараціць спажыванне памяці падчас працы алгарытму TANE ад 1 да 25%. Алгарытм TANE - класічны алгарытм па пошуку ФЗ, ён выкарыстоўвае партіціі падчас сваёй працы. У рамках практыкі быў абраны менавіта алгарытм TANE, бо ўкараніць у яго інтэрвальнае захоўванне было значна прасцей, чым, напрыклад, у PYRO, каб ацаніць, ці працуе прапанаваны падыход. Атрыманыя вынікі прадстаўлены на малюнку ніжэй. Вось X лагарыфмічная.
Канферэнцыя ADBIS-2019
Па выніках даследавання ў верасні 2019 года я выступіла з артыкулам на канферэнцыі 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). У час выступлення работу адзначыў Bernhard Thalheim, значны чалавек у галіне баз даных. Вынікі даследаванняў леглі ў аснову маёй дысертацыі ў магістратуры мат-меха СПбГУ, падчас якой абодва прапанаваныя падыходы (кэшаванне і сціск) былі ўкаранёны ў абодва алгарытму: TANE і PYRO. Пры гэтым вынікі паказалі, што прапанаваныя падыходы з'яўляюцца ўніверсальнымі, бо на абодвух алгарытмах пры абодвух падыходах назіралася значнае скарачэнне спажыванай памяці, а таксама значнае скарачэнне часу працы алгарытмаў.
Крыніца: habr.com