Берилиштердеги функционалдык көз карандылыктарды табуу маалыматтарды талдоонун ар кандай чөйрөлөрүндө колдонулат: маалыматтар базасын башкаруу, маалыматтарды тазалоо, маалымат базасын тескери инженериялоо жана маалыматтарды изилдөө. Биз буга чейин көз карандылыктын өзү жөнүндө жарыялаганбыз Анастасия Бирилло жана Никита Бобров. Бул жолу, Анастасия, быйылкы Информатика борборунун бүтүрүүчүсү, борбордо коргогон илимий ишинин алкагында бул иштин өнүгүшү менен бөлүшөт.
Тапшырма тандоо
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. Ошол эле учурда жыйынтыктар сунушталган ыкмалар универсалдуу экенин көрсөттү, анткени эки алгоритмде тең эки ыкмада тең эстутум керектөөнүн олуттуу кыскарышы, ошондой эле алгоритмдердин иштөө убактысынын олуттуу кыскарышы байкалган.
Source: www.habr.com
