{"id":86335,"date":"2020-06-24T07:42:54","date_gmt":"2020-06-24T05:42:54","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh"},"modified":"2020-06-24T07:42:54","modified_gmt":"2020-06-24T05:42:54","slug":"effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"U\u010dinkovito pretra\u017eivanje funkcionalnih zavisnosti u bazama podataka","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Iskanje funkcionalnih odvisnosti v podatkih se uporablja v razli\u010dnih podro\u010djih analize podatkov: upravljanje z bazo podatkov, \u010di\u0161\u010denje podatkov, reverzno in\u017eenirstvo baz podatkov in raziskovanje podatkov. O samih odvisnostih smo \u017ee objavili \u010dlanak<\/a><\/noindex> Anastazije Birillo in Nikite Bobrova. Tokrat Anastazija \u2014 leto\u0161nja diplomantka Computer Science Center \u2014 deli napredovanje te naloge v okviru NIR, ki jo je zagovarjala v centru. <\/p>\n

\"U\u010dinkovito
\n<\/a><\/noindex><\/p>\n

Izbira naloge <\/h3>\n

\nMed \u0161tudijem v CS centru sem za\u010dela poglobljeno raziskovati baze podatkov, zlasti iskanje funkcionalnih in razlikovnih odvisnosti. Ta tema je bila povezana z temo moje seminarske naloge na univerzi, tako da sem med delom na seminarski za\u010dela brati \u010dlanke o razli\u010dnih odvisnostih v bazah podatkov. Napisala sem pregled tega podro\u010dja \u2014 eno svojih prvih \u010dlanov<\/a><\/noindex> v angle\u0161\u010dini in jo predlo\u017eila na konferenco SEIM-2017. Bila sem zelo vesela, ko sem izvedela, da so jo sprejeli, in sem se odlo\u010dila poglobiti v to temo. Sama koncept ni nov \u2014 za\u010deli so ga uporabljati \u017ee v devetdesetih letih, a se \u0161e danes uporablja na mnogih podro\u010djih. <\/p>\n

V drugem semestru \u0161tudija v centru sem za\u010dela znanstveno-raziskovalni projekt za izbolj\u0161anje algoritmov iskanja funkcionalnih odvisnosti. Na njem sem delala skupaj s podiplomskim \u0161tudentom SPbGU Nikito Bobrovim na osnovi JetBrains Research. <\/p>\n

Ra\u010dunska zahtevnost iskanja funkcionalnih odvisnosti<\/h3>\n

\nGlavni problem \u2014 ra\u010dunska zahtevnost. \u0160tevilo mo\u017enih minimalnih in netrivialnih odvisnosti je zgoraj omejeno z vrednostjo \"U\u010dinkovito, gde \"U\u010dinkovito \u2014 \u0161tevilo atributov tabele. \u010cas delovanja algoritmov se ne meri le glede na \u0161tevilo atributov, temve\u010d tudi glede na \u0161tevilo vrstic. V devetdesetih letih so algoritmi za iskanje FZ na obi\u010dajnih namiznih ra\u010dunalnikih lahko obdelovali podatkovne nize, ki vsebujejo do 20 atributov in deset tiso\u010d vrstic, do ve\u010d ur. Sodobni algoritmi, ki delujejo na ve\u010djedrnih procesorjih, odkrivajo odvisnosti za podatkovne nize, sestavljene iz stotin atributov (do 200) in stotin tiso\u010d vrstic, pribli\u017eno v istem \u010dasu. Kljub temu to ni dovolj: tak \u010das je nesprejemljiv za ve\u010dino realnih aplikacij. Zato smo razvijali pristope za pospe\u0161evanje obstoje\u010dih algoritmov. <\/p>\n

Sheme predpomnjenja za prese\u010di\u0161\u010da particij<\/h3>\n

\nV prvem delu dela smo razvili sheme predpomnenja za razred algoritmov, ki uporabljajo metodo preseka particij. Particija za atribut predstavlja niz seznamov, kjer vsak seznam vsebuje \u0161tevilke vrstic z enakimi vrednostmi za dani atribut. Vsak tak seznam se imenuje klaster. Mnogi sodobni algoritmi uporabljajo particije za dolo\u010danje, ali se odvisnost ohranja ali ne, in sicer sledijo tezi: Odvisnost \"U\u010dinkovito se ohranja, \u010de \"U\u010dinkovito. Tukaj \"U\u010dinkovito je ozna\u010dena particija in uporablja se pojem velikosti particije \u2014 \u0161tevilo klastrov v njej. Algoritmi, ki uporabljajo particije, ob kr\u0161enju odvisnosti dodajajo dodatne atribute v levo stran odvisnosti, po \u010demer ponovno izra\u010dunajo, pri \u010demer izvajajo operacijo preseka particij. Tak\u0161na operacija se v \u010dlankih imenuje specializacija. Vendar smo opazili, da se lahko particije za odvisnosti, ki bodo ohranjene \u0161ele po ve\u010d krogih specializacije, aktivno ponovno uporabijo, kar lahko znatno zmanj\u0161a \u010das delovanja algoritmov, saj je operacija preseka draga. <\/p>\n

Zato smo predlagali heuristiko, ki temelji na Shannonovi entropiji in Ginijevi negotovosti, ter na\u0161i metriki, ki smo jo poimenovali Obra\u010duna Entropija. Ta predstavlja nepomembno modifikacijo Shannonove entropije in nara\u0161\u010da, ko nara\u0161\u010da edinstvenost nabora podatkov. Predlagana heuristika izgleda takole:<\/p>\n

\"U\u010dinkovito<\/p>\n

Tukaj \"U\u010dinkovito \u2014 stopnja edinstvenosti nedavno izra\u010dunane particije \"U\u010dinkovito, a \"U\u010dinkovito je mediane stopnje edinstvenosti za posamezne atribute. V kot metrika edinstvenosti so bile preizku\u0161ene vse tri metrike, opisane zgoraj. Prav tako je opaziti, da v heuristiki obstajata dva modifikatorja. Prvi ozna\u010duje, kako blizu je trenutna particija k primarnemu klju\u010du in omogo\u010da ve\u010dje predpomnjenje tistih particij, ki so oddaljene od potencialnega klju\u010da. Drugi modifikator omogo\u010da sledenje zasedenosti predpomnilnika in s tem stimulira dodajanje ve\u010djega \u0161tevila particij v predpomnilnik, ko je na voljo prost prostor. Uspe\u0161no re\u0161evanje te naloge je omogo\u010dilo pospe\u0161itev algoritma PYRO za 10-40% glede na nabor podatkov. Omeniti je treba, da je algoritem PYRO najbolj uspe\u0161en na tem podro\u010dju. <\/p>\n

Na spodnji sliki so prikazani rezultati uporabe predlagane heuristike v primerjavi z osnovnim pristopom k predpomnjenju, ki temelji na metodi vr\u017eenja kovan\u010dka. Os X je logaritmi\u010dna.<\/p>\n

\"U\u010dinkovito
\n<\/p>\n

Alternativen na\u010din shranjevanja particij<\/h3>\n

\nNato smo predlagali alternativen na\u010din shranjevanja particij. Particije predstavljajo niz grozdov, v katerih so shranjene \u0161tevilke tupljev z enakimi vrednostmi za dolo\u010dene atribute. Ti grozdi lahko vsebujejo dolge zaporedja \u0161tevilk tupljev, na primer, \u010de so podatki v tabeli razporejeni. Zato smo predlagali shemo stiskanja za shranjevanje particij, in sicer intervalno shranjevanje vrednosti v grozdih particij:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Prvi~interval}, underbrace{7, 8}_{Drugi~interval}, 10}}\\ downarrow{Stiskanje}\\ pi(X) = {{underbrace{$, 1, 5}_{Prvi~interval}, underbrace{7, 8}_{Drugi~interval}, 10}}$$display$$<\/p>\n

Ta metoda je lahko zmanj\u0161ala porabo pomnilnika med delovanjem algoritma TANE za 1 do 25%. Algoritem TANE je klasi\u010den algoritem za iskanje FZ, ki med delovanjem uporablja particije. V okviru praktikum je bil izbran prav algoritem TANE, saj je bilo veliko la\u017eje v njega vklju\u010diti intervalno shranjevanje kot na primer v PYRO, da bi ocenili, ali predlagani pristop deluje. Pridobljeni rezultati so prikazani na spodnji sliki. Os X je logaritmi\u010dna.<\/p>\n

\"U\u010dinkovito
\n<\/p>\n

Konferenca ADBIS-2019<\/h3>\n

\nNa podlagi raziskave septembra 2019 sem nastopila s \u010dlankom Pametno predpomnjenje za u\u010dinkovito odkrivanje funkcionalnih odvisnosti<\/a><\/noindex> na konferenci 23. Evropska konferenca o naprednih podatkovnih in informacijskih sistemih (ADBIS-2019). Med nastopom je delo pohvalil Bernhard Thalheim, pomembna oseba na podro\u010dju podatkovnih baz. Rezultati raziskav so postali osnova moje magistrske naloge na matemati\u010dno-fizikalni fakulteti Univerze v Sankt Peterburgu, v okviru katere sta bila oba predlagana pristopa (predpomnjenje in stiskanje) vklju\u010den v oba algoritma: TANE in PYRO. Rezultati so pokazali, da sta predlagana pristopa univerzalna, saj je bilo pri obeh algoritmih pri obeh pristopih opazno znatno zmanj\u0161anje porabe pomnilnika ter znatno skraj\u0161anje \u010dasa delovanja algoritmov.
\n
Izvor: habr.com<\/a> <\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u041f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u0445 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0430\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043e\u0447\u0438\u0441\u0442\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0440\u0435\u0432\u0451\u0440\u0441-\u0438\u043d\u0436\u0438\u043d\u0438\u0440\u0438\u043d\u0433 \u0431\u0430\u0437 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u044d\u043a\u0441\u043f\u043b\u043e\u0440\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u043e \u0441\u0430\u043c\u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043c\u044b \u0443\u0436\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u044e \u0410\u043d\u0430\u0441\u0442\u0430\u0441\u0438\u0438 \u0411\u0438\u0440\u0438\u043b\u043b\u043e \u0438 \u041d\u0438\u043a\u0438\u0442\u044b \u0411\u043e\u0431\u0440\u043e\u0432\u0430. \u0412 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u0410\u043d\u0430\u0441\u0442\u0430\u0441\u0438\u044f \u2014 \u0432\u044b\u043f\u0443\u0441\u043a\u043d\u0438\u0446\u0430 Computer Science Center \u044d\u0442\u043e\u0433\u043e \u0433\u043e\u0434\u0430 \u2014 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u0440\u0430\u0437\u0432\u0438\u0442\u0438\u0435\u043c \u044d\u0442\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u041d\u0418\u0420, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043e\u043d\u0430 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":86336,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-86335","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47U\u010dinkovito iskanje funkcionalnih odvisnosti v podatkovnih bazah | ProHoster","description":"Iskanje funkcionalnih odvisnosti v podatkih se uporablja na razli\u010dnih podro\u010djih analize podatkov: upravljanje podatkovnih baz, \u010di\u0161\u010denje podatkov, reverzno in\u017eenirstvo podatkovnih baz in exploracija podatkov.","canonical_url":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sl_SI","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0431\u0430\u0437\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 | ProHoster","og:description":"\u041f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u0445 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0430\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043e\u0447\u0438\u0441\u0442\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0440\u0435\u0432\u0451\u0440\u0441-\u0438\u043d\u0436\u0438\u043d\u0438\u0440\u0438\u043d\u0433 \u0431\u0430\u0437 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u044d\u043a\u0441\u043f\u043b\u043e\u0440\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445.","og:url":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2020-06-24T05:42:54+00:00","article:modified_time":"2020-06-24T05:42:54+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"86335","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":null,"breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-02-28 14:17:33","updated":"2022-09-27 17:20:14","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}