FedX federation fails with query evaluation exception when evaluating zero length property path

[aschwarte10]

Current Behavior

We found that the FedX query engine currently fails with the following exception when the query contains a zero length path (e.g. ?myClass rdfs:subClassOf* ?parentClass)

The exact exception message is:

Federation Strategy does not support org.openrdf.query.algebra.evaluation.TripleSource#getStatements. If you encounter this exception, please report it.

This is because the federation engine falls back to the DefaultEvaluationStrategy implementation for property paths, which in case of zero-path is not tailored to the use in federation.

Note that path with length minimum 1 (i.e. the + operator) are working fine.

Expected Behavior

The federation engine should support correct semantics of zero-length path

Steps To Reproduce

Can be reproduced with a query like (assuming data being present)

SELECT * WHERE {
    ?subClass (rdfs:subClassOf*) ?myClass

Version

4.3.x

Are you interested in contributing a solution yourself?

Yes

Anything else?

We would like to see this addressed in 4.3.x and eventually in in the 5.0 release

[conbon]

@aschwarte10 We have also encountered this issue recently on the 4.3.9 branch and carried out some initial debugging.
I'll provide what we have as additional input.

On a single fedx repository, the following was inserted:

INSERT DATA {
  GRAPH ex:graph {
    :a foaf:knows :b .
    :a a foaf:Thing .
    :b foaf:friend :c .
    :b a foaf:Thing .
    :a foaf:knows :c .
    :d foaf:friend :e .
    :d a foaf:Thing .
    :e foaf:knows :f .
    :e a foaf:Thing .
    :f foaf:knows :e .
    :f a foaf:Thing .
    :f foaf:name "test" .
    :a foaf:homepage :h .
  }
}

Queries
All of these are wrapped in SELECT * { } .

Query	Result	Comments
?s (foaf:knows|foaf:friend)+ ?o . ?s foaf:knows+ ?o .	🟢	ArbitraryLengthPath -> NUnion -> StatementSourcePattern
?s (foaf:knows|foaf:friend)* ?o .	🔴 Runtime exception	NUnion -> (ZeroLengthPath + 2x StatementSourcePattern)
?s (foaf:knows|foaf:friend)? ?o .	🔴 Runtime exception	ArbitraryLengthPath -> NUnion -> StatementSourcePattern (Failure against ZeroLengthPathIteration as above)
?s a foaf:Thing; (foaf:knows|foaf:friend)* ?o . ?s a foaf:Thing; (foaf:knows|foaf:friend)? ?o . ?s (foaf:knows|foaf:friend)* ?o; a foaf:Thing . ?s (foaf:knows|foaf:friend)? ?o; a foaf:Thing .	🟡 Sometimes completes, sometimes appears to cause evaluation deadlock and provided query timeout is hit.	NJoin of simple pattern before arbitrary length one appears to use different query evaluation path. It doesn’t appear to matter whether the simple pattern precedes or follows the prop path. In addition DISTINCT is generated for these which appears not be fully supported.

(Apologies for the lack of separation of patterns in the table above)

In addition, we have not observed any issues with property paths which do not use the / (i.e. alternative path). The alternative path (as can be seen from the above comments) is translated into a NUnion of each possible combination.

In fact, the following queries also trigger the issue, just like the alternative path modifier:

SELECT * {
  {
    ?s foaf:knows* ?o .
  } UNION {
    ?s foaf:friend* ?o .
  }
}

SELECT * {
    ?s foaf:knows+ ?o .
}

How to detect

• ? - NUnion containing ZeroLengthPath (need to check what pre-optimised query looks like)
  • Or maybe any ZeroLengthPath ?

• * - ArbitraryLengthPath (of zero or more presumably)

@vtermanis