Di vê gotarê de em ê li ser girêdanên fonksiyonel ên di databasan de biaxivin - ew çi ne, li ku têne bikar anîn û kîjan algorîtma hene ku wan bibînin.
Em ê di çarçoveya databasên pêwendiyê de girêdayîbûna fonksiyonel binirxînin. Bi gelemperî, di databasên weha de agahdarî di forma tabloyan de têne hilanîn. Dûv re, em têgînên nêzik ên ku di teoriya têkiliya hişk de nayên guheztin bikar tînin: em ê ji tabloyê re têkiliyek, stûnan - taybetmendî (koma wan - şema pêwendiyê) û komek nirxên rêzê li ser binkeyek taybetmendiyan bi nav bikin. - kulmek.
Mînakî, di tabloya jorîn de, (Benson, M, M organ) çendîn taybetmendiyan e (Nexweş, Pawlos, Doktor).
Bi awayekî fermî, ev bi vî awayî hatiye nivîsandin: 
[Nexweş, Zayendî, Doktor] = (Benson, M, M organ).
Naha em dikarin têgeha girêdayîbûna fonksiyonel (FD) bidin nasîn:
Pênase 1. Têkiliya R zagona federal X → Y (ku X, Y ⊆ R) têr dike ger û tenê heke ji bo çendan 
, 
∈ R heye: eger 
[X] = 
[X], paşê 
[Y] = 
[Y]. Di vê rewşê de, em dibêjin ku X (determînant, an komek diyarker) bi fonksiyonê Y (koma girêdayî) diyar dike.
Bi gotineke din, hebûna qanûneke federal X → Y tê wê wateyê ku heke em di nav de du tîp hebin R û ew di taybetmendiyan de li hev dikin X, wê demê ew ê di taybetmendiyan de li hev werin Y.
Û niha, bi rêz. Ka em li taybetmendiyan binêrin Nexweş и Sex ji bo ku em dixwazin bizanin ka di navbera wan de girêdayî hene yan na. Ji bo komek taybetmendiyên weha, dibe ku girêdayîbûna jêrîn hebin:
- Nexweş → Zayenda
- Zayenda → Nexweş
Wekî ku li jor hatî destnîşan kirin, ji bo ku pêwendiya yekem bigire, nirxa her stûnek bêhempa ye Nexweş tenê yek nirxa stûnê divê li hev bike Sex. Û ji bo tabloya nimûne ev bi rastî jî wisa ye. Lêbelê, ev di rêgezek berevajî de naxebite, ango girêdayîbûna duyemîn têr nabe, û taybetmendî Sex ji bo ne diyarker e Nexweş. Bi heman awayî, heke em girêdayîbûnê bigirin Doktor → Nexweş, hûn dikarin bibînin ku ew tê binpêkirin, ji ber ku nirx Robin ev taybetmendî çend wateyên cûda hene - Ellis û Graham.
Bi vî rengî, girêdanên fonksiyonel gengaz dike ku têkiliyên heyî yên di navbera komên taybetmendiyên tabloyê de diyar bikin. Ji vir û pê de, em ê girêdanên herî balkêş, an jî yên weha binirxînin X → Yew çi ne:
- ne-tîmalî, ango, aliyê rastê yê girêdayîbûnê ne binkomek çepê ye (Y ̸⊆ X);
- mînîmal, yanî pêwendiyeke wisa tune Z → Y, ku Z ⊂ X.
Girêdanên ku heya vê nuqteyê têne hesibandin hişk bûn, ango, wan li ser sifrê ti binpêkirin peyda nekirin, lê ji bilî wan, yên ku rê didin hin nerazîbûnên di navbera nirxên tîrêjan de jî hene. Girêdanên bi vî rengî di çînek cihêreng de têne danîn, ku jê re texmînî tê gotin, û destûr tê dayîn ku ji bo hejmareke diyarkirî ya tîpan werin binpêkirin. Ev mîqdar ji hêla nîşana xeletiya herî zêde emax ve tê rêve kirin. Ji bo nimûne, rêjeya çewtiyê 
= 0.01 dibe ku tê vê wateyê ku girêdayîbûn dikare ji hêla 1% ji jimareyên berdest ve li ser komek taybetmendiyan were binpê kirin. Ango ji bo 1000 tomar, herî zêde 10 tûp dikarin Qanûna Federal binpê bikin. Em ê metrîkek hinekî cûda bihesibînin, li ser bingeha nirxên cihêreng ên ducan ên tîrêjên ku têne berhev kirin. Ji bo addiction X → Y li ser helwesta r wiha tê hesibandin:
Ka em xeletiya ji bo hesab bikin Doktor → Nexweş ji mînaka li jor. Du tîpên me hene ku nirxên wan li ser taybetmendiyê cûda dibin Nexweş, lê li hev dikin Pizişk: 
[Doktor, Nexweş] = (Robin, Ellis) û 
[Doktor, Nexweş] = (Robin, Graham). Li dû danasîna xeletiyekê, divê em hemî cotên nakok bihesibînin, ku tê vê wateyê ku dê du ji wan hebin: (
, 
) û berevajî wê (
, 
). Ka em wê têxin şûna formula û bistînin:
Naha em hewl bidin ku bersiva pirsê bidin: "Çima ew hemî ji bo ye?" Bi rastî, qanûnên federal cuda ne. Cureya yekem ew girêdanên ku di qonaxa sêwirana databasê de ji hêla rêveber ve têne destnîşankirin. Ew bi gelemperî hindik in, hişk in, û serîlêdana sereke normalîzekirina daneyê û sêwirana şema têkildar e.
Cureya duyemîn girêdayî ye, ku daneyên "veşartî" û têkiliyên berê nenas di navbera taybetmendiyan de temsîl dikin. Ango, girêdanên weha di dema sêwiranê de nehatin fikirîn û ew ji bo berhevoka daneya heyî têne dîtin, da ku paşê, li ser bingeha gelek qanûnên federal ên naskirî, di derheqê agahdariya hilanîn de encamek were derxistin. Ya ku em bi wan re dixebitin tam bi van girêdanan in. Ew bi tevahî zeviyek danûstendina daneyê bi teknîkên cihêreng ên lêgerînê û algorîtmayên ku li ser bingeha wan hatine çêkirin ve têne rêve kirin. Ka em fêhm bikin ka girêdanên fonksiyonel ên hatine dîtin (tişt an nêzikî) di her daneyê de çawa dikarin bikêr bin.
Îro, yek ji serîlêdanên sereke yên girêdayîbûnê paqijkirina daneyê ye. Ew ji bo naskirina "daneyên qirêj" û dûv re rastkirina pêvajoyên pêşdebirinê vedihewîne. Mînakên berbiçav ên "daneyên qirêj" dubarekirin, xeletiyên daneyê an xeletî, nirxên winda, daneyên kevnar, cîhên zêde, û yên wekî wan in.
Mînakek xeletiyek daneyê:
Di daneyan de mînakek dubare:
Mînakî, tabloyek me û komek qanûnên federal hene ku divê bêne bicîh kirin. Paqijkirina daneyê di vê rewşê de guhartina daneyan digire da ku qanûnên Federal rast bibin. Di vê rewşê de, hejmara guhertinan divê hindik be (ev prosedur algorîtmayên xwe hene, ku em ê di vê gotarê de li ser nesekinin). Li jêr mînakek veguherînek daneya weha ye. Li milê çepê pêwendiya orîjînal heye, ku tê de, eşkere, FL-yên pêwîst nayên peyda kirin (mînakek binpêkirina yek ji FL-an bi sor tê ronî kirin). Li milê rastê pêwendiya nûvekirî heye, digel şaneyên kesk nirxên guhertî nîşan didin. Piştî vê prosedûrê, girêdanên pêwîst dest pê kirin.
Serlêdanek din a populer sêwirana databasê ye. Li vir hêja ye ku formên normal û normalîzekirinê bi bîr bînin. Normalîzasyon pêvajoyek e ku têkiliyek bi komek hewcedar re lihevhatî ye, ku her yek ji wan bi rengek normal bi awayê xwe tête diyar kirin. Em ê hewcedariyên cûrbecûr formên normal rave nekin (ev di her pirtûkê de li ser qursek databasê ji bo destpêk tê kirin), lê em ê tenê bala xwe bidin ku her yek ji wan bi awayê xwe têgîna girêdanên fonksiyonel bikar tîne. Beriya her tiştî, FL bi xweber astengiyên yekitiyê ne ku dema sêwirana databasek têne hesibandin (di çarçoweya vê peywirê de, FL carinan carinan wekî superkey têne gotin).
Ka em serîlêdana wan ji bo çar formên normal ên di wêneya jêrîn de bifikirin. Bînin bîra xwe ku forma normal ya Boyce-Codd ji forma sêyemîn hişktir e, lê ji ya çaremîn kêmtir hişk e. Em vê paşîn ji bo niha nahesibînin, ji ber ku formulasyona wê têgihîştina girêdanên pir-nirxî hewce dike, yên ku di vê gotarê de ji me re ne balkêş in.
Qadek din a ku pêwendiyan sepana xwe dîtiye ev e ku di peywiran de wekî avakirina dabeşkerek Bayes-a nefsbiçûk, naskirina taybetmendiyên girîng, û nûvekirina modelek regresyonê kêmkirina pîvana cîhê taybetmendiyê ye. Di gotarên orîjînal de, ji vê peywirê re tê gotin destnîşankirina pêwendiya zêde û taybetmendiyê [5, 6], û ew bi karanîna çalak a têgînên databasê tê çareser kirin. Bi hatina van karên weha re, em dikarin bibêjin ku îro daxwazek ji bo çareseriyê heye ku dihêle em databas, analîtîk û pêkanîna pirsgirêkên xweşbîniyê yên jorîn di yek amûrekê de bi hev re bikin [7, 8, 9].
Ji bo lêgerîna qanûnên federal di komek daneyê de gelek algorîtma hene (hem nûjen û ne ew qas nûjen).
- Algorîtmayên ku gera toreyên cebrî bikar tînin
- Algorîtmayên li ser bingeha lêgerîna nirxên lihevhatî (Algorîtmayên Cûdahî û lihevhatî)
- Algorîtmayên ku li ser bingeha danberhevên cot (Algorîtmayên inductiona girêdayîbûnê)
Danasînek kurt a her celeb algorîtmayê di tabloya jêrîn de tê pêşkêş kirin:
Hûn dikarin li ser vê dabeşkirinê bêtir bixwînin [4]. Li jêr nimûneyên algorîtmayan ji bo her celeb hene:
Heya nuha, algorîtmayên nû têne xuyang kirin ku ji bo dîtina girêdanên fonksiyonel gelek nêzîkatiyan berhev dikin. Mînakên van algorîtmayan Pyro [2] û HyFD [3] ne. Di gotarên jêrîn ên vê rêzenivîsê de analîzek xebata wan tê çaverê kirin. Di vê gotarê de em ê tenê têgehên bingehîn û lemmayên ku ji bo têgihiştina teknîkên tespîtkirina girêdayîbûnê hewce ne lêkolîn bikin.
Werin em bi yek sade dest pê bikin - cihêreng- û lihevhatinek, ku di celebê duyemîn algorîtmayan de tê bikar anîn. Cûdahî-set komek qertafên ku xwedan heman nirxan nîn in, dema ku lihevhatin-set, berevajî vê yekê, qertafên ku xwediyê heman nirxan in. Hêjayî gotinê ye ku di vê rewşê de em tenê aliyê çepê yê girêdayîbûnê dinirxînin.
Têgehek din a girîng a ku li jor hat dîtin, lat cebrî ye. Ji ber ku gelek algorîtmayên nûjen li ser vê têgehê tevdigerin, pêdivî ye ku em zanibin ka ew çi ye.
Ji bo danasîna têgeha latekê, pêdivî ye ku meriv komek bi qismî rêzkirî (an komek bi qismî rêzkirî, bi kurtî wekî poset) diyar bike.
Pênase 2. Komek S tê gotin ku qismî ji hêla têkiliya binaryê ⩽ ve hatî rêz kirin heke ji bo hemî a, b, c ∈ S taybetmendiyên jêrîn bicîh bibin:
- Refleksîtî, ango a ⩽ a
- Antîsimetrî, ango heke a ⩽ b û b ⩽ a, wê demê a = b
- Transîtîvîtî, ango ji bo ⩽ b û b ⩽ c-yê tê ku a ⩽ c
Têkiliyeke wiha tê gotin têkiliya rêza qismî ya qismî û ji komê re jî komek bi qismî rêzkirî tê gotin. Nîşana fermî: ⟨S, ⩽⟩.
Wek mînaka herî hêsan a komeke qismî rêzkirî, em dikarin komeka hemî jimareyên xwezayî N bi têkiliya rêza asayî ⩽ bigirin. Zehf e ku meriv rast bike ku hemî axiomên pêwîst têr in.
Mînakek watedartir. Komeka hemû binekometan {1, 2, 3}, ku li gorî pêwendiya tevlêbûnê ⊆ hatine rêzkirin, bihesibînin. Bi rastî, ev têkilî hemî şert û mercên rêza qismî têr dike, ji ber vê yekê ⟨P ({1, 2, 3}), ⊆⟩ komek bi qismî rêzkirî ye. Di jimareya jêrîn de strukturê vê komê nîşan dide: heke hêmanek bi tîran bigihîje hêmanek din, wê hingê ew di têkiliyek rêzê de ne.
Em ê ji qada matematîkê du pênaseyên hêsan ên din hewce bikin - supremum û infimum.
Pênase 3. Bila ⟨S, ⩽⟩ bibe komek qismî rêzkirî, A ⊆ S. Sînorê jorîn ê A hêmanek u ∈ S e ku ∀x ∈ S: x ⩽ u. Bila U koma hemî sînorên jorîn ên S-yê be. Heke di U-yê de hêmanek herî piçûk hebe, wê hingê jê re serwer tê gotin û sup A tê destnîşan kirin.
Têgeha sînorê jêrîn a tam bi heman rengî tête destnîşan kirin.
Pênase 4. Bila ⟨S, ⩽⟩ bibe komek bi qismî rêzkirî, A ⊆ S. Infimum ya A hêmanek l ∈ S e ku ∀x ∈ S: l ⩽ x. Bila L-ya hemû sînorên jêrîn ên S-yê be. Heke di L-yê de hêmanek herî mezin hebe, wê hingê jê re infimum tê gotin û wekî inf A tê destnîşan kirin.
Mînakî li koma jorîn bi qismî rêzkirî ⟨P ({1, 2, 3}), ⊆⟩ bihesibînin û tê de jortirîn û înfimumê bibînin:
Niha em dikarin pênaseya tora cebrî formule bikin.
Pênase 5. Bila ⟨P,⩽⟩ kombûneke qismî rêzkirî be wisa ku her binekomek du hêman xwedan sînorê jorîn û jêrîn be. Wê demê ji P re têra cebrî tê gotin. Di vê rewşê de, sup{x, y} wekî x ∨ y, û inf {x, y} wekî x ∧ y tê nivîsandin.
Werin em kontrol bikin ka mînaka meya xebatê ⟨P ({1, 2, 3}), ⊆⟩ şebek e. Bi rastî, ji bo her a, b ∈ P ({1, 2, 3}), a∨b = a∪b, û a∧b = a∩b. Mînakî, komên {1, 2} û {1, 3} bihesibînin û înfimum û serweriya wan bibînin. Ger em wan biqedînin, em ê koma {1}-ê bi dest bixin, ku dê bibe înfimum. Bi berhevkirina wan - {1, 2, 3} em serweriyê digirin.
Di algorîtmayên ji bo tespîtkirina pirsgirêkên laşî de, cîhê lêgerînê bi gelemperî di forma tîrêjê de tê destnîşan kirin, ku komên yek elementê (bixwîne asta yekem a tora lêgerînê, ku milê çepê yê girêdayîn ji yek taybetmendiyê pêk tê) her taybetmendiyê temsîl dike. têkiliya orîjînal.
Pêşîn, em girêdayînên forma ∅ → dihesibînin Taybetmendiyek yekane. Vê gav dihêle hûn diyar bikin ka kîjan taybetmendî mifteyên bingehîn in (ji bo taybetmendiyên weha diyarker tune, û ji ber vê yekê milê çepê vala ye). Digel vê yekê, algorîtmayên weha bi tîrêjê ber bi jor ve diçin. Hêjayî gotinê ye ku nekare tevahiya tîrêjê were derbas kirin, ango, heke mezinahiya herî zêde ya xwestinê ya milê çepê derbasî têketinê bibe, wê hingê algorîtma dê ji astek bi wê mezinahiyê wêdetir neçe.
Di jimareya jêrîn de nîşan dide ku di pirsgirêka dîtina FZ-ê de çawa latek cebrî dikare were bikar anîn. Li vir her keviyek (X, XY) girêdayîbûnê nîşan dide X → Y. Mînak, me asta yekem derbas kiriye û dizanin ku tiryak tê domandin A → B (em ê vê yekê wekî pêwendiyek kesk a di navbera vertîkan de nîşan bidin A и B). Ev tê vê wateyê ku bêtir, gava ku em li ser tîrêjê ber bi jor ve diçin, dibe ku em girêdanê kontrol nekin A, C → B, ji ber ku ew ê êdî hindik be. Bi heman awayî, heke girêdayîbûn pêk hat em ê wê kontrol nekin C → B.
Digel vê yekê, wekî qaîdeyek, hemî algorîtmayên nûjen ji bo lêgerîna qanûnên federal avahiyek daneyê wekî dabeşek bikar tînin (di çavkaniya orjînal de - dabeşkirina tazî [1]). Pênaseya fermî ya dabeşkirinê wiha ye:
Pênase 6. Bila X ⊆ R ji bo têkiliya r komek taybetmendiyan be. Komek komek nîşaneyên qertafên di r de ye ku ji bo X-yê heman nirxê wan heye, ango c(t) = {i|ti[X] = t[X]}. Parvekirin komek koman e, ji bilî komên dirêjahiya yekîneyê:
Bi gotinên hêsan, dabeşek ji bo taybetmendiyek X komek navnîşan e, ku her lîsteyek ji bo jimareyên rêzan bi heman nirxan vedihewîne X. Di wêjeya nûjen de, strukturên ku dabeşan temsîl dike, wekî navnîşa navnîşa pozîsyonê (PLI) tê gotin. Komên bi dirêjahiya yekîneyê ji bo mebestên berhevkirina PLI têne derxistin ji ber ku ew kom in ku tenê hejmarek tomarek bi nirxek bêhempa vedihewîne ku dê her gav hêsan were nas kirin.
Ka em li mînakekê binêrin. Ka em bi nexweşan re vegerin ser heman tabloyê û ji bo stûnan dabeşan ava bikin Nexweş и Sex (stûnek nû li milê çepê xuya bû, ku tê de hejmarên rêzên tabloyê têne nîşankirin):
Wekî din, li gorî pênase, dabeşkirina ji bo stûnê Nexweş dê bi rastî vala be, ji ber ku komikên yekane ji dabeşkirinê têne derxistin.
Dabeş dikare ji hêla çend taybetmendiyan ve were bidestxistin. Û du awayên kirina vê yekê hene: bi derbasbûna tabloyê, dabeşek bi karanîna hemî taybetmendiyên pêdivî bi yekcarî ava bikin, an jî wê bi karanîna operasyona hevberdana dabeşan bi karanîna binkomek taybetmendiyan ava bikin. Algorîtmayên lêgerîna qanûna federal vebijarka duyemîn bikar tînin.
Bi gotinên hêsan, ji bo nimûne, dabeşek bi stûnan bistînin ABC, hûn dikarin ji bo dabeşan bigirin AC и B (an jî komeke din a binekomên veqetandî) û wan bi hevûdu veqetînin. Operasyona lihevhatina du dabeşan komên bi dirêjahiya herî mezin ku ji bo her du beşan hevpar in hildibijêre.
Ka em li mînakekê binêrin:
Di doza yekem de, me dabeşek vala wergirt. Ger hûn ji nêz ve li tabloyê mêze bikin, wê hingê bi rastî, ji bo her du taybetmendiyan nirxên wekhev tune. Ger em sifrê hinekî biguhezînin (mesela li milê rastê), em ê jixwe xaçerek ne vala bistînin. Wekî din, rêzikên 1 û 2 bi rastî heman nirxan ji bo taybetmendiyan vedigirin Sex и Doktor.
Dûv re, em ê hewceyê têgehek weha wekî mezinahiya dabeşkirinê bikin. Nefermîyane:
Bi hêsanî, mezinahiya dabeşkirinê hejmara komikên ku di dabeşkirinê de ne ye (ji bîr mekin ku komikên yekane di dabeşkirinê de nabin!):
Naha em dikarin yek ji lemmayên sereke diyar bikin, ku ji bo dabeşên diyarkirî dihêle ku em diyar bikin ka pêwendiyek tê girtin an na:
Lema 1. Girêdana A, B → C heke û tenê heke hebe
Li gorî lemmayê, ji bo destnîşankirina ka pêwendiyek heye, divê çar gav bêne kirin:
- Parvekirinê ji bo aliyê çepê yê girêdayîbûnê hesab bikin
- Parvekirinê ji bo aliyê rastê yê girêdayîbûnê hesab bikin
- Berhema gava yekem û duyemîn hesab bike
- Mezinahiyên dabeşên ku di gavên yekem û sêyemîn de hatine bidestxistin berhev bikin
Li jêr mînakek kontrolkirina ka girêdayîbûna li gorî vê lemmayê heye:
Di vê gotarê de, me têgehên wekî girêdayîbûna fonksiyonel, girêdayîbûna fonksiyonel a nêzikî vekolîn, li ku derê têne bikar anîn, û her weha çi algorîtmayên lêgerîna fonksiyonên laşî hene. Me her weha bi hûrgulî têgehên bingehîn lê girîng ên ku di algorîtmayên nûjen de ji bo lêgerîna qanûnên federal bi çalak têne bikar anîn vekolîn.
Çavkanî:
- Huhtala Y. et al. TANE: Algorîtmayek bikêrhatî ji bo vedîtina girêdanên fonksiyonel û nêzîk // Kovara komputerê. – 1999. – T. 42. – No. 2. – rûpel 100-111.
- Kruse S., Naumann F. Vedîtina bikêrhatî ya girêdayiyên nêzîk // Pêvajoyên Dezgeha VLDB. – 2018. – T. 11. – No. 7. – rûpel 759-772.
- Papenbrock T., Naumann F. Nêzîkatiyek hîbrîd ji bo vedîtina girêdayîbûna fonksiyonel // Daneyên Konferansa Navneteweyî ya 2016-an li ser Rêvebiriya Daneyên. - ACM, 2016. - rûpel 821-833.
- Papenbrock T. et al. Vedîtina pêwendiya fonksiyonel: Nirxandinek ezmûnî ya heft algorîtmayan // Proceedings of the VLDB Endowment. – 2015. – T. 8. – No. 10. – rûpel 1082-1093.
- Kumar A. et al. Tevlêbûn an nebûn?: Berî hilbijartina taybetmendiyê du caran li ser tevlêbûnê difikirî //Konferansa Konferansa Navneteweyî ya 2016-an li ser Rêvebiriya Daneyan. – ACM, 2016. – rûpel 19-34.
- Abo Khamis M. et al. Fêrbûna nav databasê bi tensorên kêm // Berhemên Sempozyûma 37-emîn ACM SIGMOD-SIGACT-SIGAI li ser Prensîbên Pergalên Danegehan. - ACM, 2018. - rûpel 325-340.
- Hellerstein JM et al. Pirtûkxaneya analîtîk a MADlib: an jêhatîbûnên MAD, SQL // Proceedings of the VLDB Endowment. – 2012. – T. 5. – No. 12. – rûpel 1700-1711.
- Qin C., Rusu F. Nêzîktêdayînên spekulatîf ên ji bo optimîzasyona daketinê ya berbelavkirî ya terascale belavkirî //Bûyerên Atolyeya Çaremîn a li ser analîtîka daneyan di Cloud de. - ACM, 2015. - P. 1.
- Meng X. et al. Mllib: Fêrbûna makîneyê di çirûska apache de // Kovara Lêkolîna Fêrbûna Makîneyê. – 2016. – T. 17. – No. 1. – rûpel 1235-1241.
Nivîskarên gotarê: , lêkolîner li , и , lêkolîner li
Source: www.habr.com
