PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xiaolong Wan, Xixian Han

arXiv:2609.00783v1cs.DB

TL;DR

UCC discovery is important for identifying key constraints, but existing methods require in-memory structures that struggle with large disk-resident data. DUD uses partial difference sets, hypergraph hitting sets, theorem-based pruning, and hash-based batch validation to discover UCCs with limited memory. Experiments show that DUD remains feasible on large data sets, including one with 179.7 million tuples, while its performance trades additional disk I/O for lower memory use.

  • Problem

    Existing UCC discovery algorithms require in-memory structures that may not fit large-scale disk-resident data under limited memory.

  • Method

    DUD generates partial difference sets, enumerates minimal hypergraph hitting sets, prunes candidates using a theorem, and validates remaining candidates with hashing.

  • Results

    DUD completes on data sets with up to 179.7 million tuples where HPIValid runs out of memory.

  • Takeaways & Limitations

    DUD makes UCC discovery feasible under memory constraints by replacing global in-memory structures with disk-based sorting and sequential scans.

  • Takeaways & Limitations

    DUD may become substantially more costly when attributes or result sets are numerous, and HPIValid may be faster when its PLI structures fit in memory.

Abstract

from arXiv · show

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 large-scale 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.

I. INTRODUCTION

UCC discovery identifies minimal attribute combinations that uniquely distinguish tuples, but existing methods struggle with large disk-resident data under limited memory. DUD addresses this by combining partial difference-set generation, hypergraph hitting-set enumeration, theorem-based pruning, and hash-based validation.

  • UCCs describe table key constraints and support applications including query optimization, data cleansing, and data integration.
  • The discovery problem is difficult because the number of UCC candidates grows exponentially with the number of attributes.
  • Existing algorithms rely on in-memory structures that may not fit large disk-resident data, making limited-memory UCC discovery an open problem.
  • DUD builds a partial-information hypergraph, enumerates minimal hitting sets for candidates, validates them, and updates the hypergraph with conflicts.
  • Full useful difference sets are generated for selected attributes, allowing candidates containing those attributes to be reported as true UCCs without validation.
  • Hash-based validation checks candidates while retaining only tuples sharing a constituent attribute value, reducing memory requirements.
  • DUD is reported to achieve high efficiency on disk-resident data with limited memory in experiments on synthetic and real-life data sets.

II. PRELIMINARIES

The preliminaries define UCCs through tuple projections and minimality, then connect UCC discovery to minimal hitting sets of a hypergraph built from tuple difference sets.

  • A UCC is an attribute subset whose projection contains no duplicate values, equivalently separating every pair of distinct tuples.
  • Every superset of a UCC is also a UCC, while a minimal UCC contains no proper subset that is itself a UCC.
  • UCC discovery returns all minimal UCCs because the remaining UCCs can be derived from them.
  • The running example uses eight attributes and illustrates three UCCs for its relation instance.
  • Representing attributes as hypergraph vertices and minimal difference sets as hyperedges makes minimal UCCs correspond to minimal hitting sets.
  • A difference set contains the attributes on which two tuples differ, and a UCC must intersect every such difference set.

III. RELATED WORKS

UCC discovery spans attribute-based, tuple-based, and hybrid approaches, but existing methods often depend on memory-intensive structures. DUD addresses disk-resident data through partial difference-set generation and hash-based batch validation.

  • Existing approaches: UCC discovery methods are classified as attribute-based, tuple-based, or hybrid approaches.Attribute-based methods search an attribute lattice, tuple-based methods derive UCCs from non-UCCs, and hybrid methods combine both strategies.
  • Memory limitation: Existing algorithms can fail on large disk-resident relations when prefix trees or stripped partitions exceed available memory.The memory requirement of these global per-tuple structures can make UCC discovery impractical under constrained resources.
  • DUD approach: DUD operates directly on relation tuples rather than maintaining a global prefix tree or stripped-partition structure.This design distinguishes DUD from existing hybrid approaches in its treatment of disk-resident data.
  • DUD approach: DUD reports candidates containing selected attributes as true UCCs without validation and validates remaining candidates in batches using hashing.These strategies reduce validation work while maintaining only a small number of tuples in memory.
  • DUD approach: DUD uses partial difference-set generation, minimal hitting-set enumeration, and candidate validation across three execution phases.Phase 1 constructs a partially informed hypergraph, phase 2 generates candidates, and phase 3 validates candidates.

A. Phase 1: construction of hypergraph

DUD constructs an initial hypergraph from useful partial difference sets instead of comparing every tuple pair. It controls comparison cost through attribute types, sampling, and incremental minimization of difference sets.

  • Difference-set generation: Complete pairwise comparison is impractical on large relations, so phase 1 generates useful difference sets from a restricted subset of tuple pairs.Useful difference sets exclude at least one attribute and can be generated from tuples agreeing on a selected attribute.
  • Difference-set generation: DUD omits the full-attribute difference set because any nonempty proper subset makes it irrelevant to minimal hitting-set enumeration.This property justifies retaining only useful difference sets.
  • Attribute typing: Attributes with comparison count cmp_i ≤ γ are FG type, while those with cmp_i > γ are NG type and skip full difference-set generation.DUD determines comparison counts after sorting column files and uses γ as the comparison upper bound.
  • Attribute typing: For NG attributes, DUD supplements omitted difference sets by uniformly sampling tuples and performing additional pairwise comparisons with low memory consumption.The sampled comparison budget is tied to the number of NG attributes.
  • Hypergraph construction: DUD removes duplicate difference sets with hashing and minimizes them in batches, using delta-based minimization for newly generated sets during validation.The resulting minimal difference sets form the hyperedges of the initial hypergraph.
  • Execution process: Phase 1 decomposes the relation into column files, computes comparison counts, generates sets for FG attributes, supplements NG attributes, and builds the minimized hypergraph.The generated difference sets are substantially fewer than all possible pairwise comparisons in evaluated benchmark and real-life data sets.

B. Phase 2: enumeration of minimal hitting sets

In phase 2, DUD enumerates minimal hitting sets of the phase-1 hypergraph as UCC candidates. MMCS explores candidate attribute combinations while tracking uncovered and critical hyperedges for pruning and minimality.

  • Candidate enumeration: DUD uses MMCS to enumerate minimal hitting sets of the constructed hypergraph as candidate UCCs.The hypergraph vertices are attributes, and its hyperedges are difference sets.
  • MMCS search: MMCS represents each search node with attributes, candidate extensions, uncovered hyperedges, and critical hyperedges.These fields support breadth-first exploration and minimality checking.
  • MMCS search: A node is accepted as a minimal hitting set when it covers every hyperedge and each included attribute has a critical hyperedge.This condition is checked during the queue-based exploration.
  • Pruning strategy: MMCS limits extensions to attributes in the uncovered hyperedge with the smallest candidate intersection.The pruning rule reduces the possible child nodes while preserving potential minimal hitting sets.
  • Example: In the running example, phase 2 returns 3 UCC candidates from the hypergraph built in phase 1.Each returned candidate intersects every hyperedge.

C. Phase 3: validation of UCC candidates

Phase 3 reduces validation work by directly reporting candidates containing FG attributes as UCCs, then validates the remainder using disk-based hash batching that retains only small tuple groups in memory.

  • Candidate pruning: Candidates containing at least one FG attribute are guaranteed UCCs and can be reported without validation.Theorem IV.1 establishes this pruning rule, potentially eliminating validation entirely.
  • Running example: In the running example, two of three generated candidates are directly proved true UCCs, leaving only one candidate for validation.The later updated-hypergraph execution similarly validates only one remaining candidate.
  • Hash-based validation: DUD addresses limited-memory validation by sorting the relation on a constituent attribute and processing equal-value runs incrementally.This avoids maintaining the full relation in memory during collision checking.
  • Batch validation: Candidates are grouped by a visited NG attribute, allowing DUD to sort the relation once and validate all grouped candidates together.The sorted relation is reused for simultaneous checks of candidates in the group.
  • Collision checking: A candidate is invalid when duplicate projections occur within a run; otherwise, it is reported as a UCC.Conflicting tuples generate new difference sets that update the hypergraph for subsequent candidate generation.

D. The correctness of DUD

DUD is correct because its partial hypergraph preserves correspondence between provisional and complete minimal hitting sets, while validation resolves candidates that are not final UCCs.

  • Hypergraph basis: The complete hypergraph represents all tuple-difference constraints, and its minimal hitting sets are exactly the minimal UCCs.DUD uses a spanning subgraph containing a subset of the complete hypergraph's hyperedges.
  • Correspondence: Every minimal hitting set of the complete hypergraph contains a corresponding minimal hitting set in DUD's spanning subgraph.Removing hyperedges relaxes the hitting-set constraints and can produce smaller provisional candidates.
  • Correspondence: Every minimal hitting set generated from DUD's partial hypergraph can be extended to a minimal hitting set of the complete hypergraph.Thus provisional candidates can be completed to final minimal UCCs after additional constraints are introduced.
  • Correctness: Together, the correspondence theorems ensure that DUD either reports a candidate directly or finds conflicts and adds difference-set hyperedges until correctness is reached.The paper states this yields correct discovery of the true UCCs.

E. Cost analysis

DUD's cost is governed by difference-set generation and sorting, hypergraph enumeration, and repeated validation, with pruning and real-data structure reducing the practical burden.

  • Phase 1: Phase 1 runs in O(m × n × log2 n) time for difference-set generation and sorting when γ = 3 × n × log2 n.The remaining phase-1 operations are lower-order according to the analysis.
  • Phase 2: Phase 2 performs breadth-first minimal-hitting-set enumeration over a set-enumeration tree, with cost depending on hyperedge size and visited nodes.MMCS enumerates minimal hitting sets within O(∥E∥) for each visited node.
  • Phase 3: Phase 3 has complexity O(m × n × log2 n + m × c × d2 × (1 − Ppru) × Pa), combining sorting with collision checking for unpruned candidates.Here c is the maximum distinct-value count for NG attributes and d is the maximum duplicate-projection count within a run.
  • Overall complexity: Overall, DUD has O(b × m × n × log2 n + b × ∥E∥ × Pa) time complexity across its phases.b denotes the number of phase-3 invocations.
  • Practical behavior: On real-life data, phase 3 is invoked at most twice, Ppru often exceeds 90%, and the sorting term usually dominates total time.The analysis also reports small maximum UCC and minimal-difference-set sizes in the experiments.

V. EXPERIMENTAL EVALUATION

The evaluation compares DUD with HPIValid on synthetic and real-life data under controlled preprocessing and memory settings, while examining scaling and parameter choices.

  • Experimental setup: DUD is evaluated against HPIValid, described as a state-of-the-art UCC discovery algorithm with a small memory footprint.The comparison is implemented in Java on a workstation with 32 GB memory and a 4 TB HDD.
  • Data sets: The experiments use synthetic TPC-H lineitem tables and real-life data sets from the UCI Machine Learning Repository and Kaggle.A maximum of 24 GB is allocated to algorithm execution on the 32 GB machine.
  • Preprocessing: All data sets undergo common preprocessing that dictionary-encodes attribute values as fixed-length 8-byte integers stored on disk.The transformation preserves equality information needed for UCC discovery.
  • Parameterization: For SF = 10, the experiments examine attribute cardinalities, useful-comparison counts, and FG or NG classifications under γ = 3 × n × log2 n.The reported comparison costs motivate selective full difference-set generation.
  • Null semantics: DUD adopts NULL-EQ semantics so null values are equal to one another and unequal to non-null values, matching HPIValid and prior studies.This enables direct comparison under a shared uniqueness definition.

A. Memory Space Requirement

DUD uses less memory than HPIValid by executing its disk-oriented operations sequentially and independently. In the reported lineitem experiments, DUD remains within the memory limit while HPIValid runs out of memory at larger scale factors.

  • HPIValid requires 2.40GB, 5.14GB, and 12.21GB for SF = 1, 2, and 5, respectively, and runs out of memory for SF ≥10.The measurements are reported under a 24GB space limit.
  • The reported memory measurements trigger garbage collection before calculating used JVM heap memory.This avoids counting objects that are no longer used but have not yet been collected.
  • DUD requires less than 8GB of memory for lineitem tables with SF ≤20.Its operations are executed sequentially and independently, including sorting, difference-set handling, hypergraph construction, tuple maintenance, and hash-table validation.

B. Factor selection of γ value

DUD selects γ to balance difference-set generation against candidate validation. Experiments show that factor 3 gives the best overall performance, so the paper uses γ = 3 × n × log2 n.

  • Factor selection of γ value: 3 × n × log2 n is the γ value used in DUD experiments.The choice grows more slowly than the O(n2) upper bound on pairwise comparisons.
  • Factor selection of γ value: Lower γ factors shorten phase 1 but lengthen phase 3 because fewer attributes are classified as FG type and Theorem IV.1 prunes fewer candidates.Higher factors have the opposite trade-off: phase 1 takes longer, while phase 3 may finish sooner.
  • Factor selection of γ value: DUD’s execution time remains unchanged across factors whose γ values fall within the same gap between required full useful comparison numbers.For factors in, four attributes are of FG type.
  • Factor selection of γ value: Factor 3 produces the best overall DUD performance in Figure 12.Accordingly, γ is set to 3 × n × log2 n in the experiments.

C. Experiment 1: effect of varying tuple numbers

On increasing tuple counts, DUD scales more gently than HPIValid and uses validation memory far below the relation size. Its speed advantage comes from candidate pruning and batch validation, although HPIValid can be faster on smaller data.

  • Effect of varying tuple numbers: DUD is 3.7× faster at SF = 1 and 6.0× faster at SF = 5 than HPIValid on lineitem tables.DUD runs faster than HPIValid for SF ≤5, while HPIValid is reported only for SF = 1, 2, and 5 because it exceeds memory capacity for SF ≥10.
  • Effect of varying tuple numbers: About 90% of phase-2 candidates are removed from validation because Theorem IV.1 proves them to be UCCs directly.Hash-based batch validation also verifies several candidates in one iteration.
  • Effect of varying tuple numbers: At SF = 20, DUD maintains at most 50,554 tuples in memory for validation while the table contains 119,994,608 tuples.The maintained validation set is three orders of magnitude smaller than the total tuple count.
  • Effect of varying tuple numbers: DUD’s pairwise-comparison count is much larger than HPIValid’s on small and medium-scale data because most comparisons generate useful difference sets in phase 1.HPIValid can have lower I/O cost on these data sizes.
  • Effect of varying attribute numbers: When attributes number no more than 10, DUD does not invoke hash-based validation in experiment 2.For m = 4, HPIValid is faster than DUD at 88.70s versus 113.86s; for m = 7, times are similar at 281.67s versus 284.79s, while HPIValid runs out of memory for m ≥10.

E. Experiment 3: the real-life data sets

On real-life data, DUD’s advantage depends on scale, dimensionality, and whether HPIValid’s in-memory structures fit. DUD is especially effective when those structures exceed the memory budget, but it is not uniformly faster because disk sorting and scanning add I/O cost.

  • Real-life data sets: For data sets with fewer than 10^6 tuples, HPIValid often has lower I/O cost and can run faster when stripped partitions fit in memory.DUD often retrieves an order of magnitude more I/O because sorting costs at least twice the relation size.
  • Real-life data sets: DUD runs faster than HPIValid on pamap2, hepmass, higgs, susy, and ht sensor, while HPIValid runs out of memory on several larger or higher-dimensional data sets.HPIValid runs out of memory on ssdp flood, ids2018, ghtorrent, and hi-large trans.
  • Real-life data sets: DUD’s advantage is most significant when HPIValid’s PLI-based structures exceed the memory budget.When those structures fit, HPIValid may validate candidates directly from in-memory structures instead of paying DUD’s disk-sorting and scanning costs.
  • Real-life data sets: On prsa, only one UCC candidate is reported as true without validation because only the first attribute is classified as FG type.The sole UCC containing that attribute is {A1, A18}, so other UCCs require validation.
  • Real-life data sets: DUD’s execution time increases only gradually as allocated memory decreases from 24GB to 64MB.The increase is explained by additional I/O and the transition to two-pass multi-way merge sorting when files do not fit the sorting buffer.

G. Discussion

DUD enables UCC discovery on disk-resident data under limited memory by trading additional disk I/O for avoiding global in-memory structures. Its pruning, validation, and attribute-type strategies determine where it is most effective and expose several scope boundaries.

  • Discussion: DUD trades memory consumption for disk I/O by avoiding global in-memory structures such as stripped partitions.When HPIValid's PLI-based structures fit the memory budget, the algorithms are roughly comparable across the evaluated data sets.
  • Discussion: Candidates containing at least one FG-type attribute are true UCCs and do not require validation, while γ balances difference-set generation against validation cost.The default γ factor of 3 is reported as empirically optimal.
  • Discussion: DUD lacks a formal worst-case validation-memory bound because memory depends on data-dependent maximum run lengths of NG attributes.A reported case maintained 50,554 of 119,994,608 tuples in memory during validation.
  • Discussion: DUD may incur substantially higher candidate-management and validation costs on high-dimensional data, large UCC result sets, or data with few FG-type attributes.On highly imbalanced data such as prsa, phase 3 validation can dominate runtime.
  • Discussion: DUD handles large-scale disk-resident data under limited memory, completing experiments with up to 179.7 million tuples where HPIValid runs out of memory.This advantage comes at the cost of additional disk-based sorting and sequential scans.
  • Discussion: Several extensions remain open, including provably bounded validation memory, adaptive γ selection, distributed execution, pipelined sorting and validation, and refined pruning.The paper also identifies high-dimensional data with very large UCC result sets as an open performance challenge.
Loading 2609.00783v1…