NĂ« kĂ«tĂ« artikull do tĂ« flasim pĂ«r varĂ«sitĂ« funksionale nĂ« bazat e tĂ« dhĂ«nave â çfarĂ« janĂ«, ku pĂ«rdoren dhe cilat algorithme ekzistojnĂ« pĂ«r t'i gjetur ato.
Do ta shqyrtojmĂ« varĂ«sinĂ« funksionale nĂ« kontekstin e bazave tĂ« tĂ« dhĂ«nave relacional. NĂ«se flasim shumĂ« thjesht, nĂ« kĂ«to baza tĂ« dhĂ«nash, informacionet ruhen nĂ« formĂ«n e tabelave. MĂ« pas, do tĂ« pĂ«rdorim konceptet afĂ«r tĂ« cilat nĂ« teorinĂ« strikte relacionale nuk janĂ« tĂ« ndĂ«rrueshme: tabelĂ«n vetĂ« do ta quajmĂ« relacion, kolumnat â atributet (grupi i tyre â skema e relacionit), dhe grupin e vlerave tĂ« rreshtit nĂ« njĂ« nĂ«ngrup tĂ« Attributeve â tupiz.
Për shembull, në tabelën e mësipërme, (Benson, M, M organ) është një tupiz mbi atributet (Pacienti, Gjinia, Mjeku).
Më formalisht, kjo shkruhet në mënyrën e mëposhtme: 
[Pacienti, Gjinia, Mjeku] = (Benson, M, M organ).
Tani mund të futim konceptin e varësisë funksionale (VF):
Definicioni 1. Relacioni R plotĂ«son VF X â Y (ku X, Y â R) atĂ«herĂ« dhe vetĂ«m atĂ«herĂ« kur pĂ«r çdo tupiz 
, 
â R Ă«shtĂ« e vĂ«rtetĂ«: nĂ«se 
[X] = 
[X], atëherë 
[Y] = 
[Y]. Në këtë rast, thuhet se X (determinant, ose grupi përcaktues i atributeve) përcakton funksionalisht Y (grupi i varur).
Me fjalĂ« tĂ« tjera, pranimi i VF X â Y do tĂ« thotĂ« se nĂ«se kemi dy tupizĂ« nĂ« R dhe ato pĂ«rputhen mbi atributet X, atĂ«herĂ« ato do tĂ« pĂ«rputhen edhe mbi atributet Y.
Tani, në rend. Le të shqyrtojmë atributet Pacienti dhe Gjinia për të cilat duam të dimë nëse ekzistojnë varësi midis tyre apo jo. Për këtë grup atributesh mund të ekzistojnë varësitë e mëposhtme:
- Pacienti â Gjinia
- Gjinia â Pacienti
Sipas definicionit tĂ« mĂ«sipĂ«rm, pĂ«r tĂ« mbajtur varĂ«sinĂ« e parĂ«, çdo vlerĂ« unike tĂ« kolumnĂ«s Pacienti duhet t'i korrespondonte vetĂ«m njĂ« vlerĂ« tĂ« kolumnĂ«s Gjinia. Dhe pĂ«r tabelĂ«n-shembull, kjo Ă«shtĂ« vĂ«rtet kĂ«shtu. MegjithatĂ«, nĂ« anĂ«n tjetĂ«r, kjo nuk funksionon, domethĂ«nĂ« varĂ«sia e dytĂ« nuk pĂ«rmbushet, dhe atributi Gjinia nuk Ă«shtĂ« njĂ« determinant pĂ«r Pacientin. Po ashtu, nĂ«se marrim varĂ«sinĂ« Mjeku â Pacienti, mund tĂ« vĂ«rejmĂ« se ajo shkelet, pasi vlera Robin nĂ« kĂ«tĂ« atribut ka disa vlera tĂ« ndryshme â Ellis dhe Graham.
KĂ«shtu, varĂ«sitĂ« funksionale lejojnĂ« pĂ«rcaktimin e lidhjeve ekzistuese mes grupeve tĂ« atributeve tĂ« tabelĂ«s. Prandaj, nga tani e tutje, ne do tĂ« shqyrtojmĂ« lidhjet mĂ« interesante, konkretisht ato X â Y, tĂ« cilat janĂ«:
- jo triviale, domethĂ«nĂ« ana e djathtĂ« e varĂ«sisĂ« nuk Ă«shtĂ« nĂ«ngrup i majtĂ«s (Y Ìžâ X);
- minimale, domethĂ«nĂ« nuk ka njĂ« varĂ«si tĂ« tillĂ« Z â Y, qĂ« Z â X.
Varësitë e shqyrtuara deri tani ishin të rrepta, domethënë nuk parashikonin asnjë shkelje në tabelë, por përveç tyre ka edhe të tilla që lejojnë disa mosmarrëveshje mes vlerave të turmave. Këto varësi nxirren në një klasë të veçantë, quhen afërsisht dhe u lejohet të shkelin në një numër të caktuar turmash. Ky numër rregullohet nga treguesi i gabimit maksimal emax. Për shembull, pesha e gabimit 
= 0.01 mund tĂ« nĂ«nkuptojĂ« se varĂ«sia mund tĂ« shkelet nĂ« 1% tĂ« turmave ekzistuese nĂ« grupin e atributeve tĂ« shqyrtuara. DomethĂ«nĂ« pĂ«r 1000 regjistrime, maksimumi 10 turma mund tĂ« shkelin FZ. Ne do tĂ« shqyrtojmĂ« njĂ« metrikĂ« pak mĂ« tĂ« ndryshme, tĂ« bazuar nĂ« vlerat nĂ« çift tĂ« turmave qĂ« po krahasohen. PĂ«r varĂ«sinĂ« X â Y nĂ« raport r ajo llogaritet kĂ«shtu:
TĂ« llogarisim gabimin pĂ«r Mjeku â Pacienti nga shembulli mĂ« sipĂ«r. Kemi dy turma, vlerat e tĂ« cilave ndryshojnĂ« nĂ« atributin Pacienti, por bien dakord nĂ« Doktorin: 
[Doktor, Pacienti] = (Robin, Ellis) dhe 
[Doktor, Pacienti] = (Robin, Graham). Duke ndjekur definicionin e gabimit, ne duhet të marrim parasysh të gjitha çiftet konfliktuese, dhe kështu do të kemi dy: (
, 
) dhe invertimi i saj (
, 
). Të futim në formulë dhe të marrim:
Tani le tĂ« pĂ«rpiqemi tĂ« pĂ«rgjigjemi nĂ« pyetjen: "Pse na duhen kĂ«to tĂ« gjitha?" NĂ« tĂ« vĂ«rtetĂ«, FZ-tĂ« janĂ« tĂ« ndryshme. Lloji i parĂ« Ă«shtĂ« ai varĂ«si qĂ« pĂ«rcaktohet nga administratori nĂ« fazĂ«n e projektimit tĂ« bazĂ«s sĂ« tĂ« dhĂ«nave. Zakonisht janĂ« pak, ato janĂ« tĂ« rrepta, dhe pĂ«rdorimi kryesor â normalizimi i tĂ« dhĂ«nave dhe dizajni i skemĂ«s sĂ« raportit.
Lloji i dytë është varësitë, të cilat paraqesin të dhëna "të fshehura" dhe lidhje të panjohura më parë midis atributeve. Kjo do të thotë se për këto varësi nuk mendohej në momentin e projektimit dhe ato gjenden tashmë për një grup të dhënash të caktuar, në mënyrë që më pas, mbi bazën e shumë varësive të zbuluara, të bëhen disa përfundime mbi informacionin e ruajtur. Pikërisht me këto varësi ne punojmë. Një fushë e tërë e datamining merret me to, me teknika të ndryshme kërkimi dhe algoritme të ndërtuara mbi to. Le të shqyrtojmë se si mund të jenë të dobishme varësitë funksionale të gjetura (të sakta ose të afërta) në disa të dhëna.
Sot, ndër fushat kryesore të aplikimit të varësive, spikasin pastrimi i të dhënave. Ky proces përfshin zhvillimin e proceseve për identifikimin e "të dhënave të ndotura" me pastrimin e tyre të mëvonshëm. Disa përfaqësues të shquar të "të dhënave të ndotura" janë dublikatet, gabimet në të dhëna apo shtypjet e gabuara, vlerat e humbura, të dhënat e vjetra, hapësirat e tepërta dhe kështu me radhë.
Shembulli i një gabimi në të dhëna:
Shembulli i dublikateve në të dhëna:
Për shembull, ne kemi një tabelë dhe një grup rregullash funksionale që duhet të realizohen. Pastrimi i të dhënave në këtë rast nënkupton të ndryshojmë të dhënat në mënyrë që rregullat funksionale të bëhen të sakta. Në këtë rast, numri i modifikimeve duhet të jetë minimal (për këtë procedurë ekzistojnë algoritme të caktuara, për të cilat nuk do të fokusohemi në këtë artikull). Më poshtë është një shembull i tillë i transformimit të të dhënave. Majtas është marrëdhënia fillestare, në të cilën, sigurisht, nuk përmbushen rregullat e nevojshme (me ngjyrë të kuqe është theksuar një shembull i shkeljes së një nga rregullave). Nga ana e djathtë është paraqitur marrëdhënia e përditësuar, në të cilën kutitë e gjelbërta tregojnë vlerat e modifikuara. Pas kryerjes së kësaj procedure, varësitë e nevojshme u mbajtën.
Një fushë tjetër e zakonshme përdorimi është dizajni i bazës së të dhënave. Këtu është e rëndësishme të përmendim format normale dhe normalizimin. Normalizimi është procesi i përshtatjes së një relacioni në përputhje me një set kërkesash, secila prej të cilave përcaktohet në mënyrë të veçantë nga një format normal. Nuk do të detajojmë kërkesat e formave të ndryshme normale (kjo bëhet në çdo libër për kursin e DB për fillestarët), por thjesht do të theksojmë se secila prej tyre përdor në mënyrë të veçantë konceptin e varësive funksionale. Në fund të fundit, varësitë funksionale (VF) janë në thelb kufizime të integritetit që merren parasysh gjatë projektimit të bazës së të dhënave (në kontekstin e kësaj detyre, VF ndonjëherë quhen superçelësa).
Le të shqyrtojmë aplikimin e tyre për katër forma normale në figurën më poshtë. Të kujtojmë se forma normale e Boyce-Codd është më e rreptë se forma e tretë, por më pak e rreptë se forma e katërt. Formën e fundit nuk po e shqyrtojmë ende, pasi për ta vënë në praktikë nevojitet kuptimi i varësive shumëshkallëshe, të cilat në këtë artikull nuk janë të interesit tonë.
Një tjetër fushë ku varësitë kanë gjetur përdorim është ulja e dimensionalitetit të hapësirës së veçorive në probleme të tilla si ndërtimi i klasifikuesit naive bayesian, identifikimi i veçorive të rëndësishme dhe riparametrizimi i modelit regresiv. Në artikujt origjinalë, kjo detyrë quhet përcaktimi i veçorive të tepërta (feature redundancy) dhe të përputhshme (feature relevancy) [5, 6], dhe zgjidhet me përdorimin aktiv të koncepteve të bazës së të dhënave. Me shfaqjen e këtyre veprave, mund të flasim për një kërkesë për zgjidhje që lejojnë bashkimin e bazës së të dhënave, analizës dhe realizimin e problemeve të mësipërme të optimizimit në një mjet të vetëm [7, 8, 9].
Për të kërkuar varësitë funksionale në një grup të dhënash ekzistojnë shumë algoritma (si të rinj, ashtu edhe të vjetër). Këta algoritma mund të ndahen në tre grupe:
- Algoritmat që përdorin kalimin përmes rrjeteve algebraike (Lattice traversal algorithms)
- Algoritmat që bazohen në kërkimin e vlerave të pajtueshme (Difference- and agree-set algorithms)
- Algoritmat që bazohen në krahasime çift pas çifti (Dependency induction algorithms)
Një përshkrim të shkurtër të çdo lloji algoritmi është paraqitur në tabelën më poshtë:
Më shumë për këtë klasifikim mund të lexoni [4]. Më poshtë janë paraqitur shembuj algoritmesh për çdo një nga llojet:
Aktualisht po shfaqen algoritma të rinj që kombinon disa qasje për të gjetur varësitë funksionale. Shembuj të tillë algoritmash janë Pyro [2] dhe HyFD [3]. Analiza e funksionimit të tyre parashikohet në artikujt e ardhshëm të këtij cikli. Në këtë artikull, do të shqyrtojmë vetëm konceptet kryesore dhe lemën që nevojiten për të kuptuar teknikat e identifikimit të varësive.
TĂ« fillojmĂ« me tĂ« thjeshtĂ«n â diferencĂ« dhe set tĂ« ra, tĂ« pĂ«rdorura nĂ« llojin e dytĂ« tĂ« algoritmave. Seti i diferencĂ«s pĂ«rfaqĂ«son njĂ« grup tĂ« tupleve qĂ« nuk korrespondojnĂ« me vlerat, ndĂ«rsa seti i ra Ă«shtĂ« pĂ«rkundrazi â tuple qĂ« korrespondojnĂ« me vlerat. Duhet tĂ« theksohet se nĂ« kĂ«tĂ« rast ne shqyrtojmĂ« vetĂ«m pjesĂ«n e majtĂ« tĂ« varĂ«sisĂ«.
Një koncept tjetër të rëndësishëm që u përmend më lart është rrjeti algebraik. Duke qenë se shumë algoritma moderne operojnë me këtë koncept, na nevojitet një ide se çfarë është ai.
PĂ«r tĂ« futur konceptin e rrjetit, nevojitet njĂ« pĂ«rkufizim i grupit tĂ« pjesĂ«risht renditur (ose grup i pjesĂ«risht renditur, shkurtimisht â poset).
PĂ«rkufizimi 2. NjĂ« grup S quhet i pjesĂ«risht renditur nga njĂ« marrĂ«dhĂ«nie binare â©œ, nĂ«se pĂ«r çdo a, b, c â S janĂ« tĂ« vlefshme kĂ«to prona:
- Refleksiviteti, pra a ⩜ a
- Antisimetri, pra, nĂ«se a â©œ b dhe b â©œ a, atĂ«herĂ« a = b
- Transitiviteti, pra pĂ«r a â©œ b dhe b â©œ c, duhet qĂ« a â©œ c
Kjo marrĂ«dhĂ«nie quhet marrĂ«dhĂ«nie (jo-strikt) e renditjes sĂ« pjesshme, dhe grupi vetĂ« Ă«shtĂ« njĂ« grup i renditur pjesĂ«risht. Shenja formale: âšS, â©œâ©.
Si njĂ« shembull tĂ« thjeshtĂ« tĂ« njĂ« grupi tĂ« renditur pjesĂ«risht, mund tĂ« marrim grupin e tĂ« gjithĂ« numrave natyrorĂ« N me marrĂ«dhĂ«nien e zakonshme tĂ« rendit â©œ. Nuk Ă«shtĂ« e vĂ«shtirĂ« tĂ« verifikohet se tĂ« gjitha aksiomat e nevojshme pĂ«rmbushen.
NjĂ« shembull mĂ« informues. Le tĂ« shqyrtojmĂ« grupin e tĂ« gjitha nĂ«ngrupeve {1, 2, 3}, tĂ« renditura nga marrĂ«dhĂ«nia e pĂ«rfshirjes â. VĂ«rtet, kjo marrĂ«dhĂ«nie pĂ«rmbush tĂ« gjitha kushtet e rendit tĂ« pjesshĂ«m, prandaj âšP ({1, 2, 3}), ââ© â Ă«shtĂ« njĂ« grup i renditur pjesĂ«risht. NĂ« figurĂ«n mĂ« poshtĂ« Ă«shtĂ« pĂ«rshkruar struktura e kĂ«tij grupi: nĂ«se nga njĂ« element mund tĂ« arrihet me arrow nĂ« njĂ« tjetĂ«r element, atĂ«herĂ« ata janĂ« nĂ« marrĂ«dhĂ«nie rendit.
Na nevojiten edhe dy pĂ«rkufizime tĂ« thjeshta nga fusha e matematikĂ«s â supremum (supremum) dhe infimum (infimum).
PĂ«rkufizimi 3. Le tĂ« supozojmĂ« âšS, ⩜⩠â njĂ« grup tĂ« pjesĂ«risht renditur, A â S. Kufiri i sipĂ«rm i A Ă«shtĂ« njĂ« element u â S, e tillĂ« qĂ« pĂ«r çdo x â S: x â©œ u. Le tĂ« konsiderojmĂ« U â grupin e tĂ« gjithĂ« kufijve tĂ« sipĂ«rm tĂ« S. NĂ«se nĂ« U ekziston njĂ« element mĂ« i vogĂ«l, atĂ«herĂ« ai quhet supremum dhe shĂ«nohet si sup A.
Në mënyrë të ngjashme, prezantohet koncepti i kufirit të saktë të poshtëm.
PĂ«rkufizimi 4. Le tĂ« supozojmĂ« âšS, ⩜⩠â njĂ« grup tĂ« pjesĂ«risht renditur, A â S. Kufiri i poshtĂ«m i A Ă«shtĂ« njĂ« element l â S, e tillĂ« qĂ« pĂ«r çdo x â S: l â©œ x. Le tĂ« konsiderojmĂ« L â grupin e tĂ« gjithĂ« kufijve tĂ« poshtĂ«m tĂ« S. NĂ«se nĂ« L ekziston njĂ« element tĂ« madh, atĂ«herĂ« ai quhet infimum dhe shĂ«nohet si inf A.
TĂ« shqyrtojmĂ« si shembull grupin e sipĂ«rm tĂ« renditur âšP ({1, 2, 3}), ââ© dhe tĂ« gjejmĂ« nĂ« tĂ« supremum dhe infimum:
Tani mund të formulojmë përkufizimin e grupit algebraik.
PĂ«rkufizimi 5. Le tĂ« supozojmĂ« âšP, ⩜⩠â njĂ« grup tĂ« pjesĂ«risht renditur, i tillĂ« qĂ« çdo nĂ«ngrup dy-elementĂ«sh ka kufij tĂ« saktĂ« tĂ« sipĂ«rm dhe tĂ« poshtĂ«m. AtĂ«herĂ« P quhet grup algebraik. NĂ« kĂ«tĂ« rast, sup{x, y} shĂ«nohet si x âš y, dhe inf {x, y} â si x ⧠y.
Le tĂ« kontrollojmĂ« se shembulli ynĂ« pune âšP ({1, 2, 3}), ââ© Ă«shtĂ« grup. NĂ« tĂ« vĂ«rtetĂ«, pĂ«r çdo a, b â P ({1, 2, 3}), aâšb = aâȘb, dhe aâ§b = aâ©b. PĂ«r shembull, le tĂ« shqyrtojmĂ« grupet {1, 2} dhe {1, 3} dhe tĂ« gjejmĂ« infimum dhe supremum tĂ« tyre. NĂ«se i ndĂ«rpresim, do tĂ« marrim grupin {1}, i cili do tĂ« jetĂ« infimumi. Supremumi do tĂ« marrim duke i bashkuar â {1, 2, 3}.
Në algoritmet e identifikimit të FZ, hapësira e kërkimit shpesh paraqitet në formën e një grupi, ku grupe prej një elementi (lexo niveli i parë i grupit të kërkimit, ku ana e majtë e varësive përbëhet nga një atribut) përfaqësojnë secilin atribut të marrëdhënies fillestare.
Fillimisht shqyrtohen varĂ«sitĂ« e tilla si â
â Atribut i vetĂ«m. Ky hap lejon tĂ« pĂ«rcaktohet se cilĂ«t atribute janĂ« çelĂ«sat primarĂ« (pĂ«r ata atribute nuk ka determinante, dhe pĂ«r kĂ«tĂ« arsye ana e majtĂ« Ă«shtĂ« e zbrazĂ«t). MĂ« pas, algoritmet e tilla lĂ«vizin lart pĂ«rmes grupit. Duke pasur parasysh se grupi mund tĂ« anashkalohet, nĂ«se i jepni njĂ« madhĂ«si maksimale tĂ« dĂ«shiruar tĂ« anĂ«s sĂ« majtĂ«, algoritmi nuk do tĂ« vazhdojĂ« mĂ« tej se niveli me atĂ« madhĂ«si.
NĂ« figurĂ«n mĂ« poshtĂ« tregohet si mund tĂ« pĂ«rdoret grila algebrike nĂ« detyrĂ«n e kĂ«rkimit tĂ« FZ. KĂ«tu çdo skaj (X, XY) pĂ«rfaqĂ«son njĂ« varshmĂ«ri X â Y. PĂ«r shembull, ne kaluam nivelin e parĂ« dhe dimĂ« se mbahet varshmĂ«ria A â B (tĂ« cilĂ«n e paraqesim me lidhje tĂ« gjelbra midis kulmave A dhe B). KĂ«shtu, kur do tĂ« pĂ«rparojmĂ« nĂ« grilĂ« lart, ne mund tĂ« mos kontrollojmĂ« varshmĂ«rinĂ« A, C â B, sepse ajo do tĂ« jetĂ« tashmĂ« jo minimale. Po ashtu, ne nuk do ta kontrollonim, nĂ«se do tĂ« mbahej varshmĂ«ria C â B.
PĂ«r mĂ« tepĂ«r, zakonisht, tĂ« gjithĂ« algoritmĂ«t modernĂ« pĂ«r kĂ«rkimin e FZ pĂ«rdorin njĂ« strukturĂ« tĂ« dhĂ«nash si partitĂ« (nĂ« burim â stripped partition [1]). PĂ«rkufizimi formal i njĂ« partie Ă«shtĂ« si mĂ« poshtĂ«:
PĂ«rkufizimi 6. Le tĂ« jetĂ« X â R â njĂ« grup atributesh pĂ«r marrĂ«dhĂ«nien r. Klastri pĂ«rfaqĂ«son njĂ« grup indeksesh tuple nga r, tĂ« cilat kanĂ« vlera tĂ« njĂ«jta pĂ«r X, dmth c(t) = {i|ti[X] = t[X]}. Partita pĂ«rfaqĂ«son njĂ« grup klasrish, duke pĂ«rjashtuar klastrimet e gjatĂ«si njĂ«si:
Me fjalë të thjeshta, partida për atributin X përfaqëson një grup listash, ku çdo listë përmban numrat e rreshtave me vlera të njëjta për X. Në literaturën moderne, struktura që përfaqëson partitë quhet position list index (PLI). Klastrit e gjatësi njësi përjashtohen për qëllime kompresimi të PLI, sepse këto janë klastra që përmbajnë vetëm numrin e regjistrimit me vlerë unike, e cila gjithmonë do të jetë e lehtë për t'u përcaktuar.
Le të shqyrtojmë një shembull. Të kthehemi te e njëjta tavolinë me pacientë dhe të ndërtomë partitë për kolona Pacienti dhe Gjinia (në të majtë është shfaqur një kolonë e re, ku janë shënuar numrat e rreshtave të tavolinës):
Sipas përkufizimit, partia për kolonën Pacienti në fakt do të jetë e zbrazët, pasi klasrat e vetme përjashtohen nga partia.
Partitë mund të fitohet mbi disa atribute. Dhe për këtë ekzistojnë dy rrugë: duke kaluar përmes tavolinës, ndërtimi i një partie menjëherë për të gjithë atributet e nevojshme, ose ndërtimi i saj me anë të operacionit të ndërsektimit të partive mbi një nëngrup atributesh. Algoritmët për kërkimin e FZ përdorin variantin e dytë.
Me fjalë të thjeshta, për të marrë një parti për kolona ABC, mund të merret partitë për AC dhe B (ose grupesh të tjera të papërshtatshme) dhe t'i ndërthurim ato. Operacioni i ndërthurjes së dy grupeve identifikon klastra me gjatësi maksimale të përbashkët për të dy grupet.
Le të shqyrtojmë një shembull:
Në rastin e parë morëm një grup të zbrazët. Nëse e shohim tabelën, do të shohim që nuk ka vlera të njëjta për dy atribute. Nëse modifikojmë pak tabelën (rastin në të djathtë), do të marrim një ndërthurje jo të zbrazët. Në këtë rast, rreshtat 1 dhe 2 vërtet përmbajnë vlera të njëjta për atributet. Gjinia dhe Doktori.
Më pas do na nevojitet një koncept i tillë si madhësia e grupit. Formalisht:
Thjesht, madhësia e grupit përfaqëson numrin e klastrave që hynë në grup (kujtojmë se klastrat e vetme nuk hyjnë në grup!):
Tani mund të përcaktojmë një nga lemën kyçe, e cila për grupet e caktuara lejon të vendosim nëse mbahen varësitë apo jo:
Lema 1. VarĂ«sia A, B â C mbahet, nĂ«se dhe vetĂ«m nĂ«se
Sipas lemës, për të përcaktuar nëse mbahen varësitë, është e nevojshme të kryhen katër hapa:
- Të llogaritë grupin për anën e majtë të varësisë
- Të llogaritë grupin për anën e djathtë të varësisë
- Të llogaritë produktin e hapat e parë dhe të dytë
- Të krahasohet madhësia e grupeve që u morën në hapin e parë dhe të tretë
Më poshtë është një shembull i verifikimit nëse varësia mbahet sipas kësaj lemë:
Në këtë artikull shqyrtuam konceptet si varësia funksionale, varësia funksionale e afërt, shqyrtova se ku përdoren ato, si dhe cilat algoritmo për gjetjen e varësive funksionale ekzistojnë. Po ashtu, shqyrtuam në detaje konceptet bazë, por të rëndësishme, që përdoren në algoritmet moderne për gjetjen e varësive funksionale.
Lidhje me literaturën:
- Huhtala Y. et al. TANE: NjĂ« algoritĂ«m efikas pĂ«r zbulimin e varĂ«sive funksionale dhe tĂ« pĂ«rafĂ«rta //Revista kompjuterike. â 1999. â T. 42. â Nr. 2. â fq. 100-111.
- Kruse S., Naumann F. Zbulimi efikas i varĂ«sive tĂ« pĂ«rafĂ«rta //Proceedings of the VLDB Endowment. â 2018. â T. 11. â Nr. 7. â fq. 759-772.
- Papenbrock T., Naumann F. NjĂ« qasje hibrid pĂ«r zbulimin e varĂ«sive funksionale //Proceedings of the 2016 KonferencĂ«s NdĂ«rkombĂ«tare mbi Menaxhimin e tĂ« DhĂ«nave. â ACM, 2016. â fq. 821-833.
- Papenbrock T. et al. Zbulimi i varĂ«sive funksionale: NjĂ« vlerĂ«sim eksperimentues i shtatĂ« algoritmove //Proceedings of the VLDB Endowment. â 2015. â T. 8. â Nr. 10. â fq. 1082-1093.
- Kumar A. et al. TĂ« bashkĂ«ngjitemi apo jo?: TĂ« mendojmĂ« dy herĂ« pĂ«r bashkimet para pĂ«rzgjedhjes sĂ« veçorave //Proceedings of the 2016 KonferencĂ«s NdĂ«rkombĂ«tare mbi Menaxhimin e tĂ« DhĂ«nave. â ACM, 2016. â fq. 19-34.
- Abo Khamis M. et al. MĂ«simi nĂ« bazĂ« tĂ« tĂ« dhĂ«nave me tensorĂ« tĂ« hollĂ« //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. â ACM, 2018. â Fq. 325-340.
- Hellerstein J. M. et al. Biblioteka analitike MADlib: ose aftĂ«sitĂ« MAD, SQL //Proceedings of the VLDB Endowment. â 2012. â V. 5. â Nr. 12. â Fq. 1700-1711.
- Qin C., Rusu F. Aproksimime spekulative pĂ«r optimizimin e gradientit tĂ« shpĂ«rndarĂ« teraskal //Proceedings of the Fourth Workshop on Data analytics in the Cloud. â ACM, 2015. â Fq. 1.
- Meng X. et al. Mllib: MĂ«simi nĂ« apache spark //The Journal of Machine Learning Research. â 2016. â V. 17. â Nr. 1. â Fq. 1235-1241.
Autorët e artikullit: , kërkues në , dhe , kërkues në
Burimi: habr.com
