Ներածություն ֆունկցիոնալ կախվածություններին

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

Մենք կդիտարկենք ֆունկցիոնալ կախվածությունները հարաբերական տվյալների բազաների համատեքստում: Շատ կոպիտ ասած, նման շտեմարաններում տեղեկատվությունը պահվում է աղյուսակների տեսքով։ Այնուհետև մենք օգտագործում ենք մոտավոր հասկացություններ, որոնք փոխարինելի չեն խիստ հարաբերական տեսության մեջ. մենք ինքնին աղյուսակը կանվանենք հարաբերություն, սյունակները՝ ատրիբուտներ (դրանց հավաքածուն՝ հարաբերությունների սխեման) և ատրիբուտների ենթաբազմության վրա տողերի արժեքների հավաքածու։ - մի բազմոց:

Օրինակ, վերը նշված աղյուսակում. (Բենսոն, Մ, Մ օրգան) ատրիբուտների բազմություն է (Հիվանդ, Պողոս, բժիշկ).
Ավելի պաշտոնական, սա գրված է հետևյալ կերպ. [Հիվանդ, սեռ, բժիշկ] = (Բենսոն, Մ, Մ օրգան).
Այժմ մենք կարող ենք ներկայացնել ֆունկցիոնալ կախվածության հայեցակարգը (FD).

Սահմանում 1. R հարաբերակցությունը բավարարում է X → Y դաշնային օրենքը (որտեղ X, Y ⊆ R), եթե և միայն եթե որևէ զույգերի համար , ∈ R-ն գործում է՝ եթե [X] = [X], ապա [Y] = [Y]. Այս դեպքում մենք ասում ենք, որ X-ը (որոշիչը կամ ատրիբուտների սահմանող բազմությունը) ֆունկցիոնալորեն որոշում է Y-ը (կախյալ բազմությունը):

Այսինքն՝ դաշնային օրենքի առկայությունը X → Y նշանակում է, որ եթե մենք ունենք երկու tuples in R և դրանք համընկնում են ատրիբուտներով X, ապա ատրիբուտներով կհամընկնեն Y.
Եվ հիմա, հերթականությամբ. Եկեք նայենք ատրիբուտներին Հիվանդ и Paul որի համար ցանկանում ենք պարզել՝ նրանց միջեւ կախվածություններ կա՞ն, թե՞ ոչ։ Նման մի շարք հատկանիշների համար կարող են գոյություն ունենալ հետևյալ կախվածությունները.

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

Ինչպես սահմանված է վերևում, որպեսզի առաջին կախվածությունը պահպանվի, յուրաքանչյուր եզակի սյունակի արժեքը Հիվանդ միայն մեկ սյունակի արժեքը պետք է համապատասխանի Paul. Եվ օրինակ աղյուսակի համար դա իսկապես այդպես է: Այնուամենայնիվ, սա հակառակ ուղղությամբ չի աշխատում, այսինքն, երկրորդ կախվածությունը չի բավարարվում, և հատկանիշը. Paul համար որոշիչ չէ Հիվանդ. Նմանապես, եթե վերցնենք կախվածությունը Բժիշկ → Հիվանդ, տեսնում եք, որ այն խախտված է, քանի որ արժեքը Շիկահավ այս հատկանիշն ունի մի քանի տարբեր իմաստներ. Էլիս և Գրեհեմ.

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

• ոչ տրիվիալ, այսինքն՝ կախվածության աջ կողմը ձախի ենթաբազմություն չէ (Y ̸⊆ X);
• նվազագույն, այսինքն՝ նման կախվածություն չկա Z → YՈր Z ⊂ X.

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

Եկեք հաշվարկենք սխալը Բժիշկ → Հիվանդ վերը նշված օրինակից: Մենք ունենք երկու tuples, որոնց արժեքները տարբերվում են հատկանիշով Հիվանդ, բայց համընկնում են Բժիշկ: [Բժիշկ, հիվանդ] = (Ռոբին, Էլիս) Եվ [Բժիշկ, հիվանդ] = (Ռոբին, Գրեհեմ) Սխալի սահմանումից հետո մենք պետք է հաշվի առնենք բոլոր հակամարտող զույգերը, ինչը նշանակում է, որ դրանք կլինեն երկուսը., ) և դրա հակադարձ (, ) Եկեք այն փոխարինենք բանաձևով և ստացենք.

Հիմա եկեք փորձենք պատասխանել հարցին. «Ինչո՞ւ է այդ ամենը նախատեսված»: Փաստորեն, դաշնային օրենքները տարբեր են: Առաջին տեսակն այն կախվածություններն են, որոնք որոշվում են ադմինիստրատորի կողմից տվյալների բազայի նախագծման փուլում: Սովորաբար դրանք քիչ են, խիստ, և հիմնական կիրառումը տվյալների նորմալացումն է և հարաբերական սխեմայի ձևավորումը:

Երկրորդ տեսակը կախվածությունն է, որը ներկայացնում է «թաքնված» տվյալներ և ատրիբուտների միջև նախկինում անհայտ հարաբերություններ: Այսինքն, նախագծման ժամանակ նման կախվածությունների մասին չեն մտածել, և դրանք գտնվել են առկա տվյալների հավաքածուի համար, որպեսզի հետագայում, բացահայտված բազմաթիվ դաշնային օրենքների հիման վրա, հնարավոր լինի որևէ եզրակացություն անել պահված տեղեկատվության վերաբերյալ: Հենց այս կախվածությունների հետ ենք մենք աշխատում: Դրանցով զբաղվում է տվյալների արդյունահանման մի ամբողջ ոլորտ՝ որոնման տարբեր մեթոդներով և դրանց հիման վրա կառուցված ալգորիթմներով: Եկեք պարզենք, թե ինչպես կարող են օգտակար լինել ցանկացած տվյալների մեջ հայտնաբերված ֆունկցիոնալ կախվածությունները (ճշգրիտ կամ մոտավոր):

Այսօր կախվածության հիմնական կիրառություններից մեկը տվյալների մաքրումն է: Այն ներառում է գործընթացների մշակում՝ «կեղտոտ տվյալները» բացահայտելու և այնուհետև դրանք շտկելու համար: «Կեղտոտ տվյալների» նշանավոր օրինակներն են կրկնօրինակները, տվյալների սխալները կամ տառասխալները, բացակայող արժեքները, հնացած տվյալները, լրացուցիչ բացատները և այլն:

Տվյալների սխալի օրինակ.

Տվյալների կրկնօրինակների օրինակ.

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

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

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

Մեկ այլ ոլորտ, որտեղ կախվածությունները գտել են իրենց կիրառումը, հատկանիշի տարածության չափերի կրճատումն է այնպիսի առաջադրանքներում, ինչպիսիք են միամիտ Bayes դասակարգչի կառուցումը, նշանակալի հատկանիշների բացահայտումը և ռեգրեսիոն մոդելի վերապարամետրացումը: Բնօրինակ հոդվածներում այս խնդիրը կոչվում է ավելորդ և հատկանիշի համապատասխանության որոշում [5, 6], և այն լուծվում է տվյալների բազայի հասկացությունների ակտիվ օգտագործմամբ։ Նման աշխատանքների հայտնվելով, կարելի է ասել, որ այսօր կա այնպիսի լուծումների պահանջարկ, որոնք թույլ են տալիս միավորել տվյալների բազան, վերլուծությունը և վերը նշված օպտիմալացման խնդիրների իրականացումը մեկ գործիքի մեջ [7, 8, 9]:

Կան բազմաթիվ ալգորիթմներ (ինչպես ժամանակակից, այնպես էլ ոչ այնքան ժամանակակից) տվյալների հավաքածուում դաշնային օրենքների որոնման համար: Նման ալգորիթմները կարելի է բաժանել երեք խմբի.

• Ալգորիթմներ, որոնք օգտագործում են հանրահաշվական ցանցերի անցումը (Ցանցային անցման ալգորիթմներ)
• Համաձայնեցված արժեքների որոնման վրա հիմնված ալգորիթմներ (Տարբերության և համաձայնության սահմանման ալգորիթմներ)
• Զույգ համեմատությունների վրա հիմնված ալգորիթմներ (կախվածության ինդուկցիայի ալգորիթմներ)

Ալգորիթմի յուրաքանչյուր տեսակի համառոտ նկարագրությունը ներկայացված է ստորև բերված աղյուսակում.


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

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

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

Մեկ այլ կարևոր հասկացություն, որը հանդիպեցինք վերևում, հանրահաշվական ցանցն է: Քանի որ շատ ժամանակակից ալգորիթմներ գործում են այս հայեցակարգով, մենք պետք է պատկերացում ունենանք, թե ինչ է դա:

Վանդակ հասկացությունը ներկայացնելու համար անհրաժեշտ է սահմանել մասնակի պատվիրված բազմություն (կամ մասամբ պատվիրված հավաքածու՝ կրճատ՝ պոզետ)։

Սահմանում 2. S բազմությունը մասնակիորեն դասավորված է ⩽ երկուական կապով, եթե a, b, c ∈ S բոլորի համար բավարարված են հետևյալ հատկությունները.

1. Ռեֆլեքսիվություն, այսինքն՝ ա ⩽ ա
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: x ⩽ u: Թող U լինի S-ի բոլոր վերին սահմանների բազմությունը: Եթե U-ում կա ամենափոքր տարրը, ապա այն կոչվում է գերագույն և նշանակվում է sup A:

Նմանապես ներկայացվում է ճշգրիտ ստորին սահմանի հայեցակարգը:

Սահմանում 4. Թող ⟨S, ⩽⟩ լինի մասնակի կարգավորված բազմություն, A ⊆ S: A-ի ինֆիմումը l ∈ S տարր է, որպեսզի ∀x ∈ S: l ⩽ x: Թող L-ն լինի S-ի բոլոր ստորին սահմանների բազմությունը: Եթե L-ում կա ամենամեծ տարրը, ապա այն կոչվում է infimum և նշվում է որպես 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} բազմությունները և գտեք դրանց infimum-ը և supremum-ը: Եթե ​​հատենք դրանք, կստանանք {1} բազմությունը, որը կլինի infimum-ը: Գերագույնը ստանում ենք դրանք համադրելով՝ {1, 2, 3}։

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

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

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

Սահմանում 6. Թող X ⊆ R լինի ատրիբուտների բազմություն r հարաբերության համար: Կլաստերը r-ում բազմակի ինդեքսների բազմություն է, որոնք ունեն նույն արժեքը X-ի համար, այսինքն՝ c(t) = {i|ti[X] = t[X]}: Բաժանմունքը կլաստերների մի շարք է՝ բացառելով միավորի երկարության կլաստերները.

Պարզ բառերով, հատկանիշի միջնորմ X ցուցակների մի շարք է, որտեղ յուրաքանչյուր ցուցակ պարունակում է նույն արժեքներով տողերի համարներ X. Ժամանակակից գրականության մեջ միջնորմները ներկայացնող կառուցվածքը կոչվում է դիրքերի ցուցակի ինդեքս (PLI): Միավորի երկարությամբ կլաստերները բացառվում են PLI սեղմման նպատակներով, քանի որ դրանք կլաստերներ են, որոնք պարունակում են միայն ռեկորդային թիվ՝ եզակի արժեքով, որը միշտ հեշտ կլինի նույնականացնել:

Դիտարկենք մի օրինակ։ Եկեք վերադառնանք հիվանդների հետ նույն աղյուսակին և կառուցենք միջնորմներ սյուների համար Հիվանդ и Paul (ձախ կողմում հայտնվել է նոր սյունակ, որում նշված են աղյուսակի տողերի համարները).

Ընդ որում, ըստ սահմանման, սյունակի համար նախատեսված բաժանումը Հիվանդ իրականում դատարկ կլինի, քանի որ առանձին կլաստերները բացառված են բաժանումից:

Միջնորմները կարելի է ձեռք բերել մի քանի հատկանիշներով. Եվ դա անելու երկու եղանակ կա՝ անցնելով աղյուսակը, կառուցեք բաժանմունք՝ օգտագործելով բոլոր անհրաժեշտ ատրիբուտները միանգամից, կամ կառուցեք այն՝ օգտագործելով միջնորմների հատման գործողությունը՝ օգտագործելով ատրիբուտների ենթաբազմություն: Դաշնային օրենքների որոնման ալգորիթմներն օգտագործում են երկրորդ տարբերակը:

Պարզ բառերով, օրինակ ստանալ բաժանում ըստ սյունակների Այբբենարան, կարող եք բաժանումներ վերցնել AC и B (կամ տարանջատված ենթաբազմությունների ցանկացած այլ բազմություն) և հատել դրանք միմյանց հետ: Երկու միջնորմների հատման գործողությունը ընտրում է ամենամեծ երկարության կլաստերները, որոնք ընդհանուր են երկու բաժանմունքների համար:

Դիտարկենք օրինակ.

Առաջին դեպքում մենք ստացանք դատարկ միջնորմ։ Եթե ​​ուշադիր նայեք աղյուսակին, ապա իսկապես, երկու հատկանիշների համար նույնական արժեքներ չկան: Եթե ​​մի փոքր փոփոխենք աղյուսակը (պատյանը աջ կողմում), մենք արդեն կստանանք ոչ դատարկ խաչմերուկ։ Ավելին, 1-ին և 2-րդ տողերը իրականում պարունակում են նույն արժեքները ատրիբուտների համար Paul и Բժիշկ.

Հաջորդը, մեզ անհրաժեշտ կլինի այնպիսի հայեցակարգ, ինչպիսին է բաժանման չափը: Ձևականորեն.

Պարզ ասած, բաժանման չափը բաժանման մեջ ներառված կլաստերների քանակն է (հիշեք, որ առանձին կլաստերները բաժանման մեջ ներառված չեն):

Այժմ մենք կարող ենք սահմանել հիմնական լեմաներից մեկը, որը տվյալ միջնորմների համար թույլ է տալիս որոշել՝ արդյոք կախվածությունը պահպանվում է, թե ոչ.

Լեմմա 1. A, B → C կախվածությունը գործում է, եթե և միայն, եթե

Ըստ լեմմայի՝ որոշելու համար, թե արդյոք կախվածությունը պահպանվում է, պետք է կատարվի չորս քայլ.

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

Ստորև բերված է մի օրինակ՝ ստուգելու, թե արդյոք կախվածությունը պահպանվում է այս լեմմայի համաձայն.

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

Հղումներ:

1. Huhtala Y. et al. ՏԱՆԵ. Գործառական և մոտավոր կախվածությունների հայտնաբերման արդյունավետ ալգորիթմ //Համակարգչային ամսագիր. – 1999. – T. 42. – No. 2. – էջ 100-111։
2. Kruse S., Naumann F. Մոտավոր կախվածությունների արդյունավետ հայտնաբերում // VLDB Endowment-ի վարույթ: – 2018. – T. 11. – No. 7. – էջ 759-772։
3. Papenbrock T., Naumann F. Հիբրիդային մոտեցում ֆունկցիոնալ կախվածության բացահայտմանը // Տվյալների կառավարման միջազգային կոնֆերանսի 2016թ. – ACM, 2016. – էջ 821-833:
4. Papenbrock T. et al. Ֆունկցիոնալ կախվածության բացահայտում. Յոթ ալգորիթմների փորձարարական գնահատում //VLDB Endowment-ի գործը: – 2015. – T. 8. – No. 10. – էջ 1082-1093։
5. Kumar A. et al. Միանալ, թե՞ չմիանալ. կրկնակի մտածել միանալու մասին նախքան խաղարկային ընտրությունը //Տվյալների կառավարման միջազգային կոնֆերանսի 2016թ. – ACM, 2016. – էջ 19-34:
6. Abo Khamis M. et al. Տվյալների բազայի ուսուցում նոսր թենզորներով //ACM SIGMOD-SIGACT-SIGAI 37-րդ սիմպոզիումի նյութեր Տվյալների բազայի համակարգերի սկզբունքների վերաբերյալ: – ACM, 2018. – էջ 325-340:
7. Hellerstein JM et al. MADlib վերլուծական գրադարան. կամ MAD skills, SQL // Proceedings of the VLDB Endowment: – 2012. – T. 5. – No. 12. – էջ 1700-1711։
8. Qin C., Rusu F. Speculative approximations for terascale distributed gradient descent optimization //Cloud-ում տվյալների վերլուծության չորրորդ աշխատաժողովի նյութեր: – ACM, 2015. – P. 1:
9. Meng X. et al. Mllib: Մեքենայի ուսուցում apache spark-ում //The Journal of Machine Learning Research. – 2016. – T. 17. – No. 1. – էջ 1235-1241։

Հոդվածի հեղինակներ. Անաստասիա Բիրիլո, հետազոտող ժ JetBrains հետազոտություն, CS կենտրոնի ուսանող и Նիկիտա Բոբրով, հետազոտող ժ JetBrains հետազոտություն

Source: www.habr.com