Paying for Inverse Roles in Registers: Streaming Two-Way Path Queries with Copyless Transducers

Queries over knowledge graphs often need to walk an edge backwards. They follow hasParent in reverse, or look back from an observation to an earlier one. In description logics, allowing this "inverse role" is known to make reasoning much harder. On a data stream the problem is also practical: a forward-only pass cannot go back, so systems either buffer the entire stream or store every edge in both directions. This note proposes a middle route for one well-defined case. The case is two-way path queries that must return the path they walked, evaluated over linear streams such as time series, event logs, and provenance chains. We compile each such query into a streaming string transducer: a one-pass machine that keeps a fixed number of string buffers ("registers") and may append or prepend to them. The backward parts of a walk become prepend operations, so the machine never re-reads the stream.

The central claim is that on linear data, the cost of inverse roles moves from running time into register count. Specifically, the number of registers needed is governed by how many times the query's walk can cross any single position, which is bounded by its number of forward/backward reversals. The number of registers does not depend on the stream length. A second claim concerns queries whose path pattern avoids modular counting, the "star-free" patterns. For these, we conjecture the compiled machine stays inside the first-order-definable (aperiodic) class, and we test this directly. Whether aperiodicity survives the introduction of inverse roles is an open tension that no paper in our corpus addresses.

Background and what is already known

A streaming string transducer (SST) reads its input once, left to right, and updates finitely many string registers at each step. It is copyless if no register is used twice on the right-hand side of one update. That rule keeps output length linear in input length and makes equivalence decidable. Expressiveness of streaming string transducers proved that copyless SSTs compute exactly the MSO-definable string transformations, the same class as two-way deterministic transducers. Algorithmic analysis of array-accessing programs highlighted the trick we rely on: prepending ($X \leftarrow a\cdot X$) reverses data in a forward pass without copying. First-order definable string transformations refined this picture. It showed that first-order (FO) definable transformations are exactly those of aperiodic, 1-bounded SSTs, meaning SSTs whose combined state-and-register-flow monoid satisfies $x^n = x^{n+1}$, and it showed that checking aperiodicity is PSPACE-complete. FO-Definable Transformations of Infinite Strings extended the equivalence to infinite streams, including aperiodic two-way transducers with star-free look-around.

These papers supply our method and constrain our novelty. A general route from two-way machines to SSTs already exists, so we cannot claim that two-way queries over words are streamable at all. What they do not provide is a cost model tied to query structure: none of them asks how many registers a query needs as a function of how it uses inverses. None of them considers queries over relational data either.

On the knowledge-representation side, the "inverse penalty" is well documented. Inverse Roles Make Conjunctive Queries Hard showed that conjunctive queries in $\mathcal{ALCI}$ are 2-EXPTIME-complete. Conjunctive Regular Path Queries in Lightweight Description Logics showed that nested two-way regular path queries (2RPQs) push combined complexity in $\mathcal{EL}$ and DL-Lite from P to EXP-complete, using classical nested automata as acceptors. These results motivate the question of where the penalty goes when the data is linear. They also constrain our scope. Their hardness comes from tree- and graph-shaped models, and we make no claim to escape it there. Our contribution is to isolate the linear case, where the penalty can be measured cleanly as a machine resource.

Core Claim

Consider a two-way path query $q$ over a linear stream whose positions are linked by a forward role $R$ and its inverse $R^-$. The query returns, for each match, the sequence of labels along its witness walk, in walk order. Let $k(q)$ be the maximum number of times any witness walk of $q$ crosses a single stream position. For walks that do not zigzag without bound, this is at most one plus the number of direction reversals.

We claim three things. First, $q$ compiles to a copyless SST with $O(k(q))$ registers. The idea is that each crossing of a segment is built in its own register, appended if the walk crosses forward and prepended if it crosses backward. Input symbols can be written into several registers, and copylessness is never violated, because only registers, not input letters, are restricted. Second, a matching lower bound holds on explicit query families: we will prove that some queries with $k$ reversals need at least $k$ registers, using a pumping argument on register contents. Third, queries with unbounded crossing, such as $(R R^-)^*$ with witness output, have outputs that are not linearly bounded. They therefore fall outside any SST, and this marks a sharp boundary for the witness-producing setting.

The aperiodicity conjecture is the riskier part. If $q$'s label pattern over $\{R, R^-\}$ and the node tests is star-free, the compiled SST is aperiodic, and so $q$'s witness transformation is FO-definable. It is not obvious this holds. A star-free constraint on the walk is different from an aperiodic two-way machine, and a zigzag might simulate counting. This is exactly the unexplored point where inverse-role reasoning could break aperiodicity in streaming models.

We restrict the contribution to witness-producing queries on purpose. For yes/no queries, a two-way automaton over words can be converted to a one-way automaton with no registers at all, so registers would add nothing there.

Research Program

The theory component defines the crossing parameter $k(q)$ syntactically, from the query's expression, and shows it is computable. It then gives the compilation to a copyless SST with explicit state and register bounds, and proves lower bounds on parametrized families. For the aperiodicity question, we first try to prove preservation by composing the flow-monoid argument of First-order definable string transformations with the two-way characterization of FO-Definable Transformations of Infinite Strings. If a counterexample appears instead, we characterize the star-free fragment in which aperiodicity is preserved. Either outcome settles the tension noted above.

The systems component is a compiler from a SPARQL-property-path-like syntax with inverse steps to SSTs. It has two parts: an executor that processes one stream element in constant time for fixed $q$, and an automated aperiodicity checker for the compiled machines. The checker runs the PSPACE procedure on small instances and a monoid-enumeration search on larger ones. Composition of copyless SSTs is known to be delicate (Composing Copyless Streaming String Transducers), so we compile each query directly and do not compose per-step machines.

Baselines

The naive reference point is buffer-then-evaluate. The whole stream, or a sliding window of the size the query needs, is stored, and a two-way walk evaluator runs over it. This is what a system does if it ignores streaming. It is run on the same machine with the same window semantics, and it is beaten if our peak memory is bounded by pending output rather than by window length, with equal answers.

The strongest indexing competitor is the dual-table approach of FPIRPQ: Accelerating Regular Path Queries on Knowledge Graphs. It stores Path-Source-Target and Path-Target-Source tables so that inverse steps become lookups. It reports being "up to two orders of magnitude faster than Virtuoso and approximately one order of magnitude faster than KGDB" on LUBM10 to LUBM100, and "at least twice as efficient as KGDB" on DBpedia. No absolute runtimes on the 12-query micro-benchmark were found on Lacuna. We reimplement its dual indexing in the same language and runtime as our executor, give it the same memory budget, and compare on its own workloads restricted to chain-shaped queries. A fair win is lower memory and lower per-element latency on unbounded streams at equal or better throughput. Losing on static, fully loaded graphs is an acceptable outcome.

The strongest temporal competitor is MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators. Its past operators play the role of inverse steps on a time line, and it reports "speedups of 3x to 4x" over an SQL baseline on up to 150 million temporal facts. We encode our queries as DatalogMTL rules that derive witness traces and run MeTeoR on the same meteorological data. A win is throughput within the same order of magnitude together with bounded, stream-length-independent memory.

Two ablations isolate the key ingredient. The first is the generic two-way-to-SST construction implied by Expressiveness of streaming string transducers, with no crossing-aware register allocation. It tests whether our register bound matters in practice. The second is a variant that forbids prepending and must buffer reversed segments. It tests whether prepend-based reversal is really what removes the buffering.

Why not just…?

Why not just buffer the stream and run a two-way evaluator? For bounded windows this works. On bounded windows, the experiment against the buffering baseline measures whether our advantage is real or only constant-factor. The argument for streaming applies to long or unbounded windows, where buffering grows with the stream. On those windows, the SST keeps only the partial witness outputs.

Why not just materialize inverse edges, as FPIRPQ does? On static graphs, dual tables are hard to beat, and we expect to lose there. Materialization needs the data at rest and indexed, however, and it does not give a register bound or a decidable-equivalence guarantee for the query. On unbounded streams, that is where the proposed comparison should come out in our favour. If it does not, the systems half of the proposal fails, and the result reduces to the theory.

Why not just use the generic two-way-to-SST translation already in the literature? This is the real threat. If the generic translation already yields register counts close to $k(q)$ on realistic queries, our compiler adds little in practice. The first ablation settles this. The theoretical contribution, meaning the lower bounds and the aperiodicity result, stands either way, because the prior constructions do not address them.

Why not just use temporal Datalog with past operators? MeTeoR-style reasoning handles backward looks naturally. It works by materialization, though, and it returns derived facts rather than walk-ordered witnesses. Our DatalogMTL encoding of witness traces tests whether that encoding is practical, and we report it honestly if it is.

Proposed Experiments

The first decisive check is the register law. On synthetic query families with $k = 1$ to $12$ reversals, compiled register count should grow linearly in $k$ and stay flat in stream length. Peak memory should track pending output size. Queries with unbounded crossing should be rejected by the compiler, and the rejection should match the theoretical boundary.

The second check is aperiodicity. We generate star-free two-way patterns up to a fixed size, compile them, and run the monoid checker. Any non-aperiodic result from a star-free pattern is a counterexample to the conjecture, and we then extract the zigzag structure responsible. If no such result appears across the generated space, that supports the preservation proof attempt.

The third check is on real data. The meteorological dataset (397 million observations, from MeTeoR) is a natural linear stream, and look-back queries on it are the inverse steps. For graph data, we extract chain-shaped streams from LUBM10 to LUBM100 and DBpedia, and we use the chain queries of the RPQ micro-benchmark used by FPIRPQ, adding inverse steps. Metrics are throughput, per-element latency, peak memory, and register and state counts, compared against all baselines under equal hardware and equal tuning time.