{"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\/ro\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"C\u0103utare eficient\u0103 a dependen\u021belor func\u021bionale \u00een baze de date","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

C\u0103utarea dependen\u021belor func\u021bionale \u00een date este aplicat\u0103 \u00een diferite domenii de analiz\u0103 a datelor: managementul bazelor de date, cur\u0103\u021barea datelor, inginerie invers\u0103 a bazelor de date \u0219i explorarea datelor. Despre aceste dependen\u021be am publicat deja articol<\/a><\/noindex> Anastasia Birillo \u0219i Nikita Bobrov. De data aceasta, Anastasia \u2014 absolvent\u0103 a Computer Science Center din acest an \u2014 \u00eemp\u0103rt\u0103\u0219e\u0219te progresele realizate \u00een cadrul lucr\u0103rii sale de cercetare, pe care a sus\u021binut-o \u00een centru. <\/p>\n

\"C\u0103utare
\n<\/a><\/noindex><\/p>\n

Alegerea sarcinii <\/h3>\n

\n\u00cen timpul studiilor la CS Center, am \u00eenceput s\u0103 studiez \u00een profunzime bazele de date, mai precis, c\u0103utarea dependen\u021belor func\u021bionale \u0219i diferen\u021biale. Aceast\u0103 tem\u0103 a fost legat\u0103 de lucrarea mea de licen\u021b\u0103 de la universitate, a\u0219a c\u0103, \u00een timpul lucrului la lucrare, am \u00eenceput s\u0103 citesc articole despre diverse dependen\u021be \u00een bazele de date. Am scris o revizuire a acestui domeniu \u2014 una dintre primele mele articolele noastre<\/a><\/noindex> \u00een limba englez\u0103 \u0219i am trimis-o la conferin\u021ba SEIM-2017. Am fost foarte \u00eenc\u00e2ntat\u0103 c\u00e2nd am aflat c\u0103 a fost acceptat\u0103 \u0219i am decis s\u0103 m\u0103 aprofundez \u00een subiect. Conceptul \u00een sine nu este nou \u2014 a \u00eenceput s\u0103 fie aplicat \u00eenc\u0103 din anii '90, dar \u0219i acum g\u0103se\u0219te aplica\u021bii \u00een multe domenii. <\/p>\n

\u00cen semestrul 2 al studiilor \u00een centru, am \u00eenceput un proiect de cercetare privind \u00eembun\u0103t\u0103\u021birea algoritmilor de c\u0103utare a dependen\u021belor func\u021bionale. Am lucrat \u00eempreun\u0103 cu studentul de doctorat al SPbGU, Nikita Bobrov, la JetBrains Research. <\/p>\n

Efortul computa\u021bional necesar pentru c\u0103utarea dependen\u021belor func\u021bionale<\/h3>\n

\nProblema principal\u0103 \u2014 efortul computa\u021bional. Num\u0103rul posibilit\u0103\u021bilor de dependen\u021be minime \u0219i netriviale este limitat de valoarea \"C\u0103utare, unde \"C\u0103utare \u2014 num\u0103rul de atribute ale tabelului. Timpul de func\u021bionare al algoritmilor depinde nu doar de num\u0103rul de atribute, ci \u0219i de num\u0103rul de r\u00e2nduri. \u00cen anii '90, algoritmii de c\u0103utare a dependen\u021belor func\u021bionale pe un PC de birou obi\u0219nuit puteau procesa seturi de date care con\u021bineau p\u00e2n\u0103 la 20 de atribute \u0219i zeci de mii de r\u00e2nduri, timp de c\u00e2teva ore. Algoritmii moderni, care func\u021bioneaz\u0103 pe procesoare multicore, descoper\u0103 dependen\u021be pentru seturi de date care constau din sute de atribute (p\u00e2n\u0103 la 200) \u0219i sute de mii de r\u00e2nduri, aproximativ \u00een acela\u0219i interval de timp. Cu toate acestea, acest timp nu este suficient: este inacceptabil pentru majoritatea aplica\u021biilor reale. Prin urmare, am dezvoltat abord\u0103ri pentru accelerarea algoritmilor existen\u021bi. <\/p>\n

Scheme de caching pentru intersec\u021bia parti\u021biilor<\/h3>\n

\n\u00cen prima parte a lucr\u0103rii, am dezvoltat scheme de caching pentru o clas\u0103 de algoritmi care utilizeaz\u0103 metoda intersec\u021biei parti\u021biilor. O parti\u021bie pentru un atribut reprezint\u0103 un set de liste, unde fiecare list\u0103 con\u021bine numerele de r\u00e2nd cu valori identice pentru acel atribut. Fiecare astfel de list\u0103 se nume\u0219te cluster. Multe algoritmi moderni folosesc parti\u021bii pentru a determina dac\u0103 o dependen\u021b\u0103 este men\u021binut\u0103 sau nu, urm\u00e2nd, \u00een esen\u021b\u0103, lemma: Dependen\u021ba \"C\u0103utare este men\u021binut\u0103 dac\u0103 \"C\u0103utare. Aici \"C\u0103utare se indic\u0103 o parti\u021bie \u0219i se folose\u0219te no\u021biunea de m\u0103rimea parti\u021biei \u2014 num\u0103rul de clustere din ea. Algoritmii care folosesc parti\u021bii, \u00een cazul unei \u00eenc\u0103lc\u0103ri a dependen\u021bei, adaug\u0103 atribute suplimentare \u00een partea st\u00e2ng\u0103 a dependen\u021bei, dup\u0103 care o recalculeaz\u0103, efectu\u00e2nd opera\u021bia de intersec\u021bie a parti\u021biilor. Aceast\u0103 opera\u021bie este denumit\u0103 specializare \u00een lucr\u0103rile \u0219tiin\u021bifice. Totu\u0219i, am observat c\u0103 parti\u021biile pentru dependen\u021bele care vor fi men\u021binute doar dup\u0103 mai multe runde de specializare pot fi reutilizate activ, ceea ce poate reduce semnificativ timpul de execu\u021bie al algoritmilor, av\u00e2nd \u00een vedere c\u0103 opera\u021bia de intersec\u021bie este costisitoare. <\/p>\n

Prin urmare, am propus o euristic\u0103 bazat\u0103 pe Entropia Shannon \u0219i incertitudinea Gini, precum \u0219i pe metrica noastr\u0103, pe care am numit-o Entropia Invers\u0103. Aceasta este o modificare nesemnificativ\u0103 a Entropiei Shannon \u0219i cre\u0219te pe m\u0103sur\u0103 ce cre\u0219te unicitatea setului de date. Euristica propus\u0103 este urm\u0103toarea:<\/p>\n

\"C\u0103utare<\/p>\n

Aici \"C\u0103utare \u2014 gradul de unicitate al parti\u021biei recent calculate \"C\u0103utare, iar \"C\u0103utare este o medie a gradelor de unicitate pentru atribute specifice. Toate cele trei metrici descrise mai sus au fost testate ca metrici de unicitate. De asemenea, se poate observa c\u0103 \u00een euristic\u0103 exist\u0103 dou\u0103 modificatoare. Primul indic\u0103 c\u00e2t de aproape este partitia curent\u0103 de cheia primar\u0103 \u0219i permite o mai bun\u0103 reducere a celor care sunt departe de cheia poten\u021bial\u0103. Al doilea modificator permite monitorizarea utiliz\u0103rii cache-ului \u0219i astfel stimuleaz\u0103 ad\u0103ugarea unui num\u0103r mai mare de parti\u021bii \u00een cache atunci c\u00e2nd exist\u0103 spa\u021biu liber. Rezolvarea cu succes a acestei probleme a permis accelerarea algoritmului PYRO cu 10-40% \u00een func\u021bie de setul de date. Merit\u0103 men\u021bionat c\u0103 algoritmul PYRO este cel mai reu\u0219it \u00een acest domeniu. <\/p>\n

\u00cen figura de mai jos pot fi v\u0103zute rezultatele aplic\u0103rii euristicii propuse \u00een compara\u021bie cu abordarea de baz\u0103 de caching bazat\u0103 pe aruncarea unei monede. Axul X este logaritmic.<\/p>\n

\"C\u0103utare
\n<\/p>\n

O metod\u0103 alternativ\u0103 de stocare a parti\u021biilor<\/h3>\n

\nApoi, am propus o metod\u0103 alternativ\u0103 de stocare a parti\u021biilor. Parti\u021biile reprezint\u0103 un set de clustere, fiecare dintre care stocheaz\u0103 numerele tuplelor cu valori identice pentru anumite atribute. Aceste clustere pot con\u021bine secven\u021be lungi de numere de tuple, de exemplu, dac\u0103 datele din tabel sunt ordonate. Prin urmare, am propus un schema de compresie pentru stocarea parti\u021biilor, \u0219i anume stocarea intervalelor de valori \u00een clusterele parti\u021biilor:<\/p>\n

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

Aceast\u0103 metod\u0103 a reu\u0219it s\u0103 reduc\u0103 consumul de memorie \u00een timpul func\u021bion\u0103rii algoritmului TANE cu 1 p\u00e2n\u0103 la 25%. Algoritmul TANE este un algoritm clasic pentru descoperirea dependen\u021belor func\u021bionale, folose\u0219te parti\u021bii \u00een timpul func\u021bion\u0103rii sale. \u00cen cadrul practicii, s-a ales algoritmul TANE deoarece implementarea stoc\u0103rii pe intervale a fost semnificativ mai u\u0219oar\u0103 comparativ cu, de exemplu, PYRO, pentru a evalua dac\u0103 abordarea propus\u0103 func\u021bioneaz\u0103. Rezultatele ob\u021binute sunt prezentate \u00een figura de mai jos. Axul X este logaritmic.<\/p>\n

\"C\u0103utare
\n<\/p>\n

Conferin\u021ba ADBIS-2019<\/h3>\n

\nPe baza cercet\u0103rii din septembrie 2019, am prezentat un articol Smart Caching for Efficient Functional Dependency Discovery<\/a><\/noindex> la conferin\u021ba 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). \u00cen timpul prezent\u0103rii, Bernhard Thalheim, o persoan\u0103 semnificativ\u0103 \u00een domeniul bazelor de date, a men\u021bionat lucrarea. Rezultatele cercet\u0103rilor au stat la baza dizerta\u021biei mele din cadrul programului de master \u00een matematic\u0103 \u0219i mecanic\u0103 la SPbGU, \u00een cadrul c\u0103reia am implementat cele dou\u0103 metode propuse (caching \u0219i compresie) \u00een ambele algoritmi: TANE \u0219i PYRO. Rezultatele au ar\u0103tat c\u0103 metodele propuse sunt universale, deoarece ambele algoritmi au demonstrat o reducere semnificativ\u0103 a memoriei utilizate, precum \u0219i o reducere considerabil\u0103 a timpului de execu\u021bie.
\n
Sursa: 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\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\udd47C\u0103utarea eficient\u0103 a dependen\u021belor func\u021bionale \u00een bazele de date | ProHoster","description":"C\u0103utarea dependen\u021belor func\u021bionale \u00een date este aplicat\u0103 \u00een diverse domenii ale analizei datelor: gestionarea bazelor de date, cur\u0103\u021barea datelor, ingineria invers\u0103 a bazelor de date \u0219i explorarea datelor.","canonical_url":"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"ro_RO","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\/ro\/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\/ro\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}