arXiv CS open access

Efficient discovery of unique column combinations on disk-resident data with limited memory

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Efficient discovery of unique column combinations on disk-resident data with limited memory

arXiv:2609.00783v1 [cs.DB] 1 Sep 2026

Xiaolong Wan, Xixian Han

Abstract—The discovery of unique column combinations (UCCs) is a core task in data profiling, describing the key constraints of a table. The existing algorithms cannot deal with largescale disk-resident data well due to high memory consumption and computational cost. In this paper, a novel DUD algorithm is developed to efficiently discover UCCs on disk-resident data with limited memory, which is inspired by the relationship between UCC discovery and transversal hypergraph. Rather than complete difference set generation of quadratic complexity, DUD only generates partial difference sets for hypergraph construction, followed by minimal hitting set enumeration to generate candidates and a validation process. DUD devises a strategy to generate full useful difference sets by pairwise comparisons of tuples having the same values with respect to some selected attributes. A novel theorem is developed and proved in this paper to report the candidates including the selected attributes as true UCCs directly without validation, which reduces the number of candidates to be validated significantly. A hash-based batch validation strategy is devised to validate a set of candidates on the relation instance, which only needs to maintain a small number of tuples in memory at a time. The extensive experimental results, conducted on synthetic and real-life data sets, show that DUD can discover UCCs on disk-resident data with high efficiency and low memory consumption. Index Terms—Unique column combination discovery, Diskresident data, Limited memory, Hypergraph transversal.

I. I NTRODUCTION The metaphors “data is the new oil” and “analytics is the combustion engine” [1] assert that data has become a valuable resource for deriving insights that power modern industries. Before fully exploiting data, the necessary condition is to discover its metadata, which helps understand and process the data to make it truly an asset for decision-making. Data profiling is the systematic process of determining the metadata of data sets, which produces a small but informative summary of a given data set [2]. The discovery of unique column combinations (UCCs) is a core task in data profiling, describing the key constraints of a table. Given relation schema R, a UCC X refers to a set of attributes whose projection only contains unique values in a given relation instance r, i.e., any two distinct tuples t1 , t2 ∈ r, t1 [X] ̸= t2 [X]. Since UCCs identify tuples uniquely, they can serve as candidate keys, from which the primary key can be selected. Besides key discovery, UCCs also have many important practical cases including query optimization [3], data cleansing [4], data integration [5], database reverse engineering [6]. Due to various reasons, for example, The authors are with School of Computer Science and Technology, Harbin Institute of Technology, China. (e-mail: wxl@hit.edu.cn, hanxx@hit.edu.cn)

TABLE I PART DATA RECORDS . PKEY 1 2 3 4 5 6 7 8 9 10

NAME Golden Blush Spring Cornfl Forest Bisque Moccas Misty Thist Linen

MFGR M1 M1 M4 M3 M3 M2 M1 M4 M4 M5

BRAND B13 B13 B42 B34 B32 B24 B11 B44 B43 B54

TYPE PROMO LARGE STAND SMALL STAND PROMO SMALL PROMO SMALL LARGE

PRICE 901 902 903 904 905 906 907 908 909 910

undefined, missing or outdated, the UCC information is often not annotated in the data set, which motivates the automatic UCC discovery problem. Since any superset of a UCC is also a UCC, an important property for UCC is its minimality. A UCC X is called minimal if none of its proper subsets is a UCC. The UCC discovery problem is to determine all minimal UCCs of a relation instance, which are sufficient to infer all UCCs. Example 1. Given a part table (Table I) of a manufactory, each tuple keeps the information of a part, including part key (PKEY), part name (NAME), manufacturer (MFGR), brand (BRAND), type (TYPE) and retail price (PRICE). For the given relation instance, the discovered minimal UCCs are {PKEY}, {NAME}, {PRICE}, {MFGR, TYPE}, {BRAND, TYPE}. Because of its practical importance, the UCC discovery problem has attracted extensive attention from researchers in both academia and industry [7], [8], [9], [10], [11]. Actually, the discovery of UCC is a rather hard problem since the number of total UCC candidates is exponential to the number of attributes. The existing algorithms can be divided into three classes: attribute-based approaches, tuple-based approaches and hybrid approaches, which optimize the discovery process in different aspects. Optimizing for data sets with many tuples, attribute-based approaches [7], [9] validate the candidates one after another, which are generated through attribute lattice. Aiming at the data sets with many attributes, tuple-based approaches [11] first compare the tuples pairwise and then derive all minimal UCCs by the comparison results. Hybrid approaches [8], [10] combine the advantages of the first two approaches and switch between two approaches for better performance, optimizing for data sets with many tuples and many attributes simultaneously. The existing algorithms assume that the required data structures can be held entirely in memory. Their executions depend on some in-memory data structures, e.g. prefix tree or stripped partitions. However, the assumption fails in many real-life

situations since the memory is limited for a specified machine and often is allocated partly to a process. On large-scale diskresident data, the existing algorithms incur high execution cost, even cannot work when the required data structures cannot be maintained entirely in memory. Considering the ever-growing data volume, how to efficiently discover UCCs on disk-resident data under limited memory is still an important and open problem. This paper solves UCC discovery problem inspired by the equivalency under parsimonious reduction between UCC discovery and transversal hypergraph [12]. Given relation instance, its UCCs are the minimal hitting sets of the hypergraph [13], whose vertices are attributes of relation schema and the hyperedges are the minimal difference sets generated by the complete pairwise comparisons of tuples. For a pair of tuples, the difference set is the set of attributes on which the two tuples have different values. A candidate attribute combination fails to be a UCC exactly when some pair of tuples agrees on every attribute in the candidate, that is, when the candidate shares no attribute with the difference set of that pair. A novel DUD algorithm (Disk-resident Unique column combination Discovery) is proposed in this paper to efficiently discover all minimal UCCs on disk-resident data with limited memory. The execution of DUD consists of three phases. Since the cost of complete pairwise comparisons is prohibitively high on large-scale data, DUD first performs a subset of pairwise comparisons to build the hypergraph with partial information (phase 1). Next DUD discovers the UCC candidates by enumerating minimal hitting sets on the built hypergraph (phase 2). Then the candidates are checked by a validation process (phase 3). The candidates checked to be correct are valid UCCs, while the validation process of invalid candidates brings some conflicting tuples, which have the same projection values on the invalid candidates. The hypergraph is updated by adding new hyperedges, i.e., the difference sets generated by comparing the conflicting tuples pairwise, and DUD enumerates minimal hitting sets again on the updated hypergraph. The following processing is similar, with the only difference that the newly generated candidates already discovered to be UCCs in the previous operations should be removed. If no new UCC candidates are generated or no new candidates are validated to be invalid, the execution of DUD is over. It is observed that the enumeration of minimal hitting sets is efficient in a hypergraph stemming from real-life data sets [13]. The emphasis of DUD lies on phase 1 and phase 3, i.e., efficient generation of partial difference sets and efficient validation of UCC candidates. Emphasis 1: efficient generation of partial difference sets. How to acquire a subset of difference sets, which can be generated with limited memory in a reasonable time and also be helpful for efficient UCC discovery, is a non-trivial issue. A difference set spanning all attributes provides no useful information for UCC discovery, since every non-empty candidate would trivially intersect it. The useful difference sets for minimal hitting set enumeration, i.e., those that exclude at least one attribute, are generated by pairwise comparisons of tuples with at least one equal attribute value. An im-

portant theorem is proved in this paper that, if all useful difference sets with respect to an attribute are generated, any UCC candidates including the attribute are true UCCs definitely without validation. This actually introduces a tradeoff between partial difference set generation and validation process. This paper sets an upper-bound for the number of full useful pairwise comparisons with respect to each attribute in order to restrict the cost of generating difference sets, and the attributes are divided into two types: attributes of full difference set generation type (FG type) and attributes of no difference set generation type (NG type). DUD only generates full useful difference sets with respect to attributes of FG type, whose comparison numbers are no more than the upper-bound. Then, random sampling is performed on relation instance to supplement difference sets, whose pairwise comparison number is linear to tuple number. Emphasis 2: efficient validation of UCC candidates. The key to efficient validation with limited memory is not to maintain all tuples in memory. In this paper, a hash-based strategy is devised for validating the UCC candidates on the relation instance directly. Two tuples with the same projection on any candidate must have the same value for each constituent attribute. Therefore, the collision can be checked by first sorting the relation instance with respect to one constituent attribute and only maintaining the tuples with the same value of the constituent attribute in memory. The remaining validation candidates contain only NG attributes. Therefore, DUD accesses NG attributes in the ascending order of maximum run lengths of equal attribute values to minimize the number of tuples kept in memory. A set of candidates sharing current attribute of NG type are validated simultaneously on the same sorted relation instance. The candidates checked to be correct are valid UCCs, while the validation process of invalid candidates brings some conflicting tuples, which are used to update the hypergraph. The correctness of DUD is proved in this paper, along with its cost analysis. The extensive experiments are conducted on synthetic and real-life data sets, representing the practical data characteristics comprehensively. The experimental results show that DUD achieves remarkable efficiency on diskresident data with limited memory. The contributions of this paper are listed as follows: - This paper proposes a novel DUD algorithm for efficient UCC discovery on disk-resident data. - The efficient generation of partial difference sets is devised in this paper, along with a novel theorem which prunes UCC candidates significantly. - The hash-based validation strategy is presented to validate candidates efficiently, by maintaining a small part of tuples in memory for collision checking. - The extensive experimental results show that DUD can discover UCCs on disk-resident data with high efficiency and low memory consumption. The rest of the paper is organized as follows. Section II gives preliminaries, followed by the related works in Section III. DUD algorithm is introduced in Section IV. Section V evaluates the performance of DUD and Section VI concludes the paper.

! 1 2 0 1 1 0 0 1 0

2 1 0 0 1 2 1 1 0

3 1 1 1 1 2 1 0 1

ℎ &''

{

4 0 0 1 1 1 0 0 0

5 2 1 1 0 0 0 0 1

6 2 1 1 0 2 0 1 0

7 2 1 1 1 0 0 1 0

8 2 0 0 1 0 1 0 1

9 10 11 12 13 14 15 16 17 18 19 20 1 2 1 1 0 1 2 0 1 2 2 2 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 2 2 2 2 0 1 1 2 2 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1

} {

(

} {

}

Fig. 1. The illustration of relation instance in the running example.

II. P RELIMINARIES Given relation schema R(A1 , A2 , . . . , Am ), where Ai (1 ≤ i ≤ m) is an attribute of R, let r be an instance of R with n tuples. Given t ∈ r, ∀A ∈ R, t[A] represents the value of A in t, and ∀X ⊆ R, t[X] denotes the projection of t on X. ∀t1 , t2 ∈ r, if t1 [X] = t2 [X], it means t1 [A] = t2 [A] for ∀A ∈ X and the projection of r on X contains duplicates. If t1 [X] ̸= t2 [X], it means ∃A ∈ X, t1 [A] ̸= t2 [A]. Note that two tuples with different subscripts (e.g. t1 , t2 ∈ r) correspond to two distinct tuples in this paper. Given a subset X of R, we say X is a unique column combination (UCC) if the projection of the relation instance r on X does not contain duplicates. Definition 1. Given relation instance r of schema R, an attribute subset X (X ⊆ R) is a UCC, if and only if, ∀t1 , t2 ∈ r, t1 [X] ̸= t2 [X]. For a UCC X, any superset of X is also a UCC. A UCC is called (inclusion-wise) minimal, if it does not contain any other UCC properly. Definition 2. Given a UCC X, it is minimal if and only if, ∀Y ⊂ X, Y is a non-UCC, i.e., ∃t1 , t2 ∈ r, t1 [Y ] = t2 [Y ]. Accordingly, the UCC discovery only returns minimal UCCs, and other UCCs can be derived naturally. Definition 3. Given relation instance r of schema R, the UCC discovery is to find all minimal UCCs in r. Example 2. In this paper, we use a running example, as depicted in Figure 1, to illustrate the algorithm execution. The relation schema contains eight attributes {A1 , A2 , . . . , A8 }. Figure 1 also provides 3 UCCs of relation instance r. Below we introduce hypergraph and its intimate connection with UCC discovery. Many different data dependencies are discovered through enumerating hitting sets of hypergraphs [14], [15]. Hypergraph. A hypergraph generalizes the concept of a graph, where each edge can connect multiple vertices rather than exactly two as in a conventional graph. Formally, a hypergraph H is an ordered pair (V, E), where V is a finite vertex set and E is a hyperedge set. ∀e ∈ E, e ∈ P(V ), where P(V ) denotes the power set of V. Given a hypergraph H, a hitting set h is a subset (h ⊆ V ) of V such that h has at least one common element with every hyperedge, i.e., ∀e ∈ E,

h∩e ̸= ∅. If h does not include any other hitting set, it is called minimal. The minimal hitting sets of H form the transversal hypergraph T r(H). Given a hypergraph H = (V, E), its minimization min(H) is a hypergraph formed by vertex set V and inclusion-wise minimal hyperedges of E. It is known that T r(H) = T r(min(H)) [13]. ∀t1 , t2 ∈ r, the difference set DS(t1 , t2 ) is the subset of R, in which t1 and t2 have different attribute values, i.e., DS(t1 , t2 ) = {A ∈ R | t1 [A] ̸= t2 [A]}. As discussed in Section I, an attribute set X is a UCC exactly when X has at least one common attribute with DS(t1 , t2 ) for every pair of tuples t1 , t2 ∈ r. It is already proved that, given a hypergraph H using attributes in R as vertex set and minimal difference sets generated by all pairwise comparisons of tuples as hyperedge set, the UCC discovery problem is equivalent to transversal hypergraph problem and the minimal UCCs are equal to the minimal hitting sets in H [12]. III. R ELATED WORKS UCC discovery is one component of data profiling and metadata discovery [2], [6], a field concerned with inferring structural properties of datasets. Related problems include functional dependency (FD) discovery [16], denial constraint discovery [17], and inclusion dependency discovery [18]. Handling data that cannot be held entirely in memory is a common challenge across these problems. Scalable methods for FD discovery on massive data have also been developed [16]. Beyond relational tables, structural discovery has also been studied for semi-structured data, including schema inference for JSON [19] and FD discovery for XML [20]. This paper focuses on UCC discovery, which finds the minimal column combinations that uniquely identify tuples in a relation. The existing algorithms can be classified into three categories: attribute-based approaches, tuple-based approaches, and hybrid approaches. Attribute-based approaches. The search space is modeled as an attribute lattice and each node corresponds to a UCC candidate. The candidates are enumerated in a systematic strategy and validated by stripped partitions [21] to determine the true UCCs. HCA algorithm [7] traverses the attribute lattice in bottom-top breadth-first strategy and generates the UCC candidates in a similar way as Apriori [22]. The minimality pruning is used to reduce the search space. HCA validates the generated candidates by stripped partitions. Due to the relatively high validation cost, HCA utilizes data-based and statistics-based pruning to optimize the validation operation. DUCC algorithm [9] models the UCC discovery problem as a graph coloring problem. By traversing the attribute lattice in a depth-first and random walk, DUCC can quickly approach the border between UCCs and non-UCCs. The pruning strategy can be performed in a bottom-up and top-down manner at the same time. It is observed that the unreachable nodes may exist due to aggressive pruning, and a post-processing is presented to find and remove the unreachable parts. Tuple-based approaches. All non-UCCs are discovered by first comparing pairs of tuples, and then the minimal UCCs are derived from the non-UCCs. GORDIAN algorithm [11]

transforms the UCC discovery problem into cube computation problem, in which the count computation of the projected entities can be used to verify whether the projection is a UCC. The data set is first compressed into a prefix tree, and then the interleaving of cube computation and all non-UCC discovery is performed. The true UCCs can be computed by complementing the non-UCCs. The powerful pruning techniques are applied to reduce the time and space requirement, utilizing the idea that any subset of non-UCC is also a non-UCC. Hybrid approaches. The advantages of attribute-based approaches and tuple-based approaches are combined to achieve better performance for hybrid approaches. HyUCC algorithm [10] automatically switches between attribute-based search (sampling phase) and tuple-based search (validation phase), depending on which one performs better currently. HyUCC starts with sampling phase, which performs sampling on the tuple pairs by stripped partitions to derive non-UCCs. The sampling efficiency is measured by the number of newly discovered non-UCCs per comparison. When the sampling efficiency falls below a threshold, sampling phase becomes inefficient, then the discovered non-UCCs are used to induce the candidate UCCs and HyUCC switches to validation phase. The validation efficiency is measured by the number of valid UCCs per validation. When the validation efficiency does not reach a threshold, the algorithm switches back to sampling phase with new comparison suggestions. HyUCC relaxes the threshold a bit in every switch and ends with validation phase. HPIValid algorithm [8] models the UCC discovery problem as hitting set enumeration problem in hypergraph. Instead of comparing all pairs of tuples, HPIValid performs the UCC discovery with partial information only. The algorithm first samples the tuple pairs by stripped partitions to construct a partial hypergraph, on which the minimal hitting sets are enumerated. The newly discovered candidate UCCs are validated via stripped partitions to check whether they are true UCCs. For the invalid UCCs, new comparisons of tuple pairs are suggested to generate new hyperedges in the hypergraph. The algorithm continues until no new candidate UCCs are found by enumerating hitting sets in the updated hypergraph. UCC discovery is closely related to the hypergraph transversal problem, which has been studied independently in combinatorics [13]. The enumeration of minimal hitting sets is equivalent to enumerating the minimal transversals of a hypergraph. DUD relies on the MMCS algorithm [23] for this enumeration step. Blasius et al. [13] show that hypergraphs arising from real-life data tend to have compact structure, making enumeration tractable in practice. Similar formulations have been applied in the discovery of other data dependencies [14], [15]. Discussion. The existing UCC discovery algorithms assume that the memory is large enough to hold the required data structures entirely. The assumption often fails in practical situations. Prefix tree utilized in GORDIAN algorithm often occupies a larger size than relation instance [24] and cannot be held in memory entirely on data set of large scale. The stripped partitions used for attribute-based and hybrid approaches have nearly the same size as relation instance in the compressed representation [25], [16], and it is rather difficult for stripped

partition based algorithms to discover UCCs when the size of stripped partition is larger than the allocated memory. The algorithm proposed in this paper follows the idea of hypergraph-based UCC discovery, placing it among the hybrid approaches discussed above. However, unlike these approaches, DUD does not rely on a global per-tuple structure, such as a prefix tree or stripped partitions, whose size scales with the relation instance. Instead DUD operates directly on the tuples of the relation instance throughout all phases. It is different from the existing hybrid approaches essentially in terms of two aspects: partial difference set generation strategy and validation strategy, which also are two most important components in hybrid approaches. - Instead of generating difference sets by sampled tuple pairs, our algorithm generates full useful difference sets with respect to some attributes. By the generation strategy, our algorithm can report most of the UCC candidates, which satisfy the specified condition, as true UCCs without validation. In contrast, the existing algorithms lack a similar pruning strategy and have to validate all candidates. - The existing algorithms require the relatively expensive validation for the generated candidates one by one through manipulating stripped partitions. Our algorithm utilizes a hash-based batch validation strategy to validate a set of candidates on relation instance simultaneously by maintaining a small number of tuples in memory at a time. This paper develops the algorithm elaborately, considering both high execution efficiency and the memory constraint throughout the algorithm design. IV. DUD ALGORITHM This section introduces DUD algorithm (Disk-resident Unique column combination Discovery), which efficiently discovers UCCs on disk-resident data with limited memory without any pre-processing. Algorithm overview. DUD utilizes partial information, i.e., difference sets generated by a subset of tuple pairs, to discover UCCs by enumerating minimal hitting sets on the built hypergraph and validating the generated UCC candidates. In the beginning, DUD builds the full useful difference sets with respect to some selected attributes. This provides a significant advantage that DUD does not need to validate each candidate and most candidates can be reported to be UCCs directly. For the validation candidates, DUD develops a hash-based batch validation strategy. By the validation process, DUD refines the built hypergraph if necessary and continues the UCC discovery until all UCCs are reported. Specifically, the execution of DUD consists of three phases, whose pseudocode is listed in Algorithm 1. In phase 1, DUD computes the difference sets by comparing tuples pairwise and constructs the hypergraph H (Line 2 in Algorithm 1). Note that we do not compare all pairs of tuples in phase 1 but generate the difference sets by comparing a subset of tuple pairs. Then, the minimal hitting sets of H are enumerated in phase 2 (Line 3 in Algorithm 1), which are the candidate UCCs. If

Algorithm 1 DUD algorithm Input: relation instance r of m attributes Output: The discovered UCCs 1: STucc : an empty set to keep the true UCCs //Phase 1: generate initial difference sets and construct the hypergraph 2: Hypergraph H = BuildInitialHypergraph(r) //Phase 2: Call MMCS [23] to find minimal hitting set 3: The UCC candidate set STc = MMCS(H) //Check whether new candidates are generated. 4: while (STc = STc \ STucc is not empty) do //Phase 3: validate candidates by hashing, ∆DS is a set to maintain difference sets generated by conflicting tuples 5: ∆DS = ValidateByHash(STc , STucc ) //Generate new difference sets, enumerate minimal hitting sets on updated H 6: if(|∆DS | ̸= 0) then 7: Update H by adding ∆DS to hyperedge sets 8: STc = MMCS(H) 9: else 10: STc = ∅ 11: end while 12: return STucc

the candidates need to be validated, a hash-based validation process is executed in phase 3 without maintaining all tuples in memory (Line 5 in Algorithm 1). If all candidates are proved to be true UCCs, the execution is over. Any candidates proved to be non-UCCs indicate some conflicting tuples, which have duplicate projections on the candidates. The hypergraph H is updated by adding new hyperedges, i.e., newly generated difference sets by comparing the conflicting tuples pairwise (Line 7 in Algorithm 1). In this case, the execution returns to phase 2 and enumerates minimal hitting sets again (Line 8 in Algorithm 1). The following operation is similar, with the only difference that the newly generated candidates already discovered to be UCCs in the previous operations should be removed (Line 4 in Algorithm 1). If no new UCC candidates are generated in phase 2 or no new candidates are validated to be invalid in phase 3, the execution of DUD is over. A. Phase 1: construction of hypergraph Phase 1 computes the useful difference sets with a relatively low cost for disk-resident relation instance. A naive choice that compares all pairs of tuples is impractical on large-scale data. Given a relation instance of n tuples, the number of tuple pairs is n2 . It takes a very long time to execute n2 comparisons when n is large. The more ideal choice is to perform partial comparisons. The emphasis of phase 1 is how to compare a subset of tuple pairs with a rational cost to generate the difference sets, which can help discover UCCs quickly. We first introduce Property IV.1 that the difference set consisting of all attributes of relation schema R does not affect the enumeration of minimal hitting sets if there is any difference set which is a nonvoid proper subset of R. Property IV.1. The difference set DSF consisting of all attributes does not affect the enumeration of minimal hitting sets if any difference set DSsub which is a nonvoid proper subset of R exists. Proof. Given difference set DSF , it is obvious that difference set DSsub is a subset of DSF . As long as DSsub exists,

the minimal hitting sets remains unchanged even if DSF is removed. According to Property IV.1, DUD only needs to generate the useful difference sets, namely those that exclude at least one attribute, which requires the two tuples generating them to have at least one equal attribute value. Full generation of useful difference sets with respect to attribute Ai . Given instance r of relation schema R(A1 , A2 , . . . , Am ), the difference sets with respect to Ai (1 ≤ i ≤ m) are generated by pairs of tuples with equal Ai values. Generating difference sets via a nested-loop comparison of all tuple pairs would take O(n2 ) time. DUD avoids this by first sorting the relation instance r on the specified attribute, so that tuples with equal values on the attribute are grouped together and only tuples within the same run need to be compared. In this sense, sorting serves as an efficient primitive for reducing pairwise comparisons [26]. Two-pass multi-way merge sort (TPMMS) [27] is used to sort files which exceed the sorting buffer size, while files within this size are loaded into memory, sorted, and written back to disk without intermediate temporary files. Let ri be the sorted version of r in ascending order of Ai , and |Ai | be the cardinality of Ai . The tuples in ri with the same Ai attribute values are arranged consecutively and compared pairwise. Let ni,k (1 ≤ k ≤ |Ai |) be the number of tuples with attribute value vi,k of Ai , where P|Ai | vi,1 ≤ vi,2 ≤ . . . ≤ vi,|Ai | and n = k=1 ni,k . Hence, the pairwise comparison number cmp performed i in ri is P|Ai | ni,k n , which usually is much lower than k=1 2 2 . When computing the difference sets for ri , DUD does not need to keep all tuples in memory, but processes the tuples with Ai = vi,k (1 ≤ k ≤ |Ai |) individually. The maintained tuples are compared pairwise and the generated difference sets are stored in set MDS to avoid duplication. However, there still remains one potential problem. If the cardinality of Ai is low or there exists many duplicates for some attribute values, the value of cmpi can be very large. In an extreme case, |Ai | = 1, n2 pairwise comparisons have to be executed. For this reason, DUD does not generate full difference sets with respect to the attributes whose comparison numbers are too large. In this paper, a parameter γ is specified as an upper-bound of comparison numbers. If cmpi ≤ γ, Ai is called attribute of full difference set generation type (abbreviated as attribute of FG type), and cmpi comparisons are performed to generate difference sets. Otherwise, if cmpi > γ, Ai is called attribute of no difference set generation type (abbreviated as attribute of NG type), and DUD does not generate difference sets with respect to Ai specifically. Determination of attributes type. If Ai is of NG type, there is no need to sort r with respect to Ai at the very start actually. We need a determination process with a much lower cost to determine attribute types (FG type or NG type). The number of cmpi is concerned only with the Ai values. Before sorting r and generating difference sets, DUD first decomposes r as m column files L1 (A1 ), L2 (A2 ), . . . , Lm (Am ) [28]. Then Li (1 ≤ i ≤ m) is sorted and the number of cmpi is computed by counting the occurrence number of each distinct value. Note that DUD does not maintain all values of Li in memory but

only keeps a counter for each run to accumulate the value of cmpi . If cmpi ≤ γ, Ai is an attribute of FG type. Otherwise, Ai is an attribute of NG type. In this paper, let SF G be the set of attributes of FG type, and SN G be the set of attributes of NG type. Determination of parameter γ. For DUD, we must determine the parameter γ for its execution. Given ri , the maximum number of possible comparisons is n2 , which is too large obviously. In this paper, γ is specified to 3 × n × log2 n by default, which is smaller than n2 substantially and still large enough to generate useful difference sets. The rationality of determination of γ is verified in the experiments. Supplement of difference sets. The attributes of NG type, whose useful comparison numbers are larger than γ, are skipped in difference set generation. After all useful difference sets are generated with respect to attributes of FG type, DUD performs a uniform sampling operation on r. Let |SN G | be the number of attributes of NG type, the total pairwise comparison number for the sampled tuplespis set to n × |SN G |, and the number of sampled tuples is n × |SN G |. The aim of the above operations is to supplement the difference sets due to the neglect of attributes of NG type with a low enough cost and small enough memory consumption. In phase 1, DUD generates useful difference sets and maintains their minimal form in MDS. Generated difference sets are first collected in a hash set using their bit-set representation, which removes duplicate difference sets. DUD does not insert them into MDS one by one. Instead, minimization is performed in batch: if a collected difference set properly contains another collected difference set, the larger one is removed, so that a difference set is kept only when no proper subset of it remains in the collected set. The initial minimization has worst-case cost O(k 2 ), where k is the number of distinct collected difference sets before minimization. When new difference sets are generated during validation, DUD applies a delta-based minimization procedure: it compares old difference sets with new ones and new difference sets with each other, but does not compare old difference sets among themselves again, since they have already been minimized in the previous iteration. In this way, DUD constructs a hypergraph H(V, E), whose vertex set is the attribute set of the relation schema and whose hyperedge set consists of the minimal difference sets in MDS. Execution process of phase 1. To sum up, the execution process of phase 1 is described as below, whose pseudocode is listed in Algorithm 2. In phase 1, DUD first decomposes the relation instance r into m column files (Line 1 in Algorithm 2), computes the useful comparison number for each column file (Line 2 and Line 3), specifies γ value (Line 4) for determining the attribute types. For each attribute Ai of FG type, DUD sorts r in ascending order of Ai and performs the useful pairwise tuple comparisons to generate difference sets (Line 5 to Line 7). After generating difference sets with respect to all attributes in SF G , DUD executes a randomly uniform sampling on r to supplement the difference sets (Line 8 and Line 9). When phase 1 terminates, DUD builds the initial hypergraph with the generated difference sets as hyperedges (Line 10 and Line 11). On generating difference sets, it is found that the number of

Algorithm 2 BuildInitialHypergraph Input: relation instance r of m attributes Output: The initial hypergraph H 1: Decompose r(A1 , . . . , Am ) into column files L1 , . . . , Lm //Compute the comparison number for each attribute 2: for (i = 1; i ≤ m; i = i + 1) 3: Sort Li with respect to Ai and compute cmpi of Li //Compute the value of γ 4: γ = 3 × n × log2 n //Generate difference sets initially 5: for (i = 1; i ≤ m; i = i + 1) //Current attribute is of FG type 6: if cmpi ≤ γ then 7: Sort r to be ri with respect to Ai and generate difference sets by tuples with equal Ai values //Supplement of difference sets p 8: Randomly sample n × |SN G | tuples 9: Compare samples pairwise and build difference sets //Build initial hypergraph by minimal difference sets 10: Minimize generated difference sets in set MDS 11: Build hypergraph H(V, E) by difference sets in MDS

…

1 2 … 0

2 1 … 0

3 1 … 1

4 0 … 0

5 2 … 1

6 2 … 0

7 2 … 0

8 2 … 1

9 10 11 12 13 14 15 16 17 18 19 20 1 2 1 1 0 1 2 0 1 2 2 2 … … … … … … … … … … … … 1 0 1 1 0 1 1 0 1 1 0 1

0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 …

…

… … … … … … … … … … … … … … … … … … … … 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 . = 20 × log ) 20 = 86 "! ! " #

! 69 ,-

! "

)

(

106 *+

91 *+

94 *+

61 ,-

90 *+

91 *+

Fig. 2. The illustration of determining attribute types.

the generated difference sets is far smaller than the number of total pairwise comparisons. This is verified in the benchmark data sets and real-life data sets, which are utilized in the performance evaluation. Example 3. The execution of phase 1 is illustrated in Figure 2, Figure 3 and Figure 4. The determination of attribute type is depicted in Figure 2. After decomposing and sorting column files, the comparison number for each attribute is

! 1 2 … … 0

2 1 … 0

3 1 … 1

4 0 … 0

5 2 … 1

6 2 … 0

7 2 … 0

8 2 … 1

9 10 11 12 13 14 15 16 17 18 19 20 1 2 1 1 0 1 2 0 1 2 2 2 … … … … … … … … … … … … 1 0 1 1 0 1 1 0 1 1 0 1

! 4 13 16 2 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 2 0 2 0 0 0 1 0 1 1 1 0 0 0 0

3 1 1 1 1 2 1 0 1

9 11 12 14 17 1 1 1 1 1 1 2 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 2 2 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0

$ ℎ

(

)

{

}

5 2 1 1 0 0 0 0 1

6 2 1 1 0 2 0 1 0

7 2 1 1 1 0 0 1 0 '

{

}

{

}

{

}

8 10 15 18 19 20 2 2 2 2 2 2 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 2 1 2 2 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 ((

{

Fig. 3. The illustration of generating difference sets for r1 .

}

{

} {

ℎ

{

} {

} { {

}

{

} {

{

} {

}{

} {

}

} {

}{

}

Fig. 4. The illustration of difference sets in phase 1.

computed. Then the value of γ is set to 861 in the running example. For example, cmp1 = 69 ≤ 86 and A1 is of FG type, cmp2 = 106 > 86 and A2 is of NG type. Since A1 is of FG type, its processing is shown in Figure 3 to generate difference sets. The relation instance r is sorted with respect to A1 , and the difference sets are generated by pairwise comparisons of tuples with equal A1 values in r1 . The difference sets generated for r1 and r5 are illustrated in Figure 4. With supplement of difference sets, DUD generates eight difference sets in total, which is used to build hypergraph for minimal hitting enumeration in phase 2. The built hypergraph is provided in Figure 5. B. Phase 2: enumeration of minimal hitting sets

, ,

Fig. 5. The illustration of execution results of phase 2 on hypergraph H built in phase 1, whose vertices are {A1 , A2 , A3 , A4 , A5 , A6 , A7 , A8 } and hyperedges are {A2 }, {A7 }, {A8 }, {A1 , A3 }, {A1 , A4 }, {A1 , A6 }, {A3 , A5 } and {A4 , A5 }.

minimality condition, the child nodes of o are constructed by adding each element in o.cand. Let A be the ath element (1 ≤ a ≤ |o.cand|) in o.cand, and o.cand(a + 1, . . .) be the elements in o.cand after the ath position. The ath child node clda of o is generated with clda .atts = o.atts ∪ A, clda .cand = o.cand(a + 1, . . .), clda .uncov and clda .crit can be updated by the information in o.uncov and o.crit. The child node clda is added to Q for the following iterations. Pruning strategy. Given current node o, ∀e ∈ o.uncov, since a minimal hitting set should have at least one common element with every hyperedge, any minimal hitting set h including o.atts satisfies h ∩ e ̸= ∅. The possible extension to o.atts should be limited to e ∩ o.cand rather than o.cand. ∀e ∈ o.uncov, the hyperedge em is chosen which minimizes |e ∩ o.cand|. Therefore, only the attributes in em are used to extend o.atts and generate the child nodes of o. DUD maintains the generated minimal hitting sets (i.e., UCC candidates) of phase 2 in STc .

By the built hypergraph H(V, E), DUD enumerates minimal hitting sets in phase 2, utilizing the existing algorithm MMCS [23] (Line 3 of Algorithm 1). For better understanding and completeness of algorithm description, the implementation of MMCS is described below. The enumeration of minimal hitting sets can be treated as breadth-first exploration on a set enumeration tree T [29], assuming that A1 , A2 , . . . , Am already are arranged in lexicographic ordering. Every node in T has four fields: atts, cand, uncov and crit. - The first field atts is the set of attributes maintained by the node, and atts ⊆ V . - The second field cand is an array to maintain the attributes which can be added to atts fields of its child nodes. - The third field uncov is a set of hyperedges which have no common elements with atts, i.e., uncov = {e|e ∈ E, e ∩ atts = ∅}. - The fourth field crit keeps critical hyperedges for each attribute in atts. ∀A ∈ atts, crit(A) = {e|e ∈ E, e ∩ att = A}. This can be implemented as a hash table mapping from single attribute to corresponding critical hyperedges. Initially, the root rt of T is created, with rt.atts = ∅, rt.cand = {A1 , A2 , . . . , Am }, rt.uncov = E and empty crit field. Then rt is added to a queue Q. In each iteration, if Q has no more element, phase 2 terminates. Otherwise, the head o of Q is removed and processed. If o satisfies minimality condition, i.e., o.uncov = ∅ and o.crit(A) ̸= ∅ for ∀A ∈ o.atts, it is proved that o is a minimal hitting set [23]. Otherwise, if o does not satisfy

For issue 1, a better choice is to report true UCCs in candidates without actual validation. An important statement is proved in Theorem IV.1 that helps reduce the number of validated candidates. It is proved that any candidates which contain at least one attribute of FG type are true UCCs definitely. Of course, these candidates do not need validation anymore and can be reported directly.

1 Due to too small scale, γ is set to n × log n in running example 2 provisionally rather than 3 × n × log2 n in this paper.

Theorem IV.1. Given a UCC candidate X, if X contains an attribute Ai of FG type, it must be a UCC.

Example 4. Figure 5 depicts the results of phase 2 on the running example. Given the built hypergraph H in phase 1, phase 2 returns 3 UCC candidates, each of which has at least one common element with every hyperedge. C. Phase 3: validation of UCC candidates Since phase 1 often does not generate complete difference sets, the UCC candidates obtained in phase 2 cannot be guaranteed to be true UCCs and need to be validated. The efficient validation involves two important issues. - Issue 1. How to reduce the number of validated candidates in phase 3. - Issue 2. How to reduce the validation cost for the candidates in phase 3 under limited memory.

Algorithm 3 ValidateByHash Input: the candidate set STc and true UCC set STucc Output: a set ∆DS keeping newly generated difference sets 1: Initialize ∆DS to be an empty set 2: foreach X ∈ STc do 3: if X contains any attributes of FG type then 4: Remove X from STc and put it to STucc 5: if |STc | = 0 then 6: return ∆DS // Current ∆DS is empty // Perform hash-based validation for candidates not directly reported as UCCs // The attribute of NG type in SN G are arranged in the ascending order of maximum run length 7: foreach Aj ∈ SN G do // STpis keeps the pis of conflicting tuples 8: Initialize an empty set STpis , whose elements are sets. 9: Cj = {X|X ∈ STc and Aj ∈ X} and STc = STc \ Cj 10: if (|Cj | = 0) then 11: continue 12: Obtain rj , the relation sorted by Aj ; sort r only if rj has not been materialized. // Let vj,1 ≤ . . . ≤ vj,|Aj | be distinct values of Aj 13: for (k = 1; k ≤ |Aj |; k = k + 1) do 14: Initialize hash table HTX for X ∈ Cj 15: Retrieve each tuple t in rj with Aj = vj,k 16: Maintain (t[X], t) in HTX for X ∈ Cj 17: foreach X ∈ Cj // key is the projection on X and value is a set of tuples with the same projections. 18: foreach (key, value) ∈ HTX do 19: if value.size ≥ 2 then 20: X is an invalid UCC and add value to STpis 21: Perform |value| pairwise comparison, the 2 generated difference sets are inserted ∆DS 22: Put candidates in Cj which are not invalid to STucc // All candidates are validated 23: if (|STc | = 0) then 24: break 25: return ∆DS

{

, {

, ,

}

, ,

}

, ,

Fig. 6. The illustration of directly reporting UCC candidates in the running example.

validated to be non-UCCs because there exists conflict tuples, which are used to generate new difference sets and update the hypergraph for the following operations. The pseudocode of phase 3 is listed in Algorithm 3. Given the UCC candidates STc , ∀X ∈ STc , if ∃Ai ∈ X and Ai is of FG type, X is reported to be a true UCC and removed from STc (Line 2 to Line 4 in Algorithm 3). In this paper, the discovered UCCs are stored in STucc . In this way, the number of candidates to be validated can be reduced significantly based on the following intuition for candidate pruning. At best, all candidates can be reported as true UCCs and the validation process of relatively high cost can be avoided entirely (Line 5 and Line 6). Intuition for candidate pruning. This intuition concerns the candidates initially generated in phase 2, before the pruning by Theorem IV.1 is applied. Many of these candidates may contain at least one FG attribute, and this is why the pruning can reduce the number of candidates to be validated. As stated in Section IV-A, the threshold γ is used to distinguish FG attributes from NG attributes according to the number of pairwise comparisons required for generating useful difference sets. An FG attribute usually has relatively high cardinality, which leads to fewer tuple pairs with equal values on that attribute. Since UCCs are used to uniquely identify tuples, attributes with higher cardinalities are more likely to participate in UCCs. After this pruning step, the remaining validation candidates in STc contain only NG attributes and are handled by hash-based batch validation.

Proof. ∀t1 , t2 ∈ r, there exist two cases for the equality comparison between t1 .Ai and t2 .Ai . If t1 .Ai ̸= t2 .Ai , t1 [X] ̸= t2 [X] naturally since Ai ∈ X. If t1 .Ai = t2 .Ai , according to the execution in phase 1, the tuples with the equal Ai attribute values are compared pairwise, whose generated difference sets do not include Ai . Since X is a minimal hitting set generated in phase 2, it has at least one common element with every hyperedge. The common elements of X with the hyperedge corresponding to difference set generated by comparing t1 and t2 do not include Ai also. It means that t1 and t2 do not have equal value for at least one attribute in X other than Ai , we have t1 [X] ̸= t2 [X]. To sum up, ∀t1 , t2 ∈ r, t1 [X] ̸= t2 [X] in any case, i.e., X is a UCC.

Example 5. Figure 6 illustrates the effect of applying Theorem IV.1 to reduce the number of UCC candidates in the running example. For three UCC candidates generated in phase 2, there are two of them including A1 or A5 , which are of FG type. These candidates can be proved to be true UCCs. Only one candidate is required for validation.

Execution process of phase 3. In phase 3, DUD first reports the true UCCs from candidates by Theorem IV.1. This reduces the number of candidates to be validated. For the remaining validation candidates, the validation process is executed in several iterations. At each iteration, DUD sorts the relation instance with respect to a certain attribute of NG type, and adopts hash-based validation by maintaining a subset of tuples with equal value of the attribute in memory at a time. Note that the validation is executed in batch mode, i.e., several candidates can be validated at the same time. This reduces the validation cost further. The candidates which are validated to be true UCCs are reported directly. Some candidates are

For the validation candidates in STc , the issue 2 comes up. This paper considers disk-resident data under limited memory, and the stripped partition based validation, which is commonly used in the existing algorithms, is inapplicable to DUD. Any data structures containing full data do not work under limited memory when they cannot be held entirely in memory. DUD utilizes hash-based strategy to perform validation on relation instance directly. The hash-based validation strategy is straightforward. Given any UCC candidate X, any collision on a hash table with projection of tuples on X as key invalidates X. The important aspect to consider here is how to achieve the collision checking without maintaining full data in memory.

{

/ ℎ ℎ

(a) Naive approach

ℎ

(

)

ℎ ℎ

ℎ

, 1 2 0 1 1 0 0 1 0

, 2 0 0 1 1 1 0 0 0

, 3 2 1 1 0 0 0 0 1

, 4 2 1 1 0 2 0 1 0

567879 7: 7; 7< 7=

max

ℎ

max

10 11 11 11 12 14

} 5 2 1 1 1 0 0 1 0

6 0 1 0 0 2 0 1 0

7 1 0 1 0 2 0 0 1

8 2 0 0 0 2 0 1 1

9 10 11 12 13 14 15 16 17 18 19 20 0 2 1 1 2 1 2 1 1 1 2 2 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 2 2 2 0 0 1 1 2 1 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 ℎ

ℎ

{ 0,1,1,0,1,0 : {1}, 0,1,1,0,0,0 : {2}, 1,1,0,0,0,1 : {3}, 1,1,0,0,1,0 : {4}, 1,1,1,0,1,0 : {5}, 1,0,0,0,1,0 : {6}, 0,1,0,0,0,1 : {7}, 0,0,0,0,1,1 : {8}, 0,1,0,0,1,0 : {9}, 0,0,0,0,1,0 : {10}}

{ 0,0,1,1,1,0 : {11}, 1,1,1,1,0,1 : {12}, 1, 1, 2, 2, 1, 2 : {23, 24}, 0,1,1,1,1,1 : {14}, 0,1,1,1,0,0 : {15}, 0,0,1,1,1,1 : {16}, 0,0,0,1,1,1 : {17}, 1,0,1,1,0,1 : {19}, 0,1,1,1,0,1 : {20}}

(b) Partial-loading approach Fig. 7. The illustration of loading a subset of tuples for collision checking. (a) Naive approach of loading the entire relation instance r into memory. (b) Partial-loading approach used in DUD, which uses the relation instance rj (i.e., r sorted by attribute Aj ) and loads only the tuples within the current run into memory. Either (a) or (b) is used to load tuples before hash-based collision checking, and DUD adopts (b).

Evidently, given a UCC candidate X, any two tuples which have the same projection on X must have the same value for each constituent attribute of X. In this case, the collision can be checked by retrieving a relation instance, whose tuples are arranged in ascending order of one constituent attribute, and only maintaining the tuples with equal values of the attribute in memory. As illustrated in Figure 7, this reduces the required memory obviously. It is obvious that the validation candidates in STc only contain attributes in SN G , where SN G is the set of attributes of NG type. The validation process of phase 3 is executed in several iterations, each of which deals with an attribute in SN G . The attributes in SN G is accessed in the ascending order of maximum run lengths, i.e., the occurrence number of value that appears most often in an attribute, which are computed in phase 1. Given a candidate X ∈ STc , the sorted relation instance corresponding to any constituent attribute in X can be used to validate X gaining the benefit mentioned above but with varying degrees. The sorted relation instance with the smallest maximum run length is a better choice for validating X, since it normally minimizes the maximum number of tuples with equal attribute value. Let Aj ∈ SN G be the visited attribute in current iteration. The candidates in STc including Aj are kept in a set Cj and removed from STc (Line 9 in Algorithm 3). If Cj is empty, the next attribute in SN G is visited (Line 10 and Line 11). Otherwise, DUD sorts relation instance r in the ascending order of Aj as rj , if rj has not been materialized, and all candidates in Cj are checked simultaneously by retrieving rj once only. Hash-based batch validation by rj . ∀X ∈ Cj , the validation checks whether rj [X] contains duplicates. For candidate X, a hash table HTX is built with the projection of tuples on X as key and a set of tuples as value (Line 14 in Algorithm 3). Given that rj is sorted in ascending order of Aj , and let vj,1 ≤ vj,2 ≤ . . . ≤ vj,|Aj | be the distinct values occurred

Δ?@ = {{ / ,

0 }}

Fig. 8. The illustration of hash-based validation for C6 .

in Aj . Obviously the tuples with Aj = vj,k (1 ≤ k ≤ |Aj |) are arranged consecutively in rj . DUD retrieves the tuples in rj sequentially. Let t be the currently retrieved tuple. The following two cases are processed. - Case 1: t has the same Aj value as the previous tuple. If HTX does not contain an element whose key is t[X], (t[X], {t}) is put to HTX . Otherwise, t is added to the set of tuples corresponding to key t[X]. The latter actually indicates that X is a non-UCC since at least two tuples have the same projection on it. Given that rj is sorted with respect to Aj , the duplicates of projection on X can only exist in the tuples with the same Aj values. - Case 2: t has the greater Aj value than the previous tuple. This means that the following tuples cannot have duplicate projections on X with the preceding tuples. At this point, any values in HTX containing at least two elements are compared pairwise to generate difference sets, which is inserted into ∆DS (Line 18 to Line 21 in Algorithm 3). These tuples with the same projections on X are conflicting tuples. Then HTX is emptied, ready for the following operations. Note that in validation process, DUD utilizes an array, whose size is maximum run length in Aj , to keep the tuples for current run (Aj = vj,k ), and the values in hash table only maintain references to the tuples rather the tuples themselves. When a new attribute value occurs, the array is reused to keep the tuples of next run (Aj = vj,k+1 ). At the end of retrieval, if there does not exist any duplicate projection for candidate X, it is reported to be a UCC and maintained in STucc (Line 22 in Algorithm 3). If any candidates are validated to be non-UCCs, the difference sets in ∆DS are used to update hypergraph H as new hyperedges. Example 6. Figure 8 illustrates the hash-based validation for UCC candidates in the running example. As depicted in Figure 6, the only UCC candidate is {A2 , A3 , A4 , A6 , A7 , A8 }. Since A6 has the smallest maximum run length among SN G , DUD validates the candidate in C6 by sorting r as r6 first. The hash table HTA2 A3 A4 A6 A7 A8 is initialized to perform the collision checking. Due to the sortedness of r6 , the projections of at

, ,

Fig. 9. The illustration of second execution results of phase 2 on updated hypergraph H by adding a new hyperedge {A1 , A5 }.

most 10 tuples are maintained in HTA2 A3 A4 A6 A7 A8 instead of the total 20 tuples. By hash-based validation, the candidate in C6 is found to be non-UCC and two conflicting tuples are maintained in the hash table. The corresponding difference set {A1 , A5 } is generated and maintained in ∆DS . The iteration on SN G continues until STc is empty (Line 23 and Line 24 in Algorithm 3). By now all candidates are validated. If ∆DS is empty, it means all candidates are true UCCs, DUD ends and reports the found UCCs in STucc directly (Line 12 in Algorithm 1). Otherwise, DUD uses the difference sets in ∆DS as newly added hyperedges in H and enters phase 2 again to enumerate minimal hitting sets STc of the updated H (Line 6 to Line 8 in Algorithm 1). The following operation is executed similarly with the difference that the newly generated candidates already discovered to be UCCs in the previous operations should be removed, i.e., STc = STc \ STucc . If |STc | = 0 or all candidates in STc are validated to be true UCCs in phase 3, DUD ends and reports the UCCs in STucc . Example 7. Figure 9 illustrates second execution results of phase 2 on the updated hypergraph H by adding a new hyperedge {A1 , A5 }. Three candidates are generated on the updated H, two of which are included in STucc and removed from the candidate set. The only candidate is {A2 , A3 , A4 , A5 , A6 , A7 , A8 } is validated and reported as a true UCC. The execution of DUD is over. Implementation of the I/O procedure. In phase 1, the relation is first decomposed into m column files, with one read of the relation and one write of the column files. Each column file is sorted to compute cmpi and determine whether attribute Ai is of FG or NG type, sorting single-column files rather than the full relation. For each FG attribute, the relation is sorted by that attribute and scanned to generate full useful difference sets. Random sampling accesses a subset of tuples from the relation to supplement the initial hypergraph. If a file to be sorted exceeds the sorting buffer size, the sort requires TPMMS, with additional sequential reads and writes of temporary files. Otherwise the file is loaded into memory, sorted, and written back to disk without intermediate temporary files. In both cases, the sorted result is materialized as a file on disk rather than kept in memory, so that it can be read by subsequent steps. In phase 3, candidates are grouped by NG attribute into

batches Cj , and one scan of the relation sorted by Aj validates all candidates in Cj together, rather than scanning the relation separately for each candidate. Re-entering phase 2 after updating the hypergraph does not access the relation at all, since MMCS operates only on H. If phase 3 is invoked again, NG attributes are visited in the same ascending order of maximum run length. Only those with a non-empty Cj trigger a scan of the sorted relation. If the sorted relation was already materialized in an earlier iteration, it is reused rather than re-sorted. In our experiments, phase 3 is invoked at most twice, and the proportion of candidates reported as true UCCs without validation often exceeds 90%, so few NG attributes ever require sorting. Relation to direct validation in HyFD. The batch validation strategy of DUD is related in spirit to the direct validation procedure of HyFD [25], which also validates multiple dependency candidates together by using a PLI of an LHS attribute with many small clusters and mapping LHS clusters to RHS clusters. This is similar in purpose to the use of an NG attribute with a small maximum run length in DUD to reduce the number of tuples kept in memory. However, the validation of HyFD relies on PLIs and pliRecords built during preprocessing and held in memory, whereas DUD does not maintain such global PLI-based structures: it scans the relation sorted by the chosen NG attribute directly from disk and keeps only the tuples of the current run in memory. D. The correctness of DUD This part provides the proof for the correctness of DUD algorithm. Let HA (V, EA ) be the hypergraph whose vertices are attributes of relation schema and hyperedges are the difference sets generated by all pairwise tuple comparisons. Obviously, the minimal hitting sets in HA are the minimal UCCs surely. Any hypergraph H(V, E) used in DUD actually is a spanning subgraph of HA [30], where E ⊆ EA . Theorem IV.2. Given HA (V, EA ) and its spanning subgraph H(V, E), ∀hA ∈ T r(HA ), ∃h ∈ T r(H), hA ⊇ h. Proof. According to definition of minimal hitting sets, ∀hA ∈ T r(HA ), it satisfies: ∀eA ∈ EA , hA ∩ eA ̸= ∅. We can treat the requirements above to be satisfied as the constraints for hA . Obviously, if ∃eA ∈ EA , ∃p ∈ P(V ), and eA ∩ p = ∅, an element in eA has to be added into p to make it be minimal hitting set. In other words, any minimal hitting set is expanded from empty set to have at least one common element with every hypergraph. Since E ⊆ EA , any minimal hitting set h enumerated in H can be seen in intermediate stage of the enumeration process in HA . To sum up, ∀hA ∈ T r(HA ), there exists an element in T r(H), which is generated in the middle of expansion process, and hA ⊇ h. Theorem IV.3. Given HA (V, EA ) and its spanning subgraph H(V, E), ∀h ∈ T r(H), ∃hA ∈ T r(HA ), h ⊆ hA . Proof. With the similar argument of Theorem IV.2, ∀h ∈ H, if hyperedges in EA \ E are added to H, h can be expanded to be a minimal hitting set hA ∈ T r(HA ), i.e., h ⊆ hA .

∅

Fig. 10. The illustration of correspondence between minimal hitting sets in hypergraph used by DUD and complete hypergraph. The attribute sets underlined with red line are final minimal hitting sets and those underlined with green double line are minimal hitting sets in hypergraph used by DUD.

Combining Theorem IV.2 and Theorem IV.3, every minimal hitting set in HA corresponds to a minimal hitting set in H, and every minimal hitting set in H has a corresponding final minimal hitting set in HA , which is illustrated in Figure 10. Theorem IV.4 proves the correctness of DUD. Theorem IV.4. DUD discovers the true UCCs correctly. Proof. Given hypergraph H used by DUD, ∀h ∈ T r(H), as proved in Theorem IV.3, ∃hA ∈ T r(HA ), h ⊆ hA . If h = hA , it will be reported as true UCCs either by Theorem IV.1 or hash-based validation. If h ⊂ hA , since hA is a minimal hitting set of HA , i.e., minimal UCC in relation instance r, h is a non-UCC and the validation process for h can find conflicting tuples, which have equal projections on h. At least one hyperedge enew will be added to H, which excludes attributes in h. In the next execution of phase 2, DUD enumerates the minimal hitting sets on the updated H. For h in the current enumeration, h should have at least one element with enew and at least one more attribute in hA \ h can be expanded to h. The expansion can be continued until h = hA . This guarantees that discovered UCCs in DUD are true UCCs. As proved in Theorem IV.2, ∀hA ∈ T r(HA ), ∃h ∈ T r(H), hA ⊇ h, this actually guarantees that every true UCC will be discovered by DUD. To sum up, DUD discovers the true UCCs correctly. E. Cost analysis This part analyzes the time complexity of DUD. Three phases are discussed individually and then combined to get the overall complexity. In phase 1, the execution of DUD consists of several operations sequentially: decomposing relation instance, sorting column files and computing γ, sorting relation instances and generating difference sets with respect to attributes of FG type, supplement of difference sets by random sampling. Given that γ = 3 × n × log2 n, DUD generates difference sets within O(m × n × log2 n) time. And the sorting operation also has a O(m × n × log2 n) time complexity. The other operations in phase 1 are of linear complexity. Therefore, the time complexity of phase 1 is O(m × n × log2 n). The execution of phase 2 is a breadth-first exploration in set enumeration tree T of m attributes with the specified pruning operation. It is proved that given hypergraph H(V, E),

MMCS enumerates minimal hitting sets within O(∥E∥) for current visited node in T , where ∥E∥ is the sum of size of hyperedges in E [23]. Let a be maximum cardinality of any minimalPhitting sets, the number of visited nodes in T a is at mostP i=0 mi . The time complexity of phase 2 is a O(∥E∥ × i=0 mi ). Phase 3 involves sorting operations with respect to attributes of NG type, scans the sorted relation instances sequentially and checks collisions, where the new difference sets are generated by comparing conflicting tuples pairwise. Let c be the maximum distinct value number in attributes of NG type, and d be the maximum number of duplicate projections on candidates in any run. The time complexity of P phase 3 is a O(m × n × log2 n + m × c × d2 × (1 − Ppru ) × i=0 mi ). Here, Ppru is the proportion of candidates generated in phase 2 which can be reported as true UCCs without validation. Let b be the number of invocation of phase 3. Overall, taking into account 2n+b× phases, DUD has a O(b×m×n×log Pa three Pa ∥E∥× i=0 mi +b×m×c×d2 ×(1−Ppru )× i=0 mi ) time complexity. It is shown in [13] that the enumeration of minimal hitting sets normally runs fast on hypergraphs stemming from real-life data. This is also verified in the experiments that on all used real-life data sets, maximum size of UCCs is 12, and maximum number of minimal difference sets are 2649. The execution time of phase 2 normally is dominated by other two phases on real-life data sets. The invocation number of phase 3 is rather small, at most 2 in the experiments. The number of d usually is very small, since the validated candidates are close to actual UCCs, and they only have a small number of duplicate projection values. Besides, the value of Ppru often is greater than 90% and even up to 100%. On real-life data sets, the first factor O(b × m × n × log2 n) is the dominant part in overall time complexity of DUD. V. E XPERIMENTAL EVALUATION This section evaluates the performance of DUD, which is implemented in Java with jdk-21 windows-x64. The experiments are run on DELL OptiPlex 7010MT Workstation (Intel(R) Core(TM) i9-13900 CPU @ 2.00GHz (24 cores) + 32G memory + 64bit windows 11 + 4T HDD). The performance of DUD is evaluated against HPIValid, which is the state-of-the-art UCC discovery algorithm and is reported to be orders of magnitude faster than related work with a much

2 https://www.tpc.org/tpch/ 3 http://archive.ics.uci.edu/ 4 https://www.kaggle.com/

memory requirement (GB)

smaller memory footprint [8]. We reproduce HPIValid in Java according to the implementation in [8]. The hash tables and sets involved in the execution utilize HashMap and HashSet in the Java.util package. The sampling exponent is set to 0.3, which is proved to be a good choice for HPIValid [8]. In the experiments, we evaluate the performance of DUD on synthetic data sets and real-life data sets. The synthetic data sets (the lineitem table) are generated by TPC-H Benchmark2 , while the real-life data sets are downloaded from UCI Machine Learning Repository3 and Kaggle4 to evaluate the performance of DUD in the practical applications. In the experiments, 24GB memory (32GB in total) is allocated for the algorithm execution. The -Xmx parameter is used to specify the maximum memory an algorithm can use. Every data set is preprocessed in the same way before being given to DUD or HPIValid. For each attribute, values are read as strings, and distinct values are collected and mapped to consecutive integer IDs, which then replace the original values. Since UCC discovery only requires checking whether two values on an attribute are equal, this loses no information needed by either algorithm. The resulting table is stored on disk with each attribute value encoded as a fixed-length 8-byte integer, the format read by both DUD and HPIValid throughout the experiments. The parameters of the lineitem table are described in Table II, whose attribute number is 16 and tuple numbers are a multiple of scale factor (SF), i.e., SF × 6,000,000 approximately. Given SF = 10, Table III provides the details of the lineitem table, including cardinalities, full useful comparison numbers and types of attributes. The cost of computing full useful difference sets with respect to some attributes is prohibitively expensive, as listed in Table III. Here, we only provide the comparison information about the lineitem table with SF = 10, and the lineitem tables of other SF values have the similar situation. In the experiments, given γ = 3×n×log2 n, the first, second, sixth and sixteenth attributes in the lineitem table are of FG type, and other attributes are of NG type. It is worth noting that the number of distinct difference sets generated for each attribute is significantly less than the number of full useful pairwise comparisons. For example, for the sixth attribute in Table III, the number of full useful pairwise comparisons is 1,853,382,718, while only 1965 distinct difference sets are generated. That is to say, about 106 pairwise comparisons can generate a new difference set for the sixth attribute. Note that number of distinct difference sets with respect to the specified attribute in Table III is not the number of minimal difference sets, but just the number of difference sets after deduplication. Given SF = 10, the number of minimal difference sets generated with respect to four attributes of FG type is 198, which is much smaller than that of distinct difference sets. NULL semantics. Some real-life data sets have incomplete information, and a null value is used to indicate a missing or unknown value. This paper considers the commonly

20 16 HPIValid DUD

12 8 4 12

scale factor

Fig. 11. Memory space requirement.

used null semantics (NULL-EQ), which treats null values as identical and not equal to any non-null value [31], [8]. We adopt NULL-EQ to keep the UCC definition consistent with HPIValid and other UCC discovery studies, enabling a direct comparison under the same semantics. Under SQLstyle uniqueness semantics, where NULL values are treated as distinct, tuples with NULL values on an attribute would no longer be grouped into the same equivalence class, generally reducing cmpi and the size of validation batches in phase 3. We have not implemented or evaluated DUD under this alternative semantics. TABLE II PARAMETER INFORMATION OF LINEITEM IN TPC-H, WHERE ATTRIBUTE NUMBER IS 16, γ = 3 × n × log2 n, SF MEANS SCALE FACTOR AND UCCN UM IS THE NUMBER OF DISCOVERED UCC S .

SF 1 2 5 10 15 20

TupleNum 6,001,215 11,997,996 29,999,795 59,986,052 89,987,373 119,994,608

γ value 405,384,891 846,445,064 2,235,445,161 4,649,781,104 7,133,268,257 9,661,387,823

UCCNum 390 404 364 342 318 358

TABLE III C ARDINALITIES AND TYPES OF ATTRIBUTES IN LINEITEM , WHERE SF = 10 AND γ = 4, 649, 781, 104, DSN IS THE NUMBER OF DISTINCT DIFFERENCE SETS GENERATED WITH RESPECT TO THE SPECIFIED ATTRIBUTE .

Attr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Cardinality 15,000,000 2,000,000 100,000 7 50 1,351,462 11 9 3 2 2,526 2,466 2,555 4 7 34,378,943

TotalComparison 119,948,344 898,711,177 17,991,006,982 321,330,030,852,817 35,983,264,280,805 1,853,382,718 163,560,278,023,276 199,907,039,167,641 680,505,080,028,315 899,581,606,017,474 735,235,731,620 741,466,394,917 734,875,394,017 449,790,785,523,119 257,023,299,207,497 2,270,982,389

Type FG FG NG NG NG FG NG NG NG NG NG NG NG NG NG FG

DSN 757 1719 1965 1555

Execution time (s)

100000

TABLE IV E XECUTION TIME IN SECONDS OF THREE PHASES OF DUD WITH DIFFERENT FACTORS , WHICH IS THE MULTIPLES OF n × log2 n

DUD

10000

1000 1 3 11 13

474 475

Factor 1 3 13 475

Phase1 610.55 1217.01 2130.65 64123.34

Phase 2 0.09 0.11 0.11 0.04

Phase 3 7571.42 811.69 342.34 0.004

SF G 1,2 1,2,6,16 1,2,3,6,16 1,2,3,6,11,13,16

chosen factor

Fig. 12. Different factor selections for γ value, the experiments are executed on the lineitem table of SF = 10.

A. Memory Space Requirement This part illustrates the memory space required for HPIValid. Given the lineitem tables of SF = 1, 2, 5, 10, 15 and 20, Figure 11 illustrates the memory consumption under the space limit 24GB. It is shown that HPIValid requires about 2.40GB, 5.14GB and 12.21GB for lineitem tables with SF = 1, 2 and 5 respectively, and runs out of memory for SF ≥ 10. “OM” in Figure 11 indicates out of memory. In our implemented HPIValid, the record-ID-to-cluster-ID inverse mapping required for validation is represented by the same primitive int[][] array used to store the cluster ID of each tuple on each attribute, rather than a separate hash table. The array is built during pre-processing and used both for difference-set computation and for validation. The reported memory measurements are obtained by first triggering garbage collection and then computing the difference between total and free JVM heap memory. Without this step, objects that are no longer used but have not yet been collected would still appear as used memory, making the reported number higher than the actual memory in use. To avoid triggering garbage collection too often, it is only performed when the run is configured to report memory consumption, and only at points where heap usage exceeds the highest value recorded so far. For comparison, the memory space requirement for DUD also is depicted in Figure 11. For DUD, it only needs to sort the column files and relation instance, keep the difference sets, build the hypergraph, maintain tuples in each run and the hash tables which store projections on the UCC candidates for the tuples with equal attribute values to check duplicates. These operations are executed sequentially and independently. Hence, DUD has a lower memory overhead, less than 8GB memory at SF ≤ 20. In the experiments, we limit the maximum size of each sorted partition to be one quarter of the allocated memory. Since the sorting operation occupies the largest memory space in the execution, the memory required for sorting remains bounded on data sets of larger scale. The remaining variation in memory consumption of DUD across different SF values comes from data-dependent factors including the size of difference sets, the candidate set, and the hash tables used during validation. We discuss this issue further in Section V-G.

B. Factor selection of γ value In this paper, DUD uses 3×n×log2 n as γ value. The choice of n × log2 n is relatively straightforward since its growing rate is substantially lower than O(n2 ), which is the upperbound of pairwise comparison number. The choice of factor 3 is explained in this part through experimental verification on the lineitem table of SF = 10. The selected factors include 1, 3, 11, 13, 474 and 475, which comprehensively reflects the different cases for DUD execution. As illustrated in Figure 12, the execution time of DUD first decreases, next remains unchanged, then increases slightly and remains unchanged again, last shows a rapid growth. The time decomposition of three phases for different factors is listed in Table IV. As we expect, the execution time of phase 2 is negligible in the experiments. When the factor is lower, fewer attributes are of FG type. In the case, phase 1 terminates quickly, but phase 3 needs a longer time to validate the candidates because the pruning effect of Theorem IV.1 declines. On the contrary, when the factor is higher, more attributes are of FG type. Of course, phase 1 may require a much longer time to terminate, but phase 3 may end quickly. It is also shown that the execution time of DUD remains unchanged across a range of selected factors. This can be explained that, the required full useful pairwise comparison numbers have relatively large gaps for different attributes. If the γ values for the selected factors lie in the same gap, they do not affect the execution of DUD. For example, when the factor is chosen in [3, 11], there are four attributes of FG type. Taken together, when factor for γ value is set to 3, the overall performance of DUD does the best in Figure 12, and γ is set to 3 × n × log2 n in the experiments. TABLE V T IME DECOMPOSITION OF PHASE 1 IN EXPERIMENT 1, WHERE “D ECOM ” IS THE OPERATION TO DECOMPOSE ROW- TABLE INTO COLUMN FILES , “D ET T YPE ” IS THE OPERATION TO SORT COLUMN FILES , COMPUTE γ VALUE AND DETERMINE ATTRIBUTE TYPE , “S ORT ” IS THE OPERATION TO SORT RELATION INSTANCE WITH RESPECT TO ATTRIBUTES OF FG TYPE , “G EN DS” IS THE OPERATION TO GENERATE FULL USEFUL DIFFERENCE SETS WITH RESPECT TO ATTRIBUTES OF FG TYPE , “S UPPLE ” IS THE OPERATION TO SAMPLE RELATION INSTANCE TO SUPPLEMENT THE DIFFERENCE SETS .

SF 1 2 5 10 15 20

Decom 8.527 13.994 81.433 232.753 304.975 374.24

DetType 15.817 38.596 51.39 102.72 159.96 219.773

Sort 23.272 62.855 133.468 545.702 888.105 1189.126

GenDS 11.525 39.699 74.347 266.968 526.109 815.548

Supple 3.433 7.399 17.12 33.269 49.115 65.391

4000 3500 3000 2500 2000 1500 1000 500 0

3000 Execution time (s)

Execution time (s)

HPIValid DUD 12

phase1 phase2 phase3

2500 2000 1500 1000 500 0

scale factor

HPIValid DUD TableSize

1x1011 1x1010 1x109 HPIValid phase1(FG) phase1(supple) phase3

1x108 7

1x10

1x106 100000 12

scale factor

(d) Pairwise comparison 1x109

550 500 450 400 350 300 250 200 150 100 50

1x108 Tuple number

Candidate number

(b) Time of three phases pairwise comparison number

retrieved byte number (109)

(a) Execution time 500 450 400 350 300 250 200 150 100 50 0

scale factor

Total Validate DirectRep HPIValid UCC

1x10

LargestRunLen TotalTupNum

1x106 100000 10000 1000

scale factor

(e) UCC candidate number

scale factor

(f) Maintained tuple number

Fig. 13. The illustration of varying tuple number.

C. Experiment 1: effect of varying tuple numbers Experiment 1 evaluates the performance of DUD on the lineitem tables of SF = 1, 2, 5, 10, 15 and 20, respectively. Since the memory space required by HPIValid exceeds the allocated memory capacity for SF ≥ 10, experiment 1 reports the experimental results of HPIValid with SF = 1, 2 and 5. As shown in Figure 13(a), with a greater value of SF, execution time of DUD increases gradually, but with a much lower growing trend compared with HPIValid. The decomposition of execution times of three phases is reported in Figure 13(b), and the further decomposition of phase 1 is listed in Table V. By the reported results, DUD runs faster than HPIValid on the lineitem table of SF ≤ 5, with speedups ranging from 3.7× at SF = 1 to 6.0× at SF = 5. The significant speedup is attributed to several factors. Firstly, through sorting primitive, DUD determines the attributes of FG type and builds the useful difference sets with a relatively low cost in phase 1. Furthermore, candidate pruning and hash-based batch validation in DUD go quite a long way. Most of candidates can be reported as true UCCs directly without validation, and several candidates can be verified in one iteration. As shown in Figure 13(e), about 90% candidates generated by phase 2 are removed from validation since they are proved to be UCC by Theorem IV.1. This reduces the validation cost significantly. Just as we anticipate, the execution cost of phase 2, i.e., minimal hitting set enumeration, is very low, less than 0.2s in experiment 1. This also verifies rationality of repeatedly calling minimal hitting set enumeration to solve the problem incurred by possible partial generation of difference sets. As shown in Figure 13(c), DUD retrieves one order of

magnitude times more data than the original table. It is interesting to find that high cost of memory computation often exceeds the cost of multiple sequential scans on disk. The I/O procedure of DUD is detailed in Section IV. In this paper, sorting is treated as an individual operation, which sorts the input file to output sorted file, and the following operation retrieves the outputted sorted file directly. Although this increases the involved I/O cost, it simplifies the algorithm execution. Due to the enough number of the computed difference sets, the generated UCC candidates are true UCCs or are close to true UCCs, and the latter only have a small number of duplicate projection values. The required numbers of pairwise comparisons are illustrated in Figure 13(d). The pairwise comparison number in phase 3 is rather low compared with that in phase 1, this also indicates the number of duplicate projection values in phase 3 is very low. As illustrated in Figure 13(f), the maximum number of tuples maintained in validation at a time is three orders of magnitude fewer than total tuple number. Even at SF = 20, the lineitem table has 119,994,608 tuples and only at most 50,554 tuples are maintained in memory for validation at a time. For SF = 1, 2 and 5, the pairwise comparison numbers of HPIValid are reported in Figure 13(d). Obviously, the total comparison number of DUD is much larger than that of HPIValid. The overwhelming majority of pairwise comparisons of DUD are executed in phase 1, i.e., generating all useful difference sets with respect to attributes of FG type and supplement of difference by sampling. When performed on data set of small and medium scale, HPIValid has a lower I/O cost than DUD and a less pairwise computation number. However, it still runs several times slower than DUD at SF = 1, 2 and 5. This can be explained for a variety of reasons. Firstly, the less pairwise comparison number does not mean a lower computation cost, but means a small number of duplicate projections on the candidates. Secondly, HPIValid validates each candidate via stripped partitions, whose cost is nontrivial, while DUD adopts a batch validation to check candidates in single validation process. Thirdly, HPIValid has to validate much more candidates than DUD, as shown in Figure 13(e), since it lacks a candidate pruning operation as in DUD. D. Experiment 2: effect of varying attribute numbers Experiment 2 evaluates the performance of DUD on the lineitem tables of SF = 10 with the first 4, 7, 10, 13 and 16 attributes, respectively. Since HPIValid runs out of memory for attribute numbers of 10, 13 and 16, the experimental results of HPIValid are only reported for attribute numbers of 4 and 7. Figure 14(a) illustrates the execution time of DUD in experiment 2. It is interesting to note that when attribute number is no greater than 10, DUD does not invoke hashbased validation at all. The reason is that, in such cases, all UCC candidates generated in phase 2 contain at least one attribute of FG type, and are proved to be true UCC according to Theorem IV.1. Thus, no further validation is required for

2200 2000 1800 1600 1400 1200 1000 800 600 400 200 0

1400

HPIValid DUD

execution time (s)

Execution time (s)

1000 800

E. Experiment 3: the real-life data sets

600 400 200 0

attribute number

HPIValid DUD TableSize

200 150 100 50 0 7

1x109 1x108

HPIValid phase1(FG) phase1(supple) phase3

1x107 1x106 100000 10000 4

attribute number

(d) Pairwise comparison 1x108

Total Validate DirectRep HPIValid UCC

tuple number

candidate number

1x1010

attribute number

400 350 300 250 200 150 100 50 0

(b) Time of three phases pairwise comparison number

retrieved byte number (109)

250

attribute number

(a) Execution time

no more than 10.

phase1 phase2 phase3

1200

1x10

LargestRun TotalTupNum

1x106 100000 10000

attribute number

(e) UCC candidate number

attribute number

(f) Maintained tuple number

Fig. 14. The illustration of varying attribute number.

these candidates. This is a great advantage of DUD. For the data sets whose UCC candidates contain attributes of FG type, the UCCs can be discovered quickly, since phase 3 is not invoked at all and the hash-based validation does not need to be executed. This also is verified in Figure 14(b), Figure 14(c) and Figure 14(d). As shown in Figure 14(a), HPIValid completes for attribute numbers of 4 and 7, but runs out of memory for larger attribute numbers. When m = 4, HPIValid runs faster than DUD (88.70s vs. 113.86s). The PLI-based structures fit within the allocated memory, so HPIValid can validate candidates directly from memory without the disk-based sorting cost that DUD incurs. When m = 7, the two algorithms take similar time (281.67s vs. 284.79s). For m ≥ 10, HPIValid runs out of memory while DUD still completes. When attribute number increases from 10 to 13, there exist some UCC candidates only consisting of attributes of NG type, the execution time increases abruptly since the validation operation has to be performed. As shown in Figure 14(e), with more attributes involved, the numbers of total candidates and true UCCs increase quickly. Correspondingly, more candidates are reported as true UCCs directly without validation, and the number of candidates to be validated shows a smaller increase trend. The maximum number of tuples that are maintained in validation at a time is illustrated in Figure 14(f). Compared with total tuples, DUD only needs to keep a much small number of tuples in memory. The missing points for number of maintained tuples in Figure 14(f) are due to the fact that DUD does not invoke validation when the attribute number is

Experiment 3 evaluates the performance of DUD on reallife data sets, which range from small scale (24K tuples) to large scale (179M tuples), from low dimension (5) to high dimension (115), representing the practical data characteristics comprehensively. The execution results of the algorithms are reported in Table VI, where IOtimes is the ratio of the retrieved byte number of DUD over original table size, breakdown shows the time proportions of three phases for DUD, |SF G | is the number of attributes of FG type. On the real-life data sets whose tuple numbers are less than 106 , HPIValid only needs to retrieve data sets once, while DUD often involves an order of magnitude higher I/O cost. The I/O cost of a sorting operation is at least twice the size of the relation. When data scale is small and the stripped partitions fit in memory, HPIValid benefits from both lower I/O cost and efficient in-memory validation, and tends to run faster than DUD. DUD performs better when the number of attributes is large, as seen on atom (m = 31) and struct sheet range (m = 32). On some larger real-life data sets where the PLI-based structures of HPIValid fit within the allocated memory, HPIValid tends to outperform DUD, as seen on nycparkticket2015, hhar, phaccelerometer, foursquare spots, ditag feature and sdss. On these data sets, DUD incurs the full cost of disk-based sorting and scanning, while HPIValid validates candidates directly from its in-memory structures. On pamap2 (m = 54), hepmass (m = 29), higgs (m = 29), susy (m = 19) and ht sensor (m = 12), HPIValid still completes but DUD runs faster. This is mainly because DUD prunes a large proportion of candidates on these data sets; the reduction in validation cost outweighs the cost of disk-based sorting and scanning. When the PLI-based structures exceed the memory budget, HPIValid runs out of memory while DUD still completes. This is the case for ssdp flood (m = 115), ids2018 (m = 84), ghtorrent (n = 73.7M) and hi-large trans (n = 179.7M). DUD is not uniformly faster than HPIValid. Its advantage is most significant on data sets where PLI-based structures are too large to fit in memory. The last column Ppru in Table VI measures the proportion of the UCC candidates which are reported as true UCCs without validation. Obviously, all generated UCC candidates can be declared as true UCCs in the very great majority of cases. A notable exception is the prsa data set , which only reports one UCC candidate as true UCC without validation. On prsa, the first attribute has much greater cardinality (35064) than the maximum cardinality (2028) of other attributes. Thus cmp1 on prsa is much smaller than cmpi (2 ≤ i ≤ 18). Given γ value, only the first attribute is of FG type. For prsa, {A1 , A18 } is the only UCC containing A1 , and other UCCs have to be validated since they do not include A1 . This also explains the so large proportion of phase 3 for prsa execution. In a few rare cases, including three real-life data sets (NBA2023Shots, IDS2018 and HI-Large Trans), we have min cmpi > 3 × n × log2 n, there is no attribute of FG type 1≤i≤m

TABLE VI E XPERIMENTAL RESULTS ON REAL - LIFE DATA SETS ( RUNTIME IN SECONDS FOR HPIVALID AND DUD). T HE BOLDFACED RESULTS FOR DUD MEAN THAT THE PERFORMANCE OF DUD ON THESE DATA SETS IS BETTER THAN HPIVALID . B REAKDOWN SHOWS THE PROPORTIONS OF THREE PHASES OF DUD, WHERE YELLOW, GREEN AND RED REGIONS CORRESPOND TO PHASE 1, PHASE 2 AND PHASE 3, RESPECTIVELY. |SF G | IS THE NUMBER OF ATTRIBUTES OF FG TYPE . OM IS THE ABBREVIATION OF O UT O F M EMORY E RROR . S OME ORIGINAL DATA SETS ( INCLUDING BARCRAWL , HIGGS , SDSS ) CONTAIN DUPLICATE TUPLES AND WE PRE - PROCESS THEM BY DEDUPLICATION .

Data set n m UCCs HPIValid DUD Breakdown(%) IOtimes |SF G | Ppru reflns 24,769 37 17 0.26 0.65 16.89 4 1.0 26,139 46 3 0.25 1.29 13.91 3 1.0 entytysrcgen atom 160,000 31 691 16.61 5.73 31.87 5 0.712 sg bioentry 184,292 9 3 0.31 0.59 16.6 4 1.0 rangequeriesaggr 200,000 8 19 0.66 0.84 28.55 8 1.0 nba2023shots 217,207 26 64 3.48 14.33 16.85 3 0.388 sgemm product 241,600 18 36 2.12 2.07 17.78 4 0.972 prsa 420,768 18 378 22.09 38.64 23.78 1 0.001 onlineretail 536,641 8 1 0.69 1.68 10.55 2 1.0 struct sheet range 664,128 32 167 16.72 13.63 49.87 15 1.0 ht sensor 928,991 12 147 14.674 8.96 37.69 11 1.0 foursquare spots 957,462 15 1 2.03 3.51 16.75 4 1.0 2,259,597 8 1 2.49 2.37 7.55 1 1.0 har70plus bitcoinheist 2,916,697 10 2 5.67 4.51 7.63 1 1.0 pamap2 3,850,505 54 1206 838.83 704.21 115.92 37 1.0 ditag feature 3,960,124 13 3 9.72 28.95 16.71 4 1.0 4,077,266 115 392 OM 1956.1 169.96 55 1.0 ssdp flood susy 5,000,000 19 746 294.54 148.76 55.8 17 1.0 6,949,386 8 26 40.88 54.41 28.55 8 1.0 sdss ids2018 7,948,746 84 48506 OM 1094.5 10.95 2 1.0 nycparkticket2015 9,711,094 40 1 51.98 265.46 10.91 2 1.0 hepmass 10,500,000 29 1889 1030.78 682.87 67.86 21 1.0 10,721,302 29 8121 11172.91 3019.6 55.86 8 0.707 higgs phaccelerometer 13,062,475 10 12 39.64 67.55 13.63 3 1.0 barcrawl 14,057,535 5 1 19.32 12.37 7.33 1 1.0 26,995,107 10 7 84.78 165.71 13.63 3 1.0 hhar ghtorrent 73,749,949 11 2 OM 646.77 10.67 1 0.5 hi-large trans 179,702,079 11 3 OM 6447.6 19.66 3 1.0

if γ is set to 3 × n × log2 n, and γ is set to 5 × min cmpi . 1≤i≤m

In a word, parameter γ is determined for DUD to guarantee at least one attribute of FG type with a relative low cost. It should be noted that, all factors for n × log2 n in the three data sets are greater than 3 (default factor) and are no more than 30. The computed γ value is still in the same magnitude of the default γ value (3 × n × log2 n). F. Experiment 4: effect of different memory capacity Given SF = 10 and m = 16, experiment 4 evaluates the performance of DUD under different allocated memory capacity, from 64MB to 24GB. The buffer size used for sorting is set to one fourth of the allocated memory capacity (i.e., 6GB when the JVM heap is 24GB). Files within this size are loaded into memory, sorted, and written back to disk without intermediate temporary files, while larger files are sorted using TPMMS. This also verifies the usability of DUD under very small memory allocation. As illustrated in Figure 15(a), the execution time of DUD increases gradually when the allocated memory capacity decreases from 24GB to 64MB. It should be noted that the execution time under different memory capacity actually varies within a small range. This shows the advantages of DUD that it can run on a very small memory capacity and its performance does not seriously degenerate. The gradual increase of the execution time in experiment 4 with smaller memory capacity

can be explained by more I/O cost. A smaller memory capacity makes sort operation generate a larger number of sorted partitions and change from in-memory sorting to two-pass multi-way merge sort when file to sort cannot fit in the sorting buffer. The latter incurs a higher I/O cost, as illustrated in Figure 15(b). The memory requirement of DUD is illustrated in Figure 15(c), the actual memory consumption for DUD always lies in the range the allocated maximum capacity, and DUD can discover UCCs on disk-resident data with a very small memory capacity. G. Discussion The experimental evaluation in this section helps us understand DUD more comprehensively and clearly. Evidently, the biggest strength for DUD is its ability to deal with large-scale disk-resident data under limited memory, while the existing algorithms cannot achieve this goal. This reflects a trade-off between memory and I/O: DUD avoids maintaining global inmemory structures such as stripped partitions, at the cost of additional disk-based sorting and sequential scans. When PLIbased structures of HPIValid fit within the memory budget, the two algorithms are roughly comparable, with each winning on roughly half the data sets, as shown in Experiment 3. This also validates the beneficial effect of candidate pruning and hash-based batch validation. For DUD, the ideal case is that all UCC candidates contain at least one attribute of FG type.

DUD

100

1000

10000

allocated memory capacity (M)

(a) Execution time

2.52 2.5 2.48 2.46 2.44 2.42 2.4 2.38 2.36 2.34

DUD

100

1000

10000

Memory requirement (G)

2180 2160 2140 2120 2100 2080 2060 2040 2020 2000

retrieved byte number (1011)

Execution time (s)

used allocated

20 15 10 5 0 100

1000

10000

allocated memory capacity (M)

(b) Memory requirement

Fig. 15. The illustration of different memory capacity.

In this case, all candidates are true UCCs definitely and do not need to be validated. The execution of DUD consists of three phases, and the execution time of phase 2 can be negligible. The performance of DUD actually is a trade-off between phase 1 and phase 3, which is adjusted by the different factor selection of γ value. The smaller γ value leads to a fast execution of phase 1 but maybe a long execution of phase 3. The greater γ value leads to the opposite case. The default factor 3 in this paper is empirically shown to be the optimal choice, as described in Section V-B. The memory consumption of DUD during validation depends on the maximum run length of the NG attribute used for validation, namely the largest number of tuples sharing the same value on that attribute. This quantity is data-dependent and cannot be bounded by a fixed fraction of the relation size in general. For each candidate, DUD uses the NG attribute with the smallest maximum run length among its constituent NG attributes for validation, since NG attributes are visited in ascending order of maximum run length. A nearly constant attribute is therefore not used when another NG attribute of the same candidate yields smaller runs. A pathological case may still arise when all NG attributes in a candidate have large maximum run lengths. In that case, a validation batch can be large, and DUD does not provide a formal worst-case memory bound. In our experiments, the number of tuples maintained in memory during validation is several orders of magnitude smaller than the total tuple count: 50,554 out of 119,994,608 tuples on lineitem SF = 20 (Figure 13(f)). DUD also has limitations. When the number of attributes is large or the UCC result set is very large, the costs of candidate management and validation may increase substantially, particularly when few attributes are of FG type and the pruning effect is limited. In such cases, if the PLI-based structures of HPIValid still fit within the memory budget, HPIValid may run faster than DUD because it can benefit from inmemory PLI-based validation, whereas DUD still pays the cost of disk-based sorting and sequential scans. Therefore, we do not claim that DUD dominates in-memory PLI-based algorithms on all high-dimensional or large-result-set data sets. Its main advantage lies in memory-constrained settings where maintaining global PLI-based structures becomes difficult, and the pruning by Theorem IV.1 further contributes when it can substantially reduce validation cost. On data sets with highly imbalanced attribute cardinalities, such as prsa, only a small number of attributes may be classified as FG type, in which case phase 3 validation dominates the running time.

Among the existing UCC discovery algorithms discussed in Section III, GORDIAN, DUCC, and HyUCC mainly rely on global in-memory data structures. Under the single-node memory budget considered in this paper, these algorithms cannot be directly applied once their required structures exceed the available memory. We do not make a direct experimental comparison with these algorithms in this paper. Instead, HPIValid is used as the main baseline because it is the most recent stateof-the-art UCC discovery algorithm and has been reported to substantially outperform these earlier methods [8]. The comparison here is therefore qualitative. When the required structures fit within the memory budget, these algorithms can avoid some of the disk-based sorting and sequential scans required by DUD. When such structures exceed the available memory, their applicability becomes limited, whereas DUD remains applicable. DUD is most suitable for settings where global in-memory structures cannot be held in memory, and where the pruning by Theorem IV.1 eliminates a large fraction of candidates from validation. The disk-resident design of DUD has direct relevance to large-scale data profiling in practice. Data sets in data quality, schema discovery, and data integration tasks are often stored on disk, and available memory may be far smaller than the data size. In such settings, algorithms that require global in-memory structures cannot run. DUD shows that UCC discovery remains feasible under these constraints, at the cost of additional disk I/O. In our experiments, DUD completes on data sets with up to 179.7 million tuples where HPIValid runs out of memory. Open problems. Several directions remain for future work. A validation strategy with a provable memory bound would address the data-dependent memory behavior discussed above. Improving performance on high-dimensional data sets with very large UCC result sets is also an open problem. Replacing the fixed γ factor used in this paper with a strategy that adapts to data distributions is another possibility. Extending DUD to a distributed setting, to scale beyond a single machine, is a further direction. Pipelining sorting and validation is another direction for reducing I/O cost in future implementations, although it would require additional design to stream sorted tuples into validation while preserving the reuse of sorted results across validation batches. A more refined pruning strategy, replacing the binary FG/NG classification with attribute-level ranking or partial difference set generation for NG attributes, could mitigate the validation cost on data sets with highly imbalanced attribute cardinalities such as prsa.

VI. C ONCLUSION This paper considers the problem of discovering unique column combinations (UCCs) on disk-resident data with limited memory. The existing algorithms need to maintain inmemory data structures for full data, and cannot deal with large-scale data well. This paper proposes a novel DUD algorithm to compute UCCs on large-scale disk-resident data efficiently. The execution of DUD consists of three phases. In phase 1, DUD determines the types of attributes with a low cost, generates full useful difference sets with respect to the attributes of FG type, and supplements difference sets by random sampling. Then DUD constructs the hypergraph, whose vertices are attributes of relation schema and hyperedges correspond to the generated difference sets. The UCC candidates can be generated quickly by enumerating minimal hitting sets of constructed hypergraph in phase 2. An important theorem is proved that the candidates including at least one attribute of FG type are true UCCs without validation, which significantly reduces the number of candidates to be validated in phase 3. For the validation candidates, phase 3 exploits hash-based batch validation strategy. A small number of tuples are maintained at a time to validate a set of candidates simultaneously. Any invalid candidates indicate conflicting tuples, which have equal projections on the candidates. The pairwise comparisons are performed for the conflicting tuples to generate new hyperedges and update the hypergraph. Then, if new hyperedges exist, DUD enters phase 2 to find the new UCC candidates by the similar follow-up processing, with the only difference that the UCC candidates already discovered to be UCCs in the previous operations should be removed. The extensive experimental results, conducted on synthetic and real-life data sets, show that DUD can discover UCCs on diskresident data with limited memory quickly. R EFERENCES [1] K. Schwab, Ed., The Fourth Industrial Revolution. Crown Publishing Group, January 2017. [2] Z. Abedjan, L. Golab, F. Naumann, and T. Papenbrock, Data Profiling, ser. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2018. [3] J. Kossmann, T. Papenbrock, and F. Naumann, “Data dependencies for query optimization: a survey,” VLDB J., vol. 31, no. 1, pp. 1–22, 2022. [4] I. F. Ilyas and X. Chu, Data Cleaning, ser. ACM Books. ACM, 2019, vol. 28. [5] A. Doan, A. Y. Halevy, and Z. G. Ives, Principles of Data Integration. Morgan Kaufmann, 2012. [6] F. Naumann, “Data profiling revisited,” SIGMOD Rec., vol. 42, no. 4, pp. 40–49, 2013. [7] Z. Abedjan and F. Naumann, “Advancing the discovery of unique column combinations,” in Proceedings of the 20th ACM Conference on Information and Knowledge Management. ACM, 2011, pp. 1565–1570. [8] J. Birnick, T. Bläsius, T. Friedrich, F. Naumann, T. Papenbrock, and M. Schirneck, “Hitting set enumeration with partial information for unique column combination discovery,” Proc. VLDB Endow., vol. 13, no. 11, pp. 2270–2283, 2020. [9] A. Heise, J. Quiané-Ruiz, Z. Abedjan, A. Jentzsch, and F. Naumann, “Scalable discovery of unique column combinations,” Proc. VLDB Endow., vol. 7, no. 4, pp. 301–312, 2013. [10] T. Papenbrock and F. Naumann, “A hybrid approach for efficient unique column combination discovery,” in Datenbanksysteme für Business, Technologie und Web (BTW 2017), 17. Fachtagung des GI-Fachbereichs ,,Datenbanken und Informationssysteme” (DBIS), Proceedings, ser. LNI, vol. P-265. GI, 2017, pp. 195–204.

[11] Y. Sismanis, P. Brown, P. J. Haas, and B. Reinwald, “GORDIAN: efficient and scalable discovery of composite keys,” in Proceedings of the 32nd International Conference on Very Large Data Bases. ACM, 2006, pp. 691–702. [12] T. Bläsius, T. Friedrich, and M. Schirneck, “The complexity of dependency detection and discovery in relational databases,” Theor. Comput. Sci., vol. 900, pp. 79–96, 2022. [13] T. Bläsius, T. Friedrich, J. Lischeid, K. Meeks, and M. Schirneck, “Efficiently enumerating hitting sets of hypergraphs arising in data profiling,” J. Comput. Syst. Sci., vol. 124, pp. 192–213, 2022. [14] T. Bleifuß, T. Papenbrock, T. Bläsius, M. Schirneck, and F. Naumann, “Discovering functional dependencies through hitting set enumeration,” Proc. ACM Manag. Data, vol. 2, no. 1, pp. 43:1–43:24, 2024. [15] R. Xiao, Y. Yuan, Z. Tan, S. Ma, and W. Wang, “Dynamic functional dependency discovery with dynamic hitting set enumeration,” in 38th IEEE International Conference on Data Engineering. IEEE, 2022, pp. 286–298. [16] X. Wan, X. Han, J. Wang, and J. Li, “Efficient discovery of functional dependencies on massive data,” IEEE Trans. Knowl. Data Eng., vol. 36, no. 1, pp. 107–121, 2024. [17] X. Chu, I. F. Ilyas, and P. Papotti, “Discovering denial constraints,” Proc. VLDB Endow., vol. 6, no. 13, pp. 1498–1509, 2013. [18] T. Papenbrock, S. Kruse, J. Quiané-Ruiz, and F. Naumann, “Divide & conquer-based inclusion dependency discovery,” Proc. VLDB Endow., vol. 8, no. 7, pp. 774–785, 2015. [19] M. Baazizi, H. Ben Lahmar, D. Colazzo, G. Ghelli, and C. Sartiani, “Schema inference for massive JSON datasets,” in Proceedings of the 20th International Conference on Extending Database Technology. OpenProceedings.org, 2017, pp. 222–233. [20] C. Yu and H. V. Jagadish, “XML schema refinement through redundancy detection and normalization,” VLDB J., vol. 17, no. 2, pp. 203–223, 2008. [21] Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen, “TANE: an efficient algorithm for discovering functional and approximate dependencies,” Comput. J., vol. 42, no. 2, pp. 100–111, 1999. [22] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules in large databases,” in Proceedings of 20th International Conference on Very Large Data Bases. Morgan Kaufmann, 1994, pp. 487–499. [23] K. Murakami and T. Uno, “Efficient algorithms for dualizing large-scale hypergraphs,” Discret. Appl. Math., vol. 170, pp. 83–94, 2014. [24] J. Han, J. Pei, Y. Yin, and R. Mao, “Mining frequent patterns without candidate generation: A frequent-pattern tree approach,” Data Min. Knowl. Discov., vol. 8, no. 1, pp. 53–87, 2004. [25] T. Papenbrock and F. Naumann, “A hybrid approach to functional dependency discovery,” in Proceedings of the 2016 International Conference on Management of Data. ACM, 2016, pp. 821–833. [26] T. Roughgarden, Algorithms Illuminated: Omnibus Edition. Cambridge University Press, 2022. [27] H. Garcia-Molina, J. D. Ullman, and J. Widom, Database systems - the complete book (2. ed.). Pearson Education, 2009. [28] M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. J. O’Neil, P. E. O’Neil, A. Rasin, N. Tran, and S. B. Zdonik, “C-store: A column-oriented DBMS,” in Proceedings of the 31st International Conference on Very Large Data Bases. ACM, 2005, pp. 553–564. [29] C. C. Aggarwal and J. Han, Eds., Frequent Pattern Mining. Springer, 2014. [30] R. Diestel, Graph Theory, 5th Edition, ser. Graduate texts in mathematics. Springer, 2017, vol. 173. [31] L. Berti-Équille, H. Harmouch, F. Naumann, N. Novelli, and S. Thirumuruganathan, “Discovery of genuine functional dependencies from relational data with missing values,” Proc. VLDB Endow., vol. 11, no. 8, pp. 880–892, 2018.

Efficient discovery of unique column combinations on disk-resident data with limited memory

Analyze & explore related research in Conceptio

Related documents