En este artículo hablaremos sobre las dependencias funcionales en las bases de datos: qué son, dónde se utilizan y qué algoritmos existen para encontrarlas.
Consideraremos las dependencias funcionales en el contexto de las bases de datos relacionales. En pocas palabras, en estas bases de datos la información se almacena en forma de tablas. A continuación, utilizamos conceptos aproximados que no son intercambiables en la teoría relacional estricta: llamaremos a la tabla en sí una relación, a las columnas - atributos (su conjunto - un esquema de relación) y al conjunto de valores de las filas en un subconjunto de atributos. - una tupla.
Por ejemplo, en la tabla anterior, (Benson, M, M órgano) es una tupla de atributos (Paciente, Paul, Doctor).
Más formalmente, esto se escribe de la siguiente manera: [Paciente, Género, Médico] = (Benson, M, órgano M).
Ahora podemos introducir el concepto de dependencia funcional (FD):
Definición 1. La relación R satisface la ley federal X → Y (donde X, Y ⊆ R) si y sólo si para cualquier tupla , ∈ R se cumple: si [X] = [X], entonces [Y] = [Y]. En este caso, decimos que X (el determinante o conjunto definitorio de atributos) determina funcionalmente Y (el conjunto dependiente).
En otras palabras, la presencia de una ley federal. X → Y significa que si tenemos dos tuplas en R y coinciden en atributos X, entonces coincidirán en atributos Y.
Y ahora, en orden. Veamos los atributos El paciente и Género para lo cual queremos saber si existen dependencias entre ellos o no. Para tal conjunto de atributos, pueden existir las siguientes dependencias:
- Paciente → Género
- Género → Paciente
Como se definió anteriormente, para que se mantenga la primera dependencia, cada valor de columna único El paciente solo debe coincidir un valor de columna Género. Y en el caso de la tabla de ejemplo, este es efectivamente el caso. Sin embargo, esto no funciona en la dirección opuesta, es decir, la segunda dependencia no se satisface y el atributo Género no es un determinante para Paciente. De manera similar, si tomamos la dependencia Médico → Paciente, puedes ver que está violado, ya que el valor petirrojo este atributo tiene varios significados diferentes: Ellis y Graham.
Por tanto, las dependencias funcionales permiten determinar las relaciones existentes entre conjuntos de atributos de la tabla. De aquí en adelante consideraremos las conexiones más interesantes, o más bien aquellas X → Ylo que ellos son:
- no trivial, es decir, el lado derecho de la dependencia no es un subconjunto del izquierdo (Y̸⊆X);
- mínimo, es decir, no existe tal dependencia Z → YQue Z⊂X.
Las dependencias consideradas hasta este punto eran estrictas, es decir, no preveían violaciones en la tabla, pero además de ellas, también existen aquellas que permiten cierta inconsistencia entre los valores de las tuplas. Estas dependencias se colocan en una clase separada, llamada aproximada, y se permite violarlas para un cierto número de tuplas. Esta cantidad está regulada por el indicador de error máximo emax. Por ejemplo, la tasa de error = 0.01 puede significar que la dependencia puede ser violada por el 1% de las tuplas disponibles en el conjunto de atributos considerado. Es decir, para 1000 registros, un máximo de 10 tuplas pueden violar la Ley Federal. Consideraremos una métrica ligeramente diferente, basada en valores diferentes por pares de las tuplas que se comparan. Para la adicción X → Y en actitud r se considera así:
Calculemos el error de Médico → Paciente del ejemplo anterior. Tenemos dos tuplas cuyos valores difieren en el atributo El paciente, pero coinciden en Doctor: [médico, paciente] = (Robin, Ellis) Y [médico, paciente] = (Robin, Graham). Siguiendo la definición de error, debemos tener en cuenta todos los pares en conflicto, lo que significa que habrá dos: (, ) y su inversa (, ). Sustituyémoslo en la fórmula y obtenemos:
Ahora intentemos responder la pregunta: "¿Para qué sirve todo esto?" De hecho, las leyes federales son diferentes. El primer tipo son aquellas dependencias que determina el administrador en la etapa de diseño de la base de datos. Por lo general, son pocos, estrictos y la aplicación principal es la normalización de datos y el diseño de esquemas relacionales.
El segundo tipo son las dependencias que representan datos "ocultos" y relaciones previamente desconocidas entre atributos. Es decir, tales dependencias no se consideraron en el momento del diseño y se encuentran para el conjunto de datos existente, de modo que más tarde, basándose en las numerosas leyes federales identificadas, se puedan sacar conclusiones sobre la información almacenada. Son precisamente estas dependencias con las que trabajamos. Se ocupan de todo un campo de minería de datos con diversas técnicas de búsqueda y algoritmos construidos en base a ellos. Averigüemos cómo pueden resultar útiles las dependencias funcionales encontradas (exactas o aproximadas) en cualquier dato.
Hoy en día, una de las principales aplicaciones de las dependencias es la limpieza de datos. Implica desarrollar procesos para identificar “datos sucios” y luego corregirlos. Ejemplos destacados de "datos sucios" son duplicados, errores de datos o errores tipográficos, valores faltantes, datos desactualizados, espacios adicionales y similares.
Ejemplo de un error de datos:
Ejemplo de duplicados en datos:
Por ejemplo, tenemos una tabla y un conjunto de leyes federales que deben ejecutarse. La limpieza de datos en este caso implica cambiar los datos para que las leyes federales sean correctas. En este caso, el número de modificaciones debe ser mínimo (este procedimiento tiene sus propios algoritmos, en los que no nos centraremos en este artículo). A continuación se muestra un ejemplo de dicha transformación de datos. A la izquierda está la relación original, en la que, obviamente, no se cumplen los FL necesarios (un ejemplo de violación de uno de los FL está resaltado en rojo). A la derecha está la relación actualizada, con las celdas verdes que muestran los valores modificados. Luego de este trámite se comenzaron a mantener las dependencias necesarias.
Otra aplicación popular es el diseño de bases de datos. Aquí vale la pena recordar las formas normales y la normalización. La normalización es el proceso de poner una relación en conformidad con un cierto conjunto de requisitos, cada uno de los cuales está definido por la forma normal a su manera. No describiremos los requisitos de varias formas normales (esto se hace en cualquier libro sobre un curso de bases de datos para principiantes), pero solo observaremos que cada una de ellas utiliza el concepto de dependencias funcionales a su manera. Después de todo, los FL son inherentemente restricciones de integridad que se tienen en cuenta al diseñar una base de datos (en el contexto de esta tarea, los FL a veces se denominan superclaves).
Consideremos su aplicación para las cuatro formas normales en la siguiente imagen. Recuerde que la forma normal de Boyce-Codd es más estricta que la tercera forma, pero menos estricta que la cuarta. Esto último no lo consideraremos por ahora, ya que su formulación requiere una comprensión de las dependencias multivaluadas, que no nos interesan en este artículo.
Otra área en la que las dependencias han encontrado su aplicación es la reducción de la dimensionalidad del espacio de características en tareas como construir un clasificador Bayes ingenuo, identificar características significativas y repararmetrizar un modelo de regresión. En los artículos originales, esta tarea se denomina determinación de relevancia redundante y de características [5, 6] y se resuelve con el uso activo de conceptos de bases de datos. Con la aparición de este tipo de trabajos, podemos decir que hoy existe una demanda de soluciones que nos permitan combinar la base de datos, el análisis y la implementación de los problemas de optimización anteriores en una sola herramienta [7, 8, 9].
Para buscar leyes federales en un conjunto de datos existen muchos algoritmos (tanto modernos como no tan modernos), que se pueden dividir en tres grupos:
- Algoritmos que utilizan el recorrido de celosías algebraicas (algoritmos de recorrido de celosía)
- Algoritmos basados en la búsqueda de valores acordados (Algoritmos de diferencia y conjunto de acuerdo)
- Algoritmos basados en comparaciones por pares (Algoritmos de inducción de dependencia)
En la siguiente tabla se presenta una breve descripción de cada tipo de algoritmo:
Puedes leer más sobre esta clasificación [4]. A continuación se muestran ejemplos de algoritmos para cada tipo:
Actualmente, están apareciendo nuevos algoritmos que combinan varios enfoques para encontrar dependencias funcionales. Ejemplos de tales algoritmos son Pyro [2] y HyFD [3]. Se espera un análisis de su trabajo en los siguientes artículos de esta serie. En este artículo solo examinaremos los conceptos básicos y el lema que son necesarios para comprender las técnicas de detección de dependencia.
Comencemos con uno simple: conjunto de diferencias y acuerdos, utilizado en el segundo tipo de algoritmos. El conjunto de diferencias es un conjunto de tuplas que no tienen los mismos valores, mientras que el conjunto de acuerdo, por el contrario, son tuplas que tienen los mismos valores. Vale la pena señalar que en este caso estamos considerando sólo el lado izquierdo de la dependencia.
Otro concepto importante que se encontró anteriormente es el de red algebraica. Dado que muchos algoritmos modernos operan según este concepto, necesitamos tener una idea de qué es.
Para introducir el concepto de celosía, es necesario definir un conjunto parcialmente ordenado (o conjunto parcialmente ordenado, abreviado como poset).
Definición 2. Se dice que un conjunto S está parcialmente ordenado por la relación binaria ⩽ si para todo a, b, c ∈ S se satisfacen las siguientes propiedades:
- Reflexividad, es decir, a ⩽ a
- Antisimetría, es decir, si a ⩽ b y b ⩽ a, entonces a = b
- Transitividad, es decir, para a ⩽ b y b ⩽ c se deduce que a ⩽ c
Tal relación se llama relación de orden parcial (laxa), y el conjunto en sí se llama conjunto parcialmente ordenado. Notación formal: ⟨S, ⩽⟩.
Como ejemplo más simple de un conjunto parcialmente ordenado, podemos tomar el conjunto de todos los números naturales N con la relación de orden habitual ⩽. Es fácil verificar que se cumplen todos los axiomas necesarios.
Un ejemplo más significativo. Considere el conjunto de todos los subconjuntos {1, 2, 3}, ordenados por la relación de inclusión ⊆. De hecho, esta relación satisface todas las condiciones de orden parcial, por lo que ⟨P ({1, 2, 3}), ⊆⟩ es un conjunto parcialmente ordenado. La siguiente figura muestra la estructura de este conjunto: si se puede llegar a un elemento mediante flechas hasta otro elemento, entonces están en una relación de orden.
Necesitaremos dos definiciones más simples del campo de las matemáticas: supremum e infimum.
Definición 3. Sea ⟨S, ⩽⟩ un conjunto parcialmente ordenado, A ⊆ S. El límite superior de A es un elemento u ∈ S tal que ∀x ∈ S: x ⩽ u. Sea U el conjunto de todos los límites superiores de S. Si hay un elemento más pequeño en U, entonces se llama supremum y se denota sup A.
El concepto de límite inferior exacto se introduce de manera similar.
Definición 4. Sea ⟨S, ⩽⟩ un conjunto parcialmente ordenado, A ⊆ S. El mínimo de A es un elemento l ∈ S tal que ∀x ∈ S: l ⩽ x. Sea L el conjunto de todos los límites inferiores de S. Si hay un elemento más grande en L, entonces se llama mínimo y se denota como inf A.
Considere como ejemplo el conjunto parcialmente ordenado anterior ⟨P ({1, 2, 3}), ⊆⟩ y encuentre el supremo y el mínimo en él:
Ahora podemos formular la definición de red algebraica.
Definición 5. Sea ⟨P,⩽⟩ un conjunto parcialmente ordenado tal que cada subconjunto de dos elementos tenga un límite superior e inferior. Entonces P se llama red algebraica. En este caso, sup{x, y} se escribe como x ∨ y, e inf {x, y} como x ∧ y.
Comprobemos que nuestro ejemplo de trabajo ⟨P ({1, 2, 3}), ⊆⟩ es una red. De hecho, para cualquier a, b ∈ P ({1, 2, 3}), a∨b = a∪b y a∧b = a∩b. Por ejemplo, considere los conjuntos {1, 2} y {1, 3} y encuentre su mínimo y supremo. Si los cruzamos obtendremos el conjunto {1}, que será el mínimo. Obtenemos el supremo combinándolos: {1, 2, 3}.
En los algoritmos para identificar problemas físicos, el espacio de búsqueda a menudo se representa en forma de celosía, donde conjuntos de un elemento (léase el primer nivel de la celosía de búsqueda, donde el lado izquierdo de las dependencias consta de un atributo) representan cada atributo. de la relación original.
Primero, consideramos dependencias de la forma ∅ → Atributo único. Este paso le permite determinar qué atributos son claves primarias (para dichos atributos no hay determinantes y, por lo tanto, el lado izquierdo está vacío). Además, dichos algoritmos se mueven hacia arriba a lo largo de la red. Vale la pena señalar que no se puede atravesar toda la red, es decir, si se pasa a la entrada el tamaño máximo deseado del lado izquierdo, entonces el algoritmo no irá más allá de un nivel con ese tamaño.
La siguiente figura muestra cómo se puede utilizar una red algebraica en el problema de encontrar una FZ. Aquí cada borde (X, XY) representa una dependencia X → Y. Por ejemplo, hemos pasado el primer nivel y sabemos que la adicción se mantiene. A→B (Mostraremos esto como una conexión verde entre los vértices A и B). Esto significa que, además, cuando avanzamos a lo largo de la red, es posible que no comprobemos la dependencia. A, C → B, porque ya no será mínimo. Del mismo modo, no lo comprobaríamos si la dependencia se mantuviera C → B.
Además, como regla general, todos los algoritmos modernos para buscar leyes federales utilizan una estructura de datos como una partición (en la fuente original, partición eliminada [1]). La definición formal de partición es la siguiente:
Definición 6. Sea X ⊆ R un conjunto de atributos para la relación r. Un cluster es un conjunto de índices de tuplas en r que tienen el mismo valor para X, es decir, c(t) = {i|ti[X] = t[X]}. Una partición es un conjunto de grupos, excluidos los grupos de longitud unitaria:
En palabras simples, una partición para un atributo. X es un conjunto de listas, donde cada lista contiene números de línea con los mismos valores para X. En la literatura moderna, la estructura que representa las particiones se denomina índice de lista de posiciones (PLI). Los grupos de longitud unitaria se excluyen para fines de compresión PLI porque son grupos que contienen solo un número de registro con un valor único que siempre será fácil de identificar.
Veamos un ejemplo. Volvamos a la misma mesa con los pacientes y construyamos particiones para las columnas. El paciente и Género (Ha aparecido una nueva columna a la izquierda, en la que están marcados los números de las filas de la tabla):
Además, según la definición, la partición de la columna El paciente en realidad estará vacío, ya que los clústeres individuales están excluidos de la partición.
Las particiones se pueden obtener mediante varios atributos. Y hay dos formas de hacer esto: revisando la tabla, construir una partición usando todos los atributos necesarios a la vez, o construirla usando la operación de intersección de particiones usando un subconjunto de atributos. Los algoritmos de búsqueda de leyes federales utilizan la segunda opción.
En palabras simples, para, por ejemplo, obtener una partición por columnas. abecedario, puedes tomar particiones para AC и B (o cualquier otro conjunto de subconjuntos disjuntos) y intersecarlos entre sí. La operación de intersección de dos particiones selecciona grupos de mayor longitud que son comunes a ambas particiones.
Veamos un ejemplo:
En el primer caso, recibimos una partición vacía. Si observa detenidamente la tabla, verá que no hay valores idénticos para los dos atributos. Si modificamos ligeramente la tabla (el caso de la derecha), ya obtendremos una intersección no vacía. Además, las líneas 1 y 2 en realidad contienen los mismos valores para los atributos. Género и Médico.
A continuación, necesitaremos un concepto como el tamaño de la partición. Formalmente:
En pocas palabras, el tamaño de la partición es la cantidad de clústeres incluidos en la partición (¡recuerde que los clústeres individuales no están incluidos en la partición!):
Ahora podemos definir uno de los lemas clave, que para particiones determinadas nos permite determinar si se mantiene una dependencia o no:
Lema 1. La dependencia A, B → C se cumple si y sólo si
Según el lema, para determinar si una dependencia se mantiene, se deben realizar cuatro pasos:
- Calcular la partición para el lado izquierdo de la dependencia.
- Calcular la partición para el lado derecho de la dependencia.
- Calcula el producto del primer y segundo paso.
- Compare los tamaños de las particiones obtenidas en el primer y tercer paso.
A continuación se muestra un ejemplo de cómo comprobar si la dependencia se cumple según este lema:
En este artículo, examinamos conceptos como dependencia funcional, dependencia funcional aproximada, analizamos dónde se utilizan y qué algoritmos para buscar funciones físicas existen. También examinamos en detalle los conceptos básicos pero importantes que se utilizan activamente en los algoritmos modernos para buscar leyes federales.
Referencias:
- Huhtala Y. et al. TANE: Un algoritmo eficaz para descubrir dependencias funcionales y aproximadas //El diario informático. – 1999. – T. 42. – No. 2. – págs.100-111.
- Kruse S., Naumann F. Descubrimiento eficiente de dependencias aproximadas // Actas del VLDB Endowment. – 2018. – T. 11. – No. 7. – págs. 759-772.
- Papenbrock T., Naumann F. Un enfoque híbrido para el descubrimiento de dependencia funcional // Actas de la Conferencia Internacional sobre Gestión de Datos de 2016. – ACM, 2016. – págs. 821-833.
- Papenbrock T. et al. Descubrimiento de dependencia funcional: una evaluación experimental de siete algoritmos // Actas del VLDB Endowment. – 2015. – T. 8. – No. 10. – págs. 1082-1093.
- Kumar A. et al. ¿Unirse o no unirse?: Pensar dos veces antes de unirse antes de seleccionar funciones // Actas de la Conferencia Internacional sobre Gestión de Datos de 2016. – ACM, 2016. – págs. 19-34.
- Abo Khamis M. et al. Aprendizaje en bases de datos con tensores dispersos // Actas del 37º Simposio ACM SIGMOD-SIGACT-SIGAI sobre principios de sistemas de bases de datos. – ACM, 2018. – págs. 325-340.
- Hellerstein JM et al. La biblioteca de análisis MADlib: o habilidades MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – No. 12. – págs. 1700-1711.
- Qin C., Rusu F. Aproximaciones especulativas para la optimización del descenso de gradiente distribuido a teraescala // Actas del cuarto taller sobre análisis de datos en la nube. – ACM, 2015. – P. 1.
- Meng X. y col. Mllib: Aprendizaje automático en Apache Spark //The Journal of Machine Learning Research. – 2016. – T. 17. – No. 1. – págs. 1235-1241.
Autores del artículo: , investigador en , и , investigador en
Fuente: habr.com