{"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\/es\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"B\u00fasqueda eficiente de dependencias funcionales en bases de datos","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

La b\u00fasqueda de dependencias funcionales en datos se aplica en diferentes \u00e1reas del an\u00e1lisis de datos: gesti\u00f3n de bases de datos, limpieza de datos, ingenier\u00eda inversa de bases de datos y exploraci\u00f3n de datos. Ya hemos publicado sobre las propias dependencias art\u00edculo<\/a><\/noindex> de Anastasia Birillo y Nikita Bobrov. Esta vez, Anastasia, graduada del Computer Science Center de este a\u00f1o, comparte el desarrollo de este trabajo en el marco de la investigaci\u00f3n que defendi\u00f3 en el centro. <\/p>\n

\"B\u00fasqueda
\n<\/a><\/noindex><\/p>\n

Selecci\u00f3n de la tarea <\/h3>\n

\nDurante mis estudios en el centro de CS, empec\u00e9 a profundizar en el estudio de bases de datos, especialmente en la b\u00fasqueda de dependencias funcionales y diferencias. Este tema estaba relacionado con mi trabajo de curso en la universidad, as\u00ed que durante la realizaci\u00f3n del proyecto, comenc\u00e9 a leer art\u00edculos sobre diversas dependencias en bases de datos. Escrib\u00ed una revisi\u00f3n de este campo, uno de mis primeros art\u00edculos<\/a><\/noindex> en ingl\u00e9s y lo present\u00e9 en la conferencia SEIM-2017. Me alegr\u00f3 mucho saber que fue aceptado, y decid\u00ed profundizar en el tema. La propia concepci\u00f3n no es nueva, se comenz\u00f3 a aplicar en los a\u00f1os 90, pero todav\u00eda se utiliza en muchos campos. <\/p>\n

En el segundo semestre de estudios en el centro, comenc\u00e9 un proyecto de investigaci\u00f3n sobre la mejora de algoritmos para la b\u00fasqueda de dependencias funcionales. Trabaj\u00e9 en \u00e9l junto con el estudiante de posgrado de la SPbGU, Nikita Bobrov, en JetBrains Research. <\/p>\n

Complejidad computacional de la b\u00fasqueda de dependencias funcionales<\/h3>\n

\nEl principal problema es la complejidad computacional. El n\u00famero posible de dependencias m\u00ednimas y no triviales est\u00e1 limitado por el valor \"B\u00fasqueda, donde \"B\u00fasqueda , el n\u00famero de atributos de la tabla. El tiempo de ejecuci\u00f3n de los algoritmos depende no solo de la cantidad de atributos, sino tambi\u00e9n de la cantidad de filas. En los a\u00f1os 90, los algoritmos para la b\u00fasqueda de dependencias funcionales en PCs de escritorio pod\u00edan procesar conjuntos de datos que conten\u00edan hasta 20 atributos y decenas de miles de filas, durante varias horas. Los algoritmos modernos, que funcionan en procesadores multin\u00facleo, detectan dependencias en conjuntos de datos de cientos de atributos (hasta 200) y cientos de miles de filas, aproximadamente en el mismo tiempo. Sin embargo, esto no es suficiente: ese tiempo es inaceptable para la mayor\u00eda de las aplicaciones reales. Por lo tanto, desarrollamos enfoques para acelerar los algoritmos existentes. <\/p>\n

Esquemas de cach\u00e9 para la intersecci\u00f3n de particiones<\/h3>\n

\nEn la primera parte del trabajo, desarrollamos esquemas de cach\u00e9 para la clase de algoritmos que utilizan el m\u00e9todo de intersecci\u00f3n de particiones. Una partici\u00f3n para un atributo representa un conjunto de listas, donde cada lista contiene los n\u00fameros de fila con los mismos valores para ese atributo. Cada una de estas listas se llama cl\u00faster. Muchos algoritmos modernos utilizan particiones para determinar si una dependencia se mantiene o no, adheri\u00e9ndose a la siguiente lemma: La dependencia \"B\u00fasqueda se mantiene si \"B\u00fasqueda. Aqu\u00ed \"B\u00fasqueda se designa la partici\u00f3n y se utiliza el concepto de tama\u00f1o de partici\u00f3n, que es el n\u00famero de cl\u00fasteres en ella. Los algoritmos que utilizan particiones, cuando se rompe una dependencia, a\u00f1aden atributos adicionales al lado izquierdo de la dependencia, despu\u00e9s de lo cual recalculan la dependencia mediante la operaci\u00f3n de intersecci\u00f3n de particiones. Esta operaci\u00f3n se llama especializaci\u00f3n en los art\u00edculos. Pero hemos observado que las particiones para dependencias que se mantendr\u00e1n solo despu\u00e9s de varios rondas de especializaci\u00f3n pueden ser reutilizadas de manera activa, lo que puede reducir considerablemente el tiempo de ejecuci\u00f3n de los algoritmos, ya que la operaci\u00f3n de intersecci\u00f3n es costosa. <\/p>\n

Por lo tanto, propusimos una heur\u00edstica basada en la Entrop\u00eda de Shannon y la incertidumbre de Gini, as\u00ed como nuestra m\u00e9trica, que llamamos Entrop\u00eda Inversa. Esta es una modificaci\u00f3n menor de la Entrop\u00eda de Shannon y aumenta a medida que aumenta la singularidad del conjunto de datos. La heur\u00edstica propuesta es la siguiente:<\/p>\n

\"B\u00fasqueda<\/p>\n

Aqu\u00ed \"B\u00fasqueda es el grado de singularidad de la partici\u00f3n reci\u00e9n calculada \"B\u00fasqueda, y \"B\u00fasqueda es una medida mediana de la singularidad para atributos individuales. Se probaron las tres m\u00e9tricas mencionadas anteriormente como medidas de singularidad. Tambi\u00e9n se puede notar que la heur\u00edstica incluye dos modificadores. El primero indica cu\u00e1n cercana est\u00e1 la partici\u00f3n actual a la clave primaria y permite en mayor medida almacenar en cach\u00e9 aquellas particiones que est\u00e1n alejadas de la clave potencial. El segundo modificador permite rastrear la ocupaci\u00f3n de la cach\u00e9 y, por lo tanto, estimula la adici\u00f3n de m\u00e1s particiones a la cach\u00e9 cuando hay espacio disponible. La soluci\u00f3n exitosa de esta tarea permiti\u00f3 acelerar el algoritmo PYRO entre un 10% y un 40% dependiendo del conjunto de datos. Cabe destacar que el algoritmo PYRO es el m\u00e1s exitoso en este campo. <\/p>\n

En la figura a continuaci\u00f3n se pueden ver los resultados de la aplicaci\u00f3n de la heur\u00edstica propuesta en comparaci\u00f3n con el enfoque b\u00e1sico de almacenamiento en cach\u00e9, basado en lanzar una moneda. El eje X es logar\u00edtmico.<\/p>\n

\"B\u00fasqueda
\n<\/p>\n

M\u00e9todo alternativo de almacenamiento de particiones<\/h3>\n

\nLuego propusimos un m\u00e9todo alternativo para el almacenamiento de particiones. Las particiones representan un conjunto de cl\u00fasteres, cada uno de los cuales almacena los n\u00fameros de las tuplas con los mismos valores para ciertos atributos. Estos cl\u00fasteres pueden contener secuencias largas de n\u00fameros de tuplas, por ejemplo, si los datos en la tabla est\u00e1n ordenados. Por lo tanto, propusimos un esquema de compresi\u00f3n para el almacenamiento de particiones, a saber, el almacenamiento de intervalos de valores en los cl\u00fasteres de particiones:<\/p>\n

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

Este m\u00e9todo logr\u00f3 reducir el consumo de memoria durante la ejecuci\u00f3n del algoritmo TANE entre un 1% y un 25%. El algoritmo TANE es un algoritmo cl\u00e1sico para la b\u00fasqueda de FD, utiliza particiones en su funcionamiento. En el \u00e1mbito pr\u00e1ctico se eligi\u00f3 el algoritmo TANE, ya que implementar el almacenamiento de intervalos en \u00e9l fue significativamente m\u00e1s sencillo que, por ejemplo, en PYRO, para evaluar si el enfoque propuesto funciona. Los resultados obtenidos se presentan en la figura a continuaci\u00f3n. El eje X es logar\u00edtmico.<\/p>\n

\"B\u00fasqueda
\n<\/p>\n

Conferencia ADBIS-2019<\/h3>\n

\nSeg\u00fan los resultados de la investigaci\u00f3n en septiembre de 2019, present\u00e9 un art\u00edculo Smart Caching for Efficient Functional Dependency Discovery<\/a><\/noindex> en la conferencia 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Durante la presentaci\u00f3n, el trabajo fue destacado por Bernhard Thalheim, una figura relevante en el campo de las bases de datos. Los resultados de la investigaci\u00f3n fueron la base de mi tesis de maestr\u00eda en matem\u00e1ticas y mec\u00e1nica en SPbGU, donde ambas aproximaciones propuestas (cach\u00e9 y compresi\u00f3n) se implementaron en ambos algoritmos: TANE y PYRO. Los resultados mostraron que los enfoques propuestos son universales, ya que en ambos algoritmos, con ambos enfoques, se observ\u00f3 una reducci\u00f3n significativa de la memoria consumida, as\u00ed como una notable disminuci\u00f3n en el tiempo de ejecuci\u00f3n de los algoritmos.
\n
Fuente: 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\udd47B\u00fasqueda eficaz de dependencias funcionales en bases de datos | ProHoster","description":"La b\u00fasqueda de dependencias funcionales en los datos se aplica en diversas \u00e1reas del an\u00e1lisis de datos: gesti\u00f3n de bases de datos, limpieza de datos, ingenier\u00eda inversa de bases de datos y exploraci\u00f3n de datos.","canonical_url":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"es_ES","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\/es\/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\/es\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}