EviDC: A Violation-Guided Algorithm for Incremental Denial Constraint Discovery
2026-07-27 • Databases
Databases
AI summaryⓘ
The authors focus on Denial Constraints (DCs), rules that help keep data accurate. When new data is added, existing rules might be broken and need updating. They created EviDC, a method that organizes these rules into a tree to quickly find and fix issues without checking everything. Their tests show EviDC is faster and works better for large or changing datasets. This approach helps manage data quality more efficiently.
Denial ConstraintsData QualityIncremental DiscoveryIntegrity ConstraintsPrefix TreeDCTrieViolation PathsEvidence ConstructionRuntime EfficiencyScalability
Authors
Qian Zhou, Xixian Han, Xiaolong Wan
Abstract
Denial Constraints (DCs) are an important class of integrity constraints and have been widely used in data quality management. In dynamic datasets, newly inserted tuples may invalidate existing DCs and require the constraint set to be updated. Existing incremental DC discovery methods still generate a large amount of intermediate evidence because they do not exploit the structural information of existing DCs during evidence construction. We propose EviDC, a violation-guided incremental DC discovery algorithm. EviDC organizes existing DCs into a prefix tree structure called DCTrie, in which each path from the root to a leaf represents a potential violation path. During incremental processing, evidence is expanded only along reachable violation paths, while irrelevant branches are pruned as early as possible. We evaluate EviDC on real-world and synthetic datasets. The results show that EviDC reduces intermediate evidence and improves runtime efficiency in most scenarios. The performance gain becomes more pronounced as the insertion ratio and dataset size increase, showing the effectiveness and scalability of violation-guided evidence construction.