1
EviDC: A Violation-Guided Algorithm for Incremental Denial Constraint Discovery
arXiv:2607.24021v1 [cs.DB] 27 Jul 2026
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. Index Terms—Denial constraints, Data profiling, Integrity constraints
I. I NTRODUCTION
D
ENIAL constraints (DCs) are an important type of integrity constraints (ICs) [1] in relational databases. They can express a wide range of complex semantic rules while remaining computationally manageable [2]. Due to their strong expressive power, DCs have been widely used in various data management tasks, including query optimization [3], [4], data quality management [5] and data cleaning [6], [7]. A DC is defined over a set of predicates that cannot be satisfied simultaneously. A predicate is a comparison condition defined on a pair of tuples. For example, t.ID = s.ID is a predicate. Taking the employee dataset De in Table I as an example, there are three rules that can be expressed as DCs. ϕ1 : ¬(t.ID = s.ID), describing the semantics that there are no employees with the same ID in De; ϕ2 : ¬(t.Level = s.Level∧t.M gr 6= s.M gr), meaning that if two employees have the same level, then their supervisors should be the same; ϕ3 : ¬(t.Hired < s.Hired ∧ t.Level < s.Level), meaning that if one employee’s start date is earlier than another employee’s, then their level should not be lower than the latter’s. DCs generalize several traditional integrity constraints, including unique column combinations (UCCs) [8], functional dependencies (FDs) [9], order dependencies (ODs) [10] and so on. Using these traditional expressions, the above three rules Qian Zhou, Xixian Han and Xiaolong Wan are with the School of Computer Science and Technology, Harbin Institute of Technology (HIT), China. (e-mail: [email protected], [email protected], [email protected]).
TABLE I E MPLOYEE D ATASET D E t1 t2 t3 t4 t5
ID #1 #2 #3 #4 #5
Name Ana Sam Ana Kai Tom
Hired 2000 2001 2002 2002 2003
Level 5 4 2 2 1
Mgr #1 #1 #2 #2 #3
require three different constraint types. ϕ1 can be represented by key constraints, ϕ2 is a typical example of functional dependencies, and ϕ3 can be represented by order dependencies [11]. In addition, the importance of DCs among different forms of ICs also comes from their good tractability [2]. Due to the significant application value of DCs, the DC discovery problem has been proposed to automatically discover DCs from datasets, thereby reducing the cost of manual design. Most existing DC discovery algorithms follow a twophase framework consisting of evidence construction and DC enumeration [12]. In this framework, evidence records the predicates satisfied by tuple pairs and serves as the core intermediate structure. Based on this framework, several static DC discovery algorithms have been proposed, such as Hydra [13] and DCFinder [14]. In practical application scenarios, data are not static but are frequently updated through insertions. For example, e-commerce systems continuously receive new transaction records [15], and industrial systems continuously collect equipment operation logs [16]. Suppose a newly hired employee in De is t6 = (#1, jack, 2001, 5, #1). It has the same ID value as t1 , which violates the requirement of ϕ1 . At this time, ϕ1 is invalid. If the DCs cannot be updated and maintained in time, valid newly inserted employee records may be incorrectly flagged as violations. A straightforward solution is to recompute the DCs in dynamic datasets by rerunning static algorithms. However, this strategy introduces a large amount of redundant computation and is costly [17]. Accordingly, the problem of incremental DC discovery has been proposed, aiming to recognize invalid DCs and update them to resolve the violations. To address the incremental DC discovery problem, IncDC [18] and 3DC [19] have been proposed. Although they avoid rediscovering DCs from scratch, both methods still generate a large amount of redundant evidence. They first construct incremental evidence for affected tuple pairs and then use the generated evidence to identify violated DCs and update the constraint set. The main difference lies in how the evidence is obtained
2
and maintained. IncDC relies on index structures to filter candidate tuple pairs, which introduces considerable memory overhead and frequent index maintenance. 3DC maintains the evidence set produced in the previous discovery round to identify newly appearing evidence, and this evidence set can be costly to construct and maintain. As a result, many intermediate evidence records may be generated or stored even though they will never lead to a DC violation. This observation motivates a different direction. Instead of constructing evidence first and checking DCs afterward, we use the existing DCs to guide evidence construction from the beginning. Each DC already defines a potential violation path. A tuple pair violates a DC only if it satisfies all predicates on that path. For example, ϕ2 corresponds to such a violation path. To violate ϕ2 , a tuple pair must satisfy both t.Level = s.Level and t.M gr 6= s.M gr. Therefore, once the partial evidence of a tuple pair can no longer be extended to any existing DC, further evidence expansion for this tuple pair is unnecessary. Based on this observation, we propose EviDC, a violationguided incremental DC discovery method. We organize all potential violation paths using the existing DCs. Once a tuple pair deviates from every possible violation path, its subsequent expansion becomes unnecessary and can be pruned immediately. In this way, EviDC differs from IncDC and 3DC by embedding DC structural information directly into the evidence construction process, rather than detecting invalid DCs only after evidence has been generated. To support violation-guided evidence construction, we design a prefix-sharing structure called DCTrie to organize potential violation paths implied by existing DCs. In DCTrie, each node corresponds to a predicate, and each root-to-leaf path represents a DC. During incremental processing, evidence is expanded only along reachable paths in DCTrie. Once a tuple pair deviates from all possible violation paths, the corresponding evidence construction process terminates immediately. In this way, DCTrie effectively reduces the generation of redundant intermediate evidence. EviDC follows a two-stage framework consisting of incremental evidence construction and DC updating. EviDC focuses on reducing evidence construction cost, and uses the repair strategy adopted by existing incremental methods for DC update. The main contributions of this paper can be summarized as follows: (1) We propose EviDC, a violation-guided incremental DC discovery algorithm. EviDC incorporates the structural information of existing DCs into incremental evidence construction, so that evidence is expanded only when it may still lead to a DC violation. (2) We design DCTrie, a prefix-sharing structure that organizes existing DCs as potential violation paths. DCTrie supports reachability checking during evidence construction and enables early pruning of irrelevant evidence contexts. (3) We conduct extensive experiments on real-world and synthetic datasets. Results show that EviDC significantly reduces evidence size and achieves better efficiency in most scenarios, especially under large insertion ratios.
The remainder of this paper is organized as follows. Section II reviews related work on DC discovery and incremental DC discovery. Section III presents the preliminaries and problem definition. Section IV introduces the EviDC algorithm. Section V presents the experimental evaluation. Finally, Section VI concludes the paper. II. R ELATED W ORK In recent years, DC discovery has become an important research direction in data quality management. Based on different application scenarios, existing research can be divided into two categories: static algorithms and incremental algorithms. Early studies on DC discovery mainly focused on static datasets. Chu et al. [2] first formalized denial constraints and proposed FASTDC, which established the widely adopted twophase framework consisting of evidence construction and DC enumeration. Several studies focus on improving evidence construction efficiency. BFASTDC [20] optimized predicate verification through bitwise operations. DCFinder [14] introduced Position List Indexes (PLIs) to accelerate evidence construction. Pena et al. [21] further introduced parallel evidence pipelines to improve evidence generation efficiency. FASTADC [22] reduced evidence construction cost using clue sets, while Filho et al. [23] applied Boolean operations to reduce the memory overhead of intermediate evidence structures. Other studies mainly optimize the DC enumeration stage. Hydra [13] proposed an evidence inversion strategy to reduce enumeration overhead, while ADCMiner [24] adopted the state-of-the-art hitting set enumeration algorithm MMCS [25] to improve DC enumeration efficiency. In addition, there are studies that break through this framework. DCMiner [12] mines concise, diverse, and strongly correlated DCs based on deep reinforcement learning. DCRer [26] also discovers DCs based on deep reinforcement learning and combines them with downstream data cleaning tasks. DCArray [27] performs DC discovery in a hardware pipeline based on FPGA, which significantly improves execution efficiency. Although these methods improve different stages of static DC discovery, most of them still rely on constructing large intermediate evidence structures, which remains the fundamental bottleneck of DC discovery algorithms. Different from static algorithms, incremental DC discovery avoids the complexity in global computation by processing the updated parts of the data. This incremental problem has been studied in other constraint types, including UCCs [8], FDs [28]–[30] and so on. In DC discovery, current incremental methods include IncDC [18] and 3DC [19]. Overall, they can be viewed as following a two-stage framework: first constructing incremental evidence, and then performing DC verification and update. IncDC is the first method for incremental DC discovery. In the evidence construction stage, IncDC builds novel index structures from the original data and existing DCs, especially over highly selective predicate combinations, to filter candidate tuple pairs and accelerate incremental evidence generation.
3
In the DC update stage, the generated evidence is used to identify invalid DCs and derive repaired constraints by extending violated DCs with additional predicates, followed by validity and redundancy checking. Although IncDC avoids rediscovering DCs from scratch, its efficiency heavily depends on the maintenance of complex index structures. 3DC is an incremental method built on an existing DC discovery algorithm [21]. It introduces a parallel working pipeline based on evidence context. 3DC reuses the evidence set Er obtained from the previous discovery round. For tuple insertions, it first constructs the incremental evidence set E∆r , derives newly appearing evidence by computing E inc = E∆r \ Er , and then updates the DCs through dynamic DC enumeration. Under this framework, the maintenance of DCs is transformed into a matching problem between incremental evidence and the existing DCs. Unlike IncDC, 3DC adopts separate processing strategies for insertions and deletions, addressing IncDC’s limited support for deletion scenarios. However, 3DC relies on the availability of the complete evidence set Er , whose construction and maintenance can be costly. Our work differs in the following. Both IncDC and 3DC still construct evidence independently from the structural information of existing DCs. We organize existing DCs as potential violation paths. We also directly incorporate DC structural information into the evidence construction stage. EviDC constrains evidence expansion to paths that may still lead to violations, rather than generating evidence first and verifying violations afterward. III. P RELIMINARIES Let R(A, B, C, . . .) denote a relational schema, where A, B, C are attributes in the relation. r denotes an instance of R, representing a set of tuples in this schema. Let |R| denote the number of attributes in R. For any tuple t ∈ r, t.A is the projection of tuple t on attribute A. Predicates: predicates describe the comparison relationship between two tuples over a given attribute or a comparison between a tuple’s attribute value and a constant. For any two tuples t, s ∈ r, a predicate can be defined as: P (t, s) : t.A op s.B
or
t.A op c
where op ∈ {<, ≤, >, ≥, =, 6=}, c is a constant. For example, P : t.name = s.name is a predicate, indicating that two employees have the same name. This paper focuses on comparisons between two different tuples, considering only the case of t 6= s. Denial constraints: a denial constraint is the negation form of a set of predicate conjunctions. Given a set of predicates, DC can be defined as: ϕ : ∀t, s ∈ r, ¬(P1 (t, s) ∧ P2 (t, s) ∧ · · · ∧ Pk (t, s)) In other words, a DC is a predicate set that cannot be satisfied simultaneously. If a DC does not contain any predicates with constant values, it is called a variable denial constraint (VDC). Otherwise, it is called a constant denial constraint (CDC). If a DC ϕ holds on r, we write ϕ |= r. Based on the above definitions, we further discuss several basic properties of DCs. (1) Triviality: A DC is said to be
TABLE II E MPLOYEE P REDICATE S PACE P1 : t.ID = s.ID P4 : t.N ame 6= s.N ame P7 : t.Hired > s.Hired P10 : t.Hired 6= s.Hired P13 : t.Level > s.Level P16 : t.Level 6= s.Level
P2 : t.ID 6= s.ID P5 : t.Hired < s.Hired P8 : t.Hired ≥ s.Hired P11 : t.Level < s.Level P14 : t.Level ≥ s.Level P17 : t.M gr = s.M gr
P3 : t.N ame = s.N ame P6 : t.Hired ≤ s.Hired P9 : t.Hired = s.Hired P12 : t.Level ≤ s.Level P15 : t.Level = s.Level P18 : t.M gr 6= s.M gr
trivial if it is satisfied by any instance. For example, ¬(t.ID = s.ID ∧ t.ID 6= s.ID) contains two predicates that can never be true simultaneously. In this case, it loses its semantics, so we only consider nontrivial DCs. (2) Symmetry: For a DC ϕ = ¬(P1 (t, s) ∧ P2 (t, s) ∧ · · · ∧ Pk (t, s)), its symmetric form is defined as ϕsym = ¬(P1 (s, t) ∧ P2 (s, t) ∧ · · · ∧ Pk (s, t)). A symmetric DC can be obtained by swapping the order of tuple pairs in a DC. The two are semantically equivalent, except that the order of the tuple pairs has been swapped. The symmetric DC of ϕ3 is ϕ4 : ¬(t.Hired > s.Hired ∧ t.Level > s.Level). (3) Augmentation: If ¬(P1 ∧ . . . ∧ Pn ) is valid, then ¬(P1 ∧ . . . ∧ Pn ∧ Q) is also valid. This means that if a valid DC is extended by adding a predicate, it remains valid. For example, if ϕ1 : ¬(t.ID = s.ID) holds, then another DC, ¬(t.ID = s.ID ∧ t.N ame = s.N ame) also holds. Therefore, the objective of DC discovery is to find minimal DCs. Predicate Space: Given a relational schema R, its predicate space is denoted by P , representing all possible predicates. For categorical data, attributes can only be compared using equality or inequality operators, i.e., op ∈ {=, 6=}, and two different predicates can be generated for the same attribute. For numerical data, op ∈ {=, 6=, >, ≥, <, ≤}, and six predicates can be generated for the same attribute. Taking the employee dataset as an example, its corresponding predicate space is shown in Table II. Evidence: The concept of evidence is proposed for recording how tuple pairs satisfy predicates in the predicate space. For any two distinct tuples (t, s) ∈ r, the evidence corresponding to this tuple pair is defined as: Evi(t, s) = {p ∈ P (R) | p(t, s) = true} Thus, evidence is essentially the set of all predicates that are satisfied by a tuple pair. The evidence set over the whole dataset is defined as the collection of evidence generated by all tuple pairs: E(r) = {Evi(t, s)|t, s ∈ r, t 6= s} Based on evidence, the validity of a DC can be defined as follows: A DC ϕ = ¬(P1 ∧ P2 ∧ · · · ∧ Pk ) is valid if ∀Evi ∈ E(r), P1 , . . . , Pk * Evi A DC ϕ holds on a relational instance if and only if there does not exist any evidence that contains all predicates in ϕ. Conversely, if some evidence contains all predicates in ϕ, then this evidence violates the DC. For example, (t6 , t1 ) in De corresponds to the evidence E1 = {P1 , P4 , P5 , P6 , P10 , P12 , P14 , P15 , P17 }. ϕ1 is a subset of E1 ,
4
Input
DCTrie Construction
Violation-Guided Evidence Construction Context Structure
Predicate Space
Invalid DCs -?
DCTire Builder O uá ‹á m P u:candidate tuples ‹:current evidence m :active DCTrie nodes
Original Dataset ˜ Predicate Grouping
DC Update
š”‹•
š•’Š
:š”‹• á š•’Š ;
î6
Violation Evidences
Categorical Refinement Evidence Propagation Along DCTrie Paths
Inserted Tuples ¿˜
up L
Violation Path Encoding Original DCs -
î5
î7
î5
violation
DC Repair
Numerical Refinement pruned
ú
ö O
O
Updated DCs - ñ
Fig. 1. Overview of EviDC and its components.
that is, all predicates in ϕ1 are contained in E1 . We can say that the tuple pair (t6 , t1 ) violates ϕ1 . Based on the above core concepts, we next give a formal description of the DC discovery problem. Static DC discovery: Given a relational instance r, the goal is to find the set Σ of DCs that hold on r. Incremental DC discovery: Given an initial dataset r, an original DC set Σ, and inserted tuples ∆r, the goal is to identify the set of invalid DCs ∆Σ− and incrementally repair them to maintain the validity of the DCs. In incremental DC discovery, incremental evidence is constructed for affected tuple pairs. These affected tuple pairs are denoted as (t, t′ ), where at least one tuple belongs to ∆r. If some incremental evidence covers a DC ϕ, then ϕ becomes invalid and should be removed. IV. E VI DC A LGORITHM A. Overview of Algorithm Incremental DC discovery aims to efficiently maintain the validity of DCs under data updates. We propose EviDC, which applies a violation-guided evidence construction method that directly constrains evidence expansion using the structural information of existing DCs. We regard each DC as a potential violation path composed of a sequence of predicates. Based on this, the algorithm can more efficiently identify affected DCs while reducing the generation of irrelevant evidence. To support this process, we design a tree structure called DCTrie, which compactly organizes shared predicates and potential violation paths. During incremental processing, evidence is expanded only along reachable paths in DCTrie, while branches that can no longer lead to violations are pruned immediately. As shown in Figure 1, EviDC can be divided into three main parts: DCTrie construction, violation-guided evidence construction, and DC update. Algorithm 1 presents the overall process of EviDC. First, the algorithm constructs the predicate space and divides the predicates into groups. Then, it builds the DCTrie and constructs the violation evidence set and the affected DCs. Finally, the algorithm removes the detected invalid DCs and generates repaired DC candidates to eliminate violations. B. DCTrie Structure This paper adopts a prefix tree DCTrie to uniformly represent all existing DCs. The basic idea of DCTrie is to organize
Algorithm 1: E VI DC Input: A relational database instance r, inserted tuples ∆r, and an existing DC set Σ Output: The maintained DC set Σ′ 1 Construct the predicate space P for r; 2 Divide the categorical groups Gcat and numerical groups Gnum ; 3 Build predicate indexes; 4 Sort Gcat and Gnum ; 5 G ← hGcat , Gnum i; 6 T ← DCT RIE B UILDER (Σ, P, G); − 7 (E∆ , Σ ) ← I NCRE E VI C ONSTRUCTION (r, ∆r, T, P, G); − 8 if Σ = ∅ then 9 return Σ; foreach ϕ ∈ Σ− do 11 Eϕ ← evidence subset that violates ϕ; 12 Padd ← P \ all predicates that appear in Eϕ ; 13 foreach p ∈ Padd do 14 Generate a new DC ϕ′ ← ϕ ∪ {p}; 15 if ϕ′ is valid and non-trivial then 16 Add ϕ′ into Σr ;
10
Σ′ ← (Σ \ Σ− ) ∪ Σr ; ′ 18 return Σ ; 17
the predicates in DCs into tree nodes according to a fixed attribute order. It merges and represents the constraint paths that have the same prefix. Each DC is mapped to a path from the root node to the leaf node to correspond to the violation path. To ensure that predicates over the same attribute appear in the same layer, the predicate space needs to be grouped first. For attribute A, define its corresponding predicate group GA ⊆ P as the set of all predicates acting on attribute A, where P is the predicate space. All predicate groups form a partition G = G1 , . . . , Gm . Predicates in the same group are mutually exclusive. They are divided into different nodes in a tree’s layer. For categorical attributes, the same attribute generates only equal and unequal predicates, such as P1 : t.ID = s.ID and P2 : t.ID 6= s.ID. A tuple pair can only satisfy one of them, so they correspond to different nodes in the same layer. For numerical attributes, since there are implications among the six comparison operations, they cannot be regarded as six completely independent directions. Based on the conditions that are simultaneously satisfied, they are divided into three directions: {=, ≥, ≤}, {>, ≥, 6=}, and {<, ≤, 6=}. Each layer of the tree represents a selection branch on the attribute group. Different nodes in the same layer correspond to different predicates in the attribute group. After predicate grouping, it is also necessary to determine the order of attribute groups in DCTrie. This order directly affects the pruning effect. To eliminate the tuple pairs that are unlikely to lead to violations as early as possible, we prioritize placing the attribute groups with stronger discrimination ability at shallower layers. We sort the attribute groups based on
5
the diversity of attribute values and prioritize processing categorical attributes, then numerical attributes. This is because categorical attributes usually correspond to only a few discrete predicate branches, and their comparison results are easier to obtain. If early branches are available, the algorithm can avoid excessive branching in numerical attributes. For the same type of attribute groups, we further determine the order based on the discrimination ability of attribute values. Based on the above design, we formally define DCTrie as follows: T = (V, E, root) where V represents the nodes, E represents the edge set, root represents the empty predicate node. DCTrie satisfies the following properties: 1) The root node does not correspond to any specific predicate, and its semantics is the empty prefix. 2) Except for the root node, each node corresponds to a predicate or a set of predicates that can all be satisfied simultaneously. 3) Each layer of the tree corresponds to a predicate group. Each leaf node corresponds to a DC. 4) If a DC does not contain any predicates in the attribute group Gi , then a wildcard node ”*” is introduced at the i-th layer of the DCTrie. This special node is called a wildcard node (WildcardChild) and is used to represent that the current DC does not impose any constraints on the attribute group at that layer. 5) Leaf nodes store the DCs corresponding to their paths, which are used for DC update. In DCTrie, any path from the root node to a leaf node is regarded as a violation path. If all predicates on this path are satisfied, then the DC corresponding to this path is violated. To ensure the completeness of the matching of the violation paths, DCTrie also needs to consider the symmetric form of a DC during its construction. For a DC ϕ ∈ Σ, its symmetric form ϕsym can be obtained by exchanging the tuple order. The same violation may be caused by a tuple pair (t, s) or (s, t). They are the same tuple pair but have different evidence. To avoid missing the violation caused by tuple swapping, when constructing DCTrie, both the DC and its symmetric form need to be inserted into the tree simultaneously. Algorithm 2 presents the construction process of DCTrie. The insertion process of a single DC is recursively executed in predicate group order. For the predicate group corresponding to the current layer, if the DC contains a predicate in this group, it expands downward along the corresponding predicate node. If it does not contain a predicate, it recursively follows the wildcard node until all predicate groups are processed and records the DC at the leaf node. For the De dataset, we build the DCTrie using the attribute order ID, N ame, M gr, Hired, and Level. The resulting structure is shown in Figure 2. Here, the wildcard node ∗ indicates that the corresponding DC has no predicate constraints on the attribute group at this layer. To simplify the notation, we use A = to denote the predicate t.A = s.A. The green nodes represent the paths formed by the symmetric insertion of DCs.
Algorithm 2: DCT RIE B UILDER Input: Σ, predicate space P , sorted attribute group G = hG1 , . . . , Gm i Output: DCTrie T 1 Create the root node of T ; 2 foreach ϕ ∈ Σ do 3 I NSERT DC(root, ϕ, G, 1); 4 if ϕsym 6= ϕ then 5 I NSERT DC(root, ϕsym , G, 1); return T ; 7 Procedure I NSERT DC(node, ϕ, G, i) 8 if i > |G| then 9 mark node as a leaf node and associate with ϕ; 10 return; 6
11 12 13 14
S ← the set of predicates of ϕ belonging to Gi ; if S = ∅ then child ← wildcard child of node; I NSERT DC(child, ϕ, G, i + 1);
18
else foreach p ∈ S do child ← child node of node labeled by p; I NSERT DC(child, ϕ, G, i + 1);
19
return;
15 16 17
root
D0
D1
ID
ID=
Name
Û
D3
Mgr
Û
D5
MgrM
Hired
Û
D8
Û
Level
Û
D12
Level=
î5
î6
Û
D2
Û
D4
Û
D6
D9
D13
D7
Hired< D10
Hired> D11
Level<
Level> D15
î7
D14
î8
Fig. 2. Structure of DCTrie.
C. Incremental Evidence Construction Based on DCTrie After building DCTrie, we utilize it to guide the evidence construction. When handling new tuples, the predicate refinement process is directly advanced along the valid path in DCTrie and dynamically prunes redundant branches. Thus, the algorithm does not need to explicitly generate a large amount of irrelevant evidence, thereby reducing the size of intermediate results. In order to merge the same evidence as much as possible, we introduce a structure called Evidence Context [21] to store the corresponding evidence for tuple pairs. It is an intermediate data structure, recording the evidence and relevant context
6
information. We also maintain an active node set in each evidence context to provide pruning information. For an inserted tuple tnew , the evidence context is defined as follows:
TABLE III N EWLY I NSERTED T UPLES IN E MPLOYEE D ATASET t6 t7 t8
Evidence Context = {tnew , RightT uples, Evidence, Active}
Here, RightT uples denotes the set of tuples that have the same evidence as tnew . Evidence records the predicates jointly satisfied by these tuple pairs. Active denotes the set of currently reachable DCTrie nodes. This serves as the basic unit in evidence construction. An evidence context can be viewed as a group of tuple pairs that have not yet been pruned. These tuple pairs share the same partial evidence and path state at a certain stage. For each inserted tuple, the algorithm first builds an initial context. In the initial context, RightT uples is initialized as r∪ ∆r \ {tnew }, representing all tuples that may form tuple pairs with tnew . Evidence is initialized using the default predicate directions of each attribute group, which may not actually be satisfied. The Active set is initialized as the root node. After context initialization, the algorithm progressively refines evidence contexts following the hierarchical order of DCTrie. At the i-th layer, only predicates belonging to the current predicate group Gi are considered. Tuple pairs are divided into different sub-contexts according to the predicates they satisfy in the current group, which is referred to as context splitting. The process of updating the current evidence according to the satisfied predicates is called refinement. After refinement, tuple pairs in different sub-contexts still share the same evidence before the current layer, but correspond to different predicate selections at the current layer. During refinement, the Active set is propagated simultaneously to maintain all reachable DCTrie paths. For a refinement predicate p, the algorithm retains two types of reachable nodes: child nodes labeled by p and inherited wildcard nodes. The resulting Active set therefore contains all DCTrie nodes that remain reachable after the current refinement step. If a context’s Active set is empty after refinement, it indicates that this context cannot match any complete DCTrie path. Therefore, the tuple pairs from the context cannot violate any DCs. At this point, the subsequent refinement process of this context is terminated without further verification of the remaining predicates. The order of attribute groups not only affects the structural organization of DCTrie, but also directly influences the efficiency of refining the evidence context. For an inserted tuple, its initial context usually corresponds to a larger set of right tuples. If we prioritize the more discriminative attribute group, then this right tuples set can shrink rapidly in the early stage, thereby reducing the subsequent splitting of attribute groups. Taking the insertion of data t6 as an example, the initial right tuples are {t1 , t2 , t3 , t4 , t5 }. First, the refinement is carried out at the ID layer, and the tuples that satisfy t.ID = s.ID are only t1 . The remaining tuples fall into another sub-context. At this time, for the sub-context containing only t1 , since its size has significantly shrunk, no further splitting occurs in the subsequent layers and no comparison operations are required. To avoid excessive fragmentation of evidence contexts, EviDC initializes evidence using the default predicate direction
ID #1 #6 #7
Name Jack Ema Wile
Hired 2001 2003 2002
Level 5 3 1
Mgr #1 #2 #2
Algorithm 3: IncreEviConstruction Input: r, ∆r, DCTrie T , P , predicate groups G Output: Incremental evidence set E∆ , invalid DCs Σ− − 1 Initialize E∆ ← ∅ and Σ ← ∅; 2 Construct the base evidence Evi; 3 foreach inserted tuple ti ∈ ∆r do 4 Ir ← r ∪ (∆r \ ti ); 5 C ← {hIr , Evi, {T.root}i}; 6 foreach categorical group g ∈ Gcat do 7 C ← U pdateCategoricalContext(C, ti , g, T ); 8 9 10 11 12 13
foreach numerical group g ∈ Gnum do C ← U pdateN umericalContext(C, ti , g, T ); (Ei , Σ− i ) ← CollectEvidence(C, T ); E∆ ← E∆ ∪ Ei ; Σ− ← Σ− ∪ Σ− i ; return (E∆ , Σ− );
of each attribute group. These directions make up the initial evidence. For categorical attributes, initially the default direction is set to be unequal. For numerical attributes, predicates that satisfy {>, ≥, 6=} are adopted. The purpose is to enable most tuple pairs to continue propagating along a unified default path, while only a small subset of tuple pairs needs to be corrected. For the ID attribute, the tuple pairs satisfying P1 : t.ID = s.ID are only (t6 , t1 ), so only one tuple pair needs to be corrected to an equality predicate. Using the inserted tuples in Table III as an example, the initial evidence context constructed for t8 is: C0 (t8 ) = {t1 , t2 , t3 , t4 , t5 , t6 , t7 }, {P2 , P4 , P7 , P8 , . . . , P18 }, {root} . Algorithm 3 presents the overall incremental evidence construction procedure. For each newly inserted tuple, the algorithm first initializes a context set, then sequentially calls Algorithm 4 and Algorithm 5 to refine the categorical attribute group and the numerical attribute group, respectively. After all attribute groups have been processed, it collects the final evidence and the invalid DCs. We now describe in detail the context refinement and pruning on categorical attribute groups. For a categorical attribute group, the same attribute involves both equality predicates and inequality predicates. Since we initially assume that a tuple pair satisfies the inequality predicate, tuples that satisfy the equality relationship need to be removed from the right tuple set. At this point, we perform context splitting: one sub-context corresponds to tuple pairs that satisfy the equality predicate, and the other corresponds to tuple pairs that remain on the inequality branch. For the former, we need to update the evidence by replacing the inequality predicate with the equality predicate, and then advance the active nodes along the
7
Algorithm 4: U PDATE C ATEGORICAL C ONTEXT Input: The current context set C, inserted tuple ti , categorical predicate group g, and DCTrie T Output: Updated context set C ′ 1 peq , pneq ← the equality and inequality predicates in g; 2 Ieq ← the tuple ID set with the same value as ti on the attribute of g; 3 if Ieq = ∅ then 4 Initialize C ′ ← ∅; 5 foreach hI, e, Ai ∈ C do 6 A′ ← T.A DVANCE (A, pneq ); 7 if A′ 6= ∅ then 8 Add hI, e, A′ i into C ′ ; return C ′ ;
9
Initialize Cadd ← ∅ and Ckeep ← ∅; foreach hI, e, Ai ∈ C do 12 Imatch ← I ∩ Ieq ; 13 Irem ← I \ Imatch ; 14 Aeq ← T.A DVANCE (A, peq ); 15 Aneq ← T.A DVANCE(A, pneq ); 16 if Aneq 6= ∅ and Irem 6= ∅ then 17 Add hIrem , e, Aneq i into Ckeep ;
10
11
if Aeq 6= ∅ and Imatch 6= ∅ then e′ ← e ⊕ E Q C ATEGORICAL M ASK(peq ); Add hImatch , e′ , Aeq i into Cadd ;
18 19 20 21 22
C ← Ckeep ∪ Cadd ; return C ′ ; ′
Algorithm 5: U PDATE N UMERICAL C ONTEXT Input: The current context set C, inserted tuple ti , numerical predicate group g, and DCTrie T Output: Updated context set C ′ 1 peq , plt , pgt ← the equality, less-than, and greater-than predicates in g; 2 Ieq ← the tuple ID set with the same value as ti on the attribute of g; 3 Ilt ← the tuple ID set with a greater value than ti on the attribute of g; 4 Initialize Cadd ← ∅ and Ckeep ← ∅; 5 foreach hI, e, Ai ∈ C do 6 Aeq ← T.A DVANCE (A, peq ); 7 Alt ← T.A DVANCE(A, plt ); c 8 Ieq ← I ∩ Ieq ; c 9 if Ieq 6= ∅ and Aeq 6= ∅ then 10 eeq ← e ⊕ E Q R ANGE M ASK(peq ); c 11 Add hIeq , eeq , Aeq i into Cadd ; 12 13 14 15 16 17 18 19 20 21 22 23
equality branch. For the latter, we keep the original evidence and only need to update the set of active nodes. If the active node set becomes empty, it means that the current context cannot possibly form a violation, and should be pruned. Algorithm 4 presents the refinement process for categorical attribute groups. We define EqCategoricalM ask(peq ) as the evidence update mask associated with the current equality predicate, which is used to update the evidence accordingly. Based on the value of ti on the current attribute, the algorithm retrieves the candidate tuple set Ieq with the same attribute value. Lines 3-9 handle the case when Ieq is empty. T.advance denotes the operation that advances from the current DCTrie nodes and returns the set of reachable nodes. When Ieq is not empty, the algorithm processes each context separately. It calculates Imatch = I ∩Ieq and Irem = I\Imatch . The original context is then split into two sub-contexts accordingly. Line 21 merges the new context to obtain the updated context set C ′ , which serves as input for the next attribute group. Algorithm 5 presents the refinement process for numerical attribute groups. For a numerical group, we define a set of predicate masks to replace the default state of the current evidence with the true predicate. EqRangeM ask(peq ) updates the evidence for the equality branch. LtRangeM ask(plt) updates it for the less-than branch. For each context, the algorithm first extracts the subset of tuples that satisfy the equality relation and propagates them along the equality
c I ← I \ Ieq ; if I = ∅ then continue;
Iltc ← I ∩ Ilt ; I ← I \ Iltc ; if Iltc 6= ∅ and Alt 6= ∅ then elt ← e ⊕ LT R ANGE M ASK(plt ); Add hIltc , elt , Alt i into Cadd ; if I 6= ∅ then Agt ← T.A DVANCE(A, pgt ); if Agt 6= ∅ then Add hI, e, Agt i into Ckeep ;
C ′ ← Ckeep ∪ Cadd ; ′ 25 return C ; 24
predicate branch. If the corresponding active node set is not empty, it uses EqRangeM ask(peq ) to correct the evidence and generate a new sub-context of the equality direction. These tuples are then removed from the current right tuples. Subsequently, the algorithm extracts subsets of the remaining tuples that satisfy the less-than relationship and propagates along the less-than branch. Finally, the algorithm combines all the newly generated equalities, less-than branch contexts, and the retained default branch contexts to obtain the updated context set C ′ . We now explain why symmetric DCs need to be inserted. For DCs that only contain categorical attributes, their symmetric form is equivalent to the original form, so whether to insert it has no impact on the result. To reduce memory space, we only initialize the tuple pairs in the (tnew , told ) and (tnew , t′new ) directions, and then symmetrize the obtained evidence, resulting in the tuple pairs corresponding to (told , tnew ) and (t′new , tnew ). For DCs that contain numerical attributes, if only a single direction of the path is retained in the DCTrie, information in the opposite direction may be lost during refinement. This can cause some contexts that should
8
Input
oÙ L u• á ‹Ù á <pÙ =
In•‡”–‡† –—’Ž‡ã šá Initial right tuples: uÙ L <šÚ á šÛ á šÜ á šÝ á šÞ á šß á šà = Initial evidence: ‹Ù L –Û á –Ý á –à á –á á –ÚÙ á –ÚÜ á –ÚÝ á –Úß á –Úá •itial context: oÙ L u• á ‹Ù á <pÙ =
÷ò M oÚ L uÚ á ‹Ú á <pÛ = uÚ L uÙ ‹Ú L ‹Ù
Legend
NameM
Expand path
oÛ L uÛ á ‹Û á <pÝ =
Pruned path
uÛ L uÚ ‹Û L ‹Ú
Violation evidence
û
M
û
oÜ L uÜ á ‹Ü á <pß á pà = uÜ L <šÚ á šÛ á šÞ á šß = ‹Ü L ‹Û
ö
oÞ L uÞ á ‹Þ á <pâ á pÚÚ = uÞ L <šÚ á šÛ á šß = ‹Þ L ‹Ü
ú
O
Pruned oâ L uâ á ‹â á <”›’’=
uÝ L <šÜ á šÝ á šà = ‹Ý L ‹Ü F |Úá E <|Úà =
ö
P
L oÝ L uÝ á ‹Ý á <pà =
ö
O
O
oß L uß á ‹ß á <pâ á pÚÙ =
oà L uà á ‹à á <pÚÙ =
uß L <šÞ á šà = ‹ß L ‹Ü F |à á |á E <|Þ á |ß =
uà L <šà = ‹à L ‹Ý F |à á |á E <|Þ á |ß =
ú
L
oÚÙ L uÚÙ á ‹ÚÙ á <pÚÜ =
ú
ö
L
Pruned oá L uá á ‹á á <”›’’=
O
oÚÚ L uÚÚ á ‹ÚÚ á <pÚÝ =
uÚÙ L <šÞ = uÚÚ L <šà = ÚÙ L ß F þÚÜ á þÚÝ E <þÚÚ á þÚÛ = ÚÚ L à F þÚÜ á þÚÝ E <þÚÚ á þÚÛ =
Violation Found ÐÛ
Violation Found ÐÜ
Fig. 3. Process of evidence refinement and pruning (taking t8 as an example)
continue to propagate to be pruned incorrectly. For example, when (t7 , t3 ) is refined to the D7 node, it should continue to move in the direction of t7 .Hired > t3 .Hired. If the green node is not added, the set of forward nodes will be empty. Therefore, this evidence context will be incorrectly pruned. Figure 3 illustrates the evidence construction process using the insertion of tuple t8 as an example. Initially, all tuple pairs are assumed to satisfy the default evidence and are associated with the root node. Since the ID and N ame values of t8 differ from those of all existing tuples, no context splitting occurs in these two layers. At the M gr layer, the context is divided into two sub-contexts. Tuples t1 , t2 , t5 , t6 enter nodes D6 , D7 through the inequality branch, while tuples t3 , t4 , t7 enter node D7 through the equality branch. At the Hired layer, the context containing t3 , t4 is pruned because no child node exists for the predicate t.Hired = s.Hired. Meanwhile, the inequality branch is further divided into t1 , t2 , t6 and t5 . At the Level layer, the context containing t5 reaches leaf node D13 , identifying a violation of ϕ2 . Similarly, the context containing t7 reaches leaf node D14 , identifying a violation of ϕ3 . Therefore, the violating tuple pairs (t8 , t5 ) and (t8 , t7 ) are successfully detected. D. DC Update Based on Incremental Evidence After incremental evidence construction, the algorithm records invalid DCs together with their corresponding violating evidence. The next step is to repair invalid DCs based on the detected violations. Similar to IncDC and 3DC, EviDC updates invalid DCs by adding more specific predicate restrictions. The repaired DCs are generated through single-predicate extensions of invalid DCs. For example, the (t6 , t1 ) tuple pair violates ϕ1 . This can be achieved by rewriting ϕ1 so that it is no longer violated by this violation pair. Adding more predicate restrictions on ϕ1 , such as ϕ′1 : ¬(t.ID = s.ID ∧ t.N ame 6= s.N ame), indicates that there are no employees with the same name and ID. The DC update algorithm presented in EviDC breaks away from the double loop commonly found in DC verification. In previous methods, evidence records are first generated
independently of the DCs, and each generated evidence record must then be matched against the current DCs to locate the violation. In contrast, our method records the invalid DCs and violating evidence uniformly in an object. During evidence context refinement, once the DCTrie search reaches a leaf node, it indicates that an invalid DC has been found. To quickly locate invalid DCs and their violating evidence, we extract the DC information recorded in the leaf node, create an object for each invalid DC, and store the corresponding evidence in it. For an invalid DC, each predicate that does not appear in its violating evidence is treated as a candidate extension predicate. For a given DC ϕ, the algorithm first extracts the corresponding subset of violation evidence Eϕ , which is the set of all predicates included in the corresponding violation evidence. Then, instead of enumerating candidate constraints aimlessly from the entire predicate space, predicates that do not appear in Eϕ are selected from the predicate space as candidate extension predicates. A candidate predicate is appended to the invalid DC to generate a repaired candidate. If the resulting DC passes the validity and non-triviality checks, it is retained. It is worth noting that EviDC adopts a single predicate repair strategy. Although some violations can only be eliminated by adding multiple predicates simultaneously, enumerating all such combinations would result in a combinatorial explosion of candidate DCs. In the extreme case, a violation can always be eliminated by conjunctively adding all predicates from the predicate space to an invalid DC. Obviously, this is not a practical solution. Therefore, EviDC adopts a single predicate repair strategy. This design is consistent with existing incremental DC discovery methods such as IncDC and 3DC. E. Correctness and Complexity Analysis 1) Correctness: The invariants maintained during evidence construction are evidence contexts. For any evidence context c =< t, I, e, A >, let e denote the set of predicates that have already been verified as satisfied. The set I always contains exactly the right-hand tuples currently satisfying evidence e. The set A contains exactly the active nodes that may still be extended to a complete path in the DCTrie. Theorem 4.1: Algorithm 3 can identify all invalid DCs caused by inserted data. Proof: Assume that ϕ ∈ Σ is an invalid DC caused by inserted data. There must exist a tuple pair (ti , tj ) that satisfies all predicates along the path corresponding to ϕ, thereby violating ϕ after the data update. Initially, for each inserted tuple ti , Algorithm 3 constructs an initial evidence context c0 = hti , I0 , e0 , A0 i, where I0 contains all tuples except ti and A0 = {root}. Therefore, tuple tj must belong to the candidate right-hand tuple set at the beginning. At any level of the loop, the active node set of the evidence context containing tj is not empty and will not be pruned. Assume that at the i-th level, the active node set of the context containing tj becomes empty. The currently processed attribute predicate is pi . It indicates that no path exists in the constructed DCTrie along the direction of pi . However, this
9
contradicts the fact that ϕ has already been inserted into the DCTrie. Therefore, the evidence context containing tj must be preserved. As a result, the context containing tj continues to survive throughout the subsequent refinement stages and advances along the DCTrie path corresponding to ϕ. After all attribute groups have been processed, the refinement reaches the leaf node associated with ϕ. At this point, Algorithm 3 can correctly identify ϕ as an invalid DC and does not miss any violating evidence. Theorem 4.2: The DC repair procedure of EviDC is sound. Proof: We prove by contradiction. Suppose ϕ is an invalid DC identified by EviDC. Let Eϕ denote the set of violating evidence corresponding to ϕ. A repaired DC derived from ϕ has S the form ϕ′ = ϕ ∪ {p}, where p ∈ Padd and Padd = P \ e∈Eϕ e. Suppose that EviDC retains a repaired DC ϕ′ but ϕ′ is not valid on the updated dataset. Then there exists an evidence e containing all predicates in ϕ′ . Since ϕ′ is generated by adding a predicate p ∈ Padd to ϕ, and Padd only contains predicates absent from the violating evidence, we have p ∈ / e. However, because p ∈ ϕ′ and all predicates of ϕ′ are contained in e, it follows that p ∈ e, which is a contradiction. Therefore, every repaired DC retained by EviDC is valid on the updated dataset. Hence the theorem holds. Theorem 4.3: EviDC terminates after a finite number of steps. Proof: The number of inserted tuples is finite. Since the predicate space and the set of predicate groups are finite, the depth of DCTrie is also finite. For each inserted tuple, evidence refinement is performed over a finite number of predicate groups. Hence, the evidence construction stage performs a finite number of refinement operations. For DC update, the number of invalid DCs identified during evidence construction is finite. Therefore, the repair stage also performs a finite number of operations. Since both incremental evidence construction and DC update are finite processes, EviDC terminates after a finite number of steps. 2) Complexity: Assume that the size of the original dataset is n, the number of inserted tuples is |∆r| = m, the number of predicates is |P |, and the number of predicate groups is g. In the DCTrie construction phase, the algorithm traverses each DC in the original DC set and inserts it into the tree according to the predicate group order. For each DC, the insertion process accesses at most g layers. Therefore, the time complexity of DCTrie construction is O(|Σ|g). In terms of space, the number of nodes in DCTrie depends on the degree of prefix sharing among DCs. In the worst case, if there is no prefix sharing, each DC occupies an independent path of length at most g. Thus, the space complexity of DCTrie is O(|T |), where |T | ≤ O(|Σ| · g). In the incremental evidence construction phase, each inserted tuple ti is compared with all tuples in r ∪ (∆r \ {ti }). Therefore, the total number of tuple pairs considered is m(n + m − 1), which is bounded by O(m(n + m)). For each tuple pair, evidence refinement proceeds through at most
g predicate groups, corresponding to the depth of DCTrie. Therefore, the worst-case time complexity of incremental evidence construction is O(m(n + m)g). In practice, EviDC does not retain all candidate tuple pairs. The DCTrie-guided pruning continuously reduces the number of candidate tuples and active paths during refinement. Let ni denote the average number of candidate tuples retained at level i, and let ai denote the average number of active nodes at that level. Then the practical complexity can be expressed as ! g X ni ai , O m i=1
where usually ni ≪ n + m due to progressive context refinement and pruning. In the DC update phase, EviDC repairs invalid DCs using single-predicate extensions. For each invalid DC ϕ ∈ Σ− , S let Uϕ = e∈Eϕ e denote the set of predicates appearing in its violating evidence. The number of candidate predicates is |P | − |Uϕ |. For each generated candidate DC, the algorithm performs validity and non-triviality checking. Let Ccheck denote the cost of checking a candidate DC. Therefore, the update cost is X O (|P | − |Uϕ |) · Ccheck . ϕ∈Σ−
In the worst case, this can be bounded by O(|Σ− | · |P | · Ccheck ).
Overall, the worst-case time complexity of EviDC is O |Σ| · g + m(n + m)g + |Σ− | · |P | · Ccheck . V. E XPERIMENTAL E VALUATION
In this section, we conduct experiments to evaluate the effectiveness and scalability of EviDC. The results show that DCTrie reduces the computational overhead during DC updating in most tested settings. A. Settings All experiments were conducted on the same hardware platform equipped with an Intel Core i7-12700 processor running at 2.10 GHz, 12 physical cores, 32 GB RAM, and Windows 11. All algorithms were implemented or executed in Java using JDK 21. For each experiment, we repeated the execution 10 times and reported the average running time to reduce the influence of runtime fluctuations. We evaluated the algorithms on both real-world and synthetic datasets that have been widely used in previous DC discovery studies [13], [14], [18], [19], [21], [24]. The synthetic Tax dataset is derived from [31] and contains representative attributes of tax records. For each dataset, we first discovered initial DCs from the original relation. Then, we constructed incremental datasets with controlled violations. Specifically, violation tuples were generated according to the initial DC set and mixed with
10
TABLE IV C ORRECTNESS OF I NVALID DC D ETECTION . Dataset
EviDC
Brute-force Verifier
Precision
Recall
FD15 Hospital Claim Atom
414 50 7 1817
414 50 7 1817
1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0
regular tuples to simulate inconsistent updates in dynamic data scenarios. We implemented a naive exhaustive verifier to validate the correctness of EviDC. The verifier enumerates all evidence and checks every DC against all generated evidence to determine whether it is violated. Precision and Recall are computed based on the exact matching between the invalid DC sets returned by EviDC and the exhaustive verifier, rather than on the number of detected DCs. As shown in Table IV, EviDC achieves perfect Precision and Recall on all tested datasets, confirming the consistency of its invalid DC detection results with those of the exhaustive verifier. We compare EviDC with two representative incremental DC discovery methods, namely 3DC and IncDC. Since the source code of 3DC is not publicly available, we implemented 3DC based on the algorithm description provided in [19] and the ECP framework [21] released by the authors. We denote this implementation as 3DC* in the experimental results. To validate the reimplementation, we compared the behavior of 3DC* with the results reported in the original paper. The overall trends with respect to insertion ratios, evidence size, and runtime are consistent with those reported by the authors. IncDC was evaluated using the implementation publicly released by its authors. For all methods, runtime measures the cost of a single incremental maintenance operation, including incremental evidence construction, invalid DC detection and update, and the maintenance of auxiliary structures required during the update. In the preprocessing stage, 3DC* constructs the original evidence set Er , IncDC builds indexes over the initial dataset, and EviDC constructs the DCTrie. These preprocessing steps incur one-time costs and are therefore excluded from runtime measurements. Their construction times are reported separately in Table VI. B. Experimental Results 1) Exp-1: EviDC against 3DC, IncDC: To evaluate the performance of the proposed method under different update workloads, we compare the running times of the three algorithms on each dataset with insertion ratios λ of 0.1%, 1%, 10%, and 30%. The results are reported in Table V, where OOM indicates that the algorithm failed to complete within the time limit. As shown in Table V, the running times of all three methods increase with the insertion ratio. EviDC grows more slowly on most datasets. This is because its evidence construction is bounded by reachable violation paths rather than by the full predicate space. During refinement, its early termination reduces predicate comparison cost and context splitting cost.
Compared with 3DC*, EviDC reduces runtime by approximately 50% in most scenarios. For example, at an insertion ratio of 30%, EviDC takes 97 seconds on UCE, while 3DC* requires 269 seconds. The improvement comes from avoiding the construction and matching of evidence that cannot reach any DCTrie leaf. EviDC prunes many tuple pairs during construction and records an invalid DC when a DCTrie leaf is reached, reducing both intermediate evidence size and evidence-to-DC matching cost. The gap becomes more evident at high insertion ratios. As more tuples are inserted, the number of affected tuple pairs increases rapidly, forcing 3DC* to construct and compare a larger amount of incremental evidence. In contrast, EviDC only keeps evidence contexts that can still reach some DCTrie path, and many irrelevant tuple pairs are pruned before complete evidence records are generated. Therefore, the saved predicate evaluation and evidence matching costs become larger as the insertion ratio increases. At low insertion ratios, EviDC and 3DC* perform similarly on some datasets. On the Flights dataset, EviDC is slightly slower than 3DC* at low insertion ratios. This is because the initial DC set is relatively large, containing 57,340 DCs. A larger DC set leads to a larger DCTrie and increases the number of active nodes maintained during context refinement. When only a few tuples are inserted, the pruning benefit is not yet large enough to offset the trie traversal overhead. As the insertion ratio increases, more irrelevant tuple-pair contexts are pruned early, and the saved predicate evaluation and evidence storage costs become larger than the additional DCTrie traversal cost. Table VI compares the preprocessing cost of the three methods. Er denotes the original evidence set. Across most datasets, DCTrie construction finishes within one second. Even on larger datasets such as Flights and Ncvoter, EviDC only takes 0.18s and 0.28s, while 3DC* and IncDC require hundreds of seconds. The reason is that DCTrie construction depends mainly on the number of existing DCs and the number of predicate groups. It inserts each DC as a path and merges common prefixes. In contrast, 3DC* constructs the original evidence set over tuple pairs, and IncDC builds indexes over the original data. Therefore, their preprocessing costs grow more directly with data size. This explains why DCTrie introduces much lower preprocessing time and memory overhead. 2) Exp-2: Evidence Size under Different Insertion Ratios: In order to analyze the impact of DCTrie on evidence size, we counted the number of evidence under different insertion ratios. In Figure 4, EviDC generates much less evidence than 3DC* and IncDC across most datasets and insertion ratios. This is because DCTrie performs reachability checking during evidence refinement. If partial evidence cannot be extended to any existing DC, EviDC stops refining the corresponding context and avoids materializing a complete evidence record. Therefore, the retained evidence mainly corresponds to potential violation patterns, while 3DC* and IncDC may still generate evidence for tuple pairs irrelevant to all existing DCs.
11
TABLE V RUNTIME COMPARISON UNDER DIFFERENT INSERTION RATIOS .
99904 55100 114920 675000 147067 499300 32561 154061 14246 780000 187500
15 11 15 15 13 17 15 11 11 11 15
EviDC
EviDC
3DC*
IncDC
EviDC
3DC*
IncDC
EviDC
3DC*
IncDC
0.04 0.11 0.02 0.21 0.05 0.70 0.12 0.02 0.91 0.45 0.08
0.08 0.18 0.04 0.66 0.06 0.66 0.24 0.19 2.39 1.89 0.12
6.07 21.56 0.09 1086.24 14.43 OOM 33.76 0.14 1,427.05 OOM 0.98
0.13 0.73 0.05 1.46 0.13 5.85 0.77 0.04 5.74 2.86 0.15
0.21 1.85 0.05 4.34 0.11 5.74 1.06 0.74 8.01 4.50 0.17
56.83 128.75 0.34 OOM 235.47 OOM 84.45 0.61 OOM OOM 1.06
0.61 5.09 0.15 3.65 0.77 49.31 7.63 0.09 42.34 28.47 0.26
1.34 7.13 0.26 40.30 1.75 53.09 8.91 1.93 66.63 38.52 0.39
OOM OOM 10.69 OOM OOM OOM 352.17 4.37 OOM OOM 1.39
2.11 12.91 0.32 48.87 2.21 167.84 18.80 0.23 97.91 91.04 0.45
4.67 18.12 0.78 145.01 5.14 184.21 30.37 4.55 269.27 132.99 0.73
OOM OOM OOM OOM OOM OOM 1,043.94 18.97 OOM OOM 1.76
3DC
IncDC
103 102 101 1%
Insertion ratio
EviDC
103
104
3DC
IncDC
101
10%
EviDC
3DC
IncDC
0.1%
1%
Insertion ratio
102 101 100
10%
0.1%
(b) 3DC
1%
Insertion ratio
3DC
EviDC
102 0.1%
1%
Insertion ratio
10%
0.1%
102 101
1%
Insertion ratio
10%
(d) 3DC
IncDC
102 101
EviDC
103
# Evidences
# Evidences
# Evidences
# Evidences
103
103
IncDC
102
(c)
EviDC
3DC
103
10%
104 104
EviDC
104
103
102
(a) EviDC
30%
IncDC
# Evidences
# Evidences
10%
3DC*
105
0.1%
1%
EviDC
# Evidences
Tax Airport Hospital Ncvoter Atom Flights Adult Claim UCE Dit FD15
0.1%
|R|
# Evidences
|r|
Dataset
3DC
IncDC
102
101 0.1%
1%
Insertion ratio
10%
0.1%
1%
Insertion ratio
10%
0.1%
1%
Insertion ratio
10%
(e) (f) (g) (h) Fig. 4. Comparison of evidence size under different insertion ratios. (a) Airport, (b) Hospital, (c) Claim, (d) Tax, (e) Dit, (f) Flights, (g) FD15, (h) FD25.
TABLE VI E XECUTION T IME C OMPARISON ON P REPROCESSING S TEPS . Dataset
EviDC (DCTrie)
3DC* (Er )
IncDC (Index)
Tax Airport Hospital Ncvoter Atom Flights Adult Claim UCE Dit FD15
0.07 0.16 0.02 0.28 0.08 0.18 0.35 0.04 7.36 1.37 0.07
12.95 12.08 2.68 371.16 6.45 499.42 95.51 16.95 96.83 353.44 2.40
18.37 211.88 9.89 166.01 52.92 259.64 33.91 11.89 113.54 – 44.75
3) Exp-3: Evidence Size under Different Data Sizes: We fixed the insertion ratio at 1% and compared the changes in the amount of evidence generated by EviDC, 3DC, and IncDC under different original data sizes. In Figure 5, all methods generate more evidence as the original data size increases, but EviDC grows more slowly.
A clear gap between EviDC and the comparison methods can be observed on Flights, Hospital, and Claim. A larger dataset introduces more affected tuple pairs, but many of them cannot match any complete violation path in DCTrie. These tuple pairs are pruned after only a few predicate groups, reducing predicate comparison cost and intermediate evidence storage. This explains why EviDC suppresses evidence expansion more effectively as the data scale increases. 4) Exp-4: Impact of Predicate Space Size: To evaluate the scalability of EviDC with respect to predicate space size and DC complexity, we use the FD dataset to generate four datasets, namely FD5, FD10, FD15, and FD20. These datasets contain 5, 10, 15, and 20 attributes. As the number of attributes increases, both the predicate space and the number of discovered DCs grow significantly. The results are shown in Figure 6. Overall, the runtime of EviDC increases as the number of attributes, predicates, and original DCs grows. When the number of attributes increases from 5 to 20, the number of original DCs grows from 10 to 1120 and the number of
12
EviDC
3DC
IncDC
EviDC
102 101
3DC
IncDC
EviDC
10k
5k
20k
30k
Original data size
101 100
40k
1k
EviDC
# Evidences
3DC
101
IncDC
5k 10k 20k 30k 40k 50k 60k
EviDC
102 101
Original data size
1k
Original data size
3DC
10k
5k
20k
50k
70k
Original data size
(e)
20k
50k
Original data size
IncDC
EviDC
101
70k
3DC
IncDC
102 101 100
100 1k
10k
5k
(d)
102
103
100
5k 10k 20k 50k 100k 200k 500k
103
(c) 3DC
IncDC
102 1k
(b)
102
1k
101
Original data size
# Evidences
EviDC
103
102
100
5k 10k 20k 30k 40k 50k 60k
3DC
104
# Evidences
1k
102
(a)
# Evidences
EviDC
# Evidences
103
100
IncDC
# Evidences
104
100
3DC
103
# Evidences
# Evidences
105
1k
5k
10k
20k
50k
Original data size
(f)
70k 100k
1k
5k
(g)
10k
20k
50k
Original data size
70k 100k
(h)
Fig. 5. Comparison of evidence size under varying original data sizes. (a) Airport, (b) Hospital, (c) Claim, (d) Tax, (e) Dit, (f) Flights, (g) FD15, (h) FD25.
Insertion ratio 1%
10%
Insertion ratio 30%
1%
0.8 0.6 0.4 0.2 0.0
5
10
15
Number of columns
(a)
20
1.0
10%
50k
100k
20000
0.8 0.6
10000
0.4 0.2 0.0
1%
Runtime (ms)
1.0
0.1%
30000
30%
1.2
Running time (s)
Running time (s)
1.2
10%
10
24
38
48
Number of predicates
(b)
0
10k
500k
Number of Tuples
1M
Fig. 6. Runtime comparison under different predicate and attribute counts. (a) runtime vs. attribute count, (b) runtime vs. predicate count.
Fig. 7. Runtime of EviDC on Tax under different dataset sizes and insertion ratios.
predicates grows from 10 to 48. This trend is expected because a larger predicate space introduces more possible refinement branches, and a larger DC set leads to more potential violation paths in DCTrie. However, the increase in runtime is relatively moderate. This result shows that EviDC is not sensitive to the raw size of the candidate predicate space. The main reason is that EviDC does not enumerate evidence over the entire predicate space, but only expands branches reachable from the current active nodes in DCTrie. Therefore, even when the predicate space and the DC set become larger, many irrelevant branches are never expanded. 5) Exp-5: Scalability with Increasing Data Size: To evaluate the scalability of EviDC on large datasets, we conduct experiments on the Tax dataset with data sizes ranging from 10k to 1M tuples. Three insertion ratios, namely 0.1%, 1%, and 10%, are considered. The results are shown in Fig. 7. As the dataset size increases, the runtime of EviDC exhibits an approximately linear growth trend under all insertion ratios. Even when the dataset reaches one million tuples, the
algorithm remains efficient. This result indicates that, in this setting, the cost of EviDC grows primarily with the number of affected tuple pairs rather than the entire search space. The impact of insertion ratio becomes more noticeable as the dataset grows. When the insertion ratio increases from 0.1% to 10%, the number of incremental tuple pairs increases significantly, leading to more evidence contexts and more DCTrie traversal operations. Nevertheless, the growth rate remains stable without a sudden performance degradation. This is because EviDC performs evidence construction only along reachable violation paths and prunes irrelevant contexts early. As a result, the algorithm reduces the intermediate structure expansion commonly observed in generate-then-verify approaches, which helps maintain scalability under increasing data sizes and larger update workloads in our experiments. 6) Exp-6: Memory Usage Comparison: Figure 8 shows the memory consumption of EviDC, 3DC, and IncDC across a range of datasets. The memory usage is measured in megabytes (MB) and reflects the peak memory consumption during the incremental DC discovery process. As shown in Figure 8, EviDC achieves the lowest memory
13
Memory (MB)
EviDC (DCT ie Memo y) 200 100 50 20 10 5 2 1 0.5 0.2 0.1 0.05 0.02 0.01
Tax
Airport
Hospital
3DC (E Memo y)
IncDC (Index Memo y)
r
Ncvoter
Atom
Flights
FD15
% of runtime
Fig. 8. Memory usage comparison of EviDC (DCTrie), 3DC (Er ), and IncDC (Index) on various datasets.
construction and traversal can become more expensive. In this case, the advantage of EviDC may become smaller. When the insertion ratio grows, the benefit of EviDC becomes more evident. Therefore, EviDC is more suitable for scenarios with frequent insertions, where the DC structure can effectively guide evidence pruning. In the repair stage, EviDC adopts a single-predicate extension strategy, consistent with existing incremental DC discovery methods. This strategy aims to eliminate violations by adding more restrictions to each invalid DC, rather than exhaustively enumerating all possible repaired DCs.
100%
VI. C ONCLUSION
80%
This paper studies the problem of incremental denial constraint discovery. Existing methods construct incremental evidence without exploiting the structural information embedded in DCs, leading to a large amount of unnecessary intermediate results. To address this issue, we propose EviDC, a violationguided incremental DC discovery method. EviDC organizes existing DCs as a prefix-sharing structure called DCTrie and guides evidence construction along potential violation paths, allowing irrelevant branches to be pruned early. Experiments show that EviDC significantly reduces the size of incremental evidence and achieves better efficiency in most scenarios. The advantage becomes more pronounced as the insertion ratio and dataset size increase. Future work will focus on supporting more general update operations, including tuple deletions and modifications.
60%
BuildDCTrie BuildE idence DCUpdate
40% 20% 0%
Tax
Airport Hospital Ncvoter
Atom
Claim
Fig. 9. Percentage breakdown of EviDC runtime on different datasets.
footprint across almost all datasets. This is because it does not maintain the complete historical evidence set required by 3DC* or the index structures used by IncDC. During incremental processing, EviDC stores only DCTrie and surviving evidence contexts, and contexts that cannot reach any violation path are removed immediately. 7) Exp-7: Runtime Breakdown: To better understand the sources of EviDC’s runtime cost, we further analyze the time distribution of different components in the algorithm. Specifically, the runtime is divided into five stages, including data reading, predicate space construction, DCTrie construction, incremental evidence construction, and DC update. Figure 9 reports the percentage of total runtime spent in each stage on different datasets. Overall, the runtime mainly comes from incremental evidence construction, DCTrie construction, and data reading. Evidence construction dominates because it directly processes affected tuple pairs through predicate evaluation, context refinement, and active-node propagation. The DC update cost is relatively small because invalid DCs are located when DCTrie leaves are reached, avoiding an additional exhaustive matching step between generated evidence and existing DCs. C. Discussion The experimental results show that EviDC improves incremental DC discovery by using the structure of existing DCs during evidence construction. In this way, many irrelevant tuple pairs can be pruned early. This reduces both runtime and memory consumption. In our experiments, the construction of DCTrie and the predicate space only takes a small part of the total runtime. However, EviDC is sensitive to the size and structure of the original DC set. If the DC set is very large, DCTrie
R EFERENCES [1] A. Silberschatz, H. F. Korth, S. Sudarshan et al., Database system concepts. McGraw-Hill New York, 2002, vol. 5. [2] X. Chu, I. F. Ilyas, and P. Papotti, “Discovering denial constraints.” Proc. VLDB Endow., vol. 6, no. 13, pp. 1498–1509, 2013. [3] J. Kossmann, T. Papenbrock, and F. Naumann, “Data dependencies for query optimization: a survey,” The VLDB Journal, vol. 31, no. 1, pp. 1–22, 2022. [4] E. Pena, E. H. Pena, E. Falk, J. A. Meira, and E. C. de Almeida, “Mind your dependencies for semantic query optimization,” Journal of Information and Data Management, vol. 9, no. 1, pp. 3–3, 2018. [5] W. Fan, F. GEERTS, and X. Jia, “Improving data quality: Consistency and accuracy.” ACM, 2007. [6] X. Chu, I. F. Ilyas, and P. Papotti, “Holistic data cleaning: Putting violations into context,” in 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 2013, pp. 458–469. [7] X. Chu, I. F. Ilyas, S. Krishnan, and J. Wang, “Data cleaning: Overview and emerging challenges,” in Proceedings of the 2016 international conference on management of data, 2016, pp. 2201–2206. [8] Z. Abedjan, J.-A. Quiané-Ruiz, and F. Naumann, “Detecting unique column combinations on dynamic data,” in 2014 IEEE 30th International Conference on Data Engineering. IEEE, 2014, pp. 1036–1047. [9] Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen, “Tane: An efficient algorithm for discovering functional and approximate dependencies,” The computer journal, vol. 42, no. 2, pp. 100–111, 1999. [10] J. Szlichta, P. Godfrey, and J. Gryz, “Fundamentals of order dependencies,” arXiv preprint arXiv:1208.0084, 2012. [11] Z. Abedjan, L. Golab, F. Naumann, and T. Papenbrock, Data profiling. Springer, 2019, vol. 10. [12] L. Bian, W. Yang, J. Xu, and Z. Tan, “Discovering denial constraints based on deep reinforcement learning,” in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024, pp. 120–129. [13] T. Bleifuß, S. Kruse, and F. Naumann, “Efficient denial constraint discovery with hydra.” Proc. VLDB Endow., vol. 11, no. 3, pp. 311– 323, 2017.
14
[14] E. H. Pena, E. C. De Almeida, and F. Naumann, “Discovery of approximate (and exact) denial constraints,” Proceedings of the VLDB Endowment, vol. 13, no. 3, pp. 266–278, 2019. [15] V. Jain, B. Malviya, and S. Arya, “An overview of electronic commerce (e-commerce),” Journal of Contemporary Issues in Business and Government, vol. 27, no. 3, p. 666, 2021. [16] N. Tamalu, L. A. Ensina, E. C. de Almeida, E. H. M. Pena, and L. E. S. de Oliveira, “Fault detection in transmission lines: a denial constraint approach,” in Simpósio Brasileiro de Banco de Dados (SBBD). SBC, 2023, pp. 231–243. [17] Z. Tan, A. Ran, S. Ma, and S. Qin, “Fast incremental discovery of pointwise order dependencies,” Proceedings of the VLDB Endowment, vol. 13, no. 10, pp. 1669–1681, 2020. [18] C. Qian, M. Li, Z. Tan, A. Ran, and S. Ma, “Incremental discovery of denial constraints,” The VLDB Journal, vol. 32, no. 6, pp. 1289–1313, 2023. [19] E. H. Pena, F. Porto, and F. Naumann, “Discovering denial constraints in dynamic datasets,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 3546–3558. [20] E. H. Pena and E. C. de Almeida, “Bfastdc: A bitwise algorithm for mining denial constraints,” in International Conference on Database and Expert Systems Applications. Springer, 2018, pp. 53–68. [21] E. H. Pena, F. Porto, and F. Naumann, “Fast algorithms for denial constraint discovery,” 2022. [22] R. Xiao, Z. Tan, H. Wang, and S. Ma, “Fast approximate denial constraint discovery,” Proceedings of the VLDB Endowment, vol. 16, no. 2, pp. 269–281, 2022. [23] S. L. Marques Filho, “Discovering denial constraints using boolean patterns,” in Companion of the 2023 International Conference on Management of Data, 2023, pp. 281–283. [24] E. Livshits, A. Heidari, I. F. Ilyas, and B. Kimelfeld, “Approximate denial constraints,” arXiv preprint arXiv:2005.08540, 2020. [25] K. Murakami and T. Uno, “Efficient algorithms for dualizing largescale hypergraphs,” in 2013 Proceedings of the Fifteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2013, pp. 1–13. [26] D. Wu, D. Shen, T. Nie, and Y. Kou, “A deep reinforcement learning framework for denial constraint discovery,” in Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data. Springer, 2025, pp. 246–260. [27] S. L. MARQUES FILHO, M. A. Z. ALVES, and E. C. DE ALMEIDA, “Discovery of denial constraints with hardware acceleration,” 2026. [28] P. Schirmer, T. Papenbrock, S. Kruse, F. Naumann, D. Hempfing, T. Mayer, and D. Neuschäfer-Rube, “Dynfd: Functional dependency discovery in dynamic datasets.” in EDBT, 2019, pp. 253–264. [29] R. Xiao, Y. Yuan, Z. Tan, S. Ma, and W. Wang, “Dynamic functional dependency discovery with dynamic hitting set enumeration,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2022, pp. 286–298. [30] L. Caruccio, S. Cirillo, V. Deufemia, G. Polese et al., “Incremental discovery of functional dependencies with a bit-vector algorithm.” in SEBD, 2019. [31] P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis, “Conditional functional dependencies for data cleaning,” in 2007 IEEE 23rd international conference on data engineering. IEEE, 2006, pp. 746–755.