Në këtë artikull do të flasim për varësitë funksionale në bazat e të dhënave - çfarë janë, ku përdoren dhe cilët algoritme ekzistojnë për t'i kërkuar ato.
Ne do të shqyrtojmë varësitë funkcional në kontekstin e bazave të të dhënave relacional. Nëse flasim shumë thjesht, informacioni në këto baza të dhënash ruhet në formën e tabelave. Më tej, ne do të përdorim koncepte të afërta, të cilat në teorinë strikte relacione nuk janë të ndërlidhura: tabelën e vet e quajmë relacion, kolumnat - atribute (grupi i tyre është skema e relacionit), dhe grupi i vlerave të rreshtit mbi një nëngrup atributesh - një turmë.
Për shembull, në tabelën e mësipërme, (Benson, M, M organ) është një turmë sipas atributeve (Pacienti, Gjinia, Doktori).
Më formal, kjo shkruhet si në vijim: 
[Pacienti, Gjinia, Doktori] = (Benson, M, M organ).
Tani mund të prezantojmë konceptin e varësisë funksionale (VF):
Definicioni 1. Relationi R Ă«shtĂ« nĂ« pĂ«rputhje me VF X â Y (ku X, Y â R) atĂ«herĂ« dhe vetĂ«m atĂ«herĂ« kur pĂ«r çdo turmĂ« 
, 
â R zbatohet: nĂ«se 
[X] = 
[X], atëherë 
[Y] = 
[Y]. Në këtë rast, thuhet se X (determinanti, ose grupi përcaktues i atributeve) përcakton funksionalisht Y (grupi varës).
Me fjalĂ« tĂ« tjera, prania e VF X â Y do tĂ« thotĂ« se nĂ«se kemi dy turmĂ« nĂ« R dhe ato janĂ« tĂ« njĂ«jta sipas atributeve X, ato do tĂ« jenĂ« tĂ« njĂ«jta edhe sipas atributeve. Y.
Tani le të shohim radhazi. Të shqyrtojmë atribute Pacienti dhe Gjinia në lidhje me të cilat duam të kuptojmë nëse ka varësi mes tyre apo jo. Për këtë grup atributesh mund të ekzistojnë varësi të ndryshme:
- Pacienti â Gjinia
- Gjinia â Pacienti
Sipas definicionit tĂ« mĂ«sipĂ«rm, pĂ«r tĂ« mbajtur varĂ«sinĂ« e parĂ«, çdo vlerĂ« unike e kolumnit Pacienti duhet tĂ« ketĂ« vetĂ«m njĂ« vlerĂ« tĂ« kolumnit tjetĂ«r. GjiniaDhe pĂ«r tabelĂ«n shembuj, kjo Ă«shtĂ« me tĂ« vĂ«rtetĂ« e vĂ«rtetĂ«. MegjithatĂ«, nĂ« anĂ«n tjetĂ«r kjo nuk funksionon, pra varĂ«sia e dytĂ« nuk pĂ«rmbushet, dhe atributi Gjinia nuk Ă«shtĂ« determinanti pĂ«r Pacientin.Po ashtu, nĂ«se marrim varĂ«sinĂ« Doktori â Pacienti, mund tĂ« vĂ«rejmĂ« se ajo thyhet, pasi vlera Robin pĂ«r kĂ«tĂ« atribut ka disa vlera tĂ« ndryshme - Ellis dhe Graham..
KĂ«shtu, varĂ«sitĂ« funksionale lejojnĂ« tĂ« pĂ«rcaktohen lidhjet ekzistuese midis grupeve tĂ« atributeve tĂ« tabelĂ«s. Andaj, ne do tĂ« shqyrtojmĂ« lidhjet mĂ« interesante, pra ato X â Y, qĂ« janĂ«:
- jo triviale, do thotĂ« se ana e djathtĂ« e varĂ«sisĂ« nuk Ă«shtĂ« njĂ« nĂ«nset i anĂ«s sĂ« majtĂ« (Y Ìžâ X);
- minimale, qĂ« do tĂ« thotĂ« se nuk ka njĂ« varĂ«si tĂ« tillĂ« Z â Y, qĂ« Z â X..
Varësitë e shqyrtuara deri më tani kanë qenë strikte, pra pa parashikuar ndonjë shkelje në tabelë, por përveç tyre ekzistojnë dhe ato që lejojnë një të paqartësi të caktuar mes vlerave të turmave. Të tilla varësi përfshihen në një klasë të veçantë, quhen afër dhe u lejohet që të thyhen në një numër të caktuar turmash. Ky numër rregullohet nga treguesi i maksimumit të gabimit emax. Për shembull, përqindja e gabimit 
= 0.01 mund tĂ« dojĂ« tĂ« thotĂ« se varĂ«sia mund tĂ« thyhet nĂ« 1% tĂ« turmave tĂ« pranishme nĂ« grupin e atributeve tĂ« shqyrtuara. Pra, pĂ«r 1000 regjistrime maksimumi 10 turmĂ« mund tĂ« shkelin VF-nĂ«. Ne do tĂ« shqyrtojmĂ« njĂ« metrikĂ« paksa tĂ« ndryshme, tĂ« bazuar nĂ« vlerat e ndryshme mes çiftave tĂ« turmave qĂ« do tĂ« krahasojmĂ«. PĂ«r varĂ«sinĂ« X â Y nĂ« relacion r ajo llogaritet kĂ«shtu:
Le tĂ« llogaritim gabimin pĂ«r Doktori â Pacienti nga shembulli mĂ« sipĂ«r. Kemi dy turmĂ«, vlerat e tĂ« cilave ndryshojnĂ« nĂ« atributin Pacienti, por janĂ« tĂ« njĂ«jta nĂ« Doktor.: 
[Doktori, Pacienti] = (Robin, Ellis) dhe 
[Doktori, Pacienti] = (Robin, Graham). Në përputhje me definicionin e gabimit, ne duhet të marrë në konsideratë të gjitha çiftet konfliktuese, kështu që ka dy të tillë: () dhe inversin e saj (
, 
). Le të vendosim në formulë dhe të marim:
, 
Tani le të përpiqemi të përgjigjemi në pyetjen: "Për çfarë është ajo gjithë kjo?". Në të vërtetë, varësitë funksionale janë të ndryshme. Lloji i parë - janë ato varësi që përcaktohen nga administratori në fazën e projektimit të bazës së të dhënave. Zakonisht janë pak, ato janë strikte, dhe përdorimi kryesor - normalizimi i të dhënave dhe dizajni i skemës së relacionit.
Lloji i dytë - janë varësitë që paraqesin të dhëna "të fshehura" dhe lidhje të panjohura më parë midis atributeve. Pra, për ato varësi nuk është menduar në momentin e projektimit dhe ato gjenden tashmë për grupin e të dhënave ekzistuese, për të nxjerrë më pas përfundime mbi informacionin e ruajtur bazuar në shumë varësish funksionale të identifikuara. Pikërisht me këto varësi jemi duke punuar. Ato përbëjnë një fushë të tërë të minimit të të dhënave me teknika të ndryshme kërkimesh dhe algorithma të ndërtuara mbi to. Le të shqyrtojmë, se çfarë mund të jenë të dobishme varësitë funksionale të gjetura (të sakta ose të afërta) në disa të dhëna.
Lloji i dytë është varësitë, që përfaqësojnë të dhëna "fshehura" dhe lidhje të panjohura më parë midis atributeve. Kjo do të thotë se për këto varësi nuk ishte menduar në momentin e projektimit dhe ato zbulohen për një grup tashmë ekzistues të dhënash, për t'u bërë më pas disa përfundime mbi informacionin e ruajtur, bazuar në shumë varësi që janë zbuluar. Kjo është saktësisht çfarë ne po studiojmë. Një e tërë fushë e minierisë së të dhënave merret me to duke përdorur teknika të ndryshme kërkimi dhe algoritme të ndërtuara mbi ato. Le të shqyrtojmë se si mund të jenë të dobishme varësitë funksionale të gjetura (të sakta ose të afërta) në të dhëna të caktuara.
Sot sot ishin fushat kryesore ku përdoren varësitë, pastrimi i të dhënave. Kjo nënkupton zhvillimin e proceseve të identifikimit të "të dhënave të ndyra" me pastrimin e tyre të mëvonshëm. Përfaqësues të dukshëm të "të dhënave të ndyra" janë kopjet, gabimet në të dhëna ose gabimet e shkrimit, vlerat e humbura, të dhënat e vjetruara, hapësirat e tepërta dhe të ngjashme.
Shembulli i një gabimi në të dhëna:
Shembulli i kopjeve në të dhëna:
Për shembull, ne kemi një tabelë dhe një grup rregullash që duhet të respektohen. Pastrimi i të dhënave në këtë rast nënkupton që të dhënat duhet të ndryshohen në një mënyrë që rregullat të jenë të saktë. Numri i modifikimeve duhet të jetë minimal (për këtë procedurë ekzistojnë algoritme specifike, në të cilat nuk do të përqendrohemi në këtë artikull). Më poshtë jepet një shembull i tillë i transformimit të të dhënave. Majtas është raporti origjinal, ku, siç duket, nuk respektohen rregullat e nevojshme (me ngjyrë të kuqe është shfaqur një shembull i shkeljes së një prej rregullave). Djathtas është paraqitur raporti i azhurnuar, ku kutitë e gjelbra tregojnë vlerat e ndryshuara. Pas kryerjes së një procedure të tillë, varësitë e nevojshme filluan të mbahen.
Një fushë tjetër e njohur e aplikimit është dizajni i bazës së të dhënave. Këtu është e rëndësishme të kujtojmë format normale dhe normalizimin. Normalizimi është një proces që çon marrëdhënien në përputhje me një grup kërkesash, secila prej të cilave përcaktohet nga forma normale në mënyrën e saj. Nuk do të përshkruajmë kërkesat e ndryshme të formave normale (kjo bëhet në çdo libër për kursin e DB për fillestarët), por do të theksojmë se secila prej tyre përdor konceptin e varësive funksionale në mënyrën e saj. Sepse varësitë funksionale në thelb janë kufizime integriteti që merren parasysh gjatë projektimit të bazës së të dhënave (në kontekstin e kësaj çështjeje, varësitë funksionale ndonjëherë quhen superçelësa).
Le të shohim aplikimin e tyre për katër forma normale në imazhin më poshtë. Kujtojmë që forma normale e Boyce-Codd është më e rreptë se forma e tretë, por më pak e rreptë se forma e katërt. Ne nuk e shqyrtojmë të fundit, sepse për ta vendosur kërkohet kuptimi i varësive shumëvlerësuese, të cilat në këtë artikull nuk janë të interesuara.
Një tjetër fushë ku varësitë kanë gjetur përdorim është ulja e dimensioneve të hapësirës së tipareve në detyra si ndërtimi i klasifikatorit naiv Bayes, identifikimi i tipareve domethënëse dhe riparametrizimi i modelit regresiv. Në artikujt origjinalë, kjo detyrë quhet përcaktimi i tipareve tepër (feature redundancy) dhe të rëndësishme (feature relevancy), dhe zgjidhet me përdorimin e aktiv të koncepteve të bazave të të dhënave. Me shfaqjen e këtyre punimeve, mund të flasim se sot ka një kërkesë për zgjidhje që lejojnë bashkimin e bazës së të dhënave, analitikës dhe realizimin e problemeve të përmendura më sipër në një mjet.
Për të kërkuar varësitë funksionale në një grup të dhënash ekzistojnë shumë algoritme (si moderne ashtu edhe jo aq moderne). Këto algoritme mund të ndahen në tri grupe:
- Algoritmet që përdorin kalimin përmes algebrave të grilave (Lattice traversal algorithms)
- Algoritmet që bazohen në kërkimin e vlerave të njëpasnjëshme (Difference- and agree-set algorithms)
- Algoritmet që bazohen në krahasime në çift (Dependency induction algorithms)
Një përshkrim i shkurtër i çdo tipi algoritmesh është paraqitur në tabelën më poshtë:
Më shumë rreth kësaj klasifikimi mund të lexoni. Më poshtë janë paraqitur shembuj të algoritmeve për çdo tip:
Aktualisht po shfaqen algoritmo të rinj që kombinojnë disa qasje në kërkimin e varësive funksionale. Shembuj të tillë algoritmesh janë Pyro dhe HyFD. Analiza e funksionimit të tyre pritet të bëhet në artikujt e ardhshëm të këtij cikli. Në këtë artikull ne vetëm do të shqyrtojmë konceptet dhe lemën bazë që janë të nevojshme për të kuptuar teknikat e identifikimit të varësive.
TĂ« fillojmĂ« me tĂ« thjeshtĂ«n â setin e diferencave dhe setin e pranimit, tĂ« pĂ«rdorur nĂ« tipin e dytĂ« tĂ« algoritmeve. Seti i diferencave Ă«shtĂ« njĂ« grup tuple qĂ« nuk janĂ« tĂ« barabarta sipas vlerave, ndĂ«rsa seti i pranimit Ă«shtĂ«, pĂ«rkundrazi, tuple qĂ« janĂ« tĂ« barabarta sipas vlerave. Duhet tĂ« theksohet se nĂ« kĂ«tĂ« rast ne shqyrtojmĂ« vetĂ«m anĂ«n e majtĂ« tĂ« varĂ«sisĂ«.
Po ashtu, një koncept i rëndësishëm që u përmend më lart është grila algebraike. Duke qenë se shumë algoritme moderne operojnë me këtë koncept, ne duhet të kemi një përllogaritje se çfarë është ajo.
PĂ«r tĂ« futur konceptin e grilĂ«s, Ă«shtĂ« e nevojshme njĂ« pĂ«rcaktim i grumbullit tĂ« pjesshĂ«m tĂ« renditur (apo partially ordered set, tĂ« shkurtuar â poset).
PĂ«rcaktimi 2. Thuhet se njĂ« shumĂ« S Ă«shtĂ« pjesĂ«risht e renditur nga njĂ« marrĂ«dhĂ«nie binare â©œ, nĂ«se pĂ«r çdo a, b, c â S plotĂ«sohen vetitĂ«:
- Refleksiviteti, domethĂ«nĂ« a â©œ a
- Antisimetria, domethĂ«nĂ«, nĂ«se a â©œ b dhe b â©œ a, atĂ«herĂ« a = b
- Transitiviteti, domethĂ«nĂ« pĂ«r a â©œ b dhe b â©œ c, ndjek qĂ« a â©œ c
Kjo marrĂ«dhĂ«nie quhet marrĂ«dhĂ«nie (e patĂ«metĂ«) pjesore, dhe vetĂ« shuma quhet shumĂ« e pjesĂ«risht e renditur. Shkalla formale: âšS, â©œâ©.
Si njĂ« shembull mĂ« tĂ« thjeshtĂ« tĂ« njĂ« shume pjesĂ«risht tĂ« renditur mund tĂ« merret shuma e tĂ« gjitha numrave natyrorĂ« N me marrĂ«dhĂ«nien e rendit zakonor â©œ. Nuk Ă«shtĂ« e vĂ«shtirĂ« tĂ« kontrollohet se tĂ« gjitha aksiomat e nevojshme janĂ« tĂ« vĂ«rteta.
NjĂ« shembull mĂ« substancial. Le tĂ« shqyrtojmĂ« shumen e tĂ« gjitha nĂ«n grupeve {1, 2, 3}, e renditur sipas marrĂ«dhĂ«nies sĂ« pĂ«rfshirjes â. NĂ« tĂ« vĂ«rtetĂ«, kjo marrĂ«dhĂ«nie plotĂ«son tĂ« gjitha kushtet e njĂ« rendi tĂ« pjesshĂ«m, prandaj âšP ({1, 2, 3}), ââ© Ă«shtĂ« njĂ« shumĂ« pjesĂ«risht e renditur. NĂ« figurĂ«n mĂ« poshtĂ« tregohet struktura e kĂ«saj shume: nĂ«se nga njĂ« element mund tĂ« arrijmĂ« nĂ«pĂ«rmjet ŃŃŃĐ”Đ»ĐŸŃĐșĐ” nĂ« njĂ« element tjetĂ«r, atĂ«herĂ« ata janĂ« nĂ« marrĂ«dhĂ«nie rendi.
Na duhen edhe dy pĂ«rkufizime tĂ« thjeshta nga fusha e matematikĂ«s â supremumi (supremum) dhe infimumi (infimum).
PĂ«rkufizimi 3. Le tĂ« supozojmĂ« âšS, ⩜⩠â njĂ« shumĂ« pjesĂ«risht tĂ« renditur, A â S. Kufiri i sipĂ«rm tĂ« A Ă«shtĂ« njĂ« element u â S, nĂ« mĂ«nyrĂ« qĂ« âx â S: x â©œ u. Le tĂ« jetĂ« U â shuma e tĂ« gjithĂ« kufijve tĂ« sipĂ«rm S. NĂ«se nĂ« U ekziston njĂ« element mĂ« i vogĂ«l, atĂ«herĂ« ai quhet suprem dhe shĂ«nohet si sup A.
Po ashtu, koncepti i kufirit të saktë të poshtëm introduktohet.
PĂ«rkufizimi 4. Le tĂ« supozojmĂ« âšS, ⩜⩠â njĂ« shumĂ« pjesĂ«risht tĂ« renditur, A â S. Kufiri i poshtĂ«m tĂ« A Ă«shtĂ« njĂ« element l â S, nĂ« mĂ«nyrĂ« qĂ« âx â S: l â©œ x. Le tĂ« jetĂ« L â shuma e tĂ« gjithĂ« kufijve tĂ« poshtĂ«m S. NĂ«se nĂ« L ekziston njĂ« element mĂ« tĂ« madh, atĂ«herĂ« ai quhet infimum dhe shĂ«nohet si inf A.
Le tĂ« marrim si shembull shumen pjesĂ«risht tĂ« renditur tĂ« mĂ«sipĂ«rme âšP ({1, 2, 3}), ââ© dhe gjejmĂ« nĂ« tĂ« supremum dhe infimum:
Tani mund të formulojmë përkufizimin e rrjetës algebrajike.
PĂ«rkufizimi 5. Le tĂ« supozojmĂ« âšP, ⩜⩠â njĂ« shumĂ« pjesĂ«risht tĂ« renditur, e tillĂ« qĂ« çdo nĂ«nshumĂ« dy-elementor ka kufij tĂ« saktĂ« tĂ« sipĂ«rm dhe tĂ« poshtĂ«m. AtĂ«herĂ« P quhet rrjetĂ« algebrajike. NĂ« kĂ«tĂ« rast sup{x, y} shkruhet si x âš y, dhe inf {x, y} â si x ⧠y.
Le tĂ« verifikojmĂ« se shembulli ynĂ« punues âšP ({1, 2, 3}), ââ© Ă«shtĂ« njĂ« rrjetĂ«. 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Ă« infimumin dhe supremumin e tyre. NĂ«se i bashkojmĂ«, do tĂ« marrim grupin {1}, i cili do tĂ« jetĂ« infimumi. Supremumi do ta 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ë rrjete, ku grupet me një element (lexo nivelin e parë të rrjetës së kërkimit, ku ana e majtë e varësive përbëhet nga një atribut) paraqesin çdo atribut të marrëdhënies fillestare.
Fillimisht shqyrtohen varĂ«sitĂ« e tipit â
â Atributi i vetĂ«m. Ky hap lejon tĂ« pĂ«rcaktohet se cilat atribute janĂ« çelĂ«sa primarĂ« (pĂ«r kĂ«to atribute nuk ka determinanta, dhe pĂ«r kĂ«tĂ« arsye ana e majtĂ« Ă«shtĂ« e zbrazĂ«t). MĂ« pas algoritmet e tilla lĂ«vizin pĂ«rpjetĂ« nĂ« rrjetĂ«. NĂ« kĂ«tĂ« rast, vlen tĂ« theksohet se rrjeta nuk duhet tĂ« vizitohet e gjithĂ«, domethĂ«nĂ« nĂ«se dĂ«rgohet njĂ« madhĂ«si maksimale e dĂ«shiruar pĂ«r anĂ«n e majtĂ«, algoritmi nuk do tĂ« vazhdojĂ« mĂ« tej se niveli me atĂ« madhĂ«si.
NĂ« figurĂ«n mĂ« poshtĂ« tregohet se si mund tĂ« pĂ«rdoret rrjeta algebrajike nĂ« problemin e kĂ«rkimit tĂ« FZ. KĂ«tu çdo kresht (X, XY) paraqet njĂ« varĂ«si X â Y. PĂ«r shembull, ne kaluam nivelin e parĂ« dhe dimĂ« qĂ« mbahet varĂ«sia A â B (ta vizatojmĂ« kĂ«tĂ« me njĂ« lidhje tĂ« gjelbĂ«r mes kreshtave A dhe B). Pra, kur tĂ« avancojmĂ« pĂ«rpjetĂ« nĂ« rrjetĂ«, nuk kemi nevojĂ« tĂ« verifikojmĂ« varĂ«sinĂ« A, C â B, sepse ajo do tĂ« jetĂ« tashmĂ« jo minimale. NĂ« mĂ«nyrĂ« tĂ« ngjashme, ne nuk do ta verifikonim nĂ«se do tĂ« mbahej varĂ«sia C â B.
Për më tepër, zakonisht, të gjitha algoritmet moderne për kërkimin e FZ përdorin një strukturë të tillë të dhënash si partita (në burimin origjinal - stripped partition [1]). Përkufizimi formal i partisë është si më poshtë:
PĂ«rkufizimi 6. Le tĂ« jetĂ« X â R â njĂ« set atributesh pĂ«r marrĂ«dhĂ«nien r. Klasteri pĂ«rbĂ«n njĂ« grup indekse tĂ« ngjeshur nga r, tĂ« cilat kanĂ« tĂ« njĂ«jtin vlerĂ« pĂ«r X, domethĂ«nĂ« c(t) = {i|ti[X] = t[X]}. Partita pĂ«rbĂ«n njĂ« shume klasteresh, duke pĂ«rjashtuar klasteret me gjatĂ«si njĂ«:
Thjesht, partita për atributin X paraqet një grup listash, ku çdo listë përmban numra rreshtash me vlera të njëjta për X. Në letërsi moderne, struktura që përfaqëson partitë quhet position list index (PLI). Klasterët me gjatësi të njëjtë përjashtohen për shkak të kompresimit të PLI, sepse këto janë klasterë që përmbajnë vetëm numrin e regjistrimeve me një vlerë unike, e cila gjithmonë do të jetë e lehtë për t'u vendosur.
Le të marrim një shembull. Të kthehemi përsëri te tabela me pacientët dhe të ndërtojmë partitë për kolonat Pacienti dhe Gjinia (nga ana e majtë u shfaq një kolonë e re, në të cilën shënohen numrat e rreshtave të tabelës):
Në këtë rast, sipas përkufizimit, partia për kolonën Pacienti në të vërtetë do të jetë e zbrazët, pasi klasterët e vetme përjashtohen nga partia.
Partitë mund të krijohen sipas disa atributeve. Dhe për këtë ekzistojnë dy rrugë: kaloni përmes tabelës, të ndërtoni një parti menjëherë për të gjitha atributet e nevojshme, ose ta ndërtoni atë me ndihmën e operacionit të ndërmjetësimit të partive sipas nënshtresave të atributeve. Algoritmet e kërkimit të FZ përdorin variantin e dytë.
Me fjalë të thjeshta, për të marrë një parti për kolonat ABC, mund të marrim partitë për AC dhe B (ose çdo grup tjetër të nënshtresave jo të mbivendosur) dhe t'i ndërthurem ato. Operacioni i ndërthurit të dy partive nxjerr klasterët e gjatësi më të madhe, të përbashkët për të dy partitë.
Le të shqyrtojmë një shembull:
Në rastin e parë ne morëm një parti të zbrazët. Nëse e shikojmë tabelën, është e vërtetë se s'ka vlera të ngjashme për dy atribute. Nëse modifikojmë pak tabelën (rastin në të djathtë), atëherë do të kemi një ndërthurje jo të zbrazët. Në këtë rast, rreshtat 1 dhe 2 vërtet përmbajnë vlera të ngjashme për atributet Gjinia dhe Doktori.
Më pas do të na nevojitet një koncept si madhësia e partisë. Forma e saktë:
Thjesht, madhësia e partisë paraqet numrin e klasterëve që hyjnë në parti (mos harroni, klasterët e vetme nuk hyjnë në parti!):
Tani ne mund të përcaktojmë një nga lemat kyçe, e cila për partitë e caktuara lejon të përcaktohet nëse një varësi mbetet apo jo:
Lema 1. VarĂ«sia A, B â C mbahet nĂ«se dhe vetĂ«m nĂ«se
Sipas lemmës, për të përcaktuar nëse varësia mbahet, duhen kryer katër hapa:
- Llogaritja e partisë për pjesën e majtë të varësisë
- Llogaritja e partisë për pjesën e djathtë të varësisë
- Llogaritja e produktit të hapit të parë dhe të dytë
- Krahasimi i madhësive të partive, të marra në hapin e parë dhe të tretë
Më poshtë është një shembull verifikimi se a mbahet varësia sipas kësaj lema:
Në këtë artikull ne kemi shqyrtuar koncepte si varësia funksionale, varësia funksionale afërsisht, ku aplikohen ato dhe çfarë algoritmesh ekzistojnë për kërkimin e FZ. gjithashtu kemi diskutuar me hollësi konceptet bazë, por të rëndësishme, që përdoren gjerësisht në algoritmet moderne të kërkimit të FZ.
Referencat në literaturë:
- Huhtala Y. et al. TANE: NjĂ« algoritĂ«m efikas pĂ«r zbardhjen e varĂ«sive funksionale dhe afĂ«rsisht //Revista kompjuterike. â 1999. â T. 42. â Nr. 2. â F. 100-111.
- Kruse S., Naumann F. ZbĂ«rthimi efikas i varĂ«sive afĂ«rsisht //Aktet e Fondacionit VLDB. â 2018. â T. 11. â Nr. 7. â F. 759-772.
- Papenbrock T., Naumann F. NjĂ« qasje hibride pĂ«r zbardhjen e varĂ«sive funksionale //Aktet e KonferencĂ«s NdĂ«rkombĂ«tare mbi Menaxhimin e tĂ« DhĂ«nave 2016. â ACM, 2016. â F. 821-833.
- Papenbrock T. et al. Zbardhja e varĂ«sive funksionale: NjĂ« vlerĂ«sim eksperimental i shtatĂ« algoritmeve //Aktet e Fondacionit VLDB. â 2015. â T. 8. â Nr. 10. â F. 1082-1093.
- Kumar A. et al. TĂ« bashkosh apo jo?: TĂ« mendosh dy herĂ« pĂ«r bashkimet para pĂ«rzgjedhjes sĂ« veçorave //Aktet e KonferencĂ«s NdĂ«rkombĂ«tare mbi Menaxhimin e tĂ« DhĂ«nave 2016. â ACM, 2016. â F. 19-34.
- Abo Khamis M. et al. MĂ«simi brenda databazĂ«s me tenzora tĂ« pakta //Aktet e Simpoziumit tĂ« 37-tĂ« ACM SIGMOD-SIGACT-SIGAI mbi Parimet e Sistemeve tĂ« tĂ« DhĂ«nave. â ACM, 2018. â F. 325-340.
- Hellerstein J. M. et al. Biblioteka analitike MADlib: ose aftĂ«si MAD, SQL //Aktet e Fondacionit VLDB. â 2012. â T. 5. â Nr. 12. â F. 1700-1711.
- Qin C., Rusu F. Aproksimimet spekulative pĂ«r optimizimin e shpĂ«rndarĂ« tĂ« gradientit nĂ« tera-skalĂ« //Aktet e Workshop-it tĂ« KatĂ«rt mbi AnalitikĂ«n e tĂ« DhĂ«nave nĂ« Re. â ACM, 2015. â F. 1.
- Meng X. et al. Mllib: MĂ«simi nĂ« apache spark //Revista pĂ«r KĂ«rkimin nĂ« MĂ«simin e MakinerisĂ«. â 2016. â T. 17. â Nr. 1. â F. 1235-1241.
Autorët e artikullit: , studiues në , dhe , studiues në
Burimi: habr.com
