Utangulizi wa Vitegemezi vya Utendaji

Katika makala haya, tutajadili utegemezi wa kiutendaji katika hifadhidata-ni nini, zinatumika wapi, na ni algoriti zipi zilizopo za kuzipata.

Tutazingatia utegemezi wa kiutendaji katika muktadha wa hifadhidata za uhusiano. Kwa kusema, katika hifadhidata kama hizo, habari huhifadhiwa kwenye jedwali. Kuanzia hapa na kuendelea, tutatumia dhana takriban ambazo hazibadiliki katika nadharia kali ya uhusiano: tutaita jedwali yenyewe uhusiano, sifa za safu (seti zao ni schema ya uhusiano), na seti ya maadili ya safu kwenye sehemu ndogo ya sifa nakala.

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 hutosheleza FD X → Y (ambapo X, Y ⊆ R) ikiwa na tu ikiwa ni nakala zozote. , ∈ R imeridhika: ikiwa [X] = [X], basi [Y] = [Y]. Katika hali kama 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 watalingana katika sifa Y.
Sasa hebu tuchukue mambo 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

Kulingana na ufafanuzi hapo juu, ili utegemezi wa kwanza ushikilie, kila thamani ya kipekee ya safu Mgonjwa thamani ya safu wima moja pekee lazima ilingane Sakafu. Na kwa jedwali la mfano, hii ndio kesi. Walakini, haifanyi kazi kwa njia nyingine kote, ikimaanisha kuwa 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 huturuhusu kutambua uhusiano uliopo kati ya seti za sifa za jedwali. Kuanzia hapa na kuendelea, tutazingatia mahusiano ya kuvutia zaidi, au kwa usahihi, wale X → Ykwamba wao ni:

• 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 uliojadiliwa hadi sasa umekuwa mkali, ikimaanisha kuwa hauruhusu ukiukaji wowote kwenye jedwali. Walakini, pia kuna zile zinazoruhusu kutokubaliana kati ya maadili ya tuple. Vitegemezi hivi vimeainishwa katika tabaka tofauti, inayoitwa takriban, na inaruhusiwa kukiukwa na idadi fulani ya nakala. Nambari hii inatawaliwa na upeo wa juu wa kipeo cha makosa emax. Kwa mfano, kiwango cha makosa = 0.01 inaweza kumaanisha kuwa utegemezi unaweza kukiukwa na 1% ya nakala katika sifa iliyowekwa inayozingatiwa. Hiyo ni, kwa rekodi 1000, upeo wa nakala 10 zinaweza kukiuka FD. Tutazingatia kipimo tofauti kidogo, kulingana na thamani tofauti za jozi za nakala zikilinganishwa. Kwa utegemezi X → Y juu ya mtazamo r imehesabiwa kama hii:

Wacha tuhesabu kosa Daktari → Mgonjwa kutoka kwa mfano hapo juu. Tuna nakala mbili ambazo maadili yake hutofautiana kwenye sifa Mgonjwa, lakini zinapatana Daktari: [Daktari, Mgonjwa] = (Robin, Ellis) na [Daktari, Mgonjwa] = (Robin, Graham) Kufuatia ufafanuzi wa makosa, lazima tuzingatie jozi zote zinazopingana, ambayo inamaanisha kutakuwa na mbili kati yao: (, ) na ubadilishaji wake (, ) Badilisha katika fomula na upate:

Sasa hebu jaribu kujibu swali: "Ni nini maana ya haya yote?" Kwa kweli, kuna aina tofauti za FDs. Aina ya kwanza ni utegemezi unaofafanuliwa na msimamizi wakati wa awamu ya muundo wa hifadhidata. Kwa kawaida huwa chache kwa idadi, kali, na hutumika hasa kwa urekebishaji wa data na muundo wa schema wa uhusiano.

Aina ya pili ni tegemezi zinazowakilisha data "iliyofichwa" na uhusiano ambao haukujulikana hapo awali kati ya sifa. Vitegemezi hivi havikuzingatiwa katika hatua ya usanifu na hugunduliwa kwa mkusanyiko wa data uliopo, na hivyo kuturuhusu kufikia hitimisho kuhusu taarifa iliyohifadhiwa kulingana na tegemezi nyingi za utendakazi zilizotambuliwa. Haya ndiyo mategemeo tunayofanya kazi nayo. Wao ni somo la uwanja mzima unaoitwa madini ya data, na mbinu mbalimbali za utafutaji na algoriti zilizojengwa juu yao. Wacha tuchunguze jinsi utegemezi wa utendaji uliogunduliwa (halisi au takriban) katika data yoyote inaweza kuwa muhimu.

Leo, utakaso wa data ni moja ya maombi kuu ya utegemezi. Hii inahusisha kuendeleza michakato ya kutambua na kisha kurekebisha "data chafu." Mifano ya kawaida ya "data chafu" ni pamoja na nakala, hitilafu za data au uchapaji, thamani zinazokosekana, data iliyopitwa na wakati, nafasi za ziada, na kadhalika.

Mfano wa makosa ya data:

Mfano wa nakala katika data:

Kwa mfano, tuna jedwali na seti ya mahitaji ya kisheria ambayo lazima yatimizwe. Utakaso wa data katika kesi hii unahusisha kurekebisha data ili mahitaji ya kisheria yatimizwe. Idadi ya marekebisho inapaswa kuwa ndogo (kuna algorithms maalum ya utaratibu huu, ambayo hatutazingatia katika makala hii). Chini ni mfano wa mabadiliko kama haya ya data. Upande wa kushoto ni uhusiano wa awali, ambao kwa wazi haukidhi mahitaji ya kisheria yanayohitajika (mfano wa ukiukaji wa mojawapo ya mahitaji ya kisheria umeonyeshwa kwa rangi nyekundu). Upande wa kulia ni uhusiano uliosasishwa, ambapo seli za kijani zinaonyesha maadili yaliyobadilishwa. Baada ya utaratibu huu, utegemezi muhimu ulihifadhiwa.

Programu nyingine maarufu ni muundo wa hifadhidata. Hapa, inafaa kutaja fomu za kawaida na kuhalalisha. Kawaida ni mchakato wa kuzingatia uhusiano na seti ya mahitaji, ambayo kila mmoja hufafanuliwa na fomu ya kawaida kwa njia yake mwenyewe. Hatutaelezea mahitaji ya aina mbalimbali za kawaida (hii inaweza kufanywa katika kozi ya hifadhidata ya anayeanza), lakini tutatambua tu kwamba kila moja hutumia dhana ya utegemezi wa utendaji kwa njia yake mwenyewe. Baada ya yote, fomu za kawaida kimsingi ni vikwazo vya uadilifu ambavyo huzingatiwa wakati wa kubuni hifadhidata (katika muktadha huu, fomu za kawaida wakati mwingine huitwa funguo kuu).

Hebu tuchunguze maombi yao kwa fomu nne za kawaida katika takwimu hapa chini. Kumbuka kwamba fomu ya kawaida ya Boyce-Codd ina vikwazo zaidi kuliko fomu ya tatu, lakini ina vikwazo kidogo kuliko ya nne. Hatutazingatia kidato cha nne kwa sasa, kwani uundaji wake unahitaji uelewa wa mambo tegemezi yenye thamani nyingi, ambayo hayatuvutii katika makala haya.

Eneo lingine ambalo utegemezi umepata programu ni upunguzaji wa ukubwa wa nafasi katika matatizo kama vile kuunda kiainishaji cha Bayes, kutoa vipengele muhimu, na kurekebisha miundo ya urejeleaji. Katika karatasi asili, tatizo hili linarejelewa kama upungufu wa kipengele na umuhimu wa kipengele [5, 6], na linashughulikiwa kwa matumizi makubwa ya dhana za hifadhidata. Kwa kuibuka kwa kazi kama hizo, tunaweza kuhitimisha kuwa kuna mahitaji yanayokua ya suluhu zinazochanganya hifadhidata, uchanganuzi, na utekelezaji wa shida zilizotajwa hapo juu za uboreshaji katika zana moja [7, 8, 9].

Kuna algoriti nyingi (za kisasa na za zamani) za kutafuta sheria za shirikisho katika mkusanyiko wa data. Algorithms hizi zinaweza kugawanywa katika vikundi vitatu:

• Algorithms ya kuvuka ya kimiani
• Tofauti- na kukubaliana-kuweka algoriti
• Algorithms ya uanzishaji wa utegemezi

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


Maelezo zaidi juu ya uainishaji huu yanaweza kupatikana katika [4]. Mifano ya algorithms kwa kila aina imewasilishwa hapa chini:

Algorithms mpya kwa sasa zinaibuka ambazo zinachanganya mbinu kadhaa za kutafuta utegemezi wa utendaji. Mifano ya algoriti kama hizo ni pamoja na Pyro [2] na HyFD [3]. Uchambuzi wa uendeshaji wao unatarajiwa katika makala zinazofuata katika mfululizo huu. Katika makala haya, tutajadili tu dhana za kimsingi na lema zinazohitajika ili kuelewa mbinu za kugundua utegemezi.

Hebu tuanze na rahisi zaidi: tofauti na seti za kukubaliana, zinazotumiwa katika aina ya pili ya algorithm. Seti tofauti ni seti ya nakala ambazo hazina thamani sawa, wakati seti ya makubaliano ni seti ya nakala ambazo zina thamani sawa. Ni muhimu kuzingatia kwamba katika kesi hii, tunazingatia tu upande wa kushoto wa utegemezi.

Dhana nyingine muhimu iliyotajwa hapo juu ni kimiani cha aljebra. Kwa kuwa algorithms nyingi za kisasa zinategemea dhana hii, tunahitaji kuelewa ni nini.

Ili kuanzisha dhana ya kimiani, ufafanuzi wa seti iliyopangwa kwa sehemu (au poset kwa kifupi) inahitajika.

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

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 huo unaitwa utaratibu wa sehemu (usio mkali), na seti yenyewe inaitwa seti iliyoagizwa kwa sehemu. Nukuu rasmi: ⟨S, ⩽⟩.

Kama mfano rahisi 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 muhimu zaidi. Zingatia seti ya vikundi vyote vidogo vya {1, 2, 3}, vilivyopangwa kwa uhusiano wa kujumuisha ⊆. Hakika, uhusiano huu unakidhi masharti yote ya mpangilio usio kamili, kwa hivyo ⟨P ({1, 2, 3}), ⊆⟩ ni seti iliyopangwa kwa kiasi. Takwimu hapa chini inaonyesha muundo wa seti hii: ikiwa kipengele kimoja kinaweza kufikiwa kutoka kwa kipengele kingine kwa kufuata mishale, basi ni katika uhusiano wa kuagiza.

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

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

Wazo la kikomo cha chini kabisa huletwa kwa njia sawa.

Ufafanuzi 4. Acha ⟨S, ⩽⟩ iwe seti iliyopangwa kwa kiasi, A ⊆ S. Kipaji cha chini cha A ni kipengele l ∈ S hivi kwamba ∀x ∈ S: l ⩽ x. Acha L iwe seti ya mipaka yote ya chini ya S. Ikiwa L ina kipengele kikuu zaidi, basi inaitwa infimum na inaonyeshwa na inf A.

Hebu tuzingatie kama mfano seti iliyoagizwa kwa kiasi ⟨P ({1, 2, 3}), ⊆⟩ iliyotolewa hapo juu na tupate supremum na infimum ndani yake:

Sasa tunaweza kuunda ufafanuzi wa kimiani cha algebraic.

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

Hebu tuangalie kama mfano wetu uliofanya kazi ⟨P ({1, 2, 3}), ⊆⟩ ni kimiani. Hakika, kwa kila 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, tunapata seti {1}, ambayo ni infimum. Kiwango cha juu kinapatikana kwa muungano wao: {1, 2, 3}.

Katika algorithms ya kugundua FDs, 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 asili.
Mwanzoni, utegemezi wa aina ∅ → huzingatiwa Sifa moja. Hatua hii huturuhusu kubainisha ni sifa zipi ambazo ni funguo msingi (hakuna vibainishi vya sifa hizo, kwa hivyo upande wa kushoto hauna kitu). Algorithms hizi basi husogea juu kando ya kimiani. Inafaa kumbuka kuwa kimiani nzima inaweza kupitiwa, ikimaanisha kuwa ikiwa saizi ya juu inayohitajika ya upande wa kushoto itapitishwa kama pembejeo, algoriti haitaendelea zaidi ya kiwango na saizi hiyo.

Kielelezo hapa chini kinaonyesha jinsi kimiani cha aljebra kinaweza kutumika katika tatizo la kutafuta FD. Hapa, kila makali (X, XY) ni tegemezi X → YKwa 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 ina maana kwamba zaidi, tunaposonga juu ya gridi ya taifa, hatuwezi kuangalia utegemezi A, C → B, kwa sababu haitakuwa ndogo tena. Vile vile, hatungeiangalia ikiwa utegemezi ulifanyika. C → B.

Zaidi ya hayo, kama sheria, algoriti zote za kisasa za kutafuta sheria za shirikisho hutumia muundo wa data unaojulikana kama kizigeu (katika chanzo asili, kizigeu kilichovuliwa [1]). Ufafanuzi rasmi wa kizigeu ni kama ifuatavyo:

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

Kwa maneno rahisi, kizigeu cha sifa X ni seti ya orodha ambapo kila orodha ina nambari za safu mlalo zenye thamani sawa za XKatika fasihi ya kisasa, muundo unaowakilisha sehemu huitwa faharisi ya orodha ya msimamo (PLI). Nguzo za urefu wa moja hazijumuishwi kwa madhumuni ya kubana kwa PLI kwa sababu nguzo hizi zina nambari ya rekodi pekee yenye thamani ya kipekee ambayo itatambuliwa kwa urahisi kila wakati.

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

Katika kesi hii, kulingana na ufafanuzi, kizigeu cha safu Mgonjwa kwa kweli itakuwa tupu, kwani nguzo moja hazijajumuishwa kwenye kizigeu.

Sehemu zinaweza kupatikana kwa sifa nyingi. Kuna njia mbili za kufanya hivi: kwa kurudia kupitia jedwali, kujenga kizigeu kwa sifa zote zinazohitajika mara moja, au kwa kuingiliana kwa sehemu na sehemu ndogo ya sifa. Sheria ya shirikisho ya kutafuta algoriti hutumia chaguo la pili.

Kwa maneno rahisi, kupata, kwa mfano, kizigeu kwa safu ABC, unaweza kuchukua partitions kwa AC и B (au seti nyingine yoyote ya vijisehemu vilivyotengana) na vikatishe. Uendeshaji wa makutano ya sehemu mbili hutambua nguzo ndefu zaidi zinazojulikana kwa sehemu zote mbili.

Hebu tuangalie mfano:

Katika kesi ya kwanza, tulipata kizigeu tupu. Ukiangalia kwa karibu kwenye jedwali, utaona kuwa kwa kweli hakuna maadili sawa ya sifa hizo mbili. Walakini, ikiwa tutarekebisha meza kidogo (kesi iliyo kulia), tunapata makutano yasiyo tupu. Zaidi ya hayo, safu mlalo za 1 na 2 zina thamani zinazofanana za sifa. Sakafu и Daktari.

Ifuatayo, tutahitaji dhana ya 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 ambazo, kwa sehemu fulani, huturuhusu kuamua ikiwa 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 fulani:

Katika makala haya, tulichunguza dhana kama vile utegemezi wa kiutendaji na takriban utegemezi wa utendaji, tukajadili matumizi yao, na tukajadili kanuni zilizopo za kutafuta utegemezi wa kiutendaji. Pia tuliangazia kwa kina dhana za kimsingi, lakini muhimu, zinazotumiwa kikamilifu katika algoriti za kisasa kutafuta tegemezi za kiutendaji.

Marejeleo:

1. Huhtala Y. et al. TANE: Algorithm bora ya kugundua utegemezi wa kazi na takriban // Jarida la kompyuta. - 1999. - T. 42. - Nambari 2. - ukurasa wa 100-111.
2. Kruse S., Naumann F. Ugunduzi unaofaa wa takriban tegemezi // Mijadala ya Wakfu wa VLDB. - 2018. - T. 11. - Nambari 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. - Nambari 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 //Mijadala ya 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 JM et al. Maktaba ya uchanganuzi ya MADlib: au ujuzi wa MAD, SQL //Kesi za Wakfu wa VLDB. - 2012. - T. 5. - Nambari 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. - Nambari 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