FA-45816 / Data systems / Open access
Interval join admits intervals before their start · case 01
Interval join admits intervals before their start.
ROOT CAUSE
interval-join-sweep: Interval join admits intervals before their start.
VERIFIED REPAIR
Preserve the stated physical representation and operation order: Join probe points [id,key,time] to interval rows [id,key,start,end] under start<=time<end and ordinary non-null key equality. Emit probe-major [probe-id,interval-id] pairs, with matching intervals ordered by (start,id). Empty intervals never match; overlapping intervals all produce rows.
Unsuccessful approach: Switching to a strict start instead drops newly active intervals.
Case contract
Join probe points [id,key,time] to interval rows [id,key,start,end] under start<=time<end and ordinary non-null key equality. Emit probe-major [probe-id,interval-id] pairs, with matching intervals ordered by (start,id). Empty intervals never match; overlapping intervals all produce 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:
points,intervals=d
out=[]
for ident,key,time in points:
candidates=sorted(intervals,key=lambda r:(r[2],r[0]))
for other,k,start,end in candidates:
if key is None or key!=k: continue
if time<end:
out.append([ident,other])
return out
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('end expired', solve([[[10, 'a', 3]], [[20, 'a', 1, 3]]]), [])
check('start active', solve([[[10, 'a', 1]], [[20, 'a', 1, 3]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 1]], [[20, 'a', 2, 4]]]), [])
check('overlap order', solve([[[10, 'a', 3]], [[20, 'a', 2, 5], [21, 'a', 1, 4]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 2]], [[20, 'b', 1, 4], [21, None, 1, 4]]]), [])
check('empty interval', solve([[[10, 'a', 1]], [[20, 'a', 1, 1]]]), [])
check('null probe', solve([[[10, None, 2]], [[20, None, 1, 4]]]), [])
elif N == 2:
check('end expired', solve([[[10, 'a', 4]], [[20, 'a', 2, 4]]]), [])
check('start active', solve([[[10, 'a', 2]], [[20, 'a', 2, 4]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 2]], [[20, 'a', 3, 5]]]), [])
check('overlap order', solve([[[10, 'a', 4]], [[20, 'a', 3, 6], [21, 'a', 2, 5]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 3]], [[20, 'b', 2, 5], [21, None, 2, 5]]]), [])
check('empty interval', solve([[[10, 'a', 2]], [[20, 'a', 2, 2]]]), [])
check('null probe', solve([[[10, None, 3]], [[20, None, 2, 5]]]), [])
elif N == 3:
check('end expired', solve([[[10, 'a', 5]], [[20, 'a', 3, 5]]]), [])
check('start active', solve([[[10, 'a', 3]], [[20, 'a', 3, 5]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 3]], [[20, 'a', 4, 6]]]), [])
check('overlap order', solve([[[10, 'a', 5]], [[20, 'a', 4, 7], [21, 'a', 3, 6]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 4]], [[20, 'b', 3, 6], [21, None, 3, 6]]]), [])
check('empty interval', solve([[[10, 'a', 3]], [[20, 'a', 3, 3]]]), [])
check('null probe', solve([[[10, None, 4]], [[20, None, 3, 6]]]), [])
elif N == 4:
check('end expired', solve([[[10, 'a', 6]], [[20, 'a', 4, 6]]]), [])
check('start active', solve([[[10, 'a', 4]], [[20, 'a', 4, 6]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 4]], [[20, 'a', 5, 7]]]), [])
check('overlap order', solve([[[10, 'a', 6]], [[20, 'a', 5, 8], [21, 'a', 4, 7]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 5]], [[20, 'b', 4, 7], [21, None, 4, 7]]]), [])
check('empty interval', solve([[[10, 'a', 4]], [[20, 'a', 4, 4]]]), [])
check('null probe', solve([[[10, None, 5]], [[20, None, 4, 7]]]), [])
elif N == 5:
check('end expired', solve([[[10, 'a', 7]], [[20, 'a', 5, 7]]]), [])
check('start active', solve([[[10, 'a', 5]], [[20, 'a', 5, 7]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 5]], [[20, 'a', 6, 8]]]), [])
check('overlap order', solve([[[10, 'a', 7]], [[20, 'a', 6, 9], [21, 'a', 5, 8]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 6]], [[20, 'b', 5, 8], [21, None, 5, 8]]]), [])
check('empty interval', solve([[[10, 'a', 5]], [[20, 'a', 5, 5]]]), [])
check('null probe', solve([[[10, None, 6]], [[20, None, 5, 8]]]), [])
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 |
|---|---|---|---|
| end expired | [] | [] | Passed |
| start active | [[10, 20]] | [[10, 20]] | Passed |
| future inactive | [[10, 20]] | [] | Failed |
| overlap order | [[10, 21], [10, 20]] | [[10, 21], [10, 20]] | Passed |
| other keys | [] | [] | Passed |
| empty interval | [] | [] | Passed |
| null probe | [] | [] | Passed |
SHA-256 / 55251c1dd0bbbaa329588eb3e7d39a7c67b52f538596deb593d60f2217b188ac
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
points,intervals=d
out=[]
for ident,key,time in points:
candidates=sorted(intervals,key=lambda r:(r[2],r[0]))
for other,k,start,end in candidates:
if key is None or key!=k: continue
if start<time and time<end:
out.append([ident,other])
return out
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('end expired', solve([[[10, 'a', 3]], [[20, 'a', 1, 3]]]), [])
check('start active', solve([[[10, 'a', 1]], [[20, 'a', 1, 3]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 1]], [[20, 'a', 2, 4]]]), [])
check('overlap order', solve([[[10, 'a', 3]], [[20, 'a', 2, 5], [21, 'a', 1, 4]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 2]], [[20, 'b', 1, 4], [21, None, 1, 4]]]), [])
check('empty interval', solve([[[10, 'a', 1]], [[20, 'a', 1, 1]]]), [])
check('null probe', solve([[[10, None, 2]], [[20, None, 1, 4]]]), [])
elif N == 2:
check('end expired', solve([[[10, 'a', 4]], [[20, 'a', 2, 4]]]), [])
check('start active', solve([[[10, 'a', 2]], [[20, 'a', 2, 4]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 2]], [[20, 'a', 3, 5]]]), [])
check('overlap order', solve([[[10, 'a', 4]], [[20, 'a', 3, 6], [21, 'a', 2, 5]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 3]], [[20, 'b', 2, 5], [21, None, 2, 5]]]), [])
check('empty interval', solve([[[10, 'a', 2]], [[20, 'a', 2, 2]]]), [])
check('null probe', solve([[[10, None, 3]], [[20, None, 2, 5]]]), [])
elif N == 3:
check('end expired', solve([[[10, 'a', 5]], [[20, 'a', 3, 5]]]), [])
check('start active', solve([[[10, 'a', 3]], [[20, 'a', 3, 5]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 3]], [[20, 'a', 4, 6]]]), [])
check('overlap order', solve([[[10, 'a', 5]], [[20, 'a', 4, 7], [21, 'a', 3, 6]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 4]], [[20, 'b', 3, 6], [21, None, 3, 6]]]), [])
check('empty interval', solve([[[10, 'a', 3]], [[20, 'a', 3, 3]]]), [])
check('null probe', solve([[[10, None, 4]], [[20, None, 3, 6]]]), [])
elif N == 4:
check('end expired', solve([[[10, 'a', 6]], [[20, 'a', 4, 6]]]), [])
check('start active', solve([[[10, 'a', 4]], [[20, 'a', 4, 6]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 4]], [[20, 'a', 5, 7]]]), [])
check('overlap order', solve([[[10, 'a', 6]], [[20, 'a', 5, 8], [21, 'a', 4, 7]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 5]], [[20, 'b', 4, 7], [21, None, 4, 7]]]), [])
check('empty interval', solve([[[10, 'a', 4]], [[20, 'a', 4, 4]]]), [])
check('null probe', solve([[[10, None, 5]], [[20, None, 4, 7]]]), [])
elif N == 5:
check('end expired', solve([[[10, 'a', 7]], [[20, 'a', 5, 7]]]), [])
check('start active', solve([[[10, 'a', 5]], [[20, 'a', 5, 7]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 5]], [[20, 'a', 6, 8]]]), [])
check('overlap order', solve([[[10, 'a', 7]], [[20, 'a', 6, 9], [21, 'a', 5, 8]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 6]], [[20, 'b', 5, 8], [21, None, 5, 8]]]), [])
check('empty interval', solve([[[10, 'a', 5]], [[20, 'a', 5, 5]]]), [])
check('null probe', solve([[[10, None, 6]], [[20, None, 5, 8]]]), [])
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 |
|---|---|---|---|
| end expired | [] | [] | Passed |
| start active | [] | [[10, 20]] | Failed |
| future inactive | [] | [] | Passed |
| overlap order | [[10, 21], [10, 20]] | [[10, 21], [10, 20]] | Passed |
| other keys | [] | [] | Passed |
| empty interval | [] | [] | Passed |
| null probe | [] | [] | Passed |
SHA-256 / d380e72adca7d601aeaed3b96ff7d2d4207d2270b2a35c0252b24b06cf2204cb
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
points,intervals=d
out=[]
for ident,key,time in points:
candidates=sorted(intervals,key=lambda r:(r[2],r[0]))
for other,k,start,end in candidates:
if key is None or key!=k: continue
if start<=time and time<end:
out.append([ident,other])
return out
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('end expired', solve([[[10, 'a', 3]], [[20, 'a', 1, 3]]]), [])
check('start active', solve([[[10, 'a', 1]], [[20, 'a', 1, 3]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 1]], [[20, 'a', 2, 4]]]), [])
check('overlap order', solve([[[10, 'a', 3]], [[20, 'a', 2, 5], [21, 'a', 1, 4]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 2]], [[20, 'b', 1, 4], [21, None, 1, 4]]]), [])
check('empty interval', solve([[[10, 'a', 1]], [[20, 'a', 1, 1]]]), [])
check('null probe', solve([[[10, None, 2]], [[20, None, 1, 4]]]), [])
elif N == 2:
check('end expired', solve([[[10, 'a', 4]], [[20, 'a', 2, 4]]]), [])
check('start active', solve([[[10, 'a', 2]], [[20, 'a', 2, 4]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 2]], [[20, 'a', 3, 5]]]), [])
check('overlap order', solve([[[10, 'a', 4]], [[20, 'a', 3, 6], [21, 'a', 2, 5]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 3]], [[20, 'b', 2, 5], [21, None, 2, 5]]]), [])
check('empty interval', solve([[[10, 'a', 2]], [[20, 'a', 2, 2]]]), [])
check('null probe', solve([[[10, None, 3]], [[20, None, 2, 5]]]), [])
elif N == 3:
check('end expired', solve([[[10, 'a', 5]], [[20, 'a', 3, 5]]]), [])
check('start active', solve([[[10, 'a', 3]], [[20, 'a', 3, 5]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 3]], [[20, 'a', 4, 6]]]), [])
check('overlap order', solve([[[10, 'a', 5]], [[20, 'a', 4, 7], [21, 'a', 3, 6]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 4]], [[20, 'b', 3, 6], [21, None, 3, 6]]]), [])
check('empty interval', solve([[[10, 'a', 3]], [[20, 'a', 3, 3]]]), [])
check('null probe', solve([[[10, None, 4]], [[20, None, 3, 6]]]), [])
elif N == 4:
check('end expired', solve([[[10, 'a', 6]], [[20, 'a', 4, 6]]]), [])
check('start active', solve([[[10, 'a', 4]], [[20, 'a', 4, 6]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 4]], [[20, 'a', 5, 7]]]), [])
check('overlap order', solve([[[10, 'a', 6]], [[20, 'a', 5, 8], [21, 'a', 4, 7]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 5]], [[20, 'b', 4, 7], [21, None, 4, 7]]]), [])
check('empty interval', solve([[[10, 'a', 4]], [[20, 'a', 4, 4]]]), [])
check('null probe', solve([[[10, None, 5]], [[20, None, 4, 7]]]), [])
elif N == 5:
check('end expired', solve([[[10, 'a', 7]], [[20, 'a', 5, 7]]]), [])
check('start active', solve([[[10, 'a', 5]], [[20, 'a', 5, 7]]]), [[10, 20]])
check('future inactive', solve([[[10, 'a', 5]], [[20, 'a', 6, 8]]]), [])
check('overlap order', solve([[[10, 'a', 7]], [[20, 'a', 6, 9], [21, 'a', 5, 8]]]), [[10, 21], [10, 20]])
check('other keys', solve([[[10, 'a', 6]], [[20, 'b', 5, 8], [21, None, 5, 8]]]), [])
check('empty interval', solve([[[10, 'a', 5]], [[20, 'a', 5, 5]]]), [])
check('null probe', solve([[[10, None, 6]], [[20, None, 5, 8]]]), [])
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 |
|---|---|---|---|
| end expired | [] | [] | Passed |
| start active | [[10, 20]] | [[10, 20]] | Passed |
| future inactive | [] | [] | Passed |
| overlap order | [[10, 21], [10, 20]] | [[10, 21], [10, 20]] | Passed |
| other keys | [] | [] | Passed |
| empty interval | [] | [] | Passed |
| null probe | [] | [] | Passed |
SHA-256 / b230bbf54b4b8850023693996f3db71aa31536ec49ce830e2c86df1c1b6856cf
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:26.018299+00:00.
Case digest / 53f06c1653986e949c52f9f9ef74cc6e03644dbdbd4c65812240d515e8f9e06f