Functional dependencies (FDs) are widely applied in data management tasks. Since FDs on data are usually unknown, FD discovery techniques are studied for automatically finding hidden FDs from data. In this paper, we develop techniques to dynamically discover FDs in response to changes on data. Formally, given the complete set$\Sigma$of minimal and valid FDs on a relational instance$r$, we aim to find the complete set$\Sigma^{\prime}$of minimal and valid FDs on$r\oplus\Delta r$, where$\Delta r$is a set of tuple insertions and deletions. Different from the batch approaches that compute$\Sigma^{\prime}$on$r\oplus\Delta r$from scratch, our dynamic method computes$\Sigma^{\prime}$in response to$\triangle\uparrow$. by leveraging the known$\Sigma$on$r$, and avoids processing the whole of$r$for each update from$\Delta r$. We tackle dynamic FD discovery on$r\oplus\Delta r$by dynamic hitting set enumeration on the difference-set of$r\oplus\Delta r$. Specifically, (1) leveraging auxiliary structures built on$r$, we first present an efficient algorithm to update the difference-set of$r$to that of$r\oplus\Delta r$. (2) We then compute$\Sigma^{\prime}$, by recasting dynamic FD discovery as dynamic hitting set enumeration on the difference-set of$r\oplus\Delta r$and developing novel techniques for dynamic hitting set enumeration. (3) We finally experimentally verify the effectiveness and efficiency of our approaches, using real-life and synthetic data. The results show that our dynamic FD discovery method outperforms the batch counterparts on most tested data, even when$\Delta r$is up to 30 % of$r$.

We investigate the problem of discovering approximate denial constraints (DCs), for finding DCs that hold with some exceptions to avoid overfitting real-life dirty data and facilitate data cleaning tasks. Different methods have been proposed to address the problem, by following the same framework consisting of two phases. In the first phase a structure called evidence set is built on the given instance, and in the second phase approximate DCs are found by leveraging the evidence set. In this paper, we present novel and more efficient techniques under the same framework. (1) We optimize the evidence set construction by first building a condensed structure called clue set and then transforming the clue set to the evidence set. The clue set is more memory-efficient than the evidence set and facilitates more efficient bit operations and better cache utilization, and the transformation cost is usually trivial. We further study parallel clue set construction with multiple threads. (2) Our solution to approximate DC discovery from the evidence set is a highly non-trivial extension of the evidence inversion method for exact DC discovery. (3) Using a host of datasets, we experimentally verify our approximate DC discovery approach is on average 8.2 and 7.5 times faster than the two state-of-the-art ones that also leverage parallelism, respectively, and our methods for the two phases are up to an order of magnitude and two orders of magnitude faster than the state-of-the-art methods, respectively.