У гэтым артыкуле мы пагаворым аб функцыянальных залежнасцях у базах дадзеных – што гэта такое, дзе прымяняюцца і якія алгарытмы існуюць для іх пошуку.
Разглядаць функцыянальныя залежнасці мы будзем у кантэксце рэляцыйных баз даных. Калі казаць зусім грубіянска, то ў такіх базах дадзеных інфармацыях захоўваецца ў выглядзе табліц. Далей мы выкарыстоўваем набліжаныя паняцці, якія ў строгай рэляцыйнай тэорыі не з'яўляюцца ўзаемазаменнымі: саму табліцу будзем зваць стаўленнем, слупкі - атрыбутамі (іх мноства - схемай адносіны), а набор значэнняў радка на падмностве атрыбутаў - картэжам.
Напрыклад, у табліцы вышэй, (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.
А зараз па парадку. Разгледзім атрыбуты пацыент и Падлогу для якіх жадаем пазнаць, ці ёсць паміж імі залежнасці ці не. Для такога мноства атрыбутаў могуць існаваць наступныя залежнасці:
- Пацыент → Пол
- Пол → Пацыент
Паводле азначэння вышэй, для таго каб утрымалася першая залежнасць, кожнаму ўнікальнаму значэнню слупка. пацыент павінна адпавядаць толькі адно значэнне слупка Падлогу. І для табліцы-прыклада гэта сапраўды так. Аднак у адваротны бок гэта не працуе, гэта значыць другая залежнасць не выконваецца, а атрыбут Падлогу не з'яўляецца дэтэрмінантам для Пацыента. Аналагічна, калі ўзяць залежнасць Доктар → Пацыент, можна заўважыць, што яна парушаецца, бо значэнне Робін па гэтым атрыбуту мае некалькі розных значэнняў. Ellis і Graham.
Такім чынам, функцыянальныя залежнасці дазваляюць вызначыць наяўныя сувязі паміж мноствамі атрыбутаў табліцы. Адсюль і надалей мы будзем разглядаць найбольш цікавыя сувязі, а дакладней такія X → Y, Што яны з'яўляюцца:
- нетрывіяльнымі, гэта значыць правая частка залежнасці не з'яўляецца падмноствам левай (Y ̸⊆ X);
- мінімальнымі, гэта значыць няма такой залежнасці Z → Y, Што Z ⊂ X.
Разгляданыя да гэтага моманту залежнасці былі строгімі, гэта значыць не якія прадугледжваюць ніякіх парушэнняў на табліцы, але апроч іх ёсць і такія, якія дапушчаюць некаторую няўзгодненасць паміж значэннямі картэжаў. Такія залежнасці выносяць у асобны клас, завуць набліжанымі і дазваляюць ім парушацца на вызначанай колькасці картэжаў. Гэтая колькасць рэгулюецца паказчыкам максімальнай памылкі emax. Напрыклад, доля памылкі = 0.01 можа азначаць, што залежнасць можа парушацца на 1% ад наяўных картэжаў на разгляданым мностве атрыбутаў. Гэта значыць, для 1000 запісаў максімум 10 картэжаў могуць парушаць ФЗ. Мы ж будзем разглядаць крыху іншую метрыку, заснаваную на парамі-розных значэннях параўноўваных картэжаў. Для залежнасці X → Y на дачыненні r яна лічыцца так:
Палічым памылку для Доктар → Пацыент з прыкладу вышэй. Маем два картэжы, значэнні якіх адрозніваюцца на атрыбуце пацыент, але супадаюць на Дактары: [Доктар, Пацыент] = (Robin, Ellis) І [Доктар, Пацыент] = (Robin, Graham). Прытрымліваючыся вызначэння памылкі, мы павінны ўлічваць усе канфліктуючыя пары, а значыць такіх будзе дзве: (, ) і яе інверсія (, ). Падставім у формулу і атрымаем:
А зараз паспрабуем адказаць на пытанне: "А навошта яно ўсё?". Насамрэч, ФЗ бываюць розныя. Першы тып - гэта такія залежнасці, якія вызначаюцца адміністратарам на этапе праектавання базы дадзеных. Іх звычайна няшмат, яны строгія, а асноўнае прымяненне - нармалізацыя дадзеных і дызайн схемы адносіны.
Другі тып - залежнасці, якія прадстаўляюць «схаваныя» дадзеныя і раней невядомыя сувязі паміж атрыбутамі. Гэта значыць аб такіх залежнасцях не думалі ў момант праектавання і іх знаходзяць ужо для наяўнага набору дадзеных, каб потым на аснове мноства выяўленых ФЗ зрабіць якія-небудзь высновы аб захоўваемай інфармацыі. Якраз з такімі залежнасцямі мы і працуем. Імі займаецца цэлая вобласць дата майнінгу з рознымі тэхнікамі пошуку і пабудаванымі на іх аснове алгарытмамі. Давайце разбірацца, чым могуць быць карысныя знойдзеныя функцыянальныя залежнасці (дакладныя ці набліжаныя) у якіх-небудзь дадзеных.
Сёння сярод асноўных абласцей ужывання залежнасцяў вылучаюць ачыстку дадзеных. Яна мае на ўвазе распрацоўку працэсаў выяўлення "брудных дадзеных" з наступным іх выпраўленнем. Яркімі прадстаўнікамі "брудных дадзеных" з'яўляюцца дублікаты, памылкі ў дадзеных або памылкі друку, прапушчаныя значэння, састарэлыя дадзеныя, лішнія прабелы і таму падобнае.
Прыклад памылкі ў дадзеных:
Прыклад дублікатаў у дадзеных:
Напрыклад, мы маем табліцу і набор ФЗ, якія мусяць выконвацца. Ачыстка дадзеных у дадзеным выпадку мяркуе змяніць дадзеныя такім чынам, каб ФЗ сталі дакладныя. Пры гэтым колькасць мадыфікацый павінна быць мінімальна (для дадзенай працэдуры існуюць свае алгарытмы, на якіх мы не будзем засяроджваць увагу ў дадзеным артыкуле). Ніжэй прыведзены прыклад такога пераўтварэння дадзеных. Злева зыходнае стаўленне, у якім, відавочна, не выконваюцца неабходныя ФЗ (чырвоным колерам выдзелены прыклад парушэння адной з ФЗ). Справа прадстаўлена абноўленае стаўленне, у якім зялёныя вочкі паказваюць змененыя значэнні. Пасля правядзення такой працэдуры неабходныя залежнасці сталі ўтрымлівацца.
Іншы папулярнай вобласцю прымянення з'яўляецца дызайн базы даных. Тут трэба нагадаць пра нармальныя формы і нармалізацыю. Нармалізацыя - гэта працэс прывядзення адносіны ў адпаведнасць некаторага набору патрабаванняў, кожны з якіх вызначаецца нармальнай формай па-свойму. Распісваць патрабаванні розных нармальных формаў мы не станем (гэта робіцца ў любой кнізе па курсе БД для пачаткоўцаў), а толькі заўважым, што кожная з іх па-свойму выкарыстоўвае канцэпцыю функцыянальных залежнасцяў. Бо ФЗ па сваёй сутнасці з'яўляюцца абмежаваннямі цэласнасці, якія ўлічваюцца пры праектаванні базы дадзеных (у кантэксце гэтай задачы ФЗ часам называюць суперключамі).
Разгледзім іх ужыванне для чатырох нармальных формаў на малюнку ніжэй. Нагадаем, што нармальная форма Бойс-Кодда з'яўляецца больш строгай, чым трэцяя форма, але пры гэтым менш строгай, чым чацвёртая. Апошнюю пакуль не разглядаем, паколькі для яе пастаноўкі трэба разуменне шматзначных залежнасцяў, якія ў дадзеным артыкуле нам не цікавыя.
Яшчэ адной вобласцю, у якой залежнасці знайшлі сваё ўжыванне, з'яўляецца паніжэнне памернасці прасторы прыкмет у такіх задачах як пабудова наіўнага байесаўскай класіфікатара, вылучэнне значных прыкмет і рэпараметрызацыя рэгрэсійнай мадэлі. У арыгінальных артыкулах гэтая задача называецца вызначэннем залішніх прыкмет (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 выкананы ўласцівасці:
- Рэфлексіўнасць, гэта значыць a ⩽ a
- Антысіметрычнасць, гэта значыць, калі a ⩽ b і b ⩽ a, то a = b
- Транзітыўнасць, гэта значыць для 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 існуе найбольшы элемент, тады ён называецца інфімумам і пазначаецца як 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, C → B, таму што яна будзе ўжо не мінімальнай. Аналагічна мы б не сталі яе правяраць, калі б утрымлівалася залежнасць C → B.
Акрамя таго, як правіла, усе сучасныя алгарытмы па пошуку ФЗ выкарыстоўваюць такую структуру дадзеных, як партыцыя (у першакрыніцы - stripped partition [1]). Фармальнае вызначэнне партыцыі выглядае наступным чынам:
Вызначэнне 6. Няхай X ⊆ R — набор атрыбутаў для адносін r. Кластар уяўляе сабой набор індэксаў картэжаў з r, якія маюць аднолькавае значэнне для X, гэта значыць c(t) = {i|ti[X] = t[X]}. Партыцыя ўяўляе сабой мноства кластараў, якое выключае кластары адзінкавай даўжыні:
Простымі словамі, партыцыя для атрыбуту X уяўляе сабой набор спісаў, дзе кожны спіс утрымлівае нумары радкоў з аднолькавымі значэннямі для X. У сучаснай літаратуры структура, якая прадстаўляе партіціі, называецца position list index (PLI). Кластары адзінкавай даўжыні выключаюцца ў мэтах сціску PLI, таму што гэта кластары, якія змяшчаюць толькі нумар запісу з унікальным значэннем, якое заўсёды будзе лёгка ўсталяваць.
Разгледзім прыклад. Вернемся ўсё да той жа табліцы з пацыентамі і пабудуем партіціі для слупкоў пацыент и Падлогу (злева з'явіўся новы слупок, у якім адзначаны нумары радкоў табліцы):
Пры гэтым, паводле азначэння, партыцыя для слупка пацыент насамрэч будзе пустая, бо адзіночныя кластары выключаюцца з партіціі.
Партыцыі можна атрымліваць па некалькіх атрыбутах. І для гэтага існуе два шляхі: прайшоўшыся па табліцы, пабудаваць партыцыю адразу па ўсіх неабходных атрыбутах, ці ж пабудаваць яе з дапамогай аперацыі перасячэння партыцый па падмностве атрыбутаў. Алгарытмы пошуку ФЗ выкарыстоўваюць другі варыянт.
Простымі словамі, каб, напрыклад, атрымаць партыцыю па слупках азбука, можна ўзяць партыцыі для AC и B (або любы іншы набор неперасякальных падмностваў) і перасекчы іх паміж сабой. Аперацыя скрыжавання дзвюх партыцый вылучае кластары найбольшай даўжыні, агульныя для абедзвюх партыцый.
Давайце разгледзім прыклад:
У першым выпадку мы атрымалі пустую партыцыю. Калі дагледзецца да табліцы, то сапраўды, аднолькавых значэнняў па двух атрыбутах тамака няма. Калі ж мы крыху мадыфікуем табліцу (выпадак справа), то ўжо атрымаем няпустое скрыжаванне. Пры гэтым радкі 1 і 2 і праўда ўтрымоўваюць аднолькавыя значэнні па атрыбутах Падлогу и Доктар.
Далей нам спатрэбіцца такое паняцце, як памер партыцыі. Фармальна:
Прасцей кажучы, памер партіціі ўяўляе сабой колькасць кластараў, якія ўваходзяць у партыцыю (памятаем, што адзінкавыя кластары ў партыцыю не ўваходзяць!):
Цяпер мы можам вызначыць адну з ключавых лем, якая для зададзеных партыцый дазваляе ўсталяваць, утрымліваецца залежнасць ці не:
Лема 1. Залежнасць A, B → C утрымліваецца, калі і толькі калі
Паводле лемы, для вызначэння, ці ўтрымліваецца залежнасць, неабходна выканаць чатыры крокі:
- Вылічыць партыцыю для левай часткі залежнасці
- Вылічыць партыцыю для правай часткі залежнасці
- Вылічыць твор першага і другога кроку
- Параўнаць памеры партыцый, атрыманых на першым і трэцім кроку
Ніжэй прадстаўлены прыклад праверкі, ці ўтрымліваецца залежнасць па дадзенай леме:
У дадзеным артыкуле мы разабралі такія паняцці, як функцыянальная залежнасць, набліжаная функцыянальная залежнасць, разгледзелі, дзе яны прымяняюцца, а таксама якія алгарытмы пошуку ФЗ існуюць. Таксама мы падрабязна разабралі базавыя, але важныя паняцці, якія актыўна выкарыстоўваюцца ў сучасных алгарытмах па пошуку ФЗ.
Спасылкі на літаратуру:
- Huhtala Y. et al. TANE: Уплыў алгарытм для вызначэння функцыянальных і падыходных dependences //The computer journal. – 1999. – Т. 42. – №. 2. - С. 100-111.
- Kruse S., Naumann F. Efficient discovery of approximate dependencies //Proceedings of the VLDB Endowment. – 2018. – Т. 11. – №. 7. – С. 759-772.
- Papenbrock T., Naumann F. Як hybrid approach to functional dependency discovery //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – С. 821-833.
- Papenbrock T. et al. Functional dependency discovery: У experimental evaluation of seven algorithms //Proceedings of the VLDB Endowment. – 2015. – Т. 8. – №. 10. - С. 1082-1093.
- Kumar A. et al. Для ажыццяўлення ці не для ажыццяўлення?: Падумайце пра хрысціянства перад выбарам выбару //Працэдэнты 2016 International Conference on Management of Data. – ACM, 2016. – С. 19-34.
- Abo Khamis M. et al. У-database učení з sparse tensors //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI сімптомы на Principles of Database Systems. – ACM, 2018. – С. 325-340.
- Hellerstein JM et al. MADlib аналітыкі library: або MAD skills, SQL //Proceedings of the VLDB Endowment. – 2012. – Т. 5. – №. 12. – С. 1700-1711.
- Qin C., Rusu F. Speculative approximations for terascale distributed gradient descent optimization //Proceedings of the 2015 workshop on Data analytics in the Cloud. - ACM, 1. - С. XNUMX.
- Meng X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – Т. 17. – №. 1. – С. 1235-1241.
Аўтары артыкула: , даследчык у , и , даследчык у
Крыніца: habr.com