Տվյալներում ֆունկցիոնալ կախվածությունների որոնումը կիրառվում է տվյալների վերլուծության տարբեր ոլորտներում՝ տվյալների բազայի կառավարում, տվյալների մաքրում, տվյալների բազայի հակադարձ ինժեներիա և տվյալների ուսումնասիրություն: Մենք արդեն հրապարակումներ ենք արել կախվածությունների մասին: Անաստասիա Բիրիլլո և Նիկիտա Բոբրով։ Այս անգամ Անաստասիան, ով այս տարի ավարտել է Համակարգչային գիտությունների կենտրոնը, կիսվում է այս աշխատանքի զարգացմամբ՝ որպես կենտրոնում պաշտպանված հետազոտական աշխատանքի մաս։
Առաջադրանքների ընտրություն
Համակարգչային գիտությունների կենտրոնում սովորելիս սկսեցի խորությամբ ուսումնասիրել տվյալների բազաները, մասնավորապես՝ փնտրել ֆունկցիոնալ և դիֆերենցիալ կախվածություններ: Այս թեման կապված էր համալսարանում իմ կուրսային աշխատանքի թեմայի հետ, ուստի կուրսային աշխատանքի վրա աշխատելիս սկսեցի կարդալ հոդվածներ տվյալների բազաներում տարբեր կախվածությունների մասին: Ես գրեցի այս ոլորտի վերաբերյալ ակնարկ՝ իմ առաջիններից մեկը: անգլերեն լեզվով և ներկայացրեցի այն SEIM-2017 կոնֆերանսին։ Ես շատ ուրախացա, երբ իմացա, որ այն ընդունվել է, և որոշեցի ավելի խորը ուսումնասիրել թեման։ Հայեցակարգն ինքնին նոր չէ. այն սկսել է օգտագործվել դեռևս 90-ականներին, բայց նույնիսկ հիմա այն օգտագործվում է բազմաթիվ ոլորտներում։
Կենտրոնում իմ երկրորդ կիսամյակում սկսեցի հետազոտական նախագիծ՝ ֆունկցիոնալ կախվածություններ գտնելու ալգորիթմները բարելավելու համար։ Դրա վրա աշխատեցի Սանկտ Պետերբուրգի պետական համալսարանի ասպիրանտ Նիկիտա Բոբրովի հետ՝ JetBrains Research-ից։
Ֆունկցիոնալ կախվածությունների որոնման հաշվողական բարդությունը
Հիմնական խնդիրը հաշվողական բարդությունն է։ Հնարավոր նվազագույն և ոչ տրիվիալ կախվածությունների քանակը սահմանափակվում է վերևից՝ արժեքով։ 
Որտեղ 
— աղյուսակի ատրիբուտների քանակը։ Ալգորիթմների աշխատանքի ժամանակը կախված է ոչ միայն ատրիբուտների քանակից, այլև տողերի քանակից։ 90-ականներին սովորական սեղանադիր համակարգչի վրա FD-ներ որոնելու ալգորիթմները կարող էին մշակել մինչև 20 ատրիբուտ և տասնյակ հազարավոր տողեր պարունակող տվյալների հավաքածուներ մինչև մի քանի ժամվա ընթացքում։ Բազմամիջուկ պրոցեսորների վրա աշխատող ժամանակակից ալգորիթմները հայտնաբերում են կախվածություններ հարյուրավոր ատրիբուտներից (մինչև 200) և հարյուր հազարավոր տողերից բաղկացած տվյալների հավաքածուների համար մոտավորապես նույն ժամանակահատվածում։ Սակայն սա բավարար չէ. նման ժամանակը անընդունելի է իրական աշխարհի կիրառությունների մեծ մասի համար։ Հետևաբար, մենք մշակել ենք մոտեցումներ՝ առկա ալգորիթմները արագացնելու համար։
Քեշավորման սխեմաներ բաժանմունքների հատման համար
Հոդվածի առաջին մասում մենք մշակել ենք քեշավորման սխեմաներ ալգորիթմների դասի համար, որոնք օգտագործում են բաժանման հատման մեթոդը: Ատրիբուտի բաժանումը ցուցակների հավաքածու է, որտեղ յուրաքանչյուր ցուցակ պարունակում է տողերի քանակը՝ ատրիբուտի համար նույն արժեքներով: Յուրաքանչյուր նման ցուցակ կոչվում է կլաստեր: Շատ ժամանակակից ալգորիթմներ օգտագործում են բաժանումներ՝ որոշելու համար, թե արդյոք կախվածությունը տեղին է, թե ոչ, այսինքն՝ նրանք հետևում են լեմմային՝ Կախվածություն 
պահպանվում է, եթե 
. Այստեղ 
Նշանակվում է բաժանումը և օգտագործվում է բաժանման չափի հասկացությունը՝ դրանում կլաստերների քանակը: Բաժիններ օգտագործող ալգորիթմները, երբ կախվածությունը խախտվում է, կախվածության ձախ կողմում ավելացնում են լրացուցիչ ատրիբուտներ, ապա վերահաշվարկում են այն՝ կատարելով բաժանման հատման գործողությունը: Հոդվածներում նման գործողությունը կոչվում է մասնագիտացում: Սակայն մենք նկատեցինք, որ կախվածությունների համար նախատեսված բաժանումները, որոնք կպահպանվեն միայն մասնագիտացման մի քանի փուլերից հետո, կարող են ակտիվորեն վերօգտագործվել, ինչը կարող է զգալիորեն կրճատել ալգորիթմների աշխատանքի ժամանակը, քանի որ հատման գործողությունը թանկ է:
Հետևաբար, մենք առաջարկեցինք Շենոնի էնտրոպիայի և Ջինիի անորոշության վրա հիմնված հևրիստիկա, ինչպես նաև մեր մետրիկան, որը մենք անվանեցինք հակադարձ էնտրոպիա: Այն Շենոնի էնտրոպիայի փոքր փոփոխություն է և աճում է տվյալների բազմության եզակիության աճին զուգընթաց: Առաջարկվող հևրիստիկան հետևյալն է.
Այստեղ 
— վերջերս հաշվարկված բաժանման եզակիության աստիճանը 
Իսկ 
-ն առանձին ատրիբուտների եզակիության աստիճանների միջնարժեքն է: Վերը նկարագրված բոլոր երեք չափանիշները ստուգվել են որպես եզակիության չափանիշներ: Կարելի է նաև նշել, որ հևրիստիկաները ունեն երկու մոդիֆիկատոր: Առաջինը ցույց է տալիս, թե որքան մոտ է ընթացիկ բաժինը առաջնային բանալուն և թույլ է տալիս ավելի մեծ քանակությամբ քեշավորել այն բաժինները, որոնք հեռու են թեկնածու բանալուց: Երկրորդ մոդիֆիկատորը թույլ է տալիս հետևել քեշի զբաղվածությանը և այդպիսով խրախուսում է քեշին ավելի շատ բաժիններ ավելացնել, եթե կա ազատ տարածք: Այս խնդրի հաջող լուծումը թույլ է տվել արագացնել PYRO ալգորիթմը 10-40%-ով՝ կախված տվյալների բազմությունից: Հարկ է նշել, որ PYRO ալգորիթմն ամենահաջողակն է այս ոլորտում:
Ստորև բերված նկարը ցույց է տալիս առաջարկվող հևրիստիկայի կիրառման արդյունքները՝ համեմատած մետաղադրամի նետման քեշավորման բազային մոտեցման հետ։ X առանցքը լոգարիթմական է։
Բաժանմունքները պահելու այլընտրանքային եղանակ
Այնուհետև մենք առաջարկեցինք բաժինները պահելու այլընտրանքային եղանակ։ Բաժանումները կլաստերների հավաքածու են, որոնցից յուրաքանչյուրը պահպանում է որոշակի ատրիբուտների համար նույն արժեքներով զույգ թվեր։ Այս կլաստերները կարող են պարունակել զույգ թվերի երկար հաջորդականություններ, օրինակ, եթե աղյուսակում տվյալները դասավորված են։ Հետևաբար, մենք առաջարկեցինք բաժինները պահելու սեղմման սխեմա, այն է՝ արժեքների ինտերվալային պահպանում բաժինների կլաստերներում.
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Առաջին~ինտերվալ}, underbrace{7, 8}_{Երկրորդ~ինտերվալ}, 10}}\ downarrow{Սեղմում}\ pi(X) = {{underbrace{$, 1, 5}_{Առաջին~ինտերվալ}, underbrace{7, 8}_{Երկրորդ~ինտերվալ}, 10}}$$display$$
Այս մեթոդը կարողացավ կրճատել հիշողության սպառումը TANE ալգորիթմի գործողության ընթացքում 1-ից մինչև 25%: TANE ալգորիթմը FD-ներ որոնելու դասական ալգորիթմ է. այն իր գործողության ընթացքում օգտագործում է բաժանումներ: Գործնականում TANE ալգորիթմը ընտրվեց, քանի որ դրանում ինտերվալային պահպանում իրականացնելը շատ ավելի հեշտ էր, քան, օրինակ, PYRO-ում՝ առաջարկվող մոտեցումը աշխատո՞ւմ է: Ստացված արդյունքները ներկայացված են ստորև բերված նկարում: X առանցքը լոգարիթմական է:
ADBIS-2019 կոնֆերանս
Ուսումնասիրության արդյունքների հիման վրա ես հոդված հրապարակեցի 2019 թվականի սեպտեմբերին։ 23-րդ Եվրոպական կոնֆերանսում՝ նվիրված տվյալների բազաների և տեղեկատվական համակարգերի առաջընթացին (ADBIS-2019): Ներկայացման ժամանակ աշխատանքը նշեց Բերնհարդ Թալհայմը՝ տվյալների բազաների ոլորտի նշանակալի անձնավորությունը: Հետազոտության արդյունքները հիմք հանդիսացան Սանկտ Պետերբուրգի պետական համալսարանի մաթեմատիկայի և մեխանիկայի ֆակուլտետի մագիստրոսական ծրագրում իմ ատենախոսության համար, որի ընթացքում երկու առաջարկվող մոտեցումներն էլ (քեշավորում և սեղմում) ներդրվեցին երկու ալգորիթմներում՝ TANE-ում և PYRO-ում: Միևնույն ժամանակ, արդյունքները ցույց տվեցին, որ առաջարկվող մոտեցումները համընդհանուր են, քանի որ երկու ալգորիթմներն էլ՝ երկու մոտեցումներով, ցույց տվեցին հիշողության սպառման զգալի կրճատում, ինչպես նաև ալգորիթմների կատարման ժամանակի զգալի կրճատում:
Source: www.habr.com
