Literature review

This appendix describes the research behind the profiler’s methods and how the implementation differs from the original algorithms. It also identifies related approaches that are not implemented.

Data profiling and dependency discovery¶

Abedjan, Golab & Naumann, Profiling Relational Data (VLDB Journal, 2015), organize profiling into single-column statistics, multi-column metadata (including correlations, unique column combinations, functional dependencies, and inclusion dependencies), and conditional properties. onceover implements single-column summaries and a bounded selection of multi-column and conditional searches.

Functional dependencies. TANE (Huhtala et al., Computer Journal, 1999) searches a lattice of column sets using partitions and subset pruning. HyFD (Papenbrock & Naumann, EDBT 2016) combines sampling with validation; DFD (Abedjan et al., CIKM 2014) explores the search space using a depth-first strategy. onceover uses a hash-based screen, bounded level-wise growth with subset pruning, and verification with canonical value bytes. It does not implement these systems in full.
Approximate FDs. Kivinen & Mannila (Theoretical Computer Science, 1995) studied measures of approximate dependency error. onceover reports g1 as the fraction of evaluated rows that would need to change for the dependency to hold. Parciak et al. (ICDE 2024) compare AFD measures and their differing behavior. Approximate unique column combinations, used here to describe near-unique keys, are studied by Kruse & Naumann (PVLDB 2018).
Order dependencies. Langer & Naumann (VLDB Journal 2016) survey dependencies between orderings. onceover checks the narrower property of whether a column is ordered with row position; it does not discover general order dependencies.
Arithmetic identities. BHUNT (Brown & Haas, VLDB 2003) uses pair sampling to discover algebraic constraints. BACON (Langley, IJCAI 1977) discovers empirical laws through invariance detection. These are related approaches to onceover’s pairwise affine probe, which fits on a sample and verifies residuals on all pair-complete rows.
Soft dependencies. CORDS (Ilyas et al., SIGMOD 2004) uses correlations to propose soft functional dependencies. onceover also uses inexpensive dependence screening to choose candidates for the identity and regime passes.

Desbordante is a related dependency-discovery system and a useful reference for comparing supported dependency types. onceover contains its own implementations; its bounded searches should not be treated as exhaustive dependency discovery.

Rule induction, subgroups, and rules¶

PRISM (Cendrowska, IJMMS 1987) induces modular covering rules, one class at a time, by adding conditions. onceover uses bitset masks and adds a near-majority guard and shared rule evaluation. The chapter on rules documents these adaptations.
Decision tables (Kohavi, ECML 1995) predict using a selected subset of columns and the majority class within each lookup cell. The pass here uses greedy subset search and cross-validated cell-majority prediction, compared with a majority-class baseline.
CN2 (Clark & Niblett, 1989) and CN2-SD (Lavrač et al., JMLR 2004) use beam search and quality measures for rule induction and subgroup discovery. Coverage, precision, and significance provide related ways to assess rules. onceover does not implement WRAcc-based subgroup discovery, diversity selection (van Leeuwen & Knobbe, DMKD 2012), or self-sufficient itemsets (Webb, TKDD 2010). Its association miner uses support, confidence, and lift filters over a bounded search.
Holdout validation for rules. Megiddo & Srikant (KDD 1998) discuss validating discovered rules on separate data. The association miner uses a train/holdout split. The shared evaluator instead uses a diagnostic partition that discovery may already have seen; this is not an independent holdout.
GritBot (RuleQuest) searches for unusual values given other values in a row. This conditional-anomaly approach is related to reporting findings with explicit conditions, but onceover does not implement a conditional-anomaly pass.

Piecewise relationships and changepoints¶

Chow (1960) tests for a structural break at a specified point. onceover’s residual-shift pass uses a centered cumulative-sum scan to propose one break and evaluates it on a holdout. It reports no p-value and does not implement the Chow test.
M5 (Quinlan) and M5’ (Wang & Witten) fit linear models in tree leaves with pruning and smoothing. onceover’s regime pass is a bounded M5-style variant: standardization on training rows, QR-fitted leaves, corrected-error pruning, and ancestor smoothing. It is not intended to reproduce Weka’s output.
Muggeo (Statistics in Medicine, 2003) describes segmented regression. The supF/strucchange work (Zeileis et al.) and MOB (Zeileis, Hothorn & Hornik, JCGS 2008) provide approaches to structural change and parameter-instability testing. Multiple-break methods, including PELT (Killick, Fearnhead & Eckley, JASA 2012), and the review by Truong et al. (Signal Processing, 2020) inform possible extensions described in Directions.

Dependence measures¶

Chatterjee’s ξ (JASA, 2021) is an asymmetric, rank-based dependence coefficient computed in O(n log n). It can detect nonlinear functional relationships that Pearson correlation misses. The implementation uses the tie-corrected estimator with fixed-seed random tie-breaking. A fixed row order for breaking ties can introduce dependence on row position; regression tests cover that case. Pearson and Spearman provide linear and monotonic dependence summaries alongside ξ.

MIC (Reshef et al., Science, 2011) is another approach to dependence measurement. Kinney & Atwal (2014) discuss its equitability claims. It is not implemented here; that choice does not establish that ξ is preferable for every dataset or analysis.

The encoded matrix uses quantile binning with fixed bin counts, as in histogram-based boosting (Ke et al., NeurIPS 2017). It does not use the supervised MDLPC method (Fayyad & Irani, 1993): the shared encoding is built before any column is chosen as a prediction target.

Profiling and validation tools serve overlapping purposes. Examples include ydata-profiling, sweetviz, dtale, and skimpy for exploratory summaries; whylogs for statistical logging; DataProfiler (Capital One) for profiling and semantic type analysis; TensorFlow Data Validation for statistics and schema validation; and Great Expectations for data validation. skrub’s TableReport is also relevant to rendering table summaries. Polars provides describe() for summary statistics.

When comparing these tools, check the current release against the actual task: accepted input types, dependency and rule discovery, validation scope, output format, search limits, and runtime. This appendix does not provide a benchmark or an exhaustive feature comparison. onceover combines column summaries with bounded relationship discovery and records sampling, caps, and skipped work in its coverage block.

View and cluster models¶

CrossCat (Mansinghka et al., JMLR, 2016) is the inspiration for the views detector’s column and row partitions. The paper describes Bayesian inference over those partitions. Onceover selects one partition by greedy search with a fixed complexity penalty; its scores are not posterior probabilities. See the views method reference for the implemented criterion and its limitations.

Using the references¶

Evidence records name the algorithms used by each detector. This appendix provides context for those names and explains the implementation’s scope. The directions chapter lists possible extensions from related work.