Functional dependencies and arithmetic identities

A functional dependency states that equal input values have equal output values within the rows evaluated. The profiler screens candidate mappings, searches combinations of columns, then verifies candidates. The value_mapping form records a lookup relation; affine records a fitted equation such as y = a·x + b. Both are functional dependencies.

Semantics¶

The comparison excludes rows with a null in any input or target; n_used records the rows evaluated. Values are compared in onceover’s normalized representation, not as formatted display strings. The specification records this row-selection and comparison policy.

Discovery: screen, lattice, verify¶

Screen. All eligible input and target columns are screened using a 2,048-row stratified sample. Determinants need at least two distinct values, 30 non-null rows, and a distinct ratio below 0.98. Near-unique columns are handled by key analysis. The screen estimates violations for each input–target pair. It retains up to 16 candidate determinants per target (32 on deep).

Lattice. Determinant sets grow level-wise — singletons, then pairs (then triples on deep, drawn from the 12 columns that produced the most exact dependencies). Subset pruning skips a candidate if one of its subsets already determines the target. Determinants whose groups cover at least 95% of evaluated rows are also excluded: such a near-unique input would appear to determine almost any target.

Verify. Each candidate is rechecked using normalized values on up to 200,000 stratified rows (500,000 on deep). Hashing screens candidates; verification checks whether the mapping holds in the verification sample. A candidate that fails becomes an approximate dependency if its error is small enough; a candidate that passes is exact on the verified rows, and the finding says which rows those were.

Approximate dependencies¶

The reported g1 value is the fraction of evaluated rows that violate the mapping. Approximate dependencies require g1 ≤ 0.01. The search retains at most one per target, choosing the one with fewer violations and then fewer inputs. It suppresses an approximate dependency if a subset of its inputs already establishes the same output exactly. The finding reports the violation count and evaluated-row count.

import random

import polars as pl

import onceover

rng = random.Random(9)
n = 3_000
region_id = [rng.randrange(3) for _ in range(n)]
manager = [["Ann", "Bob", "Cid"][r] for r in region_id]
for i in (100, 900, 1700):          # exactly three violations
    manager[i] = "Dana"
df = pl.DataFrame({
    "region_id": region_id,
    "manager": manager,
    "noise": [rng.random() for _ in range(n)],
})

report = onceover.profile(df)
for f in report.findings:
    if f["category"] == "dependencies" and f.get("type") == "functional" and "manager" in f["subject"]["columns"]:
        e = f["evidence"][0]
        print(f"{f['claim']}")
        print(f"   violations={e['metrics']['violations']} n_used={e['metrics']['n_used']}")

manager → region_id holds on 99.93% of rows (2 violations in 3000 rows)
   violations=2 n_used=3000
region_id → manager holds on 99.90% of rows (3 violations in 3000 rows)
   violations=3 n_used=3000

Arithmetic identities¶

The identity pass fits y = a·x + b by least squares on up to 20,000 sampled rows. It considers pairs with |Pearson| ≥ 0.8 or ξ ≥ 0.9, up to 100 (default) or 200 (deep). It checks each fitted equation on all pair-complete rows, using a tolerance of 1e-9 absolute plus 1e-9 relative. An identity is reported when at least 99.9% of rows match, with the coefficients, the tolerance, the matching-row count, and any violating rows in the metrics. The statement is dependencies/functional with form affine; the finding’s interpretation suggests whether the target may be a derived column or a check column.

The pass checks pairwise affine relationships. Multivariate formulas are the multi-term scan’s territory (next section); nonlinear equations beyond the product and ratio of a pair are not searched (Directions).

df = pl.DataFrame({
    "quantity": [rng.randrange(1, 11) for _ in range(n)],
})
df = df.with_columns((2 * pl.col("quantity")).alias("double_quantity"))
report = onceover.profile(df)
identity = next(f for f in report.findings if f["specification"].get("form") == "affine")
print(identity["claim"])
print("a, b:", identity["specification"]["definition"]["a"], identity["specification"]["definition"]["b"])

double_quantity = 2.000000·quantity within tolerance on all 3000 non-missing row pairs
a, b: 2.0 0.0

Duplicate encodings and rollups¶

An exact dependency between two label columns usually means one of them is a second encoding of the other — a region code and a region name, an id and its display label. The duplicate_encodings detector (standard and deep budgets) states that reading directly. It pairs up text columns and whole-number code columns (identifiers excluded, since a key determines its label trivially) whose distinct value pairs number at most 1.02 times the larger column’s level count, and verifies candidates on exact canonical encodings before reporting. When the two level counts are comparable (the smaller at least 0.9 of the larger) the finding’s form is duplicate_encoding, with an exact flag for a pairing that is one-to-one on every row; when one column’s levels each map to a single level of a column with fewer levels, the form is rollup and the finer column is named first. The advisory scores below the functional dependency itself, so when both describe one pair the dependency ranks first.

cities = [f"city_{k}" for k in range(9)]
city = [cities[rng.randrange(9)] for _ in range(n)]
city_region = {c: k // 3 for k, c in enumerate(cities)}
region_id = [city_region[c] for c in city]
region_name = [["North", "Central", "South"][r] for r in region_id]
df = pl.DataFrame({"city": city, "region_id": region_id, "region_name": region_name})

report = onceover.profile(df)
for f in report.findings:
    if f.get("type") == "duplicate_encoding":
        e = f["evidence"][0]
        print(f["claim"])
        print(f"   form={e['metrics']['form']} pairs={e['metrics']['pairs']} exceptions={e['metrics']['exceptions']}")

region_id and region_name encode the same grouping: 3 levels, paired one-to-one on all 3000 rows
   form=duplicate_encoding pairs=3 exceptions=0
city rolls up to region_id: each of its 9 levels maps to one of 3 levels, on all 3000 rows
   form=rollup pairs=9 exceptions=0
city rolls up to region_name: each of its 9 levels maps to one of 3 levels, on all 3000 rows
   form=rollup pairs=9 exceptions=0

Multi-term identities¶

A separate scan looks for exact relations among two or three numeric columns. For each target column it screens five forms:

sum and difference with unit coefficients, over two or three columns (total = price + tax, change = close - open);
product and ratio of a pair (area = width · height);
linear_combination — a fitted equation over two or three predictors (target = c0 + c1·x + c2·y), with the coefficients fitted by least squares and reported in the claim.

Screening runs on a stride sample of at most 512 rows; a candidate that matches on the sample is verified on all rows and kept when at least 99.9% of the complete rows match within the identity tolerance, with any violations counted in the claim. The number of candidates screened is capped by budget — the scan is off at quick, and the caps are 2,000 candidates at standard and 8,000 at deep — and the coverage record states how many were screened and how many identities verified.

Two minimality rules keep the output to the smallest readings of each relation. A reading is dropped when a strict subset of its predictors already determines the target, and a fitted combination loses any predictor whose coefficient is zero. Rearrangements are not duplicates under these rules: when score = 2·midterm + 3·final holds, the readings that solve for midterm or for final determine a different target from a different predictor set, and each is reported.

import random

import polars as pl

import onceover

rng = random.Random(9)
n = 400
price = [round(rng.uniform(5, 50), 2) for _ in range(n)]
tax = [round(p * 0.08, 2) for p in price]
total = [p + t for p, t in zip(price, tax)]
width = [rng.randint(2, 9) for _ in range(n)]
height = [rng.randint(2, 9) for _ in range(n)]
area = [w * h for w, h in zip(width, height)]
midterm = [rng.randrange(40, 100) for _ in range(n)]
final = [rng.randrange(40, 100) for _ in range(n)]
score = [2 * m + 3 * f for m, f in zip(midterm, final)]

df = pl.DataFrame({
    "price": price, "tax": tax, "total": total,
    "width": width, "height": height, "area": area,
    "midterm": midterm, "final": final, "score": score,
})
report = onceover.profile(df)

for target in ("total", "area", "score"):
    hit = next(f for f in report.findings
               if f["claim"].startswith(target + " =")
               and f["specification"].get("form")
               in {"sum", "product", "linear_combination"})
    print(hit["specification"]["form"], "|", hit["claim"])
print("coverage:", report.coverage["multiterm_identities"]["detail"])

sum | total = price + tax within tolerance on all 400 non-missing rows
product | area = width · height within tolerance on all 400 non-missing rows
linear_combination | score = 2.000000·midterm + 3.000000·final within tolerance on all 400 non-missing rows
coverage: 756 multi-term candidates screened, 7 multi-term identities