Incremental discovery of denial constraints

We investigate the problem of incremental denial constraint (DC) discovery, aiming at discovering DCs in response to a set ▵r of tuple insertions to a given relational instance r and the known set Σ of DCs holding on r. The need for the study is evident since real-life data are often frequently updated, and it is often prohibitively expensive to perform DC discovery from scratch for every update. We tackle this problem with two steps. We first employ indexing techniques to efficiently identify the incremental evidences caused by ▵r. We present algorithms to build indexes for Σ and r in the pre-processing step, and to visit and update indexes in response to ▵r. In particular, we propose a novel indexing technique for two inequality comparisons possibly across the attributes of r. By leveraging the indexes, we can identify all the tuple pairs incurred by ▵r that simultaneously satisfy the two comparisons, with a cost dependent on log(| r|). We then compute the changes ▵Σ to Σ based on the incremental evidences, such that Σ⊕ ▵Σ is the set of DCs holding on r+ ▵r. ▵Σ may contain new DCs that are added into Σ and obsolete DCs that are removed from Σ. Our experimental evaluations show that our incremental approach is faster than the two state-of-the-art batch DC discovery approaches that compute from scratch on r+ ▵r by orders of magnitude, even when ▵r is up to 30% of r.