Bevezetés a funkcionális függőségekbe

Ebben a cikkben az adatbázisok funkcionális függőségeiről fogunk beszélni - mik ezek, hol használják őket, és milyen algoritmusok léteznek ezek megtalálására.

A funkcionális függőségeket a relációs adatbázisok kontextusában fogjuk megvizsgálni. Nagyon durván fogalmazva, az ilyen adatbázisokban az információkat táblázatok formájában tárolják. Ezután közelítő fogalmakat használunk, amelyek a szigorú relációelméletben nem felcserélhetők: magát a táblát relációnak, az oszlopokat - attribútumokat (halmazuk - relációs séma) és a sorértékek halmazát az attribútumok egy részhalmazán. - egy tuple.

Például a fenti táblázatban (Benson, M, M orgona) attribútumok sorozata (beteg, Paul, orvos).
Formálisabban ez így van leírva: [Beteg, nem, orvos] = (Benson, M, M orgona).
Most bevezethetjük a funkcionális függőség (FD) fogalmát:

1. definíció. Az R reláció akkor és csak akkor teljesíti az X → Y szövetségi törvényt (ahol X, Y ⊆ R) akkor és csak akkor, ha bármely sorra , ∈ R teljesül: ha [X] = [X] akkor [Y] = [Y]. Ebben az esetben azt mondjuk, hogy X (az attribútumok meghatározó vagy meghatározó halmaza) funkcionálisan meghatározza Y-t (a függő halmazt).

Más szóval, egy szövetségi törvény jelenléte X → Y azt jelenti, hogy ha két sorunk van R és attribútumokban egyeznek X, akkor attribútumokban egybe fognak esni Y.
És most sorrendben. Nézzük az attribútumokat beteg и Neme amelyekhez azt szeretnénk kideríteni, hogy vannak-e köztük függőségek vagy sem. Egy ilyen attribútumkészlet esetén a következő függőségek létezhetnek:

1. Beteg → Nem
2. Nem → Beteg

A fent meghatározottak szerint, hogy az első függőség megmaradjon, minden egyedi oszlopértéket beteg csak egy oszlopértéknek kell egyeznie Neme. És a példatáblázat esetében ez valóban így van. Ez azonban nem működik az ellenkező irányba, vagyis a második függőség nem teljesül, és az attribútum Neme számára nem meghatározó Beteg. Hasonlóképpen, ha a függőséget vesszük Orvos → Beteg, látható, hogy megsértették, hiszen az érték vörösbegy ennek az attribútumnak többféle jelentése van - Ellis és Graham.

Így a funkcionális függőségek lehetővé teszik a táblaattribútumkészletek közötti meglévő kapcsolatok meghatározását. Innentől kezdve a legérdekesebb összefüggéseket, vagy inkább ilyeneket fogjuk figyelembe venni X → Ymik ők:

• nem triviális, vagyis a függőség jobb oldala nem a bal részhalmaza (Y ̸⊆ X);
• minimális, vagyis nincs ilyen függőség Z → YHogy Z ⊂ X.

Az eddig figyelembe vett függőségek szigorúak voltak, vagyis nem írtak elő semmilyen szabálysértést az asztalon, de rajtuk kívül vannak olyanok is, amelyek némi inkonzisztenciát engednek meg a sorok értékei között. Az ilyen függőségek egy külön osztályba kerülnek, amelyet hozzávetőlegesnek neveznek, és bizonyos számú sor esetén megsérthetők. Ezt az összeget az emax maximális hibajelző szabályozza. Például a hibaarányt = 0.01 azt jelentheti, hogy a függőséget a rendelkezésre álló sorok 1%-a megsértheti az adott attribútumkészleten. Vagyis 1000 rekordnál legfeljebb 10 sor sértheti a szövetségi törvényt. Egy kissé eltérő mérőszámot fogunk figyelembe venni, az összehasonlított sorok páronként eltérő értékei alapján. A függőség miatt X → Y a hozzáállásról r így tekintendő:

Számítsuk ki a hibát Orvos → Beteg a fenti példából. Két sorunk van, amelyek értéke eltér az attribútumban beteg, de egybeesik Orvos: [Orvos, beteg] = (Robin, Ellis) És [Orvos, beteg] = (Robin, Graham). A hiba definícióját követően minden ütköző párt figyelembe kell vennünk, ami azt jelenti, hogy kettő lesz: (, ) és inverze (, ). Helyettesítsük be a képletbe, és kapjuk:

Most próbáljunk meg válaszolni a kérdésre: „Miért van mindez?” Valójában a szövetségi törvények mások. Az első típus azok a függőségek, amelyeket az adminisztrátor határoz meg az adatbázis tervezési szakaszában. Általában kevés, szigorúak, és fő alkalmazásuk az adatnormalizálás és a relációs sématervezés.

A második típus a függőségek, amelyek „rejtett” adatokat és az attribútumok közötti korábban ismeretlen kapcsolatokat képviselik. Vagyis ilyen függőségekre a tervezéskor nem gondoltak, és a meglévő adathalmazra megtalálják azokat, így később a sok azonosított szövetségi törvény alapján bármilyen következtetést le lehet vonni a tárolt információkról. Pontosan ezekkel a függőségekkel dolgozunk. Az adatbányászat egész területe foglalkozik velük, különféle keresési technikákkal és ezekre épülő algoritmusokkal. Nézzük meg, hogyan lehetnek hasznosak a talált funkcionális függőségek (pontos vagy közelítő) bármely adatban.

Ma a függőségek egyik fő alkalmazása az adattisztítás. Ez magában foglalja a „piszkos adatok” azonosítására, majd azok kijavítására szolgáló eljárások kidolgozását. A „piszkos adatok” szembetűnő példái az ismétlődések, adat- vagy elírási hibák, hiányzó értékek, elavult adatok, extra szóközök és hasonlók.

Példa adathibára:

Példa ismétlődésekre az adatokban:

Például van egy táblázatunk és egy sor szövetségi törvényünk, amelyeket végre kell hajtani. Az adattisztítás ebben az esetben magában foglalja az adatok módosítását, hogy a szövetségi törvények helyesek legyenek. Ebben az esetben a módosítások számának minimálisnak kell lennie (ennek az eljárásnak megvannak a maga algoritmusai, amelyekre ebben a cikkben nem foglalkozunk). Az alábbiakban egy példa látható egy ilyen adatátalakításra. A bal oldalon az eredeti kapcsolat látható, amelyben nyilvánvalóan nem teljesülnek a szükséges FL-ek (az egyik FL megsértésének példája pirossal van kiemelve). A jobb oldalon a frissített kapcsolat látható, a zöld cellák a megváltozott értékeket mutatják. Ezt az eljárást követően megkezdődött a szükséges függőségek fenntartása.

Egy másik népszerű alkalmazás az adatbázistervezés. Itt érdemes felidézni a normálformákat és a normalizálást. A normalizálás az a folyamat, amikor egy relációt összhangba hoznak egy bizonyos követelményrendszerrel, amelyek mindegyikét a normálforma határozza meg a maga módján. Nem írjuk le a különféle normálformák követelményeit (ezt minden kezdőknek szóló adatbázis-tanfolyam könyve megteszi), de csak annyit jegyezünk meg, hogy mindegyik a funkcionális függőségek fogalmát a maga módján használja. Végtére is, az FL-k eredendően integritási megszorítások, amelyeket figyelembe vesznek az adatbázis tervezésekor (ennek a feladatnak az összefüggésében az FL-ket néha szuperkulcsoknak nevezik).

Tekintsük az alábbi képen látható négy normálforma alkalmazását. Emlékezzünk vissza, hogy a Boyce-Codd normál forma szigorúbb, mint a harmadik forma, de kevésbé szigorú, mint a negyedik. Ez utóbbival egyelőre nem foglalkozunk, mivel annak megfogalmazása megköveteli a többértékű függőségek megértését, amelyek ebben a cikkben nem érdekesek számunkra.

Egy másik terület, ahol a függőségek alkalmazásra találtak, a jellemzőtér dimenziójának csökkentése olyan feladatokban, mint egy naiv Bayes-osztályozó felépítése, jelentős jellemzők azonosítása és egy regressziós modell újraparaméterezése. Az eredeti cikkekben ezt a feladatot a redundáns és a jellemző relevancia meghatározásának nevezik [5, 6], és adatbázis-koncepciók aktív használatával oldják meg. Az ilyen művek megjelenésével elmondható, hogy ma már olyan megoldásokra van igény, amelyek lehetővé teszik, hogy a fenti optimalizálási problémák adatbázisát, elemzését és megvalósítását egyetlen eszközben egyesítsük [7, 8, 9].

Számos (modern és kevésbé modern) algoritmus létezik a szövetségi törvények adathalmazban történő keresésére. Az ilyen algoritmusok három csoportra oszthatók:

• Algebrai rácsok bejárását használó algoritmusok (rács bejárási algoritmusok)
• Megállapodott értékek keresésén alapuló algoritmusok (Különbség- és egyetértési algoritmusok)
• Páronkénti összehasonlításon alapuló algoritmusok (Függőségindukciós algoritmusok)

Az egyes algoritmustípusok rövid leírása az alábbi táblázatban található:


Erről az osztályozásról bővebben olvashat [4]. Az alábbiakban példák találhatók az egyes típusokhoz tartozó algoritmusokra:

Jelenleg új algoritmusok jelennek meg, amelyek többféle megközelítést kombinálnak a funkcionális függőségek megtalálására. Ilyen algoritmusok például a Pyro [2] és a HyFD [3]. Munkájuk elemzése a sorozat következő cikkeiben várható. Ebben a cikkben csak azokat az alapfogalmakat és lemmákat vizsgáljuk meg, amelyek a függőségi kimutatási technikák megértéséhez szükségesek.

Kezdjük egy egyszerű - különbség- és egyetérthalmazzal -, amelyet a második típusú algoritmusok használnak. A Difference-set olyan sorok halmaza, amelyek nem rendelkeznek azonos értékkel, míg az egyetértés-halmaz viszont olyan sorok, amelyek azonos értékekkel rendelkeznek. Érdemes megjegyezni, hogy ebben az esetben csak a függőség bal oldalát vesszük figyelembe.

Egy másik fontos fogalom, amellyel fentebb találkoztunk, az algebrai rács. Mivel sok modern algoritmus működik ezen a koncepción, tudnunk kell, mi is ez.

A rács fogalmának bevezetéséhez szükséges egy részben rendezett halmaz (vagy részben rendezett halmaz, rövidítve poset) definiálása.

2. definíció. Egy S halmazt részlegesen rendezettnek mondunk a ⩽ bináris relációval, ha minden a, b, c ∈ S esetén teljesülnek a következő tulajdonságok:

1. Reflexivitás, azaz a ⩽ a
2. Antiszimmetria, vagyis ha a ⩽ b és b ⩽ a, akkor a = b
3. A tranzitivitás, azaz a ⩽ b és b ⩽ c esetén az következik, hogy a ⩽ c

Az ilyen relációt (laza) részleges rendű relációnak, magát a halmazt pedig részlegesen rendezett halmaznak nevezzük. Formális jelölés: ⟨S, ⩽⟩.

A részlegesen rendezett halmaz legegyszerűbb példájaként felvehetjük az összes N természetes szám halmazát a szokásos ⩽ sorrendi összefüggéssel. Könnyen ellenőrizhető, hogy az összes szükséges axióma teljesül-e.

Értelmesebb példa. Tekintsük az összes {1, 2, 3} részhalmaz halmazát, a ⊆ befogadási reláció szerint rendezve. Valójában ez az összefüggés minden részleges rendezettségi feltételt teljesít, így ⟨P ({1, 2, 3}), ⊆⟩ egy részlegesen rendezett halmaz. Az alábbi ábra ennek a halmaznak a felépítését mutatja: ha egy elemet nyilakkal lehet elérni egy másik elemhez, akkor azok sorrendi kapcsolatban állnak.

Még két egyszerű definícióra lesz szükségünk a matematika területéről - supremum és infimum.

3. definíció. Legyen ⟨S, ⩽⟩ részlegesen rendezett halmaz, A ⊆ S. A felső korlátja egy u ∈ S elem, amelyre ∀x ∈ S: x ⩽ u. Legyen U az S összes felső határának halmaza. Ha U-ban van egy legkisebb elem, akkor azt szuprémumnak nevezzük, és sup A-val jelöljük.

Hasonlóan vezetjük be a pontos alsó korlát fogalmát.

4. definíció. Legyen ⟨S, ⩽⟩ részlegesen rendezett halmaz, A ⊆ S. A infimuma olyan l ∈ S elem, hogy ∀x ∈ S: l ⩽ x. Legyen L az S összes alsó határának halmaza. Ha L-ben van egy legnagyobb elem, akkor azt infimumnak nevezzük, és inf A-ként jelöljük.

Tekintsük példaként a fenti részben rendezett ⟨P ({1, 2, 3}), ⊆⟩ halmazt, és keressük meg benne a felső és infimumot:

Most meg tudjuk fogalmazni az algebrai rács definícióját.

5. definíció. Legyen ⟨P,⩽⟩ egy részlegesen rendezett halmaz úgy, hogy minden kételemű részhalmaznak van felső és alsó korlátja. Ekkor P-t algebrai rácsnak nevezzük. Ebben az esetben a sup{x, y} mint x ∨ y, az inf {x, y} pedig x ∧ y-ként van felírva.

Ellenőrizzük, hogy a ⟨P ({1, 2, 3}), ⊆⟩ munkapéldánk egy rács. Valójában bármely a, b ∈ P ({1, 2, 3}) esetén a∨b = a∪b, és a∧b = a∩b. Vegyük például az {1, 2} és {1, 3} halmazokat, és keressük meg az infimumjukat és a felsőbb értéküket. Ha metszi őket, akkor a {1} halmazt kapjuk, ami az infimum lesz. A szuprémumot úgy kapjuk meg, hogy összevonjuk őket - {1, 2, 3}.

A fizikai problémák azonosítására szolgáló algoritmusokban a keresési teret gyakran rács formájában ábrázolják, ahol egy elem halmazai (a keresési rács első szintje, ahol a függőségek bal oldala egy attribútumból áll) képviselik az egyes attribútumokat. az eredeti viszonyról.
Először is megvizsgáljuk a ∅ → alakú függőségeket Egyetlen attribútum. Ez a lépés lehetővé teszi annak meghatározását, hogy mely attribútumok az elsődleges kulcsok (az ilyen attribútumokhoz nincsenek meghatározók, ezért a bal oldal üres). Továbbá az ilyen algoritmusok felfelé mozognak a rács mentén. Érdemes megjegyezni, hogy nem lehet a teljes rácsot bejárni, vagyis ha a bal oldal kívánt maximális méretét átadjuk a bemenetnek, akkor az algoritmus ezzel a mérettel nem megy tovább egy szintnél.

Az alábbi ábra bemutatja, hogyan használható egy algebrai rács az FZ megtalálásának problémájában. Itt minden él (X, XY) függőséget jelent X → Y. Például túljutottunk az első szinten, és tudjuk, hogy a függőség megmarad A → B (ezt zöld kapcsolatként fogjuk megjeleníteni a csúcsok között A и B). Ez azt jelenti, hogy ha tovább haladunk a rács mentén, nem biztos, hogy ellenőrizzük a függőséget A, C → B, mert már nem lesz minimális. Hasonlóképpen nem ellenőriznénk, ha a függőség fennállna C → B.

Ezenkívül a szövetségi törvények keresésére szolgáló összes modern algoritmus általában olyan adatstruktúrát használ, mint például egy partíció (az eredeti forrásban - lecsupaszított partíció [1]). A partíció formális meghatározása a következő:

6. definíció. Legyen X ⊆ R attribútumok halmaza r relációhoz. A klaszter az r-beli sorok indexeinek halmaza, amelyek X-hez azonos értékűek, azaz c(t) = {i|ti[X] = t[X]}. A partíció fürtök halmaza, kivéve az egységnyi hosszúságú klasztereket:

Egyszerű szavakkal, partíció egy attribútum számára X egy listák halmaza, ahol minden lista sorszámokat tartalmaz, amelyek azonos értékekkel rendelkeznek X. A modern irodalomban a partíciókat reprezentáló struktúrát pozíciólista indexnek (PLI) nevezik. Az egységhosszúságú fürtök nem használhatók PLI-tömörítési célokra, mivel ezek olyan fürtök, amelyek csak egy rekordszámot tartalmaznak egyedi értékkel, amely mindig könnyen azonosítható.

Nézzünk egy példát. Térjünk vissza ugyanahhoz a táblázathoz a betegekkel, és építsünk partíciókat az oszlopokhoz beteg и Neme (bal oldalon egy új oszlop jelent meg, amelyben a táblázat sorszámai vannak jelölve):

Sőt, a definíció szerint az oszlop partíciója beteg valójában üres lesz, mivel az egyes klaszterek ki vannak zárva a partícióból.

A partíciók többféle attribútummal szerezhetők be. És ennek két módja van: a táblán végighaladva készítsen egy partíciót az összes szükséges attribútum használatával egyszerre, vagy építse fel a partíciók metszéspontja művelettel az attribútumok egy részhalmazával. A szövetségi törvény keresési algoritmusai a második lehetőséget használják.

Egyszerű szavakkal, például oszlopok szerinti partíció beszerzéséhez ABC, partíciókat vehet igénybe AC и B (vagy bármely más diszjunkt részhalmazok halmazát), és metszi őket egymással. A két partíció metszéspontjának művelete a legnagyobb hosszúságú klasztereket választja ki, amelyek mindkét partícióban közösek.

Nézzünk egy példát:

Az első esetben egy üres partíciót kaptunk. Ha alaposan megnézi a táblázatot, akkor valóban nincs azonos értéke a két attribútumnak. Ha kissé módosítjuk a táblázatot (a jobb oldali esetet), máris egy nem üres kereszteződést kapunk. Ezenkívül az 1. és 2. sor valójában ugyanazokat az attribútumértékeket tartalmazza Neme и Orvos.

Ezután szükségünk lesz egy olyan fogalomra, mint a partíció mérete. Formálisan:

Egyszerűen fogalmazva, a partíció mérete a partícióban lévő fürtök száma (ne feledje, hogy az egyes fürtök nem szerepelnek a partícióban!):

Most meghatározhatjuk az egyik kulcslemmát, amely adott partíciók esetén lehetővé teszi annak meghatározását, hogy fennáll-e a függőség vagy sem:

1. lemma. Az A, B → C függőség akkor és csak akkor érvényesül

A lemma szerint annak megállapításához, hogy fennáll-e egy függőség, négy lépést kell végrehajtani:

1. Számítsa ki a partíciót a függőség bal oldalán
2. Számítsa ki a partíciót a függőség jobb oldalához
3. Számítsa ki az első és a második lépés szorzatát!
4. Hasonlítsa össze az első és harmadik lépésben kapott válaszfalak méretét

Az alábbiakban egy példa annak ellenőrzésére, hogy a függőség fennáll-e e lemma szerint:

Ebben a cikkben olyan fogalmakat vizsgáltunk meg, mint a funkcionális függőség, a hozzávetőleges funkcionális függőség, megvizsgáltuk, hol használják őket, valamint hogy milyen algoritmusok léteznek a fizikai függvények keresésére. Részletesen megvizsgáltuk azokat az alapvető, de fontos fogalmakat is, amelyeket a szövetségi törvények keresésére szolgáló modern algoritmusok aktívan használnak.

Referenciák:

1. Huhtala Y. et al. TANE: Hatékony algoritmus funkcionális és közelítő függőségek felfedezésére //A számítógépes napló. – 1999. – T. 42. – Sz. 2. – 100-111.
2. Kruse S., Naumann F. Közelítő függőségek hatékony felfedezése // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Sz. 7. – 759-772.
3. Papenbrock T., Naumann F. A funkcionális függőség felfedezésének hibrid megközelítése //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – 821-833.
4. Papenbrock T. et al. Funkcionális függőség felfedezése: hét algoritmus kísérleti kiértékelése //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Sz. 10. – 1082-1093.
5. Kumar A. et al. Csatlakozni vagy nem csatlakozni?: Kétszer meggondolva a csatlakozást a funkciók kiválasztása előtt //A 2016-os adatkezelési nemzetközi konferencia előadásai. – ACM, 2016. – 19-34.
6. Abo Khamis M. et al. Adatbázison belüli tanulás ritka tenzorokkal //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – 325-340.
7. Hellerstein J. M. et al. A MADlib analitikai könyvtár: vagy MAD-készségek, az SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Sz. 12. – 1700-1711.
8. Qin C., Rusu F. Speculative approximations for terascale elosztott gradiens süllyedés optimalizálás //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – 1. o.
9. Meng X. et al. Mllib: Gépi tanulás az apache sparkjában //The Journal of Machine Learning Research. – 2016. – T. 17. – Sz. 1. – 1235-1241.

A cikk szerzői: Anastasia Birillo, kutató a JetBrains kutatás, CS center hallgató и Nyikita Bobrov, kutató a JetBrains kutatás

Forrás: will.com