FA-44626 / Data systems / Open access
Incremental join matches null join keys · case 01
Incremental join matches null join keys.
ROOT CAUSE
delta-inner-join: Incremental join matches null join keys.
VERIFIED REPAIR
Preserve the stated physical representation and operation order: Apply simultaneous signed changes to two bag relations. Emit the consolidated join delta Ldelta*Rold + Lold*Rdelta + Ldelta*Rdelta. Inputs are [key,value,weight]; ordinary non-null equality joins. Return sorted [leftvalue,rightvalue,weight] nonzero rows.
Unsuccessful approach: Treating null as a wildcard creates additional impossible matches.
Case contract
Apply simultaneous signed changes to two bag relations. Emit the consolidated join delta Ldelta*Rold + Lold*Rdelta + Ldelta*Rdelta. Inputs are [key,value,weight]; ordinary non-null equality joins. Return sorted [leftvalue,rightvalue,weight] nonzero rows.
Why this case matters
A bounded deterministic data engine model makes representation and changelog faults reproducible.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,dl,dr=d
terms=[(dl,right),(left,dr),(dl,dr)]
weights={}
for a,b in terms:
for ka,va,wa in a:
for kb,vb,wb in b:
if ka!=kb: continue
key=(va,vb)
weights[key]=weights.get(key,0)+wa*wb
return [[a,b,w] for (a,b),w in sorted(weights.items()) if w!=0]
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('simultaneous insert', solve([[], [], [['k', 1, 1]], [['k', 2, 1]]]), [[1, 2, 1]])
check('right retraction', solve([[['k', 1, 2]], [['k', 2, 1]], [], [['k', 2, -1]]]), [[1, 2, -2]])
check('left retraction', solve([[['k', 1, 1]], [['k', 2, 3]], [['k', 1, -1]], []]), [[1, 2, -3]])
check('null equality', solve([[], [[None, 2, 1]], [[None, 1, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 2, 1]], [['k', 1, 1], ['k', 1, -1]], []]), [])
check('two payloads', solve([[], [['k', 2, 1], ['k', 3, 1]], [['k', 1, 1]], []]), [[1, 2, 1], [1, 3, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 2:
check('simultaneous insert', solve([[], [], [['k', 2, 1]], [['k', 3, 1]]]), [[2, 3, 1]])
check('right retraction', solve([[['k', 2, 2]], [['k', 3, 1]], [], [['k', 3, -1]]]), [[2, 3, -2]])
check('left retraction', solve([[['k', 2, 1]], [['k', 3, 3]], [['k', 2, -1]], []]), [[2, 3, -3]])
check('null equality', solve([[], [[None, 3, 1]], [[None, 2, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 3, 1]], [['k', 2, 1], ['k', 2, -1]], []]), [])
check('two payloads', solve([[], [['k', 3, 1], ['k', 4, 1]], [['k', 2, 1]], []]), [[2, 3, 1], [2, 4, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 3:
check('simultaneous insert', solve([[], [], [['k', 3, 1]], [['k', 4, 1]]]), [[3, 4, 1]])
check('right retraction', solve([[['k', 3, 2]], [['k', 4, 1]], [], [['k', 4, -1]]]), [[3, 4, -2]])
check('left retraction', solve([[['k', 3, 1]], [['k', 4, 3]], [['k', 3, -1]], []]), [[3, 4, -3]])
check('null equality', solve([[], [[None, 4, 1]], [[None, 3, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 4, 1]], [['k', 3, 1], ['k', 3, -1]], []]), [])
check('two payloads', solve([[], [['k', 4, 1], ['k', 5, 1]], [['k', 3, 1]], []]), [[3, 4, 1], [3, 5, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 4:
check('simultaneous insert', solve([[], [], [['k', 4, 1]], [['k', 5, 1]]]), [[4, 5, 1]])
check('right retraction', solve([[['k', 4, 2]], [['k', 5, 1]], [], [['k', 5, -1]]]), [[4, 5, -2]])
check('left retraction', solve([[['k', 4, 1]], [['k', 5, 3]], [['k', 4, -1]], []]), [[4, 5, -3]])
check('null equality', solve([[], [[None, 5, 1]], [[None, 4, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 5, 1]], [['k', 4, 1], ['k', 4, -1]], []]), [])
check('two payloads', solve([[], [['k', 5, 1], ['k', 6, 1]], [['k', 4, 1]], []]), [[4, 5, 1], [4, 6, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 5:
check('simultaneous insert', solve([[], [], [['k', 5, 1]], [['k', 6, 1]]]), [[5, 6, 1]])
check('right retraction', solve([[['k', 5, 2]], [['k', 6, 1]], [], [['k', 6, -1]]]), [[5, 6, -2]])
check('left retraction', solve([[['k', 5, 1]], [['k', 6, 3]], [['k', 5, -1]], []]), [[5, 6, -3]])
check('null equality', solve([[], [[None, 6, 1]], [[None, 5, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 6, 1]], [['k', 5, 1], ['k', 5, -1]], []]), [])
check('two payloads', solve([[], [['k', 6, 1], ['k', 7, 1]], [['k', 5, 1]], []]), [[5, 6, 1], [5, 7, 1]])
check('empty change', solve([[], [], [], []]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| simultaneous insert | [[1, 2, 1]] | [[1, 2, 1]] | Passed |
| right retraction | [[1, 2, -2]] | [[1, 2, -2]] | Passed |
| left retraction | [[1, 2, -3]] | [[1, 2, -3]] | Passed |
| null equality | [[1, 2, 1]] | [] | Failed |
| cancelled delta | [] | [] | Passed |
| two payloads | [[1, 2, 1], [1, 3, 1]] | [[1, 2, 1], [1, 3, 1]] | Passed |
| empty change | [] | [] | Passed |
SHA-256 / 031558273d38272e963ade8661821e58b9640f16b4afcc99d257b85e34157825
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,dl,dr=d
terms=[(dl,right),(left,dr),(dl,dr)]
weights={}
for a,b in terms:
for ka,va,wa in a:
for kb,vb,wb in b:
if ka!=kb and ka is not None and kb is not None: continue
key=(va,vb)
weights[key]=weights.get(key,0)+wa*wb
return [[a,b,w] for (a,b),w in sorted(weights.items()) if w!=0]
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('simultaneous insert', solve([[], [], [['k', 1, 1]], [['k', 2, 1]]]), [[1, 2, 1]])
check('right retraction', solve([[['k', 1, 2]], [['k', 2, 1]], [], [['k', 2, -1]]]), [[1, 2, -2]])
check('left retraction', solve([[['k', 1, 1]], [['k', 2, 3]], [['k', 1, -1]], []]), [[1, 2, -3]])
check('null equality', solve([[], [[None, 2, 1]], [[None, 1, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 2, 1]], [['k', 1, 1], ['k', 1, -1]], []]), [])
check('two payloads', solve([[], [['k', 2, 1], ['k', 3, 1]], [['k', 1, 1]], []]), [[1, 2, 1], [1, 3, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 2:
check('simultaneous insert', solve([[], [], [['k', 2, 1]], [['k', 3, 1]]]), [[2, 3, 1]])
check('right retraction', solve([[['k', 2, 2]], [['k', 3, 1]], [], [['k', 3, -1]]]), [[2, 3, -2]])
check('left retraction', solve([[['k', 2, 1]], [['k', 3, 3]], [['k', 2, -1]], []]), [[2, 3, -3]])
check('null equality', solve([[], [[None, 3, 1]], [[None, 2, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 3, 1]], [['k', 2, 1], ['k', 2, -1]], []]), [])
check('two payloads', solve([[], [['k', 3, 1], ['k', 4, 1]], [['k', 2, 1]], []]), [[2, 3, 1], [2, 4, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 3:
check('simultaneous insert', solve([[], [], [['k', 3, 1]], [['k', 4, 1]]]), [[3, 4, 1]])
check('right retraction', solve([[['k', 3, 2]], [['k', 4, 1]], [], [['k', 4, -1]]]), [[3, 4, -2]])
check('left retraction', solve([[['k', 3, 1]], [['k', 4, 3]], [['k', 3, -1]], []]), [[3, 4, -3]])
check('null equality', solve([[], [[None, 4, 1]], [[None, 3, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 4, 1]], [['k', 3, 1], ['k', 3, -1]], []]), [])
check('two payloads', solve([[], [['k', 4, 1], ['k', 5, 1]], [['k', 3, 1]], []]), [[3, 4, 1], [3, 5, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 4:
check('simultaneous insert', solve([[], [], [['k', 4, 1]], [['k', 5, 1]]]), [[4, 5, 1]])
check('right retraction', solve([[['k', 4, 2]], [['k', 5, 1]], [], [['k', 5, -1]]]), [[4, 5, -2]])
check('left retraction', solve([[['k', 4, 1]], [['k', 5, 3]], [['k', 4, -1]], []]), [[4, 5, -3]])
check('null equality', solve([[], [[None, 5, 1]], [[None, 4, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 5, 1]], [['k', 4, 1], ['k', 4, -1]], []]), [])
check('two payloads', solve([[], [['k', 5, 1], ['k', 6, 1]], [['k', 4, 1]], []]), [[4, 5, 1], [4, 6, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 5:
check('simultaneous insert', solve([[], [], [['k', 5, 1]], [['k', 6, 1]]]), [[5, 6, 1]])
check('right retraction', solve([[['k', 5, 2]], [['k', 6, 1]], [], [['k', 6, -1]]]), [[5, 6, -2]])
check('left retraction', solve([[['k', 5, 1]], [['k', 6, 3]], [['k', 5, -1]], []]), [[5, 6, -3]])
check('null equality', solve([[], [[None, 6, 1]], [[None, 5, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 6, 1]], [['k', 5, 1], ['k', 5, -1]], []]), [])
check('two payloads', solve([[], [['k', 6, 1], ['k', 7, 1]], [['k', 5, 1]], []]), [[5, 6, 1], [5, 7, 1]])
check('empty change', solve([[], [], [], []]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| simultaneous insert | [[1, 2, 1]] | [[1, 2, 1]] | Passed |
| right retraction | [[1, 2, -2]] | [[1, 2, -2]] | Passed |
| left retraction | [[1, 2, -3]] | [[1, 2, -3]] | Passed |
| null equality | [[1, 2, 1]] | [] | Failed |
| cancelled delta | [] | [] | Passed |
| two payloads | [[1, 2, 1], [1, 3, 1]] | [[1, 2, 1], [1, 3, 1]] | Passed |
| empty change | [] | [] | Passed |
SHA-256 / d4ba488c13d9fc0c838278540ee73d1c7f50bf68d0d95e112856e835a06832da
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,dl,dr=d
terms=[(dl,right),(left,dr),(dl,dr)]
weights={}
for a,b in terms:
for ka,va,wa in a:
for kb,vb,wb in b:
if ka is None or kb is None or ka!=kb: continue
key=(va,vb)
weights[key]=weights.get(key,0)+wa*wb
return [[a,b,w] for (a,b),w in sorted(weights.items()) if w!=0]
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('simultaneous insert', solve([[], [], [['k', 1, 1]], [['k', 2, 1]]]), [[1, 2, 1]])
check('right retraction', solve([[['k', 1, 2]], [['k', 2, 1]], [], [['k', 2, -1]]]), [[1, 2, -2]])
check('left retraction', solve([[['k', 1, 1]], [['k', 2, 3]], [['k', 1, -1]], []]), [[1, 2, -3]])
check('null equality', solve([[], [[None, 2, 1]], [[None, 1, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 2, 1]], [['k', 1, 1], ['k', 1, -1]], []]), [])
check('two payloads', solve([[], [['k', 2, 1], ['k', 3, 1]], [['k', 1, 1]], []]), [[1, 2, 1], [1, 3, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 2:
check('simultaneous insert', solve([[], [], [['k', 2, 1]], [['k', 3, 1]]]), [[2, 3, 1]])
check('right retraction', solve([[['k', 2, 2]], [['k', 3, 1]], [], [['k', 3, -1]]]), [[2, 3, -2]])
check('left retraction', solve([[['k', 2, 1]], [['k', 3, 3]], [['k', 2, -1]], []]), [[2, 3, -3]])
check('null equality', solve([[], [[None, 3, 1]], [[None, 2, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 3, 1]], [['k', 2, 1], ['k', 2, -1]], []]), [])
check('two payloads', solve([[], [['k', 3, 1], ['k', 4, 1]], [['k', 2, 1]], []]), [[2, 3, 1], [2, 4, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 3:
check('simultaneous insert', solve([[], [], [['k', 3, 1]], [['k', 4, 1]]]), [[3, 4, 1]])
check('right retraction', solve([[['k', 3, 2]], [['k', 4, 1]], [], [['k', 4, -1]]]), [[3, 4, -2]])
check('left retraction', solve([[['k', 3, 1]], [['k', 4, 3]], [['k', 3, -1]], []]), [[3, 4, -3]])
check('null equality', solve([[], [[None, 4, 1]], [[None, 3, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 4, 1]], [['k', 3, 1], ['k', 3, -1]], []]), [])
check('two payloads', solve([[], [['k', 4, 1], ['k', 5, 1]], [['k', 3, 1]], []]), [[3, 4, 1], [3, 5, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 4:
check('simultaneous insert', solve([[], [], [['k', 4, 1]], [['k', 5, 1]]]), [[4, 5, 1]])
check('right retraction', solve([[['k', 4, 2]], [['k', 5, 1]], [], [['k', 5, -1]]]), [[4, 5, -2]])
check('left retraction', solve([[['k', 4, 1]], [['k', 5, 3]], [['k', 4, -1]], []]), [[4, 5, -3]])
check('null equality', solve([[], [[None, 5, 1]], [[None, 4, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 5, 1]], [['k', 4, 1], ['k', 4, -1]], []]), [])
check('two payloads', solve([[], [['k', 5, 1], ['k', 6, 1]], [['k', 4, 1]], []]), [[4, 5, 1], [4, 6, 1]])
check('empty change', solve([[], [], [], []]), [])
elif N == 5:
check('simultaneous insert', solve([[], [], [['k', 5, 1]], [['k', 6, 1]]]), [[5, 6, 1]])
check('right retraction', solve([[['k', 5, 2]], [['k', 6, 1]], [], [['k', 6, -1]]]), [[5, 6, -2]])
check('left retraction', solve([[['k', 5, 1]], [['k', 6, 3]], [['k', 5, -1]], []]), [[5, 6, -3]])
check('null equality', solve([[], [[None, 6, 1]], [[None, 5, 1]], []]), [])
check('cancelled delta', solve([[], [['k', 6, 1]], [['k', 5, 1], ['k', 5, -1]], []]), [])
check('two payloads', solve([[], [['k', 6, 1], ['k', 7, 1]], [['k', 5, 1]], []]), [[5, 6, 1], [5, 7, 1]])
check('empty change', solve([[], [], [], []]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| simultaneous insert | [[1, 2, 1]] | [[1, 2, 1]] | Passed |
| right retraction | [[1, 2, -2]] | [[1, 2, -2]] | Passed |
| left retraction | [[1, 2, -3]] | [[1, 2, -3]] | Passed |
| null equality | [] | [] | Passed |
| cancelled delta | [] | [] | Passed |
| two payloads | [[1, 2, 1], [1, 3, 1]] | [[1, 2, 1], [1, 3, 1]] | Passed |
| empty change | [] | [] | Passed |
SHA-256 / 291b0bf46542b98ea6f18cf8b7fa1210d6509a6e684673f555e3f936c139d46a
Verification & scope
Offline stipulated semantics over valid small inputs; no performance, concurrency, or production-engine conformance claim. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:44:14.069887+00:00.
Case digest / 907a02e1e61c733be6f472fe018dba5376e0b3cfa3cad7c00b902a8fa4098d14