Dîtina girêdanên fonksiyonel ên di daneyê de di warên cihêreng ên analîzkirina daneyê de tê bikar anîn: rêveberiya databasê, paqijkirina daneyê, endezyariya berevajî ya databasê û lêgerîna daneyê. Me berê jî li ser girêbestan belav kiriye Anastasia Birillo û Nikita Bobrov. Vê carê, Anastasia, mezûna Navenda Zanistiya Kompîturê ya îsal, pêşveçûna vê xebatê wekî beşek ji xebata lêkolînê ya ku li navendê parastibû parve dike.
Hilbijartina peywirê
Dema ku li navenda CS-ê dixwend, min dest bi lêkolîna databasan bi kûrahî kir, ango, lêgerîna girêdanên fonksiyonel û cûdahiyê. Ev mijar bi mijara qursa min a li zanîngehê ve girêdayî bû, ji ber vê yekê dema ku li ser qursê dixebitim, min dest bi xwendina gotarên li ser cûrbecûr girêdayîbûnên di databasan de kir. Min nirxandinek li ser vê deverê nivîsand - yek ji yekemên min bi Îngilîzî û pêşkêşî konferansa SEIM-2017 kir. Ez pir kêfxweş bûm gava ku min fêr kir ku ew piştî her tiştî hate pejirandin, û biryar da ku ez di mijarê de kûrtir bigerim. Têgîn bi xwe ne nû ye - ew di salên 90-an de dest pê kir ku were bikar anîn, lê heya niha jî ew di gelek deveran de tê bikar anîn.
Di nîvsala xweya duyemîn de li navendê, min dest bi projeyek lêkolînê kir da ku algorîtmayan ji bo dîtina girêdanên fonksiyonel baştir bike. Wê bi xwendekara mezûn a Zanîngeha Dewletê ya St.
Tevliheviya hesabkirinê ya lêgerîna girêdanên fonksiyonel
Pirsgirêka sereke tevliheviya hesabkirinê ye. Hejmara pêwendiyên hindiktirîn û ne-pîvan ên gengaz li jor ji hêla nirxê ve sînorkirî ye 
ko 
- hejmara taybetmendiyên tabloyê. Dema xebitandina algorîtmayan ne tenê bi hejmara taybetmendiyan, lê bi hejmara rêzan jî ve girêdayî ye. Di salên 90-an de, algorîtmayên lêgerîna qanûna federal li ser PC-ya sermaseya birêkûpêk dikaribû di çend demjimêran de berhevokên daneyê yên ku heya 20 taybetmendî û bi deh hezaran rêzan vedihewîne pêvajoyê bikin. Algorîtmayên nûjen ên ku li ser pêvajoyên pir-bingehîn têne xebitandin ji bo komikên daneyê yên ku ji sedan taybetmendî (heta 200) û bi sed hezaran rêzikan pêk tên di hema hema heman demê de ve girêdayî tespît dikin. Lêbelê, ev ne bes e: demek wusa ji bo piraniya serîlêdanên cîhana rastîn nayê pejirandin. Ji ber vê yekê, me nêzîkatiyên ji bo bilezkirina algorîtmayên heyî pêşxist.
Planên caching ji bo xaçerêyên dabeşkirinê
Di beşa yekem a xebatê de, me ji bo çînek algorîtmayan ku rêbaza dabeşkirina dabeşkirinê bikar tînin, nexşeyên caching pêşve xistin. Parvekirinek ji bo taybetmendiyek komek navnîşan e, ku her navnîş ji bo taybetmendiyek diyar hejmarên rêzê bi heman nirxan vedihewîne. Ji her navnîşek weha re komek tê gotin. Gelek algorîtmayên nûjen dabeşan bikar tînin da ku diyar bikin ka pêwendiyek tê girtin an na, ango, ew bi lemmayê ve girêdayî ne: Girîng 
pêk hat eger 
. Vir 
dabeşek tê destnîşan kirin û têgeha mezinahiya dabeşkirinê tê bikar anîn - hejmara komikên tê de. Algorîtmayên ku dabeşan bikar tînin, dema ku girêdayîbûn tê binpêkirin, taybetmendiyên din li milê çepê yê girêdayîbûnê zêde dikin, û dûv re wê ji nû ve hesab dikin, operasyona hevberdana dabeşan pêk tînin. Ji vê operasyonê re di gotaran de pisporî tê gotin. Lê me dît ku dabeşên ji bo girêdanên ku dê tenê piştî çend gerokên pisporbûnê werin hilanîn dikarin bi rengek çalak ji nû ve werin bikar anîn, ku dikare dema xebitandina algorîtmayan bi girîngî kêm bike, ji ber ku operasyona hevberdanê biha ye.
Ji ber vê yekê, me li ser bingeha Shannon Entropy û Ginny Uncertainty, û hem jî metrîka xwe, ku me jê re digot Entropya Berevajî, heurîstîkek pêşniyar kir. Ew guheztinek sivik a Shannon Entropy ye û her ku taybetmendiya berhevoka daneyê zêde dibe zêde dibe. Heurîstîkî ya pêşniyarkirî wiha ye:
Ev e 
- asta bêhempabûna dabeşkirina vê dawîyê ya hesabkirî 
û 
navgîniya dereceyên bêhempabûna taybetmendiyên kesane ye. Her sê metrîkên ku li jor hatine destnîşan kirin wekî metrîka bêhempa hatine ceribandin. Her weha hûn dikarin bala xwe bidin ku di heuristic de du guhêrbar hene. Ya yekem destnîşan dike ku dabeşkirina heyî çiqasî nêzî mifteya bingehîn e û dihêle hûn bi rêjeyek mezintir wan dabeşên ku ji mifteya potansiyel dûr in cache bikin. Guherkera duyemîn destûrê dide te ku çavdêriya dagirkirina cache-ê bike û bi vî rengî teşwîq dike ku heke cîhê belaş hebe bêtir dabeşan li cache zêde bike. Çareseriya serketî ya vê pirsgirêkê hişt ku em algorîtmaya PYRO% 10-40% li gorî databasê bilez bikin. Hêjayî gotinê ye ku di vî warî de algorîtmaya PYRO ya herî serkeftî ye.
Di jimareya jêrîn de hûn dikarin encamên sepandina heurîstîkê ya pêşniyarkirî li gorî nêzîkatiyek bingehîn a cachkirina coin-flip bibînin. Eksê X logarîtmîk e.
Rêyek alternatîf ji bo hilanîna dabeşan
Dûv re me rêyek alternatîf ji bo hilanîna dabeşan pêşniyar kir. Dabeş komek koman in, ku her yek ji wan ji bo hin taybetmendiyan jimareyên tîrêjan bi nirxên wekhev diparêze. Dibe ku di van koman de rêzikên dirêj ên hejmarên pirjimar hebin, mînakî heke daneyên di tabloyekê de hatine rêz kirin. Ji ber vê yekê, me ji bo hilanîna dabeşan nexşeyek berhevkirinê, ango hilanîna navberê ya nirxan di komên dabeşan de pêşniyar kir:
$$display$$pi(X) = {{binavber{1, 2, 3, 4, 5}_{navbera yekem}, binerd{7, 8}_{navbera duyemîn}, 10}}\ xwar{1} \ pi(X) = {{binavbera{$, 5, 7}_{Yekemîn~navber}, binavber{8, 10}_{Navenda~duyemîn}, XNUMX}}$$display$$
Vê rêbazê di dema xebitandina algorîtmaya TANE de ji 1 heta 25% bikar anîna bîranînê kêm bike. Algorîtmaya TANE ji bo lêgerîna qanûnên federal algorîtmayek klasîk e ku di dema xebata xwe de dabeşan bikar tîne. Wekî beşek ji pratîkê, algorîtmaya TANE hate hilbijartin, ji ber ku pêkanîna hilanîna navberê di wê de ji, mînakî, li PYRO-yê pir hêsantir bû da ku binirxîne ka nêzîkatiya pêşniyarkirî dixebite. Encamên ku hatine bidestxistin di wêneya jêrîn de têne pêşkêş kirin. Eksê X logarîtmîk e.
Konferansa ADBIS-2019
Li ser bingeha encamên lêkolînê, di îlona 2019 de min gotarek weşand di 23. Konferansa Ewropî ya li ser Pêşkeftinên Di Database û Pergalên Agahdariyê de (ADBIS-2019). Di dema pêşkêşiyê de, xebat ji hêla Bernhard Thalheim, kesek girîng di warê databasan de hate destnîşan kirin. Encamên lêkolînê bingehê teza min li ser lîsansa matematîk û mekanîkê li Zanîngeha Dewletê ya St. Digel vê yekê, encaman destnîşan kir ku nêzîkatiyên pêşniyarkirî gerdûnî ne, ji ber ku li ser her du algorîtmayan, bi her du nêzîkatiyan re, kêmbûnek girîng di xerckirina bîranînê de, û her weha kêmbûnek girîng di dema xebitandina algorîtmayan de hate dîtin.
Source: www.habr.com
