NULL Values

SQL’s NULL comes with famously subtle semantics: predicates over NULLs follow a three-valued logic, set operations switch to a different notion of equality, aggregates skip NULL inputs, and queries that look equivalent stop being equivalent the moment a NULL appears. ProvSQL tracks provenance through these rules: the rewritten query returns what vanilla PostgreSQL returns, and the provenance and probabilities it computes are correct with respect to SQL’s own NULL semantics. This chapter states the rules ProvSQL follows and the few places where its behavior is a deliberate, documented choice.

What NULL Means Here

ProvSQL implements the SQL-operational reading of NULL: a NULL is a value like any other, predicates over it evaluate to unknown per SQL’s three-valued logic (3VL), and a row whose condition is unknown is not an answer. ProvSQL does not interpret NULL as an unknown quantity ranging over possible values (the “incomplete information” reading); NULL stays NULL in every possible world.

Two rules pin the semantics down:

Selection rule. Every condition is evaluated under SQL’s 3VL on the actual data; a tuple whose condition evaluates to unknown or false is not an answer: depending on the construct it is either removed from the result or kept with the semiring zero as its annotation, which is equivalent to absence (see Zero-Annotated Rows May Stay Visible below). Unknown never becomes “maybe” in the annotation, and never silently becomes “true”.
Possible-worlds criterion. For Boolean provenance (and everything built on it: probabilities, Shapley values, knowledge compilation), a tuple’s annotation must satisfy: the tuple is in the query answer over a world W – evaluated under SQL’s own semantics, NULLs included – exactly when W satisfies the tuple’s Boolean provenance.

Behavior by Construct

WHERE, JOIN, and HAVING predicates. PostgreSQL itself evaluates deterministic predicates, 3VL included; ProvSQL only combines the tokens of rows that survive. WHERE b > 5 drops rows with a NULL b, a NULL join key matches nothing, and their tokens simply never enter the circuit.

IN and EXISTS. x IN (SELECT …) with no true match makes the row a non-answer whether the comparison is false or unknown – that is SQL’s own top-level rule, and the annotation is zero either way. EXISTS / NOT EXISTS only ever ask whether a true match exists, so they compose correctly with NULLs as-is.

NOT IN and quantified comparisons (op ALL). Negation is where NULLs bite: x NOT IN Q is unknown – hence not an answer – as soon as Q contains a NULL (or x is NULL and Q is non-empty). ProvSQL’s rewriting accounts for this: the removal condition it builds treats an unknown comparison like a match, so a subquery row with a NULL removes the outer row in every world containing it. Consequently, NOT IN, NOT EXISTS, and EXCEPT – equivalent on NULL-free data – get genuinely different provenance on data with NULLs, matching their different SQL answers. (See Step 12 of case study 5 for the three side by side.)

Set operations, DISTINCT, GROUP BY. SQL deliberately switches to syntactic equality here: two NULLs are the same value. DISTINCT and GROUP BY collapse NULL keys into one group whose annotation is the ⊕ of all contributing tokens; UNION merges NULL rows from both sides; EXCEPT matches NULL rows on the two sides against each other (its antijoin uses IS NOT DISTINCT FROM matching). INTERSECT is not supported and fails with an explicit error.

Aggregates. sum / avg / min / max skip NULL inputs; count(col) counts non-NULL values while count(*) counts rows; an all-NULL (or empty) group yields a NULL aggregate whose formula readout is NULL as well. The same holds for aggregates over random_variable columns: a NULL cell contributes to neither the sum nor avg’s count.

HAVING over a NULL aggregate. A comparison against a NULL aggregate never passes – neither on the actual instance (the group’s annotation is zero) nor in any possible world where the aggregate comes out NULL (a world with no contributing row). HAVING <agg> IS [NOT] NULL is fully supported across possible worlds: sum(b) IS NULL holds in exactly the worlds where the group exists but no non-NULL-valued row is present.

Outer joins. The supported shape – a two-relation LEFT/RIGHT/FULL JOIN between tracked arms, with no outer reference to the join – is lowered into its matched and NULL-padded arms with correct (monus) provenance for the padding. An outer join whose null-padded side is entirely untracked is also fine as-is: which rows are padded is then deterministic. Any other outer join with a tracked relation on a null-padded side is refused with an explicit error rather than silently mis-tracked.

Comparisons on NULL random variables. A comparison involving a NULL random_variable – a NULL constant or a NULL cell – is unknown in every world: the row is annotated zero (probability 0). IS NULL on a random_variable column is an ordinary deterministic predicate. (See Step 19 of case study 6.)

Zero-Annotated Rows May Stay Visible

A row whose annotation is the semiring zero is equivalent to an absent row, and ProvSQL does not always spend the effort of filtering such rows out: rewritten queries may return rows that vanilla SQL does not, whose annotation evaluates to zero. Typical examples are the antijoin arm of a difference (a row removed on this instance but present in worlds where its remover is absent – exactly what makes its probability meaningful) and HAVING groups that fail the predicate. Deciding zero-ness in general requires evaluating the provenance and is semiring-relative, so visible-but-zero is the deliberate default.

When the vanilla result set is wanted, filter explicitly with present:

SELECT * FROM (...) t WHERE provsql.present(provenance());

present(token) is true exactly when the row is in the answer the query has without provenance tracking (the circuit evaluated in the Boolean semiring with every leaf true). Its general form, nonzero, tests the annotation against a semiring’s zero: 'boolean' as above, 'counting' for bag multiplicity, and – with semiring omitted – a universal zero test that is false only when the annotation is provably zero in every (m-)semiring under every leaf valuation, so filtering on it can never contradict any downstream evaluation. Both keep rows they cannot prove zero (and untracked rows, whose NULL token reads as the neutral 1); the cost is one circuit evaluation per candidate row.

NULL Provenance Tokens

Data NULLs are not the only NULLs around: a provenance token slot can itself be NULL, and each combinator maps a NULL token to its own neutral element:

Combinator	NULL token reads as	Situation that produces it
`provenance_times` (⊗)	1 (neutral)	untracked source in a join
`provenance_plus` (⊕)	0 (neutral)	padded/absent row’s slot in a disjunction
`provenance_monus` (⊖, right side)	0 (neutral)	antijoin with no matching right rows
`provenance_delta` (δ)	1	untracked source

The load-bearing rule: a NULL token never means “false”. Whenever a condition is unknown or fails, ProvSQL’s rewriting produces an explicit zero gate (for instance, provenance_cmp returns gate_zero when an operand is NULL) rather than letting a NULL token reach ⊗, where it would read as certainly true.

Unset Probabilities Are Certain

An input token that was never given a probability with set_prob is treated as certain (probability 1.0) by probability_evaluate and everything downstream. This is the intended convention – in typical deployments most tuples are deterministic and only a few tables are probabilistic – but note the API asymmetry: get_prob returns NULL for such a token (“never set”), while evaluation uses 1.0.

`EXCEPT ALL`: the Documented Bag Difference

Plain EXCEPT (set semantics) is a full SQL-conformance target. For EXCEPT ALL, ProvSQL deliberately implements a different multiset difference than SQL: a left row is removed entirely whenever a syntactically equal right row exists, rather than cancelling copies one-for-one (SQL’s max(0, m − n)). The reason is provenance tractability: SQL’s semantics assigns no canonical provenance to an individual surviving copy (which left copy is cancelled by which right copy is an arbitrary pairing), whereas the chosen semantics is definable row by row. The two coincide after duplicate elimination. Matching is syntactic in both readings: a NULL row on the right removes NULL rows on the left.

Empty Groups in Evaluated Worlds

The value-aware evaluators (Monte Carlo sampling, HAVING world enumeration, the moment readouts) must give each aggregate a value in worlds where its group has no contributing row. The conventions:

A HAVING comparison never passes in a world where the aggregate is NULL (no contributing row for sum/avg/min/max).
The moment readouts (expected and friends) over aggregate-valued arguments are conditional on the aggregate being defined, returning NULL only when the aggregate is defined with probability 0. sum and count are defined in every world (an empty group’s sum is the real value 0 there); min/max/avg are defined exactly when some contributing row is present.