Efficient validation of functional dependencies during incremental discovery

The discovery of functional dependencies (FDs) from data is facing novel challenges also due to the necessity of monitoring datasets that evolves over time. In these scenarios, incremental FD discovery algorithms have to efficiently verify which of the previously discovered FDs still hold on the updated dataset, and also infer new valid FDs. This requires the definition of search strategies and validation methods able to analyze only the portion of the dataset affected by new changes. In this paper we propose a new validation method, which can be used in combination with different search strategies, that exploits regular expressions and compressed data structures to efficiently verify whether a candidate FD holds on an updated version of the input dataset. Experimental results demonstrate the effectiveness of the proposed method on real-world datasets adapted for incremental scenarios, also compared with a baseline incremental FD discovery algorithm.