Proper handling of the empty

[hannahbast]

@RobinTF @joka921

The "empty path" is currently not handled properly by QLever in all cases. This issue serves to document how the right handling should look like. It can be closed when this has been implemented, hopefully soon. There are two cases:

Case 1: Genuine empty path

In some cases, there is no way around computing the empty path. The most typical example is the following query, which assumes that the predicate <does_not_exist> does not exist in the graph:

SELECT * WHERE { ?x <does_not_exist>? ?y }

Note the ? after the predicate, which means that there should be a property path from ?x to ?y containing 0 or 1 edges of the predicate. Since the predicate does not exist in the graph, only the path of length 0 remains. According to the standard, the result is then equivalent to that of the following query:

SELECT DISTINCT ?x ?x WHERE { { ?x ?p ?y } UNION { ?y ?p ?x } }

That is, one row for each entity that occurs at least once as subject or object of any predicate, and each rows contains that entity twice.

Case 2: Spurious empty path

More frequently than in the case above, the query contains an occurrence of the empty path, but the empty path does not actually have to be computed and it would be too expensive (and therefore not good) to compute it. Here is an example:

SELECT * WHERE {
  wd:Q11629 wdt:P31/(wdt:P279*|wdt:P31*) ?class
}

This query is equivalent to the following query (and QLever internally indeed rewrites it to that query):

SELECT * WHERE {
  wd:Q11629 wdt:P31 ?tmp .
  { ?tmp wdt:P279* ?class } UNION { ?tmp wdt:P31* ?class }
}

Here we have one occurrences of the empty path on each side of the UNION. But it would be a mistake to compute the (potentially very many) matches because the set of bindings for ?tmp would be reduced again by the set of bindings for wd:Q11629 wdt:P31 ?tmp. Instead, the correct way to evaluate this query would be:

SELECT * WHERE {
  { wd:Q11629 wdt:P31/wdt:P279* ?class } UNION { wd:Q11629 wdt:P31/wdt:P31* ?class) }
}

Now, neither of the two sides of the UNION involve the computation of the empty path.

[RobinTF]

@hannahbast For case 2 I have a solution in the works that does more or less exactly what you proposed. But for it to work properly (works in my proof of concept) I need to be able to properly deep copy operation trees, which isn't possible yet (but I'm working on it)