Publicación: A METHOD TO FIND FUNCTIONAL DEPENDENCIES THROUGH REFUTATIONS AND DUALITY OF HYPERGRAPHS
Fecha
2015
Título de la revista
ISSN de la revista
Título del volumen
Editor
COMPUTER JOURNAL
Resumen
ONE OF THE MOST IMPORTANT STEPS IN OBTAINING A RELATIONAL MODEL FROM LEGACY SYSTEMS IS THE EXTRACTION OF FUNCTIONAL DEPENDENCIES (FDS) THROUGH DATA MINING TECHNIQUES. SEVERAL METHODS HAVE BEEN PROPOSED FOR THIS PURPOSE AND MOST USE DIRECT SEARCH METHODS THAT TRAVERSE THE SEARCH SPACE IN EXPONENTIAL TIME IN THE NUMBER OF ATTRIBUTES OF THE RELATION. AS IT IS NOT UNCOMMON TO FIND IN PRACTICE RELATIONS WITH TENS OF ATTRIBUTES, A NEED EXISTS TO FURTHER DEVELOP MORE EFFICIENT TECHNIQUES TO FIND FDS. THE METHOD STUDIED HERE FINDS THE MINIMAL SET OF MINIMAL FDS USING ALGORITHMS THAT SOLVE THE HYPERGRAPH DUALITY PROBLEM APPLIED ON THE COMPLEMENT OF THE REFUTATION HYPERGRAPH OF THE RELATION WITHOUT GOING THROUGH THE EXPONENTIAL SEARCH SPACE. AFTER SHOWING THAT THE EXTRACTION OF FDS CAN BE REDUCED TO THE HYPERGRAPH DUALITY PROBLEM, EXPERIMENTAL RESULTS ARE GIVEN AS VERIFICATION AND CHARACTERIZATION OF THE CORRECTNESS AND TIME COMPLEXITY OF THE PROPOSED TOOL.
Descripción
Palabras clave
MINIMAL TRANSVERSALS, FUNCTIONAL DEPENDENCIES, DUALITY OF HYPERGRAPHS
