FAILURE MAP
← Case archive

FA-45801 / Data systems / Open access

Recursive query joins frontier values to target rather than source · case 01

Recursive query joins frontier values to target rather than source.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

recursive-bag-frontier: Recursive query joins frontier values to target rather than source.

VERIFIED REPAIR

Preserve the stated physical representation and operation order: Evaluate a bounded recursive UNION ALL query. Anchors are integer values; each frontier value joins all rules [source,target], preserving duplicate anchors and duplicate rules. Emit [depth,value] for depth zero through max-depth, expanding only the newest frontier. Preserve anchor and rule encounter order.

Unsuccessful approach: Making rules bidirectional introduces extra derivations.

Case contract

Evaluate a bounded recursive UNION ALL query. Anchors are integer values; each frontier value joins all rules [source,target], preserving duplicate anchors and duplicate rules. Emit [depth,value] for depth zero through max-depth, expanding only the newest frontier. Preserve anchor and rule encounter order.

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:
        anchors,rules,depth_limit=d
        frontier=list(anchors); result=[[0,v] for v in frontier]
        for depth in range(1,depth_limit+1):
            next_rows=[]
            for value in frontier:
                for source,target in rules:
                    if target==value: next_rows.append(source)
            result.extend([[depth,v] for v in next_rows])
            frontier=next_rows
        return result
    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('chain frontier', solve([[1], [[1, 2], [2, 3]], 2]), [[0, 1], [1, 2], [2, 3]])
    check('duplicate anchors', solve([[1, 1], [[1, 2]], 1]), [[0, 1], [0, 1], [1, 2], [1, 2]])
    check('duplicate rules', solve([[1], [[1, 2], [1, 2]], 1]), [[0, 1], [1, 2], [1, 2]])
    check('zero depth', solve([[1], [[1, 2]], 0]), [[0, 1]])
    check('reverse nonedge', solve([[2], [[1, 2]], 1]), [[0, 2]])
    check('bounded cycle', solve([[1], [[1, 1]], 2]), [[0, 1], [1, 1], [2, 1]])
    check('empty anchor', solve([[], [[1, 2]], 2]), [])
elif N == 2:
    check('chain frontier', solve([[2], [[2, 3], [3, 4]], 2]), [[0, 2], [1, 3], [2, 4]])
    check('duplicate anchors', solve([[2, 2], [[2, 3]], 1]), [[0, 2], [0, 2], [1, 3], [1, 3]])
    check('duplicate rules', solve([[2], [[2, 3], [2, 3]], 1]), [[0, 2], [1, 3], [1, 3]])
    check('zero depth', solve([[2], [[2, 3]], 0]), [[0, 2]])
    check('reverse nonedge', solve([[3], [[2, 3]], 1]), [[0, 3]])
    check('bounded cycle', solve([[2], [[2, 2]], 2]), [[0, 2], [1, 2], [2, 2]])
    check('empty anchor', solve([[], [[2, 3]], 2]), [])
elif N == 3:
    check('chain frontier', solve([[3], [[3, 4], [4, 5]], 2]), [[0, 3], [1, 4], [2, 5]])
    check('duplicate anchors', solve([[3, 3], [[3, 4]], 1]), [[0, 3], [0, 3], [1, 4], [1, 4]])
    check('duplicate rules', solve([[3], [[3, 4], [3, 4]], 1]), [[0, 3], [1, 4], [1, 4]])
    check('zero depth', solve([[3], [[3, 4]], 0]), [[0, 3]])
    check('reverse nonedge', solve([[4], [[3, 4]], 1]), [[0, 4]])
    check('bounded cycle', solve([[3], [[3, 3]], 2]), [[0, 3], [1, 3], [2, 3]])
    check('empty anchor', solve([[], [[3, 4]], 2]), [])
elif N == 4:
    check('chain frontier', solve([[4], [[4, 5], [5, 6]], 2]), [[0, 4], [1, 5], [2, 6]])
    check('duplicate anchors', solve([[4, 4], [[4, 5]], 1]), [[0, 4], [0, 4], [1, 5], [1, 5]])
    check('duplicate rules', solve([[4], [[4, 5], [4, 5]], 1]), [[0, 4], [1, 5], [1, 5]])
    check('zero depth', solve([[4], [[4, 5]], 0]), [[0, 4]])
    check('reverse nonedge', solve([[5], [[4, 5]], 1]), [[0, 5]])
    check('bounded cycle', solve([[4], [[4, 4]], 2]), [[0, 4], [1, 4], [2, 4]])
    check('empty anchor', solve([[], [[4, 5]], 2]), [])
elif N == 5:
    check('chain frontier', solve([[5], [[5, 6], [6, 7]], 2]), [[0, 5], [1, 6], [2, 7]])
    check('duplicate anchors', solve([[5, 5], [[5, 6]], 1]), [[0, 5], [0, 5], [1, 6], [1, 6]])
    check('duplicate rules', solve([[5], [[5, 6], [5, 6]], 1]), [[0, 5], [1, 6], [1, 6]])
    check('zero depth', solve([[5], [[5, 6]], 0]), [[0, 5]])
    check('reverse nonedge', solve([[6], [[5, 6]], 1]), [[0, 6]])
    check('bounded cycle', solve([[5], [[5, 5]], 2]), [[0, 5], [1, 5], [2, 5]])
    check('empty anchor', solve([[], [[5, 6]], 2]), [])
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 fixtureActualExpectedOutcome
chain frontier[[0, 1]][[0, 1], [1, 2], [2, 3]]Failed
duplicate anchors[[0, 1], [0, 1]][[0, 1], [0, 1], [1, 2], [1, 2]]Failed
duplicate rules[[0, 1]][[0, 1], [1, 2], [1, 2]]Failed
zero depth[[0, 1]][[0, 1]]Passed
reverse nonedge[[0, 2], [1, 1]][[0, 2]]Failed
bounded cycle[[0, 1], [1, 1], [2, 1]][[0, 1], [1, 1], [2, 1]]Passed
empty anchor[][]Passed

SHA-256 / b2f60b5807d282e6c7593503bc1f326cfd2ea690ee1d5766e39333fe3d77ddae

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    try:
        anchors,rules,depth_limit=d
        frontier=list(anchors); result=[[0,v] for v in frontier]
        for depth in range(1,depth_limit+1):
            next_rows=[]
            for value in frontier:
                for source,target in rules:
                    if source==value or target==value: next_rows.append(target)
            result.extend([[depth,v] for v in next_rows])
            frontier=next_rows
        return result
    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('chain frontier', solve([[1], [[1, 2], [2, 3]], 2]), [[0, 1], [1, 2], [2, 3]])
    check('duplicate anchors', solve([[1, 1], [[1, 2]], 1]), [[0, 1], [0, 1], [1, 2], [1, 2]])
    check('duplicate rules', solve([[1], [[1, 2], [1, 2]], 1]), [[0, 1], [1, 2], [1, 2]])
    check('zero depth', solve([[1], [[1, 2]], 0]), [[0, 1]])
    check('reverse nonedge', solve([[2], [[1, 2]], 1]), [[0, 2]])
    check('bounded cycle', solve([[1], [[1, 1]], 2]), [[0, 1], [1, 1], [2, 1]])
    check('empty anchor', solve([[], [[1, 2]], 2]), [])
elif N == 2:
    check('chain frontier', solve([[2], [[2, 3], [3, 4]], 2]), [[0, 2], [1, 3], [2, 4]])
    check('duplicate anchors', solve([[2, 2], [[2, 3]], 1]), [[0, 2], [0, 2], [1, 3], [1, 3]])
    check('duplicate rules', solve([[2], [[2, 3], [2, 3]], 1]), [[0, 2], [1, 3], [1, 3]])
    check('zero depth', solve([[2], [[2, 3]], 0]), [[0, 2]])
    check('reverse nonedge', solve([[3], [[2, 3]], 1]), [[0, 3]])
    check('bounded cycle', solve([[2], [[2, 2]], 2]), [[0, 2], [1, 2], [2, 2]])
    check('empty anchor', solve([[], [[2, 3]], 2]), [])
elif N == 3:
    check('chain frontier', solve([[3], [[3, 4], [4, 5]], 2]), [[0, 3], [1, 4], [2, 5]])
    check('duplicate anchors', solve([[3, 3], [[3, 4]], 1]), [[0, 3], [0, 3], [1, 4], [1, 4]])
    check('duplicate rules', solve([[3], [[3, 4], [3, 4]], 1]), [[0, 3], [1, 4], [1, 4]])
    check('zero depth', solve([[3], [[3, 4]], 0]), [[0, 3]])
    check('reverse nonedge', solve([[4], [[3, 4]], 1]), [[0, 4]])
    check('bounded cycle', solve([[3], [[3, 3]], 2]), [[0, 3], [1, 3], [2, 3]])
    check('empty anchor', solve([[], [[3, 4]], 2]), [])
elif N == 4:
    check('chain frontier', solve([[4], [[4, 5], [5, 6]], 2]), [[0, 4], [1, 5], [2, 6]])
    check('duplicate anchors', solve([[4, 4], [[4, 5]], 1]), [[0, 4], [0, 4], [1, 5], [1, 5]])
    check('duplicate rules', solve([[4], [[4, 5], [4, 5]], 1]), [[0, 4], [1, 5], [1, 5]])
    check('zero depth', solve([[4], [[4, 5]], 0]), [[0, 4]])
    check('reverse nonedge', solve([[5], [[4, 5]], 1]), [[0, 5]])
    check('bounded cycle', solve([[4], [[4, 4]], 2]), [[0, 4], [1, 4], [2, 4]])
    check('empty anchor', solve([[], [[4, 5]], 2]), [])
elif N == 5:
    check('chain frontier', solve([[5], [[5, 6], [6, 7]], 2]), [[0, 5], [1, 6], [2, 7]])
    check('duplicate anchors', solve([[5, 5], [[5, 6]], 1]), [[0, 5], [0, 5], [1, 6], [1, 6]])
    check('duplicate rules', solve([[5], [[5, 6], [5, 6]], 1]), [[0, 5], [1, 6], [1, 6]])
    check('zero depth', solve([[5], [[5, 6]], 0]), [[0, 5]])
    check('reverse nonedge', solve([[6], [[5, 6]], 1]), [[0, 6]])
    check('bounded cycle', solve([[5], [[5, 5]], 2]), [[0, 5], [1, 5], [2, 5]])
    check('empty anchor', solve([[], [[5, 6]], 2]), [])
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 fixtureActualExpectedOutcome
chain frontier[[0, 1], [1, 2], [2, 2], [2, 3]][[0, 1], [1, 2], [2, 3]]Failed
duplicate anchors[[0, 1], [0, 1], [1, 2], [1, 2]][[0, 1], [0, 1], [1, 2], [1, 2]]Passed
duplicate rules[[0, 1], [1, 2], [1, 2]][[0, 1], [1, 2], [1, 2]]Passed
zero depth[[0, 1]][[0, 1]]Passed
reverse nonedge[[0, 2], [1, 2]][[0, 2]]Failed
bounded cycle[[0, 1], [1, 1], [2, 1]][[0, 1], [1, 1], [2, 1]]Passed
empty anchor[][]Passed

SHA-256 / 9027d0c4256b0724062e9ac006004951c49492ef7984d1b55811e988e3d0a692

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    try:
        anchors,rules,depth_limit=d
        frontier=list(anchors); result=[[0,v] for v in frontier]
        for depth in range(1,depth_limit+1):
            next_rows=[]
            for value in frontier:
                for source,target in rules:
                    if source==value: next_rows.append(target)
            result.extend([[depth,v] for v in next_rows])
            frontier=next_rows
        return result
    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('chain frontier', solve([[1], [[1, 2], [2, 3]], 2]), [[0, 1], [1, 2], [2, 3]])
    check('duplicate anchors', solve([[1, 1], [[1, 2]], 1]), [[0, 1], [0, 1], [1, 2], [1, 2]])
    check('duplicate rules', solve([[1], [[1, 2], [1, 2]], 1]), [[0, 1], [1, 2], [1, 2]])
    check('zero depth', solve([[1], [[1, 2]], 0]), [[0, 1]])
    check('reverse nonedge', solve([[2], [[1, 2]], 1]), [[0, 2]])
    check('bounded cycle', solve([[1], [[1, 1]], 2]), [[0, 1], [1, 1], [2, 1]])
    check('empty anchor', solve([[], [[1, 2]], 2]), [])
elif N == 2:
    check('chain frontier', solve([[2], [[2, 3], [3, 4]], 2]), [[0, 2], [1, 3], [2, 4]])
    check('duplicate anchors', solve([[2, 2], [[2, 3]], 1]), [[0, 2], [0, 2], [1, 3], [1, 3]])
    check('duplicate rules', solve([[2], [[2, 3], [2, 3]], 1]), [[0, 2], [1, 3], [1, 3]])
    check('zero depth', solve([[2], [[2, 3]], 0]), [[0, 2]])
    check('reverse nonedge', solve([[3], [[2, 3]], 1]), [[0, 3]])
    check('bounded cycle', solve([[2], [[2, 2]], 2]), [[0, 2], [1, 2], [2, 2]])
    check('empty anchor', solve([[], [[2, 3]], 2]), [])
elif N == 3:
    check('chain frontier', solve([[3], [[3, 4], [4, 5]], 2]), [[0, 3], [1, 4], [2, 5]])
    check('duplicate anchors', solve([[3, 3], [[3, 4]], 1]), [[0, 3], [0, 3], [1, 4], [1, 4]])
    check('duplicate rules', solve([[3], [[3, 4], [3, 4]], 1]), [[0, 3], [1, 4], [1, 4]])
    check('zero depth', solve([[3], [[3, 4]], 0]), [[0, 3]])
    check('reverse nonedge', solve([[4], [[3, 4]], 1]), [[0, 4]])
    check('bounded cycle', solve([[3], [[3, 3]], 2]), [[0, 3], [1, 3], [2, 3]])
    check('empty anchor', solve([[], [[3, 4]], 2]), [])
elif N == 4:
    check('chain frontier', solve([[4], [[4, 5], [5, 6]], 2]), [[0, 4], [1, 5], [2, 6]])
    check('duplicate anchors', solve([[4, 4], [[4, 5]], 1]), [[0, 4], [0, 4], [1, 5], [1, 5]])
    check('duplicate rules', solve([[4], [[4, 5], [4, 5]], 1]), [[0, 4], [1, 5], [1, 5]])
    check('zero depth', solve([[4], [[4, 5]], 0]), [[0, 4]])
    check('reverse nonedge', solve([[5], [[4, 5]], 1]), [[0, 5]])
    check('bounded cycle', solve([[4], [[4, 4]], 2]), [[0, 4], [1, 4], [2, 4]])
    check('empty anchor', solve([[], [[4, 5]], 2]), [])
elif N == 5:
    check('chain frontier', solve([[5], [[5, 6], [6, 7]], 2]), [[0, 5], [1, 6], [2, 7]])
    check('duplicate anchors', solve([[5, 5], [[5, 6]], 1]), [[0, 5], [0, 5], [1, 6], [1, 6]])
    check('duplicate rules', solve([[5], [[5, 6], [5, 6]], 1]), [[0, 5], [1, 6], [1, 6]])
    check('zero depth', solve([[5], [[5, 6]], 0]), [[0, 5]])
    check('reverse nonedge', solve([[6], [[5, 6]], 1]), [[0, 6]])
    check('bounded cycle', solve([[5], [[5, 5]], 2]), [[0, 5], [1, 5], [2, 5]])
    check('empty anchor', solve([[], [[5, 6]], 2]), [])
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 fixtureActualExpectedOutcome
chain frontier[[0, 1], [1, 2], [2, 3]][[0, 1], [1, 2], [2, 3]]Passed
duplicate anchors[[0, 1], [0, 1], [1, 2], [1, 2]][[0, 1], [0, 1], [1, 2], [1, 2]]Passed
duplicate rules[[0, 1], [1, 2], [1, 2]][[0, 1], [1, 2], [1, 2]]Passed
zero depth[[0, 1]][[0, 1]]Passed
reverse nonedge[[0, 2]][[0, 2]]Passed
bounded cycle[[0, 1], [1, 1], [2, 1]][[0, 1], [1, 1], [2, 1]]Passed
empty anchor[][]Passed

SHA-256 / c1863a9bff0a55f025200ea35c28f0f5d55a461911cfd34c81e35b94133db1b4

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:25.814044+00:00.

Case digest / 9ac9d8a2f9765e3a9614b2cf63e6391eb4ba7e24109756f6551363b000551098