Departamento de Computación

Dado un conjunto de atributos en una bases de datos relacionales, obtuvimos de forma correcta todas las dependencias funcionales mínimas y no triviales de dicha relación mediante una modificación al algoritmo TANE para hacer uso de funciones de similitud. Con el fin de hallar nuevas relaciones para el descubrimiento automático de conocimiento en distintas bases de datos, realizamos experimentos sobre ellas, variando los umbrales de las funciones de similitud implementadas. La metodología implementada fue capaz de hallar nuevas relaciones de dependencia en las bases de datos que, con un algoritmo de búsqueda de dependencias funcionales exactas no puede ser obtenido debido a las restricciones de este tipo de dependencia. Adicionalmente esta metodología es útil para el proceso de limpieza y diseño de la base de datos puesto que utilizando funciones de similitud es posible determinar cuando existen tuplas que no cumplen con alguna dependencia funcional que deber ser válida en la relación. En un caso como este nuestra metodología tiene la ventaja de que no requiere modificar los datos antes de determinar si la dependencia funcional será válida.

Abstract

Given a set of attributes in a relational database, we correctly found all minimal non-trivial functional dependencies of a database using a modified TANE algorithm that employs similarity functions. In order to find new relations to perform automated knowledge discovery, we perform several experiments with different thresholds for each similarity function implemented. The proposed methodology is able to find relations that would be impossible to find using traditional algorithms for the inference of exact functional dependencies. Furthermore, using our methodology it is possible to determine if some tuples prevent a functional dependency from being valid. If such dependency must be valid then we know that there are anomalies in the data that must be corrected. Such results are useful for data cleaning, or for the design of relational databases. One advantage of our methodology is that data does not need to be modified to verify if a functional dependency holds in the database.