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