Дерекқорлардағы функционалдық тәуелділіктерді тиімді табыңыз

Деректердегі функционалдық тәуелділіктерді табу деректерді талдаудың әртүрлі салаларында қолданылады: дерекқорды басқару, деректерді тазалау, дерекқорды кері инженериялау және деректерді зерттеу. Біз тәуелділіктердің өздері туралы жариялаған болатынбыз мақала Анастасия Бирильо және Никита Бобров. Бұл жолы Информатика орталығының биылғы түлегі Анастасия орталықта қорғаған ғылыми-зерттеу жұмысының бір бөлігі ретінде осы жұмыстың дамуымен бөліседі.

Тапсырманы таңдау

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 жылдың қыркүйегінде мен мақала жарияладым Функционалды тәуелділікті тиімді табуға арналған Smart кэштеу Дерекқорлар мен ақпараттық жүйелердегі жетістіктер бойынша 23-еуропалық конференцияда (ADBIS-2019). Тұсаукесер барысында жұмысты деректер базасы саласындағы елеулі тұлға Бернхард Тальхайм атап өтті. Зерттеу нәтижелері менің Санкт-Петербург мемлекеттік университетінің математика және механика магистрі дәрежесіндегі диссертациясының негізі болды, оның барысында ұсынылған екі тәсіл де (кэштеу және қысу) екі алгоритмде де жүзеге асырылды: TANE және PYRO. Сонымен бірге, нәтижелер ұсынылған тәсілдер әмбебап екенін көрсетті, өйткені екі алгоритмде де екі тәсілмен де жадты тұтынудың айтарлықтай төмендеуі, сонымен қатар алгоритмдердің жұмыс уақытының айтарлықтай қысқаруы байқалды.

Ақпарат көзі: www.habr.com