Az adatokban a funkcionális függőségek megtalálását az adatelemzés különböző területein használják: adatbáziskezelés, adattisztítás, adatbázis-visszafejtés és adatfeltárás. Magukról a függőségekről már publikáltunk Anastasia Birillo és Nikita Bobrov. Ezúttal Anastasia, a Számítástechnikai Központ idén végzett hallgatója osztja meg ennek a munkának a fejlesztését a központban megvédett kutatómunka részeként.
Feladat kiválasztása
A CS központban való tanulás során elkezdtem mélyrehatóan foglalkozni az adatbázisokkal, nevezetesen a funkcionális és különbségi függőségek keresésével. Ez a téma az egyetemi kurzusaim témájához kapcsolódott, így a kurzuson dolgozva elkezdtem olvasni a különféle adatbázis-függőségekről szóló cikkeket. Írtam egy értékelést erről a területről - az egyik első angol nyelven, és benyújtotta a SEIM-2017 konferenciára. Nagyon örültem, amikor megtudtam, hogy mégis elfogadták, és úgy döntöttem, hogy jobban beleásom magam a témába. Maga a koncepció nem új - a 90-es években kezdték használni, de még ma is sok területen használják.
A központban töltött második félévemben kutatási projektbe kezdtem a funkcionális függőségek keresési algoritmusainak fejlesztésére. Együtt dolgozott rajta a Szentpétervári Állami Egyetem végzős hallgatójával, Nikita Bobrovval, a JetBrains Researchnél.
A funkcionális függőségek keresésének számítási bonyolultsága
A fő probléma a számítási bonyolultság. A lehetséges minimális és nem triviális függőségek számát fent az érték korlátozza 
Ahol 
— a táblázat attribútumainak száma. Az algoritmusok működési ideje nemcsak az attribútumok számától függ, hanem a sorok számától is. A 90-es években a szövetségi törvények keresési algoritmusai egy hagyományos asztali számítógépen akár 20 attribútumot és több tízezer sort tartalmazó adatkészleteket dolgozhattak fel akár több órán belül. A többmagos processzorokon futó modern algoritmusok megközelítőleg ugyanabban az időben észlelik a több száz attribútumból (legfeljebb 200-ig) és több százezer sorból álló adatkészletek függőségét. Ez azonban nem elég: ez az idő elfogadhatatlan a legtöbb valós alkalmazás számára. Ezért megközelítéseket dolgoztunk ki a meglévő algoritmusok felgyorsítására.
Gyorsítótárazási sémák partíciók metszéspontjaihoz
A munka első részében gyorsítótárazási sémákat dolgoztunk ki egy olyan algoritmusosztályhoz, amely a partíció metszéspontját használja. Egy attribútum partíciója egy listák halmaza, ahol minden lista sorszámokat tartalmaz, amelyek azonos értékekkel rendelkeznek egy adott attribútumhoz. Minden ilyen listát klaszternek neveznek. Sok modern algoritmus partíciókat használ annak meghatározására, hogy fennáll-e a függőség vagy sem, nevezetesen ragaszkodnak a lemmához: Függőség 
tartott ha 
. Itt 
kijelölünk egy partíciót, és használjuk a partícióméret fogalmát - a benne lévő klaszterek számát. A partíciókat használó algoritmusok, ha a függőséget megsértik, további attribútumokat adnak hozzá a függőség bal oldalához, majd újraszámítják azt, végrehajtva a partíciók metszéspontjának műveletét. Ezt a műveletet szakosodásnak nevezik a cikkekben. De észrevettük, hogy a függőségek partíciói, amelyek csak néhány szakosodási kör után maradnának meg, újra aktívan felhasználhatók, ami jelentősen csökkentheti az algoritmusok futási idejét, mivel a metszésponti művelet költséges.
Ezért javasoltunk egy Shannon Entropy és Ginny Uncertainty alapú heurisztikát, valamint a metrikánkat, amelyet fordított entrópiának neveztünk. Ez a Shannon Entropy enyhe módosítása, és az adatkészlet egyediségének növekedésével növekszik. A javasolt heurisztika a következő:
Itt 
— a nemrég számított partíció egyediségének foka 
És 
az egyedi tulajdonságok egyediségi fokának mediánja. Mindhárom fent leírt mérőszámot egyediségi mérőszámként teszteltük. Azt is észreveheti, hogy két módosító van a heurisztikában. Az első azt jelzi, hogy az aktuális partíció milyen közel van az elsődleges kulcshoz, és lehetővé teszi a potenciális kulcstól távol eső partíciók nagyobb mértékű gyorsítótárazását. A második módosító lehetővé teszi a gyorsítótár foglaltságának figyelését, és ezáltal további partíciók hozzáadását a gyorsítótárhoz, ha van szabad hely. A probléma sikeres megoldása lehetővé tette, hogy adatkészlettől függően 10-40%-kal gyorsítsuk fel a PYRO algoritmust. Érdemes megjegyezni, hogy ezen a területen a PYRO algoritmus a legsikeresebb.
Az alábbi ábrán láthatja a javasolt heurisztika alkalmazásának eredményeit az alapvető érmefeldobás gyorsítótárazási megközelítéshez képest. Az X tengely logaritmikus.
A partíciók tárolásának alternatív módja
Ezután alternatív módot javasoltunk a partíciók tárolására. A partíciók fürtök halmaza, amelyek mindegyike számos, bizonyos attribútumokhoz tartozó azonos értékkel rendelkező sorokat tárol. Ezek a klaszterek hosszú sorszámokat tartalmazhatnak, például ha a táblázatban lévő adatok rendezettek. Ezért javasoltunk egy tömörítési sémát a partíciók tárolására, nevezetesen az értékek intervallum tárolását partíciók klasztereiben:
$$megjelenítés$$pi(X) = {{kapcsos zárójel{1, 2, 3, 4, 5}_{Első intervallum}, alsó zárójel{7, 8}_{Második intervallum}, 10}}\ downarrow{ Tömörítés} \ pi(X) = {{kapcsos zárójel{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Ezzel a módszerrel 1-ről 25%-ra sikerült csökkenteni a memóriafelhasználást a TANE algoritmus működése során. A TANE algoritmus egy klasszikus algoritmus a szövetségi törvények keresésére, munkája során partíciókat használ. A gyakorlat részeként a TANE algoritmusra esett a választás, mivel abban sokkal könnyebb volt intervallumtárolást megvalósítani, mint például a PYRO-ban, hogy kiértékeljük, működik-e a javasolt megközelítés. A kapott eredményeket az alábbi ábra mutatja be. Az X tengely logaritmikus.
ADBIS-2019 konferencia
A kutatás eredményei alapján 2019 szeptemberében publikáltam egy cikket a 23. európai konferencián az Advances in Database and Information Systems (ADBIS-2019) címmel. Az előadás során Bernhard Thalheim, az adatbázisok területén jelentős ember jegyezte meg a munkát. A kutatási eredmények képezték az alapját a Szentpétervári Állami Egyetem matematika és mechanika mesterképzésén végzett disszertációmnak, melynek során mindkét javasolt megközelítést (caching és tömörítés) implementáltam mindkét algoritmusban: TANE és PYRO. Ezen túlmenően az eredmények azt mutatták, hogy a javasolt megközelítések univerzálisak, mivel mindkét algoritmuson, mindkét megközelítésnél jelentős memória-felhasználás, valamint az algoritmusok működési idejének jelentős csökkenése volt megfigyelhető.
Forrás: will.com
