La búsqueda de dependencias funcionales en los datos se utiliza en diversas áreas del análisis de datos: gestión de bases de datos, limpieza de datos, ingeniería inversa de bases de datos y exploración de datos. Ya hemos publicado sobre las propias dependencias. Anastasia Birillo y Nikita Bobrov. En esta ocasión, Anastasia, egresada del Centro de Informática este año, comparte el desarrollo de este trabajo como parte del trabajo de investigación que defendió en el centro.
Selección de tareas
Mientras estudiaba en el centro de informática, comencé a estudiar en profundidad las bases de datos, es decir, la búsqueda de dependencias funcionales y diferenciales. Este tema estaba relacionado con el tema de mi trabajo de curso en la universidad, por lo que mientras trabajaba en el curso, comencé a leer artículos sobre varias dependencias en bases de datos. Escribí una reseña de esta área, una de mis primeras en inglés y lo presentó a la conferencia SEIM-2017. Me alegré mucho cuando descubrí que, después de todo, fue aceptada y decidí profundizar más en el tema. El concepto en sí no es nuevo: comenzó a utilizarse en los años 90, pero incluso ahora se utiliza en muchas áreas.
Durante mi segundo semestre en el centro, comencé un proyecto de investigación para mejorar algoritmos para encontrar dependencias funcionales. Trabajó en ello junto con el estudiante graduado de la Universidad Estatal de San Petersburgo, Nikita Bobrov, en JetBrains Research.
Complejidad computacional de la búsqueda de dependencias funcionales.
El principal problema es la complejidad computacional. El número de posibles dependencias mínimas y no triviales está limitado anteriormente por el valor Donde — número de atributos de la tabla. El tiempo de funcionamiento de los algoritmos depende no sólo del número de atributos, sino también del número de filas. En los años 90, los algoritmos de búsqueda de la ley federal en una PC de escritorio normal podían procesar conjuntos de datos que contenían hasta 20 atributos y decenas de miles de filas en hasta varias horas. Los algoritmos modernos que se ejecutan en procesadores multinúcleo detectan dependencias para conjuntos de datos que constan de cientos de atributos (hasta 200) y cientos de miles de filas aproximadamente al mismo tiempo. Sin embargo, esto no es suficiente: ese momento es inaceptable para la mayoría de las aplicaciones del mundo real. Por lo tanto, desarrollamos enfoques para acelerar los algoritmos existentes.
Esquemas de almacenamiento en caché para intersecciones de particiones
En la primera parte del trabajo, desarrollamos esquemas de almacenamiento en caché para una clase de algoritmos que utilizan el método de intersección de particiones. Una partición para un atributo es un conjunto de listas, donde cada lista contiene números de línea con los mismos valores para un atributo determinado. Cada una de estas listas se denomina clúster. Muchos algoritmos modernos utilizan particiones para determinar si se mantiene o no una dependencia, es decir, se adhieren al lema: Dependencia celebrado si . aquí Se designa una partición y se utiliza el concepto de tamaño de partición: la cantidad de clústeres que contiene. Los algoritmos que utilizan particiones, cuando se viola la dependencia, agregan atributos adicionales al lado izquierdo de la dependencia y luego la recalculan realizando la operación de intersección de particiones. Esta operación se llama especialización en los artículos. Pero notamos que las particiones para dependencias que solo se conservarían después de algunas rondas de especialización se pueden reutilizar activamente, lo que puede reducir significativamente el tiempo de ejecución de los algoritmos, ya que la operación de intersección es costosa.
Por lo tanto, propusimos una heurística basada en la entropía de Shannon y la incertidumbre de Ginny, así como nuestra métrica, a la que llamamos entropía inversa. Es una ligera modificación de la entropía de Shannon y aumenta a medida que aumenta la unicidad del conjunto de datos. La heurística propuesta es la siguiente:
es — grado de unicidad de la partición calculada recientemente Y es la mediana de los grados de unicidad de los atributos individuales. Las tres métricas descritas anteriormente se probaron como métrica de unicidad. También puedes notar que hay dos modificadores en la heurística. El primero indica qué tan cerca está la partición actual de la clave primaria y permite almacenar en caché en mayor medida aquellas particiones que están alejadas de la clave potencial. El segundo modificador le permite monitorear la ocupación de la caché y, por lo tanto, fomenta la adición de más particiones a la caché si hay espacio libre disponible. La solución exitosa de este problema nos permitió acelerar el algoritmo PYRO entre un 10% y un 40%, según el conjunto de datos. Vale la pena señalar que el algoritmo PYRO es el más exitoso en esta área.
En la siguiente figura puede ver los resultados de aplicar la heurística propuesta en comparación con un enfoque básico de almacenamiento en caché al lanzar una moneda. El eje X es logarítmico.
Una forma alternativa de almacenar particiones.
Luego propusimos una forma alternativa de almacenar particiones. Las particiones son un conjunto de grupos, cada uno de los cuales almacena un número de tuplas con valores idénticos para ciertos atributos. Estos grupos pueden contener largas secuencias de números de tupla, por ejemplo si los datos de una tabla están ordenados. Por lo tanto, propusimos un esquema de compresión para almacenar particiones, es decir, almacenamiento a intervalos de valores en grupos de particiones:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Primer intervalo}, underbrace{7, 8}_{Segundo intervalo}, 10}}\ downarrow{ Compresión} \ pi(X) = {{brazalete{$, 1, 5}_{Primer~intervalo}, brazalete{7, 8}_{Segundo~intervalo}, 10}}$$display$$
Este método logró reducir el consumo de memoria durante la operación del algoritmo TANE del 1 al 25%. El algoritmo TANE es un algoritmo clásico para buscar leyes federales; utiliza particiones durante su trabajo. Como parte de la práctica, se eligió el algoritmo TANE, ya que era mucho más fácil implementar el almacenamiento de intervalos en él que, por ejemplo, en PYRO para evaluar si el enfoque propuesto funciona. Los resultados obtenidos se presentan en la siguiente figura. El eje X es logarítmico.
Conferencia ADBIS-2019
Con base en los resultados de la investigación, en septiembre de 2019 publiqué un artículo. en la 23ª Conferencia Europea sobre Avances en Bases de Datos y Sistemas de Información (ADBIS-2019). Durante la presentación, Bernhard Thalheim, una persona importante en el campo de las bases de datos, destacó el trabajo. Los resultados de la investigación formaron la base de mi disertación en la maestría en matemáticas y mecánica de la Universidad Estatal de San Petersburgo, durante la cual se implementaron ambos enfoques propuestos (almacenamiento en caché y compresión) en ambos algoritmos: TANE y PYRO. Además, los resultados mostraron que los enfoques propuestos son universales, ya que en ambos algoritmos, con ambos enfoques se observó una reducción significativa en el consumo de memoria, así como una reducción significativa en el tiempo de operación de los algoritmos.
Fuente: habr.com