Ֆունկցիաների կախվածություններին ծանոթացում

Այս հոդվածում մենք կբարձրանանք ֆունկցիոնալ կախվածությունների մասին տվյալների բազաներում՝ ինչի մասին է խոսքը, որտեղ են կիրառում և quais ալգորիթմներ են պաշտպանված դրանց որոնման համար:

Ֆունկցիոնալ կախվածությունների քննարկումը մենք կմեկնարկենք ռելացիոն տվյալների բազաների համատեքստում։ Եթե շատ грубо ասենք, ապա նման տվյալների բազաներում տեղեկատվությունը պահպանվում է աղյուսակների ձևով։ Ապա մենք կիրառում ենք մոտավոր հասկացություններ, որոնք խիստ ռելացիոն տեսության մեջ փոխանակable չեն լինում. ինքն աղյուսակը կանենք հարաբերություն անվանության, սյունակները՝ ատրիբուտներ (նրանց ամբողջությունը՝ հարաբերության սխեմա), իսկ շարքերի արժեքների հավաքածուն՝ ենթախմբի ատրիբուտների վրա՝ կորսեզ:

Օրինակ, վերևում նշված աղյուսակում, (Benson, M, M organ) հանդիսանում է կորսեզ տվյալների ատրիբուտների տակ (Հիվանդ, Սեռ, բժիշկ).
Դուք բարձր ձայնում կգրանցվեք հետևյալ տեսքով: [Հիվանդ, Սեռ, բժիշկ] = (Benson, M, M organ).
Այժմ մենք կարող ենք ներկայացնել ֆունկցիոնալ կախվածության (ՖՔ) հասկացությունը։

Սահմանում 1։ Համակարգ R բավարարում է ՖՔ X → Y (որտեղ X, Y ⊆ R) միայն այն ժամանակ, երբ ցանկացած կորսեզ , ∈ R իրականացվում է։ եթե [X] = [X], ապա [Y ] = [Y ]։ Այդ դեպքում ասում են, որ X (պատճենահանող կամ որոշակի ատրիբուտների հավաքածու) ֆունկցիոնալ որոշում է Y (կախված օբյեկտ)։

Այնպիսով, ՖՔ-ի առկայությունը X → Y նշանակում է, որ եթե մենք ունենք երկու կորսեզ R և նրանք համընկնում են ատրիբուտներով X, ապա նրանք կհամընկնեն նաև ատրիբուտներով Y.
Այժմ հաշվի առնենք ատրիբուտները Հիվանդ և Սեռ որոնք ցանկանում ենք իմանալ, արդյո՞ք միջեւ կախվածություն կա, թե ոչ։ Այս ատրիբուտների հավաքածուի համար կարող են առաջանալ հետևյալ կախվածությունները՝

1. Հիվանդ → Սեռ
2. Սեռ → Հիվանդ

Ավելի վեր է նշված սահմանման համաձայն՝ առաջին կախվածությունը պահպանվելու համար, յուրաքանչյուր յուրահատուկ արժեքի սյունակում Հիվանդ պիտի համապատասխանի միայն մեկ արժեքի սյունակում Սեռ։ Եվ ցուցակի օրինակային համար սա իսկապես այդպեսն է։ Սակայն հակառակ կողմից սա չի աշխատում, այսինքն՝ երկրորդ կախվածությունը չի կատարում, а ատրիբուտը Սեռ չի հանդիսանում պատճենահանող Հիվանդ։ Անալոկի, եթե վերցնենք կախվածությունը Բժիշկ → Հիվանդ, կարող ենք նկատել, որ այն խախտվում է, քանի որ արժեքը Robin այս ատրիբուտով ունի մի քանի տարբեր արժեքներ՝ Ellis և Graham.

Այսպիսով, Ֆունկցիոնալ կախվածությունները թույլ են տալիս որոշել առկա կապերի միջև ատրիբուտների հավաքածուներում։ Այստեղից և շարունակաբար մենք կնայենք առավել հետաքրքիր կապերը, ավելի ճիշտ, այնպիսիք, X → Y, որոնք հանդիսանում են՝

• ոչ triv ցնցող, զուտ այն է, որ կախվածության դափլակի մասը չի համարվում ձուլ տվել առաջի (Y ̸⊆ X);
• չափածր, δηλαδή нет такой зависимости Z → Y, that Z ⊂ X.

Անցյալում դիտարկված կախվածությունները խիստ էին, یعنی չեն ենթադրում որևէ խախտում աղյուսակում, բայց կան նաև այնպիսիք, որոնք թույլ են տալիս որոշակի անհամաձայնություն tuples արժեքների միջև։ Այդպիսի կախվածությունները առանձնանում են առանձին դասի, կոչվում են մոտեցված և թույլատրվում է դրանց խախտվել որոշակի թվով tuples վրա։ Այս քանակը կարգավորվում է առավելագույն սխալով emax։ Օրինակ, սխալի բաժինը = 0.01 կարող է նշանակել, որ կախվածությունը կարող է խախտվել 1%-ով կային tuples-ների դիտարկվող հատկանիշների բազմության վրա։ Այսինքն, 1000 գրառումից առավելագույնը 10 tuples կարող են խախտել ֆունկցիոնալ կախվածությունը։ Բայց մենք կդիտարկենք մի փոքր այլ չափանիշ, որը հիմնված է համաբար տարբեր tuples արժեքների վրա։ Կախվածության X → Y համար: r այն հաշվարկվում է այսպես՝

Հաշվենք սխալը Բժիշկ → Հիվանդ վերը նշված օրինակից։ ունենք երկու tuples, որոնց արժեքները տարբերվում են հատկանիշներով Հիվանդ, բայց համընկնում են Doktor: [Doktor, Հիվանդ] = (Robin, Ellis) և [Doktor, Հիվանդ] = (Robin, Graham). Հետևելով սխալի սահմանմանը, մենք պետք է հաշվի առնենք բոլոր հակասական զույգերը, ուստի կունենանք երկուսը՝ (, ) և դրա հակադարձությունը (, )։ Ստեղծենք բանաձևում և կունենանք՝

Եկեք հիմա փորձենք պատասխանել հարցին՝ «Ինչի համար է դա ամենը»։ Իրականում ֆունկցիոնալ կախվածությունները տարբեր են։ Առաջին տեսակը՝ դա այնպիսի կախվածություններն են, որոնք որոշվում են ադմինիստրատոր կողմից տվյալների բազայի նախագծման փուլում։ Դրանք սովորաբար քիչ են, խիստ են, իսկ հիմնական կիրառումը՝ տվյալների նորմալիզացիան և հարաբերության սխեմայի դիզայնը։

Երկրորդ տեսակը՝ կախվածություններ, որոնք ներկայացնում են «թաքնված» տվյալները ու նախկինում չգիտելի կապերը հատկանիշների միջև։ Այսինքն՝ նման կախվածությունների մասին չեն խելացել նախագծման պահին, և դրանք գտվում են արդեն գոյություն ունեցող տվյալների հավաքածուի համար, որպեսզի հետո հիմնվելով հայտնաբերված ֆունկցիոնալ կախվածությունների բազմության՝ որոշակի եզրակացություններ անեն պահպանվող տեղեկությունների մասին։ Ինչպես раз с такими зависимостями мы и работаем. Ими занимается целая область дата майнинга с различными техниками поиска и построенными на их основе алгоритмами. Давайте разбираться, чем могут быть полезны найденные функциональные зависимости (точные или приближенные) в каких-либо данных.

Այսօր, կախվածությունների հիմնական կիրառման ոլորտներում առանձնացնում են տվյալների մաքրում։ Սա ենթադրում է «պղտոր տվյալների» հայտնաբերման գործընթացների մշակում՝ հետագայում դրանց ուղղման հետ միասին։ «Պղտոր տվյալների» яркими представителями являются կրկնօրինակները, տվյալների սխալները կամ սխալները, բաց թողնված արժեքները, հին տվյալները, ավելորդ տարածքները և նմանատիպը։

Օրինակ, տվյալների սխալը՝

Օրինակ, տվյալների կրկնօրինակները՝

Օրինակ, մեզ մոտ կա աղյուսակ և իրավական պահանջների հավաքածու, որոնք պետք է կատարվեն: Տվյալների մաքրումը այս պարագայում ենթադրում է տվյալները փոփոխելու այնպես, որ իրավական պահանջները ճիշտ լինեն: Այս ընթացքում փոփոխությունների թիվը պետք է լինի նվազագույն (այս գործընթացի համար կան իր տրամադրական ալգորիթմներ, որոնց վրա չենք կենտրոնանա այս հոդվածում): Ներկայացնում ենք տվյալների այսպիսի փոխակերպման օրինակ: Ձախ կողմում է սկզբնական հարաբերությունը, որտեղ ակնհայտ է, որ անհրաժեշտ իրավական պահանջները չեն բավարարվում (կարմիր գույնով ընդգծվել է իրավական պահանջերից մեկի խախտման օրինակ): Աջ կողմում ներկայացված է թարմացված հարաբերությունը, որտեղ կանաչ բջիջները ցույց են տալիս փոփոխված արժեքները: Ինձ այսպիսի գործընթաց իրականացնելուց հետո անհրաժեշտ կախվածությունները պահպանվել են.

Այլ հանրաճանաչ կիրառման ոլորտը տվյալների բազայի դիզայնն է: Սա հիշանք պետք է անել նորմալ ձևերի և նորմալացման մասին: Նորմալացում՝ դա գործընթացն է, որը հանգեցնում է հարաբերության համապատասխանեցման որոշակի պահանջներին, որոնցից յուրաքանչյուրը սահմանվում է նորմալ ձևով իր ձևով: Մենք չենք մանրամասնելու տարբեր հեռանկարների պահանջները (այս ձեռնարկը չի անելու դա, որովհետև սա է նշված ցանկացած դեպքի մասին ցանկացած ԲԴ դասագրքում), միայն կդիտարկենք, որ յուրաքանչյուրը իր ձևով օգտագործում է ֆունկցիոնալ կախվածությունների կոնցեպցիան: Ի վերջո, խոսեցինք, որ ֆունկցիոնալ կախվածությունները իրենց էությամբ Integrity constraints են, որոնք պետք է հաշվի առնվեն տվյալների բազայի նախագծման ժամանակ (այս խնդիրների համատեքստում ֆունկցիոնալ պահանջները երբեմն անվանել են սուպեր-բանalmարգ):

Եկեք դիտարկենք դրանց կիրառությունը չորս նորմալ ձևերի համար ստորև նշված նկարում: Ապառաքպ մեր հետևում, որ Բոյս-Կոդի նորմալ ձևը ավելի խիստ է, քան երրորդ ձևը, բայց միաժամանակ menos խիստ, քան չորրորդը: Վերջինի մասին դեռ չենք խոսում, քանի որ դրա համար անհրաժեշտ է հասկանալ բազմազան կախվածությունները, որոնք այս հոդվածում մեզ հետաքրքրում չեն.

Այլ ոլորտներից մեկը, որտեղ կախվածությունները գտնում են իրենց կիրառումը, դրա վրա իրականացնելու գործընթացն է տարածության չափին կրճատելը տողերի առանձին բանաձևերում, ինչպիսիք են պարզ Բայեսի դասակարգիչի կառուցումը, նշանակալի հատկանիշների առանձնացումը և ռեգրեսիոն մոդելի վերականգնումը: Օրիգինալ հոդվածներում այս խնդիրն անվանում են ավելորդ հատկանիշների սահմանումը (feature redundancy) և համապատասխան հատկանիշներ (feature relevancy) [5, 6], և այն լուծվում է ակտիվորեն տվյալների բազայի կոնցեպցիաների օգնությամբ: Այդպիսի աշխատանքների հետ միասին մենք կարող ենք ասել, որ այսօր տեղի է ունենում պահանջ լուծումների, որոնք թույլ կտան համատեղել տվյալների բազան, վերլուծությունը և վերոհիշյալ օպտիմիզացիայի խնդիրների իրականացումը մեկ գործիքի մեջ [7, 8, 9].

Հիմնական տվյալների հավաքածուի մեջ ֆունկցիոնալ կախվածությունները գտնելու համար առկա են բազմաթիվ ալգորիթմներ (որոնք արդիական են, թե ոչ): Այսպիսի ալգորիթմները կարելի է բաժանել երեք խմբի:

• Ալգորիթմներ, որոնք օգտագործում են ալգեբրայական ցանցի անցման (Lattice traversal algorithms)
• Համաձայնված արժեքների վրա հիմնված ալգորիթմներ (Difference- and agree-set algorithms)
• Այն ալգորիթմներ, որոնք հիմնված են զույգերի համեմատությունների վրա (Dependency induction algorithms)

Ալգորիթմների յուրաքանչյուր տեսակի կարճ նկարագրությունն ներկայացված է ստորև նշված աղյուսակում:


Այս դասակարգման վերաբերյալ ավելի մանրամասն կարելի է կարդալ [4]. Ստորև ներկայացված են օրինակներ ալգորիթմների յուրաքանչյուր տեսակի վրա:

Այսօր նոր ալգորիթմներ են ի հայտ գալիս, որոնք համադրում են մի քանի մոտեցում ֆունկցիոնալ կախվածությունների որոնման համար: Նման ալգորիթմների օրինակներ են Pyro [2] և HyFD [3]. Դրանց աշխատանքը վերլուծելու մտադրություն կա այս հոդվածների հաջորդ շարքում: Այս հոդվածում մենք միայն կներկայացնենք հիմնական հասկացությունները և լեմման, որոնք անհրաժեշտ են կախվածությունների հայտնաբերման տեխնիկաների ըմբռնելու համար.

Սկսենք պարզից՝ difference- և agree-set, որոնք օգտագործվում են երկրորդ տեսակի ալգորիթմներում: Difference-set-ը առավելություններ է ներկայացնում տարրերով, որոնք արժեքներով չեն համընկնում, իսկ agree-set-ը հակառակը՝ արժեքներով համընկնող տարրեր: Պետք է նշել, որ այս դեպքում մենք рассматриваем միայն կախվածության ձախ կողմը.

Այնպես որ, բարձր նշել հայտարարված կարևոր եզրույթներից մեկը ալգեբրաական ցանցն է: Ինչպես շատ ժամանակակից ալգորիթմներ օգտագործում են այս միտումը, մեզ հարկավոր է ունենալ պատկերացում, թե ինչ է դա:

Ցանցի հասկացությունը ներկայացնելու համար անհրաժեշտ է մասամբ դասավորված հավաքածուի (или partially ordered set, կրճատ՝ poset) սահմանումը:

Հայտարարում 2. Ասվում է, որ S հավաքածուն մասամբ դասավորված է ⩽ բինարային հարաբերությամբ, եթե ցանկացած a, b, c ∈ S համար կատարվում են հաջորդ հատկությունները:

1. Ռեֆլեքսիվություն, այսինքն՝ a ⩽ a
2. Անտի սիմետրիկություն, այսինքն՝ եթե a ⩽ b և b ⩽ a, ապա a = b
3. Տրանսիտիվություն, այսինքն՝ եթե a ⩽ b և b ⩽ c, ապա a ⩽ c

Այս հարաբերությունը կոչվում է (անստեղծ) մասամբ դասակարգման հարաբերություն, իսկ ինքը՝ հավաքածուն՝ մասամբ դասավորված հավաքածու: Անձնավորումը՝ ⟨S, ⩽⟩.

Որպես մասամբ դասավորված հավաքածուի ամենահեշտ օրինակ կարող ենք վերցնել բոլոր բնութագրական թվերի N՝ սովորական դասակարգման ⩽ հարաբերությամբ։ Չեն դժվարացել ստուգել, որ բոլոր անհրաժեշտ ակսիոները կատարվում են.

Ավելի նյութական օրինակ: Պետք է քննարկել բոլոր ենթահավաքածուների հավաքածուն {1, 2, 3}, որոնց դասակարգումը հիմնված է ներառման ⊆ հարաբերության վրա: Այս իրականում, այս հարաբերությունը բավարարում է մասամբ դասակարգման բոլոր պայմանները, այդ պատճառով ⟨P({1, 2, 3}), ⊆⟩՝ մասամբ դասավորված հավաքածու: Աղյուսակում ստորև պատկերված այս հավաքածուի संरույթն է. եթե մեկ տարրից կարելի է գնալ մեկ այլ տարրի, ապա նրանք հարաբերության մեջ են:

Մենք ևս պետք ենք ունենալ երկու պարզ սահմանումներ մաթեմատիկայի ոլորտում՝ սուպրեմում (supremum) և ինֆիմում (infimum).

Համաձայնեցում 3. Թող ⟨S, ⩽⟩ — մասամբ դասակարգված հավաքածու, A ⊆ S: A-ի վերին սահմանը այն թվի u ∈ S-ն է, որին վերաբերող x ∈ S-ի համար հավասար կլինի u-ի։ Թող U — բոլոր A-ի վերին սահմանների հավաքածուն։ Եթե U-ում գոյություն ունի ամենափոքր տարր, ապա այն կոչվում է սուպրեմումը և նշվում է որպես sup A։

Անալոգիկ կերպով ներդրվում է ճշգրիտ ցածր սահմանների հասկացությունը։

Նիվ 4։ Թող ⟨S, ⩽⟩ — մասամբ դասակարգված հավաքածու, A ⊆ S: A-ի ցածր սահմանը այն l ∈ S-ն է, որին վերաբերող x ∈ S-ի համար l ≤ x։ Թող L — բոլոր A-ի ցածր սահմանների հավաքածուն։ Եթե L-ում գոյություն ունի ամենամեծ տարր, ապա այն կոչվում է ինֆիմումը և նշվում է որպես inf A։

Դիտարկենք օրինակ, որը նշված է վերևում, մասամբ դասակարգված հավաքածու ⟨P ({1, 2, 3}), ⊆⟩՝ գտնելու սուպրեմում և ինֆիմում։

Հիմա կարող են ձևակերպել ալգեբրիական решետкայի սահմանումը։

Նիվ 5։ Թող ⟨P, ⩽⟩ — մասամբ դասակարգված հավաքածու, որտեղ յուրաքանչյուր երկու լրացուցիչ ենթախմբի համար գոյություն ունեն ճշգրիտ վերին և ցածր սահմաններ։ Այդ դեպքում P-ն կոչվում է ալգեբրիական решետկա։ Այս ժամանակ sup{x, y}-ը գրում են որպես x ∨ y, իսկ inf {x, y} — որպես x ∧ y։

Նայենք, որ մեր աշխատանքային օրինակ ⟨P ({1, 2, 3}), ⊆⟩ համարվում է решետկա։ Իհարկե, ցանկացած a, b ∈ P ({1, 2, 3}), a∨b = a∪b, իսկ a∧b = a∩b։ Օրինակ, դիտարկենք {1, 2} և {1, 3} հավաքածուները, և գտնենք իրենց ինֆիմումն ու սուպրեմումն։ Եթե մենք նրանց հատման վերաբերմունք ստեղծենք, ապա կստանանք {1} հավաքածուն, որը կլինի ինֆիմումը։ Սուպրեմն, սակայն, ստանում ենք նրանց միավորման միջոցով՝ {1, 2, 3}:

Համակարգային կախվածությունների իմանման ալգորիթմներում որոնման տարածքը հաճախ ներկայացվում է решետկայի տեսքով, որտեղ մեկ տարրից բաղկացած հավաքածուները (առաջին մակարդակի որոնման решետկայում, որտեղ կախվածությունների ձախ մասը բաղկացած է մեկ ատրիբուտից)։
Սկզբում դիտարկվում են կախվածություններ՝ ∅ → Մեկ ատրիբուտ։ Այս քայլը թույլ է տալիս պարզել, թե որոնք ատրիբուտներն են առաջնային բանալիներ (այսպիսի ատրիբուտների համար չկան որոշիչներ, ուստի ձախ մասը դատարկ է)։ Այնուհետև նման ալգորիթմներն անցնում են решետկայով վեր։ նշենք, որ решետկան հնարավոր է շրջանցել ամբողջովին, այդ թվում եթե ձեր ուզած մեծագույն չափը ձախ մասի համար անցանցջի, ապա ալգորիթմն այդ մակարդակը չի կամրանա։

Նկարագրում ստորև ցույց է տալիս, թե ինչպես կարելի է օգտագործել ալգեբրիական решետկան ՖԶ որոնման խնդրի լուծման մեջ։ Այստեղ յուրաքանչյուր կող (X, XY) ներկայացնում է կախվածություն։ X → Y. Օրինակ, մենք անցել ենք առաջին մակարդակը և գիտենք, թե ինչ կախվածություն է պահպանվում՝ A → B (նշենք, որ սա ցուցադրվում է կանաչ կապով գագաթների միջև A և B)։ Սա նշանակում է, որ երբ պետք է բարձրանալ решетկայով, մենք չենք կարող ստուգել կախվածություն A, C → B, քանի որ դա արդեն չի լինի նվազագույն։ Անալոգիկ մեզ չեն ստուգի, եթե պահպանված լինի կախվածություն C → B.

Բացի այդ, որպես կանոն, բոլոր ժամանակակից ալգորիթմները հասարակական որոնման համար օգտագործում են տվյալների նման կառուցվածք, ինչպիսին է բաժանումը (մասնագիտացված աղբյուրում` stripped partition [1]). Բաժանման պաշտոնական սահմանումը հետևյալն է.

Սահմանում 6. Վ пусть X ⊆ R — ռելացիայի r համար բնութագրերի խումբ: Կլաստերը պատկերացնում է r-ի տTuple-ների ինդեքսների խումբ, որոնք ունեն նույն արժեքը X-ի համար, δηλαδή c(t) = {i|ti[X] = t[X]}. Բաժանումը նրա կլաստերների ամբողջություն է, բացառելով միատի երկարությամբ կլաստերները:

Ընդհանրապես, բաժանումը բնութագրի համար X ներկայացնում է ցուցակների խումբ, որտեղ յուրաքանչյուր ցուցակ պարունակում է շարքերի համարներ նույն արժեքների համար X. ժամանակակից գրականությունում կառուցվածքը, որը ներկայացնում է բաժանումները, կոչվում է position list index (PLI). Միատի երկարությամբ կլաստերները բացառվում են PLI-ի կրճատման նպատակով, քանի որ դրանք կլաստերներ են, որոնք պարունակում են միայն ռեկանման համար, որի արժեքը միշտ հեշտ է հաստատել.

Նայենք օրինակին. Եկեք վերադարձնենք նույն դաշտը հիվանդների մասին և կառուցենք բաժանումներ колонաների համար Հիվանդ և Սեռ (նոր колонան երևում է ձախում, որտեղ նշվում են աղյուսակի շարքերի համարները):

Միևնույն ժամանակ, սահմանման համաձայն, колонայի բաժանման համար Հիվանդ իրականում կլինի դատարկ, քանի որ մենակ կլաստերները բացառվում են բաժանումից.

Բաժանումներ կարելի է ձևավորել մի քանի բնութագրերի հիման վրա: Դրա համար կա երկու ճանապարհ՝ անցնելով աղյուսակի միջով, միանգամից կառուցել բաժանում, կամ կառուցել այն մի քանի բնութագրերի ենթախմբերի հատման գործողության միջոցով: Այժմ ՖՈՒ-ի որոնման ալգորիթմները օգտագործում են երկրորդ տարբերակը.

Ընդհանրապես, որպեսզի, օրինակ, բաժանում ենք ստանալ կարող ենք, օրինակ, օգտվել ABC, բաժանումները վերցնելով AC և B (կամ ցանկացած այլ անհամատեղելի ենթախմբերից) և հատել դրանք միմյանց հետ: Երկու բաժանումների հատման գործողությունը առանձնացնում է կլաստերները ամենաերկար երկարությամբ, ընդհանուր երկու բաժանման համար.

Դարձենք մի օրինակ:

Առաջին դեպքում մենք ստանում ենք դատարկ բաժանում: Եթե նշեք աղյուսակին, իր thật, նմանատիպ արժեքներ չկա երկու բնութագրերի համար: Սակայն, եթե մենք մի փոքր փոփոխենք աղյուսակը (ճիշտ դեպքում), ապա արդեն կունենանք ոչ դատարկ հատում: Այդ դեպքում շարքեր 1 և 2 իսկապես պարունակում են նույն արժեքները բնութագրերի համար Սեռ և Ա doktor.

Այստեղ մեզ պետք կլինի փոխաբերության չափը: Բարձրաձայն:

Ընդհանրաբար, բաժանման չափը ներկայացնում է բաժանում մտնող կլաստերների քանակը (հիշում ենք, որ միատի կլաստերները չեն մտնում բաժանման մեջ):

Այժմ մենք կարող ենք սահմանել մեկ բանալի լեմմա, որը վերաբերելու համար տվյալների համար դրվագում պահպանվում է կամ ոչ.

Լեմմա 1. Ա կախվածություն A, B → C պահպանվում է, եթե և միայն եթե

Համաձայն լեմմայի, որոշելու համար, պահպանվում է կամ ոչ, պետք է կատարել չորս քայլ:

1. ձախ կողմի կախվածության համար բաժին որոշել
2. ա աջ կողմի կախվածության համար բաժին որոշել
3. առաջին և երկրորդ քայլերի արտադրյալը հաշվարկել
4. Կվիրվածքների չափերը համեմատեք, որոնք ձեռք են բերվել առաջին և երրորդ քայլերում

Ահա օրինակ, թե ինչպես ստուգել, պահվում է արդյոք կախվածությունը տվյալ լեմայի շուրջ:

Այս հոդվածում մենք վերլուծում ենք ֆունկցիոնալ կախվածություն, մոտեցված ֆունկցիոնալ կախվածություն, քննարկում որտեղ են դրանք կիրառվում, ինչպես նաև ինչ ալգորիթմներ գոյություն ունեն ՖԶ-ի որոնման համար: Մենք նաև մանրամասն վերլուծեցինք հիմնական, բայց կարևոր հասկացությունները, որոնք ակտիվորեն օգտագործվում են ժամանակակից ՖԶ որոնման ալգորիթմներում:

Գրականության հղումները:

1. Huhtala Y. և այլք: TANE: Ֆունկցիոնալ և մոտեցված կախվածությունների հայտնաբերման արդյունավետ ալգորիթմ // The computer journal. – 1999. – Թ. 42. – №. 2. – Ս. 100-111.
2. Kruse S., Naumann F. Մոտեցված կախվածությունների արդյունավետ հայտնաբերումը // Proceedings of the VLDB Endowment. – 2018. – Թ. 11. – №. 7. – Ս. 759-772.
3. Papenbrock T., Naumann F. Ֆունկցիոնալ կախվածությունների հայտնաբերման խառն նպատակ // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – Ս. 821-833.
4. Papenbrock T. և այլք. Ֆունկցիոնալ կախվածության հայտնաբերում: Ս seven ալգորիթմների փորձնական գնահատում // Proceedings of the VLDB Endowment. – 2015. – Թ. 8. – №. 10. – Ս. 1082-1093.
5. Kumar A. և այլք. Միացնե՞լ, թե՞ ոչ: Դեկտեմբերի տոներին միացնելից առաջ մտածեք // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – Ս. 19-34.
6. Abo Khamis M. և այլք. Դատարկ տ tensors -ում ուսուցում // Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – Ս. 325-340.
7. Hellerstein J. M. և այլք. MADlib վերլուծական գրադարան: կամ MAD ունակություններ, SQL // Proceedings of the VLDB Endowment. – 2012. – Թ. 5. – №. 12. – Ս. 1700-1711.
8. Qin C., Rusu F. Speculative approximations for terascale distributed gradient descent optimization // Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – Ս. 1.
9. Meng X. և այլք. Mllib: Հաշվարկային ուսուցում apache spark-ում // The Journal of Machine Learning Research. – 2016. – Թ. 17. – №. 1. – Ս. 1235-1241.

Հոդվածի հեղինակները: Անასტասիա Բիրիլլո, հետազոտող JetBrains Research, CS կենտրոնի ուսանող և Նիկիտա ԱԲՈՎ, հետազոտող JetBrains Research

Ընտանիք: habr.com