Ҷустуҷӯи вобастагии функсионалии додаҳо дар соҳаҳои гуногуни таҳлили додаҳо истифода мешавад: идоракунии пойгоҳи додаҳо, тозакунии додаҳо, муҳандисии баръакси пойгоҳи додаҳо ва таҳқиқоти додаҳо. Мо аллакай дар бораи вобастагӣ нашр кардаем Анастасия Бирилло ва Никита Бобров. Ин дафъа, Анастасия, хатмкардаи Маркази илмҳои компютерии имсола, таҳияи ин корро ҳамчун як қисми корҳои тадқиқотие, ки дар марказ дифоъ кардааст, мубодила мекунад.
Интихоби вазифа
Ҳангоми таҳсил дар маркази CS, ман ба омӯзиши амиқи пойгоҳи додаҳо, яъне ҷустуҷӯи вобастагии функсионалӣ ва фарқият шурӯъ кардам. Ин мавзӯъ ба мавзӯи кори курсии ман дар донишгоҳ алоқаманд буд, аз ин рӯ ҳангоми кор дар болои кори курсӣ ман ба хондани мақолаҳо дар бораи вобастагии гуногун дар пойгоҳи додаҳо шурӯъ кардам. Ман як баррасии ин соҳа навиштам - яке аз аввалини ман инглисӣ ва ба конфронси SEIM-2017 пешниҳод намуд. Вақте ки ман фаҳмидам, ки ӯро қабул кардаанд, хеле шод шудам ва тасмим гирифтам, ки ба мавзӯъ амиқтар омӯзам. Худи консепсия нав нест - он дар солҳои 90-ум истифода мешуд, аммо ҳоло ҳам дар бисёр соҳаҳо истифода мешавад.
Дар давоми семестри дуюми худ дар марказ ман як лоиҳаи тадқиқотиро барои такмил додани алгоритмҳо барои дарёфти вобастагии функсионалӣ оғоз кардам. Вай дар болои он якҷоя бо аспиранти Донишгоҳи давлатии Санкт-Петербург Никита Бобров дар JetBrains Research кор кардааст.
Мушкилии ҳисоббарории ҷустуҷӯи вобастагии функсионалӣ
Мушкилоти асосӣ ин мураккабии ҳисоббарорӣ мебошад. Миқдори вобастагии ҳадди ақал ва ғайритиҷоратӣ дар боло аз рӯи арзиш маҳдуд аст ки дар - шумораи атрибутҳои ҷадвал. Мӯҳлати кори алгоритмҳо на танҳо аз шумораи атрибутҳо, балки аз шумораи сатрҳо низ вобаста аст. Дар солҳои 90-ум, алгоритмҳои ҷустуҷӯи қонуни федералӣ дар компютери муқаррарии мизи корӣ метавонанд маҷмӯи додаҳои дорои то 20 атрибут ва даҳҳо ҳазор сатрро дар тӯли то чанд соат коркард кунанд. Алгоритмҳои муосир, ки дар протсессори бисёраслӣ кор мекунанд, вобастагии маҷмӯи додаҳоро, ки аз садҳо атрибутҳо (то 200) ва садҳо ҳазор сатрҳо иборатанд, дар як вақт муайян мекунанд. Аммо, ин кофӣ нест: чунин вақт барои аксари барномаҳои воқеии ҷаҳон қобили қабул нест. Аз ин рӯ, мо равишҳоро барои суръат бахшидан ба алгоритмҳои мавҷуда таҳия кардем.
Схемаи кэш барои чорроҳаҳои тақсимот
Дар қисми аввали кор, мо схемаҳои кэшро барои як синфи алгоритмҳо таҳия кардем, ки усули буридани қисмҳоро истифода мебаранд. Қисм барои атрибут маҷмӯи рӯйхатҳо мебошад, ки дар он ҳар як рӯйхат рақамҳои сатрро бо арзишҳои якхела барои атрибути додашуда дар бар мегирад. Ҳар як чунин рӯйхат кластер номида мешавад. Бисёр алгоритмҳои муосир қисмҳоро барои муайян кардани он, ки вобастагӣ нигоҳ дошта мешавад ё не, истифода мебаранд, яъне онҳо ба лемма риоя мекунанд: Вобастагӣ баргузор мешавад, агар . Дар ин ҷо бахш таъин карда мешавад ва мафҳуми андозаи тақсимот истифода мешавад - шумораи кластерҳо дар он. Алгоритмҳое, ки қисмҳоро истифода мебаранд, ҳангоми вайрон шудани вобастагӣ ба тарафи чапи вобастагӣ атрибутҳои иловагиро илова мекунанд ва сипас онро аз нав ҳисоб карда, амали буриши қисмҳоро иҷро мекунанд. Ин амалиёт дар мақолаҳо тахассус номида мешавад. Аммо мо мушоҳида кардем, ки қисмҳои вобастагӣ, ки танҳо пас аз чанд даври тахассус нигоҳ дошта мешаванд, метавонанд фаъолона дубора истифода шаванд, ки ин метавонад вақти кори алгоритмҳоро ба таври назаррас коҳиш диҳад, зеро амалиёти буриш гарон аст.
Аз ин рӯ, мо эвристикаеро дар асоси Энтропияи Шеннон ва Номаи Ҷинни ва инчунин метрикаи худро пешниҳод кардем, ки мо онро Энтропияи баръакс меномидем. Ин як тағироти ночизи Энтропияи Шеннон аст ва бо афзоиши беназири маҷмӯи додаҳо меафзояд. Эвристикаи пешниҳодшуда чунин аст:
Ин аст, — дараҷаи беҳамтоии қисмати ба наздикӣ ҳисобшуда ва миёнаравӣ дараҷаҳои нотакрорӣ барои сифатҳои инфиродӣ мебошад. Ҳар се ченакҳои дар боло тавсифшуда ҳамчун ченаки беназир санҷида шуданд. Шумо инчунин метавонед аҳамият диҳед, ки дар эвристика ду тағирдиҳанда мавҷуд аст. Якум нишон медиҳад, ки қисмати ҷорӣ ба калиди ибтидоӣ то чӣ андоза наздик аст ва ба шумо имкон медиҳад, ки он қисматҳоеро, ки аз калиди эҳтимолӣ дуранд, то андозае кэш кунед. Тағирдиҳандаи дуюм ба шумо имкон медиҳад, ки ишғоли кэшро назорат кунед ва ба ин васила илова кардани қисмҳои бештар ба кэшро ташвиқ мекунад, агар фазои холӣ мавҷуд бошад. Ҳалли бомуваффақияти ин масъала ба мо имкон дод, ки алгоритми PYRO вобаста ба маҷмӯи додаҳо 10-40% суръат бахшем. Қобили зикр аст, ки алгоритми PYRO дар ин соҳа муваффақтарин аст.
Дар расми зер шумо метавонед натиҷаҳои татбиқи эвристикаи пешниҳодшударо дар муқоиса бо равиши асосии кэшкунии танга бинед. Меҳвари X логарифмикӣ аст.
Роҳи алтернативии нигоҳдории қисмҳо
Сипас мо роҳи алтернативии нигоҳдории қисмҳоро пешниҳод кардем. Қисмҳо маҷмӯи кластерҳо мебошанд, ки ҳар яки онҳо ададҳои наворҳоро бо арзишҳои якхела барои атрибутҳои муайян нигоҳ медоранд. Ин кластерҳо метавонанд пайдарпайии тӯлонии рақамҳои корбарро дар бар гиранд, масалан, агар маълумот дар ҷадвал тартиб дода шуда бошад. Аз ин рӯ, мо нақшаи фишурдасозиро барои нигоҳдории қисмҳо, яъне нигоҳдории фосилавии арзишҳо дар кластерҳои қисмҳо пешниҳод кардем:
$$дисплей$$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 амалӣ карда шуданд. Ғайр аз он, натиҷаҳо нишон доданд, ки равишҳои пешниҳодшуда универсалӣ мебошанд, зеро дар ҳарду алгоритм бо ҳарду равиш, коҳиши назарраси истеъмоли хотира ва инчунин коҳиши назарраси вақти кори алгоритмҳо мушоҳида шудааст.
Манбаъ: will.com