Trovi funkciajn dependecojn en datumoj estas uzata en diversaj areoj de datuma analizo: datumbaza administrado, datumpurigado, datumbaza inversa inĝenierado kaj datumesplorado. Ni jam publikigis pri la dependecoj mem Anastasia Birillo kaj Nikita Bobrov. Ĉi-foje, Anastazio, diplomiĝinto de la ĉi-jara Komputika Centro, dividas la evoluon de ĉi tiu laboro kiel parto de la esplorlaboro, kiun ŝi defendis en la centro.
Elekto de taskoj
Studante en la CS-centro, mi komencis profunde studi datumbazojn, nome la serĉon de funkciaj kaj diferencaj dependecoj. Ĉi tiu temo rilatis al la temo de mia kurslaboro en la universitato, do dum mi laboris pri la kurslaboro, mi eklegis artikolojn pri diversaj dependecoj en datumbazoj. Mi skribis recenzon pri ĉi tiu areo - unu el miaj unuaj en la angla kaj sendis ĝin al la SEIM-2017-konferenco. Mi estis tre feliĉa kiam mi eksciis, ke ŝi estas ja akceptita, kaj decidis profundiĝi en la temon. La koncepto mem ne estas nova - ĝi komencis esti uzata jam en la 90-aj jaroj, sed eĉ nun ĝi estas uzata en multaj areoj.
Dum mia dua semestro ĉe la centro, mi komencis esplorprojekton por plibonigi algoritmojn por trovi funkciajn dependecojn. Ŝi laboris pri ĝi kune kun St. Petersburg State University gradstudanto Nikita Bobrov ĉe JetBrains Research.
Komputila komplekseco de serĉado de funkciaj dependecoj
La ĉefa problemo estas komputila komplekseco. La nombro da eblaj minimumaj kaj ne-trivialaj dependecoj estas limigita supre per la valoro kie — nombro da tabelaj atributoj. La funkciada tempo de la algoritmoj dependas ne nur de la nombro da atributoj, sed ankaŭ de la nombro da vicoj. En la 90-aj jaroj, federaciaj leĝaj serĉalgoritmoj sur regula labortabla komputilo povis prilabori datumajn arojn enhavantajn ĝis 20 atributojn kaj dekojn da miloj da vicoj en ĝis pluraj horoj. Modernaj algoritmoj funkcianta per multkernaj procesoroj detektas dependecojn por datumserioj konsistantaj el centoj da atributoj (ĝis 200) kaj centoj da miloj da vicoj en proksimume la sama tempo. Tamen tio ne sufiĉas: tia tempo estas neakceptebla por plej multaj realaj aplikoj. Tial ni evoluigis alirojn por akceli ekzistantajn algoritmojn.
Caching skemoj por dispartigaj intersekcoj
En la unua parto de la laboro, ni evoluigis kaŝmemorkabalojn por klaso de algoritmoj kiuj uzas la sekcion-intersekcmetodon. Vando por atributo estas aro de listoj, kie ĉiu listo enhavas linionumeroj kun la samaj valoroj por donita atributo. Ĉiu tia listo estas nomita areto. Multaj modernaj algoritmoj uzas sekciojn por determini ĉu dependeco estas tenita aŭ ne, nome, ili aliĝas al la lemo: Dependeco tenis se . Jen sekcio estas indikita kaj la koncepto de diskgrandeco estas uzata - la nombro da aretoj en ĝi. Algoritmoj, kiuj uzas sekciojn, kiam la dependeco estas malobservita, aldonas pliajn atributojn al la maldekstra flanko de la dependeco, kaj poste rekalkulas ĝin, plenumante la operacion de intersekco de sekcioj. Ĉi tiu operacio nomiĝas specialiĝo en la artikoloj. Sed ni rimarkis, ke sekcioj por dependecoj, kiuj nur estus konservitaj post kelkaj raŭndoj de specialiĝo, povas esti aktive reuzitaj, kio povas signife redukti la rultempon de la algoritmoj ĉar la intersekciĝooperacio estas multekosta.
Tial, ni proponis heŭristiko bazitan sur Shannon Entropy kaj Ginny Uncertainty, same kiel nia metriko, kiun ni nomis Inversa Entropio. Ĝi estas eta modifo de Shannon Entropy kaj pliiĝas kiam la unikeco de la datumaro pliiĝas. La proponita heŭristiko estas kiel sekvas:
estas — grado de unikeco de la lastatempe kalkulita vando kaj estas la mediano de la gradoj de unikeco por individuaj atributoj. Ĉiuj tri metrikoj priskribitaj supre estis testitaj kiel unikecmetriko. Vi ankaŭ povas rimarki, ke estas du modifiloj en la heŭristiko. La unua indikas kiom proksime la nuna sekcio estas al la ĉefa ŝlosilo kaj permesas vin konservi en kaŝmemoro en pli granda mezuro tiujn sekciojn kiuj estas malproksime de la ebla ŝlosilo. La dua modifilo permesas vin monitori kaŝmemorokupon kaj tiel instigas aldoni pliajn sekciojn al la kaŝmemoro se libera spaco estas havebla. La sukcesa solvo de ĉi tiu problemo permesis al ni akceli la PYRO-algoritmon je 10-40%, depende de la datumaro. Indas rimarki, ke la algoritmo PYRO estas la plej sukcesa en ĉi tiu areo.
En la suba figuro vi povas vidi la rezultojn de aplikado de la proponita heŭristiko kompare kun baza moner-flip-kaŝ-aliro. La X-akso estas logaritma.
Alternativa maniero konservi sekciojn
Ni tiam proponis alternativan manieron konservi sekciojn. Dispartigoj estas aro da aretoj, ĉiu el kiuj stokas nombrojn da opoj kun identaj valoroj por certaj atributoj. Tiuj aretoj povas enhavi longajn sekvencojn de opoj, ekzemple se la datenoj en tabelo estas ordigitaj. Tial ni proponis kunpreman skemon por stoki sekciojn, nome intervalan stokadon de valoroj en aretoj de sekcioj:
$$montro$$pi(X) = {{subŝnuro{1, 2, 3, 4, 5}_{Unua intervalo}, subŝnuro{7, 8}_{Dua intervalo}, 10}}\malsupren{ Kunpremo} \ pi(X) = {{subŝnuro{$, 1, 5}_{Unua~intervalo}, subŝnuro{7, 8}_{Dua~intervalo}, 10}}$$montro$$
Ĉi tiu metodo povis redukti la konsumon de memoro dum la funkciado de la algoritmo TANE de 1 ĝis 25%. La TANE-algoritmo estas klasika algoritmo por serĉi federaciajn leĝojn; ĝi uzas sekciojn dum sia laboro. Kiel parto de la praktiko, la TANE-algoritmo estis elektita, ĉar estis multe pli facile efektivigi intervalstokadon en ĝi ol, ekzemple, en PYRO por taksi ĉu la proponita aliro funkcias. La rezultoj akiritaj estas prezentitaj en la suba figuro. La X-akso estas logaritma.
Konferenco ADBIS-2019
Surbaze de la rezultoj de la esplorado, en septembro 2019 mi publikigis artikolon ĉe la 23-a Eŭropa Konferenco pri Progresoj en Datumaroj kaj Informaj Sistemoj (ADBIS-2019). Dum la prezento, la laboro notis Bernhard Thalheim, signifa persono en la kampo de datumbazoj. La esplorrezultoj formis la bazon de mia disertacio ĉe la magistro pri matematiko kaj mekaniko en Sankt-Peterburga Ŝtata Universitato, dum kiu ambaŭ proponitaj aliroj (kaŝkaptado kaj kunpremado) estis efektivigitaj en ambaŭ algoritmoj: TANE kaj PYRO. Krome, la rezultoj montris ke la proponitaj aliroj estas universalaj, ĉar ĉe ambaŭ algoritmoj, kun ambaŭ aliroj, signifa redukto en memorkonsumo estis observita, same kiel signifa redukto en la funkciada tempo de la algoritmoj.
fonto: www.habr.com