Өгөгдөл дэх функциональ хамаарлыг олох нь өгөгдлийн шинжилгээний янз бүрийн салбарт ашиглагддаг: өгөгдлийн сангийн менежмент, өгөгдлийг цэвэрлэх, мэдээллийн сангийн урвуу инженерчлэл, өгөгдөл хайх. Бид хараат байдлын талаар аль хэдийн нийтэлсэн. Анастасия Бирилло, Никита Бобров нар. Энэ удаад Компьютерийн шинжлэх ухааны төвийн энэ жил төгсөгч Анастасия тус төвд хамгаалсан энэхүү судалгааны төслийнхөө хөгжлийг хуваалцаж байна.
Даалгаврын сонголт
Би CS төвд суралцаж байхдаа мэдээллийн санг гүнзгийрүүлэн судалж, ялангуяа функциональ болон дифференциал хамаарлыг хайж эхэлсэн. Энэ сэдэв миний их сургуулийн курсын ажилтай холбоотой байсан тул үүн дээр ажиллаж байхдаа мэдээллийн сан дахь янз бүрийн хамаарлын тухай нийтлэлүүдийг уншиж эхэлсэн. Би энэ талбарын талаар шүүмж бичсэн нь миний анхныхуудын нэг юм англи хэл дээр SEIM-2017 чуулганд өргөн мэдүүлсэн. Үүнийг хүлээж авснаар би маш их баярлаж, сэдвийг гүнзгийрүүлэхээр шийдсэн. Энэхүү үзэл баримтлал нь өөрөө шинэ зүйл биш - 90-ээд оноос хойш бий болсон боловч өнөөг хүртэл олон салбарт хэрэглээгээ олсоор байна.
Тус төвд хоёр дахь семестрт байхдаа би функциональ хамаарлыг олох алгоритмыг сайжруулах судалгааны төслийг эхлүүлсэн. Би JetBrains Research-ийн Санкт-Петербургийн их сургуулийн аспирант Никита Бобровтой үүн дээр ажилласан.
Функциональ хамаарлыг хайх тооцооллын нарийн төвөгтэй байдал
Гол асуудал бол тооцооллын нарийн төвөгтэй байдал юм. Боломжит хамгийн бага болон чухал бус хамаарлын тоог дээрээс нь хязгаарладаг 
хаана 
- хүснэгтийн шинж чанаруудын тоо. Алгоритмуудын ажиллах хугацаа нь зөвхөн шинж чанаруудын тооноос гадна мөрийн тооноос хамаарна. 90-ээд онд ердийн ширээний компьютер дээр холбооны хуулийг илрүүлэх алгоритмууд нь 20 хүртэлх шинж чанар, хэдэн арван мянган мөр агуулсан мэдээллийн багцыг хэдэн цагийн турш боловсруулж чаддаг байв. Олон цөмт процессорууд дээр ажилладаг орчин үеийн алгоритмууд нь ойролцоогоор ижил хугацаанд хэдэн зуун шинж чанар (200 хүртэл), хэдэн зуун мянган мөрнөөс бүрдэх өгөгдлийн багцын хамаарлыг илрүүлдэг. Гэсэн хэдий ч энэ нь хангалтгүй: ийм хугацаа нь ихэнх бодит хэрэглээний програмуудад хүлээн зөвшөөрөгдөхгүй. Тиймээс бид одоо байгаа алгоритмуудыг хурдасгах арга барилыг боловсруулсан.
Хуваалтын огтлолцлын кэшийн схемүүд
Ажлын эхний хэсэгт бид хуваалтын огтлолцлын аргыг ашиглан алгоритмын ангиллын кэшийн схемийг боловсруулсан. Атрибутын хуваалт нь жагсаалт бүр нь тухайн шинж чанарын хувьд ижил утгатай мөрийн дугааруудыг агуулсан жагсаалтуудын багц юм. Ийм жагсаалт бүрийг кластер гэж нэрлэдэг. Орчин үеийн олон алгоритмууд нь хамаарал байгаа эсэхийг тодорхойлохын тулд хуваалтуудыг ашигладаг, тухайлбал, дараах лемма-г баримталдаг. 
хадгалагдаж байгаа бол 
. Энд байна 
Хуваалтыг -р тэмдэглэж, хуваалтын хэмжээ буюу доторх кластеруудын тоо гэсэн ойлголтыг ашигладаг. Хуваалтуудыг ашигладаг алгоритмууд нь хамаарал зөрчигдсөн тохиолдолд хамаарлын зүүн талд нэмэлт шинж чанаруудыг нэмж, дараа нь хуваалтын огтлолцлын үйлдлийг гүйцэтгэх замаар дахин тооцоолно. Энэ үйл ажиллагааг нийтлэлд мэргэшүүлэх гэж нэрлэдэг. Гэсэн хэдий ч бид хэд хэдэн удаа мэргэшсэний дараа л хадгалагдах хамаарлын хуваалтыг идэвхтэйгээр дахин ашиглах боломжтой бөгөөд энэ нь огтлолцох ажиллагаа нь үнэтэй байдаг тул алгоритмын ажиллах хугацааг мэдэгдэхүйц бууруулж чадна гэдгийг бид тэмдэглэсэн.
Тиймээс бид Шенноны энтропи ба Жинигийн тодорхойгүй байдал дээр үндэслэсэн эвристикийг санал болгосны зэрэгцээ урвуу энтропи гэж нэрлэдэг өөрийн хэмжүүрийг санал болгосон. Энэ нь Шеннон энтропийн бага зэрэг өөрчлөлт бөгөөд өгөгдлийн багцын өвөрмөц байдал нэмэгдэх тусам нэмэгддэг. Санал болгож буй эвристик нь дараах байдалтай байна.
энд 
- саяхан тооцоолсон хуваалтын өвөрмөц байдлын зэрэг 
болон 
нь хувь хүний шинж чанаруудын өвөрмөц байдлын дундаж үзүүлэлт юм. Дээр дурдсан бүх гурван хэмжүүрийг өвөрмөц байдлын хэмжүүр болгон шалгасан. Түүнчлэн эвристик нь хоёр хувиргагчийг агуулдаг болохыг тэмдэглэж болно. Эхнийх нь одоогийн хуваалт нь үндсэн түлхүүртэй хэр ойрхон байгааг харуулж, нэр дэвшигчийн түлхүүрээс хол байгаа хуваалтыг илүү их кэш хийх боломжийг олгодог. Хоёрдахь хувиргагч нь кэшийн эзэлхүүнийг хянадаг бөгөөд ингэснээр зай байгаа үед кэшэд илүү олон хуваалтуудыг нэмэхийг дэмждэг. Энэ асуудлыг амжилттай шийдсэн нь PYRO алгоритмыг өгөгдлийн багцаас хамааран 10-40% хурдасгах боломжийг олгосон. PYRO алгоритм нь энэ чиглэлээр хамгийн амжилттай гэдгийг тэмдэглэх нь зүйтэй.
Доорх зураг нь зоос эргүүлэхэд суурилсан үндсэн кэш хийх аргатай харьцуулахад санал болгож буй эвристикийг хэрэглэсний үр дүнг харуулж байна. X тэнхлэг нь логарифм юм.
Хуваалтуудыг хадгалах өөр арга
Дараа нь бид хуваалтуудыг хадгалах өөр аргыг санал болгов. Хуваалтууд нь кластеруудын багц бөгөөд тэдгээр нь тус бүр нь тодорхой шинж чанаруудын хувьд ижил утгатай тоонуудыг хадгалдаг. Эдгээр кластерууд нь жишээлбэл, хүснэгтэд байгаа өгөгдлийг эрэмбэлсэн тохиолдолд урт дараалсан тоонуудыг агуулж болно. Тиймээс бид хуваалтуудыг хадгалах шахалтын схемийг санал болгов, тухайлбал хуваалтын кластер дахь утгыг интервалаар хадгалах.
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, {First, 5}in,{7} 8}_{Хоёр дахь~интервал}, 10}}$$дэлгэц$$
Энэ арга нь TANE алгоритмыг гүйцэтгэх явцад санах ойн зарцуулалтыг 1-25% бууруулах боломжтой болсон. TANE алгоритм нь логик бүсийг хайх сонгодог алгоритм юм; энэ нь үйл ажиллагааны явцад хуваалтуудыг ашигладаг. Практик зорилгоор TANE алгоритмыг сонгосон, учир нь интервалын хадгалалтыг хэрэгжүүлэх нь жишээлбэл, санал болгож буй аргын боломжит байдлыг үнэлэхийн тулд PYRO-ээс хамаагүй хялбар байсан. Үр дүнг доорх зурагт үзүүлэв. X тэнхлэг нь логарифм юм.
ADBIS-2019 бага хурал
Судалгааны үр дүнд үндэслэн би 2019 оны 9-р сард нийтлэл хэвлүүлсэн. Мэдээллийн сан ба мэдээллийн системийн дэвшлийн тухай Европын 23 дугаар бага хуралд (ADBIS-2019) уг ажлыг мэдээллийн сангийн салбарын нэрт зүтгэлтэн Бернхард Тальхайм үнэлэв. Судалгааны үр дүн нь Санкт-Петербургийн Улсын Их Сургуулийн Математик, Механикийн факультетэд магистрын зэрэг олгох диссертацийн ажлын үндэс болсон бөгөөд энэ хугацаанд санал болгож буй аргуудыг (кэш ба шахалт) TANE болон PYRO алгоритмын аль алинд нь хэрэгжүүлсэн. Үр дүн нь санал болгож буй аргууд нь бүх нийтийнх болохыг харуулж байна, учир нь аль алиных нь алгоритмууд санах ойн хэрэглээг мэдэгдэхүйц бууруулж, гүйцэтгэх хугацааг мэдэгдэхүйц бууруулж байгааг харуулсан.
Эх сурвалж: www.habr.com
