Position of OPTIONAL influences result

[fkleedorfer]

Current Behavior

Data:

ex:car1 a ex:Car .
ex:car2 a ex:Car .
ex:car1 ex:hasColor ex:blue .

Query with trailing optional (works as expected);

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX ex: <http://example.com/>
SELECT  ?s ?o 
WHERE { 
  ?s rdf:type ex:Car .
  OPTIONAL { ?s ex:hasColor ?o . }
}
Result:
[s=http://example.com/car1;o=http://example.com/blue]
[s=http://example.com/car2]

Query with leading optional omits the second solution;

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX ex: <http://example.com/>
SELECT ?s ?o 
WHERE { 
  OPTIONAL { ?s ex:hasColor ?o . }
  ?s rdf:type ex:Car .
}
Result:
[s=http://example.com/car1;o=http://example.com/blue]

Expected Behavior

both results should be the same (ignoring ordering)

Steps To Reproduce

Self-contained reproduction class:

https://gist.github.com/fkleedorfer/71f805ddcfc9f2dc5676fe0775ed11d3

Version

4.3.6, 4.3.11

Are you interested in contributing a solution yourself?

None

Anything else?

No response

[fkleedorfer]

This was tested using the MemoryStore, i.e.

SailRepository repo = new SailRepository(new MemoryStore());

[hmottestad]

[hmottestad]

I checked the sparql validator and these two queries produce quite different plans, even after optimisation. Essentially there is a scoping issue. The ?s from the type statement isn't in scope of the optional if the optional is written first.

[hmottestad]

From the spec:

"In an optional match, either the optional graph pattern matches a graph, thereby defining and adding bindings to one or more solutions, or it leaves a solution unchanged without adding any additional bindings."

In your case the query with the optional clause first will define new solutions, but since it's before the type pattern it won't see the results from that pattern.

The reason it works when the optional is after the type pattern is because of: "or it leaves a solution unchanged without adding any additional bindings." With the optional clause first though, there won't be any solutions to leave unchanged since there are no previous solutions.

[fkleedorfer]

Are you trying to say, this works as intended? GraphDB, for one, does not agree, I believe. Will run more checks.

[fkleedorfer]

I just tested the example with jena 3.16.0 and GraphDB 10.6.2
Jena produces the same results as RDF4J, ie

---------------------
| s       | o       |
=====================
| ex:car1 | ex:blue |
| ex:car2 |         |
---------------------

and 
---------------------
| s       | o       |
=====================
| ex:car1 | ex:blue |
---------------------

GraphDB produces the results I was expecting in both cases, ie both times

---------------------
| s       | o       |
=====================
| ex:car1 | ex:blue |
| ex:car2 |         |
---------------------

[hmottestad]

From reading the spec and looking at the W3C SPARQL Validator, it looks like RDF4J and Jena are both working according to spec. GraphDB looks like they are incorrect.

[fkleedorfer]

It may be according to spec, but it is very counter-intuitive. Maybe that is why GraphDB changed it - it only invites errors without any advantage to the user whatsoever.

[hmottestad]

Try to read the query sequentially where OPTIONAL means "for the above query patterns add the following query patterns if they exist".

Might be that it's a bug with GraphDB.

[tokovach]

GraphDB deviates from the specification on this issue due to the fact that the benefit from optimizing the position of the optional outweighs the fact that if you place it first it will ignore results that do not match the pattern initially + as you mention it is the more intuitive resolution.

[frensjan]

Preferably semantics of queries are in line with the intuition of most users indeed. I don't know whether that's the case here though. For me these two queries are pretty clear and clearly different :)

"Find statements with type Car and for every statement, left-join with statements for hasColor on ?s."
or stated differently: "find cars and find they color if they have them."

?s rdf:type ex:Car .
OPTIONAL { ?s ex:hasColor ?o . }

"Find statements for hasColor and if they exist, then (inner) join with statements for type Car on ?s."
or stated differently: "find collored cars, or if there aren't any, just find cars."

{ }
OPTIONAL { ?s ex:hasColor ?o . }
?s rdf:type ex:Car .

(the { } was added in correspondence to 6.1 Optional Pattern Matching
in the SPARQL 1.1. specification).

Whether deviating from the semantics actually allows for an optimisation eludes me. You need some (minimal) extra branching perhaps for the second query, but other than that I'd say you can do the same type of (block) nested loops, hash joins or whatever it is best given the cardinalities.