Utangulizi wa Vitegemezi vya Utendaji

Katika makala hii tutazungumza juu ya utegemezi wa kazi katika hifadhidata - ni nini, zinatumika wapi na ni algorithms gani zipo kuzipata.

Tutazingatia utegemezi wa kiutendaji katika muktadha wa hifadhidata za uhusiano. Ili kuiweka takribani, katika hifadhidata hizo habari huhifadhiwa kwa namna ya meza. Ifuatayo, tunatumia dhana takriban ambazo hazibadiliki katika nadharia kali ya uhusiano: tutaita meza yenyewe uhusiano, safu - sifa (seti zao - schema ya uhusiano), na seti ya maadili ya safu kwenye sehemu ndogo ya sifa. - tuple.

Kwa mfano, katika jedwali hapo juu, (Benson, M, M chombo) ni nakala ya sifa (Mgonjwa, Paul, Daktari).
Rasmi zaidi, hii imeandikwa kama ifuatavyo: [Mgonjwa, Jinsia, Daktari] = (Benson, M, M chombo).
Sasa tunaweza kuanzisha dhana ya utegemezi wa kazi (FD):

Ufafanuzi 1. Uhusiano R unakidhi sheria ya shirikisho X → Y (ambapo X, Y ⊆ R) ikiwa na tu ikiwa ni nakala zozote. , ∈ R inashikilia: ikiwa [X] = [X], basi [Y] = [Y]. Katika kesi hii, tunasema kwamba X (kiasi, au seti ya kufafanua ya sifa) huamua Y (seti tegemezi).

Kwa maneno mengine, uwepo wa sheria ya shirikisho X → Y inamaanisha kuwa ikiwa tunayo nakala mbili ndani R na zinalingana katika sifa X, basi zitalingana katika sifa Y.
Na sasa, kwa utaratibu. Hebu tuangalie sifa Mgonjwa и Sakafu ambayo tunataka kujua kama kuna utegemezi kati yao au la. Kwa seti kama hiyo ya sifa, tegemezi zifuatazo zinaweza kuwepo:

1. Mgonjwa → Jinsia
2. Jinsia → Mvumilivu

Kama ilivyofafanuliwa hapo juu, ili utegemezi wa kwanza ushikilie, kila thamani ya safu wima ya kipekee Mgonjwa thamani ya safu wima moja pekee lazima ilingane Sakafu. Na kwa mfano meza hii ni kweli kesi. Walakini, hii haifanyi kazi kwa mwelekeo tofauti, ambayo ni, utegemezi wa pili haujaridhika, na sifa. Sakafu sio kiashiria cha Mgonjwa. Vile vile, ikiwa tutachukua utegemezi Daktari → Mgonjwa, unaweza kuona kwamba imekiukwa, kwa kuwa thamani Robin sifa hii ina maana kadhaa tofauti - Ellis na Graham.

Kwa hivyo, utegemezi wa kazi hufanya iwezekanavyo kuamua uhusiano uliopo kati ya seti za sifa za meza. Kuanzia hapa na kuendelea tutazingatia viunganisho vya kuvutia zaidi, au tuseme vile X → Ywao ni nini:

• yasiyo ya maana, yaani, upande wa kulia wa utegemezi sio sehemu ndogo ya kushoto (Y ̸⊆ X);
• ndogo, yaani, hakuna utegemezi huo Z → YHiyo Z ⊂ X.

Utegemezi uliozingatiwa hadi wakati huu ulikuwa mkali, ambayo ni, haukutoa ukiukwaji wowote kwenye meza, lakini kwa kuongezea, pia kuna zile zinazoruhusu kutokubaliana kati ya maadili ya nakala. Utegemezi kama huo huwekwa katika darasa tofauti, inayoitwa takriban, na inaruhusiwa kukiukwa kwa idadi fulani ya nakala. Kiasi hiki kinadhibitiwa na kiashirio cha juu cha makosa emax. Kwa mfano, kiwango cha makosa = 0.01 inaweza kumaanisha kuwa utegemezi unaweza kukiukwa na 1% ya nakala zinazopatikana kwenye seti inayozingatiwa ya sifa. Hiyo ni, kwa rekodi 1000, upeo wa nakala 10 zinaweza kukiuka Sheria ya Shirikisho. Tutazingatia kipimo tofauti kidogo, kulingana na thamani tofauti za jozi za nakala zinazolinganishwa. Kwa uraibu X → Y juu ya mtazamo r inazingatiwa kama hii:

Wacha tuhesabu kosa Daktari → Mgonjwa kutoka kwa mfano hapo juu. Tuna nakala mbili ambazo maadili yake hutofautiana kwenye sifa Mgonjwa, lakini sanjari Daktari: [Daktari, Mgonjwa] = (Robin, Ellis) na [Daktari, Mgonjwa] = (Robin, Graham) Kufuatia ufafanuzi wa kosa, lazima tuzingatie jozi zote zinazokinzana, ambayo inamaanisha kutakuwa na mbili kati yao: (, ) na kinyume chake (, ) Wacha tuibadilishe katika fomula na tupate:

Sasa hebu tujaribu kujibu swali: "Kwa nini ni kwa ajili ya yote?" Kwa kweli, sheria za shirikisho ni tofauti. Aina ya kwanza ni zile tegemezi ambazo zimedhamiriwa na msimamizi katika hatua ya muundo wa hifadhidata. Kawaida huwa chache kwa idadi, kali, na matumizi kuu ni kuhalalisha data na muundo wa schema wa uhusiano.

Aina ya pili ni tegemezi, ambayo inawakilisha data "iliyofichwa" na uhusiano usiojulikana hapo awali kati ya sifa. Hiyo ni, utegemezi huo haukufikiriwa wakati wa kubuni na tayari hupatikana kwa kuweka data iliyopo, ili baadaye, kwa kuzingatia sheria nyingi za shirikisho zilizotambuliwa, hitimisho lolote linaweza kutolewa kuhusu habari iliyohifadhiwa. Ni tegemezi hizi haswa ambazo tunafanya kazi nazo. Zinashughulikiwa na uwanja mzima wa uchimbaji data na mbinu mbalimbali za utafutaji na algorithms zilizojengwa kwa misingi yao. Wacha tuone jinsi utegemezi wa kazi uliopatikana (sawa au takriban) katika data yoyote unaweza kuwa muhimu.

Leo, moja ya matumizi kuu ya utegemezi ni kusafisha data. Inahusisha kuendeleza michakato ya kutambua "data chafu" na kisha kuirekebisha. Mifano maarufu ya "data chafu" ni nakala, hitilafu za data au uchapaji, thamani zinazokosekana, data iliyopitwa na wakati, nafasi za ziada, na kadhalika.

Mfano wa hitilafu ya data:

Mfano wa nakala katika data:

Kwa mfano, tuna jedwali na seti ya sheria za shirikisho ambazo lazima zitekelezwe. Kusafisha data katika kesi hii inahusisha kubadilisha data ili Sheria za Shirikisho ziwe sahihi. Katika kesi hii, idadi ya marekebisho inapaswa kuwa ndogo (utaratibu huu una algorithms yake, ambayo hatutazingatia katika makala hii). Chini ni mfano wa mabadiliko kama haya ya data. Kwa upande wa kushoto ni uhusiano wa awali, ambao, ni wazi, FLs muhimu hazipatikani (mfano wa ukiukwaji wa moja ya FL umeonyeshwa kwa rangi nyekundu). Upande wa kulia ni uhusiano uliosasishwa, na seli za kijani zinaonyesha maadili yaliyobadilishwa. Baada ya utaratibu huu, utegemezi muhimu ulianza kudumishwa.

Programu nyingine maarufu ni muundo wa hifadhidata. Hapa inafaa kukumbuka fomu za kawaida na kuhalalisha. Kusawazisha ni mchakato wa kuleta uhusiano kulingana na seti fulani ya mahitaji, ambayo kila moja inafafanuliwa na fomu ya kawaida kwa njia yake mwenyewe. Hatutaelezea mahitaji ya aina mbalimbali za kawaida (hii inafanywa katika kitabu chochote kwenye kozi ya database kwa Kompyuta), lakini tutaona tu kwamba kila mmoja wao anatumia dhana ya utegemezi wa kazi kwa njia yake mwenyewe. Baada ya yote, FL ni vikwazo vya asili vya uadilifu ambavyo huzingatiwa wakati wa kuunda hifadhidata (katika muktadha wa kazi hii, FL wakati mwingine huitwa funguo kuu).

Hebu tuchunguze maombi yao kwa fomu nne za kawaida kwenye picha hapa chini. Kumbuka kwamba fomu ya kawaida ya Boyce-Codd ni kali zaidi kuliko fomu ya tatu, lakini chini ya kali kuliko ya nne. Hatuzingatii mwisho kwa sasa, kwani uundaji wake unahitaji ufahamu wa utegemezi wa thamani nyingi, ambao hautuvutii katika nakala hii.

Eneo lingine ambalo utegemezi umepata matumizi yao ni kupunguza ukubwa wa nafasi ya kipengele katika kazi kama vile kujenga kiainishaji cha Bayes ambacho hakijui, kubainisha vipengele muhimu, na kurekebisha muundo wa rejista. Katika vifungu asili, kazi hii inaitwa uamuzi wa kutohitajika tena na umuhimu wa kipengele [5, 6], na inatatuliwa kwa utumiaji hai wa dhana za hifadhidata. Pamoja na ujio wa kazi hizo, tunaweza kusema kwamba leo kuna mahitaji ya ufumbuzi ambayo inaruhusu sisi kuchanganya database, analytics na utekelezaji wa matatizo ya juu optimization katika chombo moja [7, 8, 9].

Kuna algoriti nyingi (za kisasa na sio za kisasa) za kutafuta sheria za shirikisho katika seti ya data. Algoriti kama hizo zinaweza kugawanywa katika vikundi vitatu:

• Algorithms kwa kutumia traversal ya latisi aljebra (Lattice traversal algoriti)
• Kanuni za msingi za utafutaji wa thamani zilizokubaliwa (Tofauti- na algoriti zilizowekwa za kukubaliana)
• Algorithms kulingana na ulinganisho wa jozi (algorithms ya uingizaji wa utegemezi)

Maelezo mafupi ya kila aina ya algorithm imewasilishwa kwenye jedwali hapa chini:


Unaweza kusoma zaidi kuhusu uainishaji huu [4]. Ifuatayo ni mifano ya algorithms kwa kila aina:

Hivi sasa, algorithms mpya zinaonekana ambazo zinachanganya mbinu kadhaa za kutafuta utegemezi wa kazi. Mifano ya algoriti kama hizo ni Pyro [2] na HyFD [3]. Uchambuzi wa kazi zao unatarajiwa katika makala zifuatazo za mfululizo huu. Katika makala haya tutachunguza tu dhana za kimsingi na lema ambazo ni muhimu kuelewa mbinu za kugundua utegemezi.

Hebu tuanze na rahisi - tofauti- na kukubaliana-kuweka, kutumika katika aina ya pili ya algorithms. Tofauti-seti ni seti ya nakala ambazo hazina thamani sawa, wakati makubaliano-seti, kinyume chake, ni nakala ambazo zina thamani sawa. Ni muhimu kuzingatia kwamba katika kesi hii tunazingatia tu upande wa kushoto wa utegemezi.

Dhana nyingine muhimu ambayo ilikutana hapo juu ni latiti ya algebraic. Kwa kuwa algorithms nyingi za kisasa zinafanya kazi kwenye wazo hili, tunahitaji kuwa na wazo la ni nini.

Ili kuanzisha dhana ya kimiani, ni muhimu kufafanua seti iliyoagizwa kwa sehemu (au seti iliyoagizwa kwa sehemu, iliyofupishwa kama poset).

Ufafanuzi 2. Seti ya S inasemekana kupangwa kwa sehemu na uhusiano wa mfumo wa jozi ⩽ ikiwa kwa yote a, b, c ∈ S sifa zifuatazo zimeridhika:

1. Reflexive, yaani, a ⩽ a
2. Antisymmetry, yaani, ikiwa ⩽ b na b ⩽ a, basi a = b
3. Upitishaji, yaani, kwa ⩽ b na b ⩽ c inafuata kwamba a ⩽ c

Uhusiano kama huo unaitwa uhusiano wa mpangilio wa sehemu (huru), na seti yenyewe inaitwa seti iliyoagizwa kwa sehemu. Nukuu rasmi: ⟨S, ⩽⟩.

Kama mfano rahisi zaidi wa seti iliyoagizwa kiasi, tunaweza kuchukua seti ya nambari zote asilia N na uhusiano wa kawaida wa mpangilio ⩽. Ni rahisi kuthibitisha kwamba axioms zote muhimu zimeridhika.

Mfano wa maana zaidi. Zingatia seti ya vikundi vidogo vyote {1, 2, 3}, vilivyopangwa kwa uhusiano wa kujumuisha ⊆. Hakika, uhusiano huu unakidhi masharti yote ya mpangilio, kwa hivyo ⟨P ({1, 2, 3}), ⊆⟩ ni seti iliyoagizwa kiasi. Takwimu hapa chini inaonyesha muundo wa seti hii: ikiwa kipengele kimoja kinaweza kufikiwa kwa mishale kwa kipengele kingine, basi wao ni katika uhusiano wa utaratibu.

Tutahitaji ufafanuzi mbili rahisi zaidi kutoka kwa uwanja wa hisabati - supremum na infimum.

Ufafanuzi 3. Acha ⟨S, ⩽⟩ iwe seti iliyopangwa kwa kiasi, A ⊆ S. Upeo wa juu wa A ni kipengele u ∈ S ambacho ∀x ∈ S: x ⩽ u. Acha U iwe seti ya mipaka yote ya juu ya S. Ikiwa kuna kipengele kidogo zaidi katika U, basi inaitwa supremum na inaashiria sup A.

Wazo la kikomo cha chini kabisa huletwa vivyo hivyo.

Ufafanuzi 4. Acha ⟨S, ⩽⟩ iwe seti iliyopangwa kwa kiasi, A ⊆ S. Infimum ya A ni kipengele l ∈ S hivi kwamba ∀x ∈ S: l ⩽ x. Acha L iwe seti ya mipaka yote ya chini ya S. Ikiwa kuna kipengele kikubwa zaidi katika L, basi inaitwa infimum na inaashiriwa kama inf A.

Fikiria kama mfano seti iliyoagizwa kidogo ⟨P ({1, 2, 3}), ⊆⟩ na upate supremum na infimum ndani yake:

Sasa tunaweza kuunda ufafanuzi wa kimiani cha algebraic.

Ufafanuzi 5. Wacha ⟨P,⩽⟩ iwe seti iliyoagizwa kiasi kwamba kila sehemu ndogo ya vipengele viwili iwe na kikomo cha juu na cha chini. Kisha P inaitwa kimiani cha algebraic. Katika hali hii, sup{x, y} imeandikwa kama x ∨ y, na inf {x, y} kama x ∧ y.

Hebu tuangalie kama mfano wetu wa kazi ⟨P ({1, 2, 3}), ⊆⟩ ni kimiani. Hakika, kwa yoyote a, b ∈ P ({1, 2, 3}), a∨b = a∪b, na a∧b = a∩b. Kwa mfano, zingatia seti {1, 2} na {1, 3} na upate infimum na supremum yao. Ikiwa tutaziingilia, tutapata seti {1}, ambayo itakuwa infimum. Tunapata supremum kwa kuzichanganya - {1, 2, 3}.

Katika algorithms ya kutambua shida za mwili, nafasi ya utaftaji mara nyingi huwakilishwa kwa namna ya kimiani, ambapo seti za kitu kimoja (soma kiwango cha kwanza cha kimiani cha utaftaji, ambapo upande wa kushoto wa utegemezi una sifa moja) huwakilisha kila sifa. ya uhusiano wa awali.
Kwanza, tunazingatia utegemezi wa fomu ∅ → Sifa moja. Hatua hii hukuruhusu kuamua ni sifa zipi ni funguo za msingi (kwa sifa kama hizo hakuna viashiria, na kwa hivyo upande wa kushoto hauna tupu). Zaidi ya hayo, algorithms kama hizo husogea juu kando ya kimiani. Ni muhimu kuzingatia kwamba sio kimiani nzima inayoweza kupitiwa, yaani, ikiwa ukubwa wa juu unaohitajika wa upande wa kushoto hupitishwa kwa pembejeo, basi algorithm haitakwenda zaidi ya kiwango na ukubwa huo.

Takwimu hapa chini inaonyesha jinsi latiti ya algebraic inaweza kutumika katika tatizo la kutafuta FZ. Hapa kila makali (X, XY) inawakilisha utegemezi X → Y. Kwa mfano, tumepita kiwango cha kwanza na tunajua kuwa uraibu unadumishwa A → B (tutaonyesha hii kama unganisho la kijani kibichi kati ya wima A и B) Hii inamaanisha kuwa zaidi, tunaposonga kando ya kimiani, hatuwezi kuangalia utegemezi A, C → B, kwa sababu haitakuwa ndogo tena. Vile vile, hatungeiangalia ikiwa utegemezi ulifanyika C → B.

Kwa kuongezea, kama sheria, algoriti zote za kisasa za kutafuta sheria za shirikisho hutumia muundo wa data kama vile kizigeu (katika chanzo asili - kizigeu kilichovuliwa [1]). Ufafanuzi rasmi wa kizigeu ni kama ifuatavyo:

Ufafanuzi 6. Acha X ⊆ R iwe seti ya sifa za uhusiano r. Kundi ni seti ya fahirisi za nakala katika r ambazo zina thamani sawa ya X, yaani, c(t) = {i|ti[X] = t[X]}. Kuhesabu ni seti ya vikundi, bila kujumuisha nguzo za urefu wa kitengo:

Kwa maneno rahisi, kizigeu cha sifa X ni seti ya orodha, ambapo kila orodha ina nambari za mstari zilizo na maadili sawa X. Katika fasihi ya kisasa, muundo unaowakilisha sehemu huitwa index ya orodha ya nafasi (PLI). Nguzo za urefu wa kitengo hazijajumuishwa kwa madhumuni ya ukandamizaji wa PLI kwa sababu ni makundi ambayo yana nambari ya rekodi pekee yenye thamani ya kipekee ambayo itakuwa rahisi kutambua kila wakati.

Hebu tuangalie mfano. Wacha turudi kwenye meza moja na wagonjwa na tujenge sehemu za nguzo Mgonjwa и Sakafu (safu mpya imeonekana upande wa kushoto, ambayo nambari za safu ya jedwali zimewekwa alama):

Kwa kuongezea, kulingana na ufafanuzi, kizigeu cha safu Mgonjwa kwa kweli itakuwa tupu, kwani nguzo moja hazijajumuishwa kwenye kizigeu.

Sehemu zinaweza kupatikana kwa sifa kadhaa. Na kuna njia mbili za kufanya hivyo: kwa kupitia meza, jenga kizigeu kwa kutumia sifa zote muhimu mara moja, au ujenge kwa kutumia makutano ya sehemu kwa kutumia sehemu ndogo ya sifa. Sheria ya shirikisho ya kutafuta algoriti hutumia chaguo la pili.

Kwa maneno rahisi, kwa, kwa mfano, kupata kizigeu kwa safu ABC, unaweza kuchukua partitions kwa AC и B (au seti nyingine yoyote ya vijisehemu vilivyotengana) na vikatishe baina ya vingine. Uendeshaji wa makutano ya partitions mbili huchagua makundi ya urefu mkubwa zaidi ambayo ni ya kawaida kwa partitions zote mbili.

Hebu tuangalie mfano:

Katika kesi ya kwanza, tulipokea kizigeu tupu. Ikiwa utaangalia kwa karibu kwenye jedwali, basi kwa kweli, hakuna maadili sawa ya sifa hizo mbili. Ikiwa tutarekebisha meza kidogo (kesi iliyo kulia), tayari tutapata makutano yasiyo tupu. Kwa kuongezea, mistari ya 1 na 2 ina maadili sawa ya sifa Sakafu и Daktari.

Ifuatayo, tutahitaji dhana kama saizi ya kizigeu. Rasmi:

Kwa ufupi, saizi ya kizigeu ni idadi ya nguzo iliyojumuishwa kwenye kizigeu (kumbuka kuwa nguzo moja hazijajumuishwa kwenye kizigeu!):

Sasa tunaweza kufafanua mojawapo ya lema muhimu, ambayo kwa kizigeu fulani huturuhusu kuamua kama utegemezi unashikiliwa au la:

Lema 1. Utegemezi A, B → C unashikilia ikiwa na tu ikiwa

Kulingana na lemma, ili kuamua ikiwa utegemezi unashikilia, hatua nne lazima zifanyike:

1. Kuhesabu kizigeu kwa upande wa kushoto wa utegemezi
2. Kuhesabu kizigeu kwa upande wa kulia wa utegemezi
3. Kuhesabu bidhaa ya hatua ya kwanza na ya pili
4. Linganisha ukubwa wa sehemu zilizopatikana katika hatua ya kwanza na ya tatu

Ifuatayo ni mfano wa kuangalia ikiwa utegemezi unashikilia kulingana na lemma hii:

Katika makala haya, tulichunguza dhana kama vile utegemezi wa utendaji kazi, takriban utegemezi wa utendaji, tuliangalia mahali zinatumika, na vile vile ni algoriti gani za kutafuta kazi za kimwili zilizopo. Pia tulichunguza kwa kina dhana za kimsingi lakini muhimu ambazo zinatumika kikamilifu katika kanuni za kisasa za kutafuta sheria za shirikisho.

Marejeleo:

1. Huhtala Y. et al. TANE: Algorithm bora ya kugundua utegemezi wa kazi na takriban // Jarida la kompyuta. - 1999. - T. 42. - No. 2. - ukurasa wa 100-111.
2. Kruse S., Naumann F. Ugunduzi unaofaa wa takriban tegemezi // Mijadala ya Wakfu wa VLDB. - 2018. - T. 11. - No. 7. - ukurasa wa 759-772.
3. Papenbrock T., Naumann F. Mbinu mseto ya ugunduzi wa utegemezi wa utendaji //Kesi za Mkutano wa Kimataifa wa 2016 wa Usimamizi wa Data. - ACM, 2016. - ukurasa wa 821-833.
4. Papenbrock T. et al. Ugunduzi wa utegemezi wa kiutendaji: Tathmini ya majaribio ya algoriti saba //Kesi za Wakfu wa VLDB. - 2015. - T. 8. - No. 10. - ukurasa wa 1082-1093.
5. Kumar A. et al. Je, unataka kujiunga au kutojiunga?: Unafikiria mara mbili kuhusu kujiunga kabla ya uteuzi wa vipengele //Kesi za Mkutano wa Kimataifa wa 2016 kuhusu Usimamizi wa Data. - ACM, 2016. - ukurasa wa 19-34.
6. Abo Khamis M. et al. Kujifunza ndani ya hifadhidata kwa kutumia tensor ndogo //Kesi za Kongamano la 37 la ACM SIGMOD-SIGACT-SIGAI kuhusu Kanuni za Mifumo ya Hifadhidata. - ACM, 2018. - ukurasa wa 325-340.
7. Hellerstein J. M. et al. Maktaba ya uchanganuzi ya MADlib: au ujuzi wa MAD, SQL //Kesi za Wakfu wa VLDB. - 2012. - T. 5. - No. 12. - ukurasa wa 1700-1711.
8. Qin C., Rusu F. Makadirio ya kubahatisha ya uboreshaji wa ukoo wa upinde rangi uliosambazwa wa terascale //Kesi za Warsha ya Nne ya uchanganuzi wa Data katika Wingu. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Kujifunza kwa mashine katika cheche za apache //Jarida la Utafiti wa Kujifunza kwa Mashine. - 2016. - T. 17. - No. 1. - ukurasa wa 1235-1241.

Waandishi wa makala: Anastasia Birillo, mtafiti katika Utafiti wa JetBrains, Mwanafunzi wa kituo cha CS и Nikita Bobrov, mtafiti katika Utafiti wa JetBrains

Chanzo: mapenzi.com