{"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\/pt\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Busca eficiente por depend\u00eancias funcionais em bancos de dados","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

A busca por depend\u00eancias funcionais em dados \u00e9 aplicada em v\u00e1rias \u00e1reas da an\u00e1lise de dados: gest\u00e3o de bancos de dados, limpeza de dados, engenharia reversa de bancos de dados e explora\u00e7\u00e3o de dados. Sobre essas depend\u00eancias, j\u00e1 publicamos artigo<\/a><\/noindex> Anast\u00e1sia Birillo e Nikita Bobrov. Desta vez, Anast\u00e1sia \u2014 graduada do Computer Science Center deste ano \u2014 compartilha o desenvolvimento deste trabalho no \u00e2mbito da pesquisa cient\u00edfica que ela defendeu no centro. <\/p>\n

\"Busca
\n<\/a><\/noindex><\/p>\n

Escolha da tarefa <\/h3>\n

\nDurante meu tempo de estudos no centro CS, comecei a explorar em profundidade os bancos de dados, especialmente a busca por depend\u00eancias funcionais e diferenciais. Este tema estava relacionado ao meu trabalho de curso na universidade, ent\u00e3o, enquanto trabalhava no meu projeto, comecei a ler artigos sobre diversas depend\u00eancias em bancos de dados. Escrevi uma revis\u00e3o dessa \u00e1rea \u2014 um dos meus primeiros de artigos<\/a><\/noindex> em ingl\u00eas e a apresentei na confer\u00eancia SEIM-2017. Fiquei muito feliz ao saber que foi aceita e decidi me aprofundar no assunto. A pr\u00f3pria concep\u00e7\u00e3o n\u00e3o \u00e9 nova \u2014 come\u00e7ou a ser aplicada ainda na d\u00e9cada de 90, mas ainda \u00e9 relevante em muitas \u00e1reas. <\/p>\n

No segundo semestre do meu curso no centro, iniciei um projeto de pesquisa sobre a melhoria dos algoritmos de busca por depend\u00eancias funcionais. Trabalhei nele junto com o p\u00f3s-graduando da SPbGU, Nikita Bobrov, na JetBrains Research. <\/p>\n

Dificuldade computacional na busca por depend\u00eancias funcionais<\/h3>\n

\nO principal problema \u00e9 a dificuldade computacional. O n\u00famero de depend\u00eancias m\u00ednimas e n\u00e3o triviais poss\u00edveis \u00e9 limitado superiormente pelo valor \"Busca, onde \"Busca \u2014 o n\u00famero de atributos da tabela. O tempo de execu\u00e7\u00e3o dos algoritmos depende n\u00e3o apenas do n\u00famero de atributos, mas tamb\u00e9m do n\u00famero de linhas. Nos anos 90, algoritmos de busca por depend\u00eancias funcionais em PCs comuns conseguiam processar conjuntos de dados com at\u00e9 20 atributos e dezenas de milhares de linhas em at\u00e9 algumas horas. Algoritmos modernos, que operam em processadores multi-core, detectam depend\u00eancias em conjuntos de dados consistindo de centenas de atributos (at\u00e9 200) e centenas de milhares de linhas, aproximadamente no mesmo tempo. No entanto, isso n\u00e3o \u00e9 suficiente: esse tempo \u00e9 inaceit\u00e1vel para a maioria das aplica\u00e7\u00f5es reais. Portanto, desenvolvemos abordagens para acelerar os algoritmos existentes. <\/p>\n

Esquemas de cache para interse\u00e7\u00e3o de parti\u00e7\u00f5es<\/h3>\n

\nNa primeira parte do trabalho, desenvolvemos esquemas de cache para uma classe de algoritmos que utilizam o m\u00e9todo de interse\u00e7\u00e3o de parti\u00e7\u00f5es. Uma parti\u00e7\u00e3o para um atributo representa um conjunto de listas, onde cada lista cont\u00e9m os n\u00fameros das linhas com valores iguais para esse atributo. Cada uma dessas listas \u00e9 chamada de cluster. Muitos algoritmos modernos usam parti\u00e7\u00f5es para determinar se uma depend\u00eancia \u00e9 mantida ou n\u00e3o, precisamente seguindo a lemma: A depend\u00eancia \"Busca \u00e9 mantida se \"Busca. Aqui \"Busca \u00e9 indicada a parti\u00e7\u00e3o e utiliza-se o conceito de tamanho da parti\u00e7\u00e3o \u2013 a quantidade de clusters nela. Algoritmos que utilizam parti\u00e7\u00f5es, ao quebrar uma depend\u00eancia, adicionam atributos adicionais ao lado esquerdo da depend\u00eancia, ap\u00f3s o que recalculam-na, realizando a opera\u00e7\u00e3o de interse\u00e7\u00e3o de parti\u00e7\u00f5es. Essa opera\u00e7\u00e3o em artigos \u00e9 chamada de especializa\u00e7\u00e3o. Mas notamos que as parti\u00e7\u00f5es para depend\u00eancias que ser\u00e3o mantidas apenas ap\u00f3s v\u00e1rias rodadas de especializa\u00e7\u00e3o podem ser reutilizadas ativamente, o que pode reduzir significativamente o tempo de execu\u00e7\u00e3o dos algoritmos, uma vez que a opera\u00e7\u00e3o de interse\u00e7\u00e3o \u00e9 cara. <\/p>\n

Portanto, propusemos uma heur\u00edstica baseada na Entropia de Shannon e na incerteza de Gini, al\u00e9m da nossa m\u00e9trica que chamamos de Entropia Inversa. Esta \u00e9 uma modifica\u00e7\u00e3o sutil da Entropia de Shannon e cresce \u00e0 medida que aumenta a singularidade do conjunto de dados. A heur\u00edstica proposta \u00e9 a seguinte:<\/p>\n

\"Busca<\/p>\n

Aqui \"Busca \u2014 grau de singularidade da parti\u00e7\u00e3o recentemente calculada \"Busca, e \"Busca \u00e9 a mediana de graus de exclusividade para atributos individuais. Todas as tr\u00eas m\u00e9tricas mencionadas acima foram testadas como m\u00e9tricas de exclusividade. Tamb\u00e9m \u00e9 poss\u00edvel notar que h\u00e1 dois modificadores na heur\u00edstica. O primeiro indica o qu\u00e3o pr\u00f3xima a parti\u00e7\u00e3o atual est\u00e1 da chave prim\u00e1ria e permite um maior cache das parti\u00e7\u00f5es que est\u00e3o longe da chave potencial. O segundo modificador permite monitorar a ocupa\u00e7\u00e3o do cache, incentivando assim a adi\u00e7\u00e3o de mais parti\u00e7\u00f5es ao cache quando h\u00e1 espa\u00e7o livre. A solu\u00e7\u00e3o bem-sucedida dessa tarefa permitiu acelerar o algoritmo PYRO em 10-40%, dependendo do conjunto de dados. Vale ressaltar que o algoritmo PYRO \u00e9 o mais bem-sucedido nesta \u00e1rea. <\/p>\n

Na figura abaixo, \u00e9 poss\u00edvel ver os resultados da aplica\u00e7\u00e3o da heur\u00edstica proposta em compara\u00e7\u00e3o com a abordagem b\u00e1sica de cache baseada em lan\u00e7amentos de moeda. O eixo X \u00e9 logar\u00edtmico.<\/p>\n

\"Busca
\n<\/p>\n

M\u00e9todo alternativo de armazenamento de parti\u00e7\u00f5es<\/h3>\n

\nEm seguida, propusemos um m\u00e9todo alternativo para armazenar parti\u00e7\u00f5es. As parti\u00e7\u00f5es representam um conjunto de clusters, em cada um dos quais s\u00e3o armazenados os n\u00fameros das tuplas com valores iguais para determinados atributos. Esses clusters podem conter longas sequ\u00eancias de n\u00fameros de tuplas, por exemplo, se os dados na tabela estiverem ordenados. Portanto, propusemos um esquema de compress\u00e3o para o armazenamento das parti\u00e7\u00f5es, especificamente o armazenamento intervalar de valores nos clusters das parti\u00e7\u00f5es:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Primeiro~intervalo}, underbrace{7, 8}_{Segundo~intervalo}, 10}}\\ downarrow{Compress\u00e3o}\\ pi(X) = {{underbrace{$, 1, 5}_{Primeiro~intervalo}, underbrace{7, 8}_{Segundo~intervalo}, 10}}$$display$$<\/p>\n

Este m\u00e9todo conseguiu reduzir o consumo de mem\u00f3ria durante a execu\u00e7\u00e3o do algoritmo TANE em 1 a 25%. O algoritmo TANE \u00e9 um algoritmo cl\u00e1ssico para descoberta de depend\u00eancias funcionais, que utiliza parti\u00e7\u00f5es em seu funcionamento. Na pr\u00e1tica, foi escolhido o algoritmo TANE, pois implementar o armazenamento intervalar nele foi significativamente mais f\u00e1cil do que, por exemplo, no PYRO, para avaliar se a abordagem proposta funciona. Os resultados obtidos est\u00e3o apresentados na figura abaixo. O eixo X \u00e9 logar\u00edtmico.<\/p>\n

\"Busca
\n<\/p>\n

Confer\u00eancia ADBIS-2019<\/h3>\n

\nCom base nos resultados da pesquisa em setembro de 2019, apresentei um artigo Cache Inteligente para Descoberta Eficiente de Depend\u00eancias Funcionais<\/a><\/noindex> na confer\u00eancia 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Durante a apresenta\u00e7\u00e3o, o trabalho foi destacado por Bernhard Thalheim, uma figura importante na \u00e1rea de bancos de dados. Os resultados das pesquisas serviram de base para a minha disserta\u00e7\u00e3o de mestrado no departamento de Matem\u00e1tica e F\u00edsica da SPbGU, durante a qual ambas as abordagens propostas (caching e compress\u00e3o) foram implementadas em ambos os algoritmos: TANE e PYRO. Os resultados mostraram que as abordagens propostas s\u00e3o universais, pois, em ambos os algoritmos e com ambas as abordagens, houve uma redu\u00e7\u00e3o significativa da mem\u00f3ria consumida, bem como uma diminui\u00e7\u00e3o consider\u00e1vel no tempo de execu\u00e7\u00e3o dos algoritmos.
\n
Fonte: 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\udd47Busca eficiente de depend\u00eancias funcionais em bancos de dados | ProHoster","description":"A busca de depend\u00eancias funcionais em dados \u00e9 aplicada em v\u00e1rias dire\u00e7\u00f5es de an\u00e1lise de dados: gerenciamento de bancos de dados, limpeza de dados, engenharia reversa de bancos de dados e explora\u00e7\u00e3o de dados.","canonical_url":"https:\/\/prohoster.info\/pt\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pt_PT","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\/pt\/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\/pt\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}