Бұл мақалада біз дерекқорлардағы функционалдық тәуелділіктер туралы айтатын боламыз - олар не, олар қайда пайдаланылады және оларды табу үшін қандай алгоритмдер бар.
Функционалдық тәуелділіктерді реляциялық деректер қоры контекстінде қарастырамыз. Шамамен айтқанда, мұндай деректер қорларында ақпарат кесте түрінде сақталады. Әрі қарай, біз қатаң реляциялық теорияда өзара алмастырылмайтын шамамен ұғымдарды қолданамыз: кестенің өзін қатынас, бағандарды - атрибуттар (олардың жиыны - қатынас схемасы) және атрибуттардың ішкі жиынындағы жол мәндерінің жиыны деп атаймыз. - кортеж.
Мысалы, жоғарыдағы кестеде (Бенсон, М, М органы) атрибуттар кортежі болып табылады (Науқас, Пол, Дәрігер).
Ресми түрде бұл келесідей жазылған: [Науқас, жыныс, дәрігер] = (Бенсон, М, М органы).
Енді біз функционалдық тәуелділік (FD) ұғымын енгізе аламыз:
Анықтама 1. R қатынасы X → Y федералды заңын (мұндағы X, Y ⊆ R) қанағаттандырады, егер қандай да бір кортеждер үшін , ∈ R орындалады: егер [X] = [X], содан кейін [Y] = [Y]. Бұл жағдайда X (анықтаушы немесе атрибуттардың анықтаушы жиыны) Y (тәуелді жиын) функционалды түрде анықтайды деп айтамыз.
Басқаша айтқанда, федералды заңның болуы X → Y дегенді білдіреді, егер бізде екі кортеж болса R және олар атрибуттары бойынша сәйкес келеді X, содан кейін олар атрибуттарда сәйкес келеді Y.
Ал енді ретімен. Атрибуттарды қарастырайық Науқас и Секс ол үшін олардың арасында тәуелділік бар ма, жоқ па соны білгіміз келеді. Мұндай атрибуттар жиынтығы үшін келесі тәуелділіктер болуы мүмкін:
- Пациент → Жынысы
- Жынысы → Пациент
Жоғарыда анықталғандай, бірінші тәуелділікті сақтау үшін әрбір бірегей баған мәні Науқас тек бір баған мәні сәйкес келуі керек Секс. Ал мысал кесте үшін бұл шынымен де солай. Бірақ бұл қарама-қарсы бағытта жұмыс істемейді, яғни екінші тәуелділік қанағаттандырылмайды және атрибут Секс үшін анықтаушы болып табылмайды Науқас. Сол сияқты, егер тәуелділікті алсақ Дәрігер → Пациент, сіз оның бұзылғанын көре аласыз, өйткені мән Робин бұл атрибуттың бірнеше түрлі мағынасы бар - Эллис және Грэм.
Осылайша, функционалдық тәуелділіктер кесте атрибуттарының жиындары арасындағы бар байланыстарды анықтауға мүмкіндік береді. Осыдан кейін біз ең қызықты байланыстарды, дәлірек айтқанда, осындайларды қарастырамыз X → Yолар қандай:
- тривиальды емес, яғни тәуелділіктің оң жағы сол жақтың ішкі жиыны емес (Y ̸⊆ X);
- минималды, яғни мұндай тәуелділік жоқ Z → Yсол Z ⊂ X.
Осы уақытқа дейін қарастырылған тәуелділіктер қатаң болды, яғни олар кестеде ешқандай бұзушылықтарды қарастырмады, бірақ олардан басқа, кортеждердің мәндері арасында кейбір сәйкессіздіктерге жол беретіндер де бар. Мұндай тәуелділіктер жуық деп аталатын бөлек класқа орналастырылады және кортеждердің белгілі бір саны үшін бұзылуына рұқсат етіледі. Бұл сома қателіктің максималды индикаторы emax арқылы реттеледі. Мысалы, қателік деңгейі = 0.01 тәуелділікті қарастырылатын атрибуттар жиынындағы қолжетімді кортеждердің 1% бұзуы мүмкін екенін білдіруі мүмкін. Яғни, 1000 жазба үшін ең көп дегенде 10 кортеж Федералдық заңды бұзуы мүмкін. Біз салыстырылатын кортеждердің жұптық әр түрлі мәндеріне негізделген сәл басқа метриканы қарастырамыз. Тәуелділік үшін X → Y көзқарасы бойынша r ол былай қарастырылады:
үшін қатені есептейік Дәрігер → Пациент жоғарыдағы мысалдан. Бізде мәндері атрибут бойынша әр түрлі болатын екі кортеж бар Науқас, бірақ сәйкес келеді Дәрігер: [Дәрігер, пациент] = (Робин, Эллис) Және [Дәрігер, пациент] = (Робин, Грэм). Қатенің анықтамасынан кейін біз барлық қарама-қайшы жұптарды ескеруіміз керек, яғни олардың екеуі болады: (, ) және оның кері (, ). Оны формулаға қойып, мынаны аламыз:
Енді «бәрі не үшін?» деген сұраққа жауап беруге тырысайық. Іс жүзінде федералды заңдар әртүрлі. Бірінші түрі - дерекқорды жобалау кезеңінде әкімші анықтайтын тәуелділіктер. Олар әдетте саны жағынан аз, қатаң және негізгі қолданбасы деректерді қалыпқа келтіру және реляциялық схеманы жобалау болып табылады.
Екінші түрі – «жасырын» деректерді және атрибуттар арасындағы бұрын белгісіз қатынастарды көрсететін тәуелділіктер. Яғни, мұндай тәуелділіктер жобалау кезінде ойластырылмаған және олар бар деректер жиынтығы үшін табылған, сондықтан кейінірек көптеген анықталған федералды заңдар негізінде сақталған ақпарат туралы кез келген қорытынды жасауға болады. Біз дәл осы тәуелділіктермен жұмыс істейміз. Олармен әртүрлі іздеу әдістерімен және олардың негізінде құрылған алгоритмдермен деректерді өңдеудің тұтас саласы айналысады. Кез келген деректерде табылған функционалдық тәуелділіктердің (дәл немесе шамамен) қалай пайдалы болуы мүмкін екенін анықтайық.
Бүгінгі таңда тәуелділіктердің негізгі қосымшаларының бірі деректерді тазалау болып табылады. Ол «лас деректерді» анықтау, содан кейін оларды түзету процестерін әзірлеуді қамтиды. «Лас деректердің» көрнекті мысалдары көшірмелер, деректер қателері немесе теру қателері, жетіспейтін мәндер, ескірген деректер, қосымша бос орындар және т.б.
Деректер қатесінің мысалы:
Деректердегі көшірмелердің мысалы:
Мысалы, бізде орындалуы керек федералдық заңдардың кестесі мен жиынтығы бар. Бұл жағдайда деректерді тазалау Федералдық заңдардың дұрыс болуы үшін деректерді өзгертуді қамтиды. Бұл жағдайда өзгертулер саны аз болуы керек (бұл процедураның өз алгоритмдері бар, біз бұл мақалада тоқталмаймыз). Төменде осындай деректерді түрлендірудің мысалы келтірілген. Сол жақта қажетті FL сәйкес келмейтін бастапқы қарым-қатынас (FL бірінің бұзылуының мысалы қызыл түспен белгіленген). Оң жақта өзгертілген мәндерді көрсететін жасыл ұяшықтары бар жаңартылған қатынас. Осы процедурадан кейін қажетті тәуелділіктер сақтала бастады.
Тағы бір танымал қолданба дерекқорды жобалау болып табылады. Бұл жерде қалыпты формалар мен қалыпқа келтіруді еске түсірген жөн. Нормаландыру - бұл қатынасты белгілі бір талаптар жиынтығына сәйкес келтіру процесі, олардың әрқайсысы өзінше қалыпты формамен анықталады. Біз әртүрлі қалыпты формалардың талаптарын сипаттамаймыз (бұл жаңадан бастаушыларға арналған дерекқор курсы бойынша кез келген кітапта жасалады), бірақ олардың әрқайсысы функционалдық тәуелділіктер түсінігін өзінше қолданатынын ғана атап өтеміз. Өйткені, FL - бұл дерекқорды жобалау кезінде ескерілетін тұтастық шектеулері (осы тапсырманың контекстінде FL кейде суперкілт деп аталады).
Төмендегі суреттегі төрт қалыпты пішінге олардың қолдануын қарастырайық. Еске салайық, Boyce-Codd қалыпты формасы үшінші формаға қарағанда қатаңырақ, бірақ төртіншіден азырақ. Біз әзірше соңғысын қарастырмаймыз, өйткені оны тұжырымдау осы мақалада бізге қызық емес көп мәнді тәуелділіктерді түсінуді талап етеді.
Тәуелділіктер өз қолданбасын тапқан тағы бір сала - қарапайым Bayes жіктеуішін құру, маңызды мүмкіндіктерді анықтау және регрессия үлгісін қайта параметрлеу сияқты тапсырмалардағы мүмкіндіктер кеңістігінің өлшемділігін азайту. Түпнұсқа мақалаларда бұл тапсырма артық және мүмкіндіктің өзектілігін анықтау деп аталады [5, 6] және ол мәліметтер қоры ұғымдарын белсенді қолдану арқылы шешіледі. Мұндай жұмыстардың пайда болуымен бүгінгі таңда мәліметтер базасын, аналитиканы және жоғарыда аталған оңтайландыру мәселелерін жүзеге асыруды бір құралға біріктіруге мүмкіндік беретін шешімдерге сұраныс бар деп айта аламыз [7, 8, 9].
Деректер жиынында федералдық заңдарды іздеудің көптеген алгоритмдері бар (қазіргі және соншалықты заманауи емес).Мұндай алгоритмдерді үш топқа бөлуге болады:
- Алгебралық торлардың өтуін пайдаланатын алгоритмдер (торлы торлардың өту алгоритмдері)
- Келісілген мәндерді іздеуге негізделген алгоритмдер (Айырмашылық және келісілген алгоритмдер)
- Жұптық салыстыруға негізделген алгоритмдер (Тәуелділік индукциясы алгоритмдері)
Алгоритмнің әрбір түрінің қысқаша сипаттамасы төмендегі кестеде берілген:
Бұл классификация туралы толығырақ оқуға болады [4]. Төменде әр түрге арналған алгоритмдердің мысалдары берілген:
Қазіргі уақытта функционалдық тәуелділікті табудың бірнеше тәсілдерін біріктіретін жаңа алгоритмдер пайда болуда. Мұндай алгоритмдердің мысалдары Pyro [2] және HyFD [3]. Олардың жұмысына талдау осы серияның келесі мақалаларында күтіледі. Бұл мақалада біз тәуелділікті анықтау әдістерін түсіну үшін қажет негізгі ұғымдар мен лемманы ғана қарастырамыз.
Қарапайымнан бастайық - екінші типтегі алгоритмдерде қолданылатын айырмашылық және келісілген жиын. Айырмашылық жиыны – мәндері бірдей емес кортеждер жиыны, ал келісімді жиын – керісінше, бірдей мәндерге ие кортеждер. Айта кетерлігі, бұл жағдайда тәуелділіктің сол жағын ғана қарастырамыз.
Жоғарыда кездескен тағы бір маңызды ұғым - алгебралық тор. Көптеген заманауи алгоритмдер бұл тұжырымдамада жұмыс істейтіндіктен, біз оның не екенін түсінуіміз керек.
Тор түсінігін енгізу үшін жартылай реттелген жиынды (немесе жартылай реттелген жиынды, қысқартылған посет) анықтау қажет.
Анықтама 2. S жиыны екілік қатынас ⩽ бойынша ішінара реттелген деп аталады, егер барлық a, b, c ∈ S үшін келесі қасиеттер орындалса:
- Рефлексивтілік, яғни a ⩽ a
- Антисиметрия, яғни a ⩽ b және b ⩽ a болса, онда a = b
- Өтпелілік, яғни a ⩽ b және b ⩽ c үшін a ⩽ c
Мұндай қатынасты (бос) ішінара реттілік қатынас деп, ал жиынның өзін ішінара реттелген жиын деп атайды. Ресми белгілеу: ⟨S, ⩽⟩.
Жартылай реттелген жиынның қарапайым мысалы ретінде әдеттегі реттік қатынасы ⩽ бар барлық натурал сандар N жиынын алуға болады. Барлық қажетті аксиомалардың орындалғанын тексеру оңай.
Неғұрлым мағыналы мысал. ⊆ қосу қатынасы бойынша реттелген барлық ішкі жиындардың {1, 2, 3} жиынын қарастырайық. Шынында да, бұл қатынас барлық жартылай реттілік шарттарын қанағаттандырады, сондықтан ⟨P ({1, 2, 3}), ⊆⟩ жартылай реттелген жиын болып табылады. Төмендегі суретте осы жиынның құрылымы көрсетілген: егер бір элемент басқа элементке көрсеткілер арқылы жетуге болатын болса, онда олар реттік қатынаста болады.
Математика саласының тағы екі қарапайым анықтамасы қажет болады - супримум және инфимум.
Анықтама 3. ⟨S, ⩽⟩ жартылай реттелген жиын, A ⊆ S болсын. А-ның жоғарғы шекарасы ∀x ∈ S: x ⩽ u болатын u ∈ S элементі. U S-тің барлық жоғарғы шекараларының жиыны болсын. Егер U-де ең кіші элемент болса, онда ол супремум деп аталады және A sup деп белгіленеді.
Дәл төменгі шек ұғымы да осылай енгізілген.
Анықтама 4. ⟨S, ⩽⟩ жартылай реттелген жиын, A ⊆ S болсын. А-ның инфимумы ∀x ∈ S: l ⩽ x болатындай l ∈ S элементі. L - S-тің барлық төменгі шекараларының жиыны болсын. Егер L-де ең үлкен элемент болса, онда ол инфимум деп аталады және inf A деп белгіленеді.
Мысал ретінде жоғарыдағы жартылай реттелген ⟨P ({1, 2, 3}), ⊆⟩ жиынын қарастырып, ондағы жоғарғы және инфимумды табыңыз:
Енді біз алгебралық тордың анықтамасын тұжырымдай аламыз.
Анықтама 5. ⟨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}.
Физикалық есептерді анықтау алгоритмдерінде іздеу кеңістігі жиі тор түрінде көрсетіледі, мұнда бір элементтің жиындары (іздеу торының бірінші деңгейін оқыңыз, мұнда тәуелділіктердің сол жағы бір атрибуттан тұрады) әрбір атрибутты көрсетеді. бастапқы қатынастан.
Алдымен ∅ → түріндегі тәуелділіктерді қарастырамыз Жалғыз атрибут. Бұл қадам қандай атрибуттар негізгі кілттер екенін анықтауға мүмкіндік береді (мұндай атрибуттар үшін анықтауыштар жоқ, сондықтан сол жағы бос). Әрі қарай, мұндай алгоритмдер тор бойымен жоғары қарай жылжиды. Айта кету керек, бүкіл торды айналып өту мүмкін емес, яғни сол жақтың қажетті максималды өлшемі кіріске берілсе, алгоритм сол өлшеммен деңгейден арыға кетпейді.
Төмендегі суретте алгебралық торды FZ табу мәселесінде қалай қолдануға болатыны көрсетілген. Мұнда әрбір шеті (X, XY) тәуелділікті білдіреді X → Y. Мысалы, біз бірінші деңгейден өттік және тәуелділіктің сақталғанын білеміз A → B (біз мұны шыңдар арасындағы жасыл байланыс ретінде көрсетеміз A и B). Бұл одан әрі торды жоғары жылжытқанда, біз тәуелділікті тексермеуіміз мүмкін дегенді білдіреді A, C → B, себебі ол енді минималды болмайды. Сол сияқты, егер тәуелділік сақталса, біз оны тексермейтін едік C → B.
Сонымен қатар, әдетте, федералды заңдарды іздеудің барлық заманауи алгоритмдері бөлім сияқты деректер құрылымын пайдаланады (түпнұсқа көзде - жойылған бөлім [1]). Бөлімнің ресми анықтамасы келесідей:
Анықтама 6. X ⊆ R r қатынасы үшін атрибуттар жиыны болсын. Кластер – X үшін бірдей мәнге ие, яғни c(t) = {i|ti[X] = t[X]} r-дағы кортеждер индекстерінің жиыны. Бөлім - бірлік ұзындықтағы кластерлерді қоспағанда, кластерлер жиынтығы:
Қарапайым сөзбен айтқанда, атрибутқа арналған бөлім X әрбір тізімде бірдей мәндері бар жол нөмірлері болатын тізімдер жиынтығы X. Қазіргі әдебиетте бөлімдерді білдіретін құрылым позициялар тізімінің индексі (PLI) деп аталады. Бірлік ұзындығы кластерлері PLI қысу мақсаттары үшін алынып тасталады, себебі олар әрқашан анықтау оңай болатын бірегей мәні бар жазба нөмірін ғана қамтитын кластерлер.
Мысал қарастырайық. Пациенттермен бір кестеге оралайық және бағандар үшін бөлімдер құрастырайық Науқас и Секс (сол жақта кесте жолының нөмірлері белгіленген жаңа баған пайда болды):
Сонымен қатар, анықтамаға сәйкес, бағанға арналған бөлім Науқас жалғыз кластерлер бөлімнен шығарылғандықтан, шын мәнінде бос болады.
Бөлімдерді бірнеше атрибуттар бойынша алуға болады. Мұны істеудің екі жолы бар: кестені қарап шығу арқылы, барлық қажетті атрибуттарды пайдаланып бөлімді бірден құрастырыңыз немесе атрибуттардың ішкі жиынын пайдаланып бөлімдердің қиылысу операциясын қолдана отырып құрастырыңыз. Федералды заң іздеу алгоритмдері екінші нұсқаны пайдаланады.
Қарапайым сөзбен айтқанда, мысалы, бағандар бойынша бөлімді алу ABC, үшін бөлімдерді алуға болады AC и B (немесе бөлінбеген ішкі жиындардың кез келген басқа жиыны) және оларды бір-бірімен қиылысу. Екі бөлімнің қиылысу әрекеті екі бөлімге де ортақ ең үлкен ұзындықтағы кластерлерді таңдайды.
Мысал қарастырайық:
Бірінші жағдайда біз бос бөлімді алдық. Егер сіз кестеге мұқият қарасаңыз, онда екі атрибут үшін бірдей мәндер жоқ. Егер кестені сәл өзгертсек (оң жақтағы корпус), біз бос емес қиылысатын боламыз. Сонымен қатар, 1 және 2-жолдарда атрибуттар үшін бірдей мәндер бар Секс и Доктор.
Әрі қарай, бізге бөлім өлшемі сияқты тұжырымдама қажет болады. Ресми түрде:
Қарапайым тілмен айтқанда, бөлім өлшемі бөлімге енгізілген кластерлердің саны болып табылады (бір кластерлер бөлімге қосылмағанын есте сақтаңыз!):
Енді біз берілген бөлімдер үшін тәуелділіктің сақталғанын немесе сақталмағанын анықтауға мүмкіндік беретін негізгі леммалардың бірін анықтай аламыз:
Лемма 1. A, B → C тәуелділігі тек және егер ғана орындалады
Леммаға сәйкес, тәуелділіктің орындалатынын анықтау үшін төрт қадамды орындау керек:
- Тәуелділіктің сол жағына арналған бөлімді есептеңіз
- Тәуелділіктің оң жағына арналған бөлімді есептеңіз
- Бірінші және екінші қадамның көбейтіндісін есептеңіз
- Бірінші және үшінші қадамдарда алынған бөлімдердің өлшемдерін салыстырыңыз
Төменде осы леммаға сәйкес тәуелділіктің орындалатынын тексерудің мысалы келтірілген:
Бұл мақалада біз функционалдық тәуелділік, шамамен функционалдық тәуелділік сияқты ұғымдарды қарастырдық, олардың қайда қолданылатынын, сондай-ақ физикалық функцияларды іздеудің қандай алгоритмдері бар екенін қарастырдық. Біз сондай-ақ федералды заңдарды іздеудің заманауи алгоритмдерінде белсенді қолданылатын негізгі, бірақ маңызды ұғымдарды егжей-тегжейлі қарастырдық.
Анықтамалар:
- Huhtala Y. et al. TANE: Функционалдық және жуық тәуелділіктерді табудың тиімді алгоритмі //Компьютер журналы. – 1999. – Т. 42. – Жоқ. 2. – 100-111 б.
- Kruse S., Naumann F. Болжалды тәуелділіктерді тиімді ашу // VLDB қорының еңбектері. – 2018. – Т. 11. – Жоқ. 7. – 759-772 б.
- Папенброк Т., Науман Ф. Функционалдық тәуелділікті ашуға гибридті көзқарас //Деректерді басқару жөніндегі 2016 жылғы халықаралық конференция материалдары. – ACM, 2016. – 821-833 б.
- Papenbrock T. et al. Функционалдық тәуелділікті ашу: Жеті алгоритмнің эксперименттік бағалауы //VLDB Endowment материалдары. – 2015. – Т. 8. – Жоқ. 10. – 1082-1093 б.
- Кумар А. және т.б. Қосылу керек пе, қосылмау керек пе?: Функцияны таңдаудан бұрын қосылулар туралы екі рет ойлану //Деректерді басқару жөніндегі 2016 жылғы халықаралық конференция материалдары. – ACM, 2016. – 19-34 б.
- Abo Khamis M. et al. Сирек тензорлармен деректер базасында оқыту // Деректер базасы жүйелерінің принциптері бойынша 37-ші ACM SIGMOD-SIGACT-SIGAI симпозиумының материалдары. – ACM, 2018. – 325-340 б.
- Hellerstein JM және т.б. MADlib аналитикалық кітапханасы: немесе MAD дағдылары, SQL //VLDB қорының материалдары. – 2012. – Т. 5. – Жоқ. 12. – 1700-1711 б.
- Qin C., Rusu F. Тераскалдың бөлінген градиенттік түсуін оңтайландыруға арналған алыпсатарлық жуықтаулар //Бұлттағы деректерді талдау бойынша төртінші семинардың материалдары. – ACM, 2015. – 1 б.
- Мэн X. және т.б. Mllib: apache ұшқынындағы машинаны оқыту //Машиналарды оқытуды зерттеу журналы. – 2016. – Т. 17. – Жоқ. 1. – 1235-1241 беттер.
Мақала авторлары: , ғылыми қызметкері , и , ғылыми қызметкері
Ақпарат көзі: www.habr.com