Jump to content

Wikidata Query Service/Migration/Rewrite of GAS

From Wikitech

This document explains the logic and process for rewriting WDQS queries that use Blazegraph's GAS (Gather-Apply-Scatter) service. It recommends using QLever's Path Search service as the best alternative for migrating queries to run on the WDQS v2 backend.

The GAS service provides a server-side, graph traversal abstraction for Wikidata. Blazegraph provides GAS through a custom SPARQL service, which implements breadth-first search (BFS), single-source shortest path (SSSP), connected components (CC), and PageRank (PR) features.

Key considerations for query rewrites

To translate GAS Blazegraph functionality to SPARQL 1.1, we must consider the following:

  • Feature parity: Property paths are the closest SPARQL-native primitive for BFS traversal. Property paths support forward/reverse/alternative/sequence paths, and arbitrary-length (*, +, ?) connectivity. However, taking a property path approach to query rewrites doesn't achieve full parity with GAS, since it doesn't expose intermediate vertices, predecessor nodes, path length, and path count.
  • Timeouts: Unbounded property paths (* and +) increase the likelihood of query timeouts. Public WDQS queries timeout after 60 seconds, so the query rewrite solution must be bounded and selective.
    • For example, a GAS algorithm could retrieve graph nodes starting from a source and expanding out based on given parameters. To avoid timeout, the request should always be explicitly reformulated as "retrieve up to depth k, over this fixed property set, from these seed nodes, returning at most this much data."
    • If GAS queries omit a gas:linkType parameter, the service examines every predicate/triple in Wikidata, which would cause a Blazegraph timeout. So, the rewrite analysis below assumes that a query always specifies a path’s property/link.
  • Vendor-specific alternatives: QLever provides a Path Search service that is more performant and less cumbersome than using only SPARQL 1.1 to rewrite GAS queries. Since QLever is the backend replacement for Blazegraph in WDQS v2, this document recommends using that service to rewrite queries.

GAS classes and parameters irrelevant for Wikidata

Due to Wikidata's RDF structure, BFS and SSSP are the only traversal mechanisms available, and thus the only ones to consider in query rewrites for migration to WDQS v2. The GAS service includes three other classes: SSSP (single source shortest path), CC (connected-components) and PageRank (PR). These are either functionally equivalent to BFS, or not possible to execute on Blazegraph for Wikidata. The query rewrite analysis below also omits any GAS parameters that aren't relevant to Wikidata.

Expand for more details
  • SSSP: The Blazegraph implementation defines edge "weights" by reading link attributes from RDR-encoded statements (reification-done-right)[1]. But, there are no RDR statements in Wikidata. Every edge is a normal subject-predicate-object triple. Therefore, SSSP falls back to unit weights on every edge and becomes BFS.
  • CC: The algorithm's design assumes the graph is small and begins by initializing its frontier with all vertices. On a Wikidata-scale store, the initialization pass alone exceeds query timeouts. Unfortunately, the use of the gas:in parameter does nothing to scope the algorithm.
  • PR: The implementation begins as does CC, with an initialization of all vertices. Similarly, it times out on Wikidata.

GAS parameters irrelevant for Wikidata:

  • gas:nthreads: a Blazegraph-specific server parallelism hint
  • gas:linkAttrType: selects and filters traversal to edges with a specified edge property type. Appears to be tied strictly to Blazegraph’s reification-done-right (RDR) statement declaration
  • gas:scheduler not exposed in WDQS

Summary of GAS Breadth First Search (BFS) logic

Blazegraph's GAS BFS is a scatter-only, breadth-first traversal, using the following logic:

  • Begin at one or more seed vertices (defined via gas:in).
  • Follow edges (matching gas:linkType) in the direction set by the gas:traversalDirection parameter (Forward, Reverse, or Undirected).
  • Report results about each visited vertex: hop-count depth output as the variable in gas:out1, and discovery predecessor from gas:out2.

Each vertex is visited exactly once. The first execution thread to encounter a vertex "wins", and sets both depth and predecessor values for that vertex in the results. Subsequent visits to the same vertex contribute nothing to the results, which enforces shortest-path semantics for predecessors.

Queries can enforce bounds via gas:maxIterations (a hard depth cap), gas:maxVisited (caps the number of vertices visited), and gas:target with gas:maxIterationsAfterTargets. The latter is the only mechanism that gives early termination -- but only when the execution reaches specific target endpoints[2].

The following table presents the GAS service parameters:

Parameter Type Effect
gas:in Multi-valued IRI/QID Initial frontier
gas:linkType Single-valued PID Edge predicate defining the path
gas:traversalDirection Enum: Forward, Reverse, Undirected Edge direction
gas:maxIterations Integer Number of iterations/depth
gas:Target Multi-valued IRI/QID Output filter
gas:maxIterationsAfterTargets Integer Early termination if a target is defined and found
gas:maxVisited Integer Number of vertices visited[3]
gas:out Variable IRI of a visited vertex
gas:out1 Variable Depth of the visited vertex
gas:out2 Variable Predecessor IRI for a visited vertex

A GAS service query takes the form: 

SERVICE gas:service {
    gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ;
                gas:in <seed_iri> ;                   # May be more than 1
                gas:linkType <predicate_iri> ;   
                gas:traversalDirection "Forward" ;    # Default
                gas:maxIterations 5 ;                 # Valuable to specify a limit
                gas:target <target_iri> ;             # Optional, may be > 1
                gas:maxIterationsAfterTargets 0 ;     # Only relevant with gas:target
                gas:out      ?vertex ;
                gas:out1     ?depth ;
                gas:out2     ?predecessor .
}

The following sections discuss the considerations involved in rewriting GAS queries using QLever’s Path Search service.

Parameters

In many respects, rewriting with Path Search is straightforward, due to a logical correspondence between the Path Search parameters and GAS parameters:

GAS QLever Analog Comments
gas:in <QID> pathSearch:source <QID> Required for both
gas:out2 ?predecessor pathSource:start ?predecessor Required for QLever; Note that for GAS, at depth 0, ?predecessor = ":in" QID
gas:target <QID> pathSearch:target <QID> Optional for both; Can be multi-valued but has processing implications for QLever[4]
gas:out ?vertex pathSearch:end ?vertex Required for both
gas:linkType <PID> Nested subquery binding - ?predecessor <PID> ?vertex Required, single-valued for GAS
gas:out1 ?depth pathSearch:edgeColumn ?edge depth[5] = QLever’s ?edge + 1
gas:maxIterations # pathSearch:maxDepth # 5 or less[6]
pathSearch:pathColumn ?p Must be specified in the query, but is unused

Algorithms

The GAS and Path Search algorithms are fundamentally different: GAS uses a breadth-first search approach, limiting its path traversal by the first encounter of a node. Path Search takes a depth-first approach, and is only limited by its target and/or maxDepth parameter values.

Result sets

GAS results are the set of visited vertices, with shortest-path metadata: one row per vertex, ties silently broken, non-shortest paths invisible.

Path Search walks each path to maxDepth before backtracking, and its results enumerate each path. A vertex reachable by N different paths appears in N rows. The result is therefore a bag of paths, including non-shortest ones up to the maxDepth bound. This would also be the result of a SPARQL 1.1-compliant query.

GAS query rewrite pattern

To achieve equivalence with GAS, apply the following processing pattern (using SPARQL 1.1 and/or Path Search):

  1. Get the paths up to N depth.
  2. For each vertex, find MIN(depth) across all paths reaching it.
  3. Filter to keep only paths at that minimum depth (or equivalently: filter at MIN(depth) per vertex).
  4. SAMPLE (or otherwise pick one) predecessor from the surviving paths.
  5. Return the vertex, depth, and predecessor based on the SAMPLE vertex.

The rest of this document provides examples and more specific analyses for each part of this rewrite pattern. For a functional implementation of rewrite logic, see the Wikidata Query Rewriter Tool and examples in GitLab.

Reachability and depth

This section examines a request to find the children/grandchildren/great-grandchildren/… (P40) of a person (Q9682, Queen Elizabeth). The Blazegraph query is: 

SELECT ?vertex ?depth WHERE {
    SERVICE gas:service {
       gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ;
                  gas:in wd:Q9682 ;            
                  gas:linkType wdt:P40 ;   
                  gas:maxIterations 5 ; 
                  gas:out ?vertex ;                   
                  gas:out1 ?depth }
 } ORDER BY ?depth

A subset of the results (27 results in total) is:

vertex depth
wd:Q9682 0
wd:Q43274 1
wd:Q151754 1
wd:Q154920 1
wd:Q153300 1
wd:Q344408 2
wd:Q165709 2
wd:Q36812 2
wd:Q147663 2
wd:Q165657 2
wd:Q550183 2
wd:Q680304 2
wd:Q152316 2
wd:Q13590412 3
wd:Q62938826 3
wd:Q106153177 3

In total, there are 3 levels of child, grandchild, and great-grandchild from wd:Q9682 (Elizabeth II), but the query defined a limit (maxIterations) of 5. The GAS algorithm simply ran out of nodes to explore using the P40 predicate.

An equivalent SPARQL 1.1 query is not feasible if there is no limit on depth:

  • The query will be so deep as to exceed the 60 second timeout,
  • Or, if explicitly rewritten (wdt:P40/wdt:P40/wdt:P40/…/wdt:P40, the author will tire of defining the depth.

For a simple query like the one above, which is known to have a limited path, we can rewrite the query using a property path approach: 

SELECT DISTINCT ?vertex WHERE {
    wd:Q9682 wdt:P40* ?vertex 
}

But, this fails because it is not possible to get the depth variable. If you're only interested in the vertices, this is sufficient.

Note Note: The property path * includes zero-length paths. So, it includes the initial gas:in value (which GAS reports as depth 0). If you change the property path to +, then the subject node (in this case, wd:Q9682) is not reported.

To achieve equivalent results with MINIMUM depth and to return the gas:in value, we must explicitly rewrite the query as: 

SELECT ?vertex (MIN(?d) AS ?depth) WHERE {
    { { BIND(wd:Q9682 AS ?vertex) . BIND(0 AS ?d) }
      UNION { wd:Q9682 wdt:P40 ?vertex . BIND(1 AS ?d) }
      UNION { wd:Q9682 wdt:P40/wdt:P40 ?vertex . BIND(2 AS ?d) }
      UNION { wd:Q9682 wdt:P40/wdt:P40/wdt:P40 ?vertex . BIND(3 AS ?d) }
      UNION { wd:Q9682 wdt:P40/wdt:P40/wdt:P40/wdt:P40 ?vertex . BIND(4 AS ?d) }
      UNION { wd:Q9682 wdt:P40/wdt:P40/wdt:P40/wdt:P40/wdt:P40 ?vertex . BIND(5 AS ?d) } }
} GROUP BY ?vertex ORDER BY ?depth

On QLever, running this query, the same 27 results were returned.

Performing the same rewrite using Path Search, the query becomes: 

PREFIX pathSearch: <https://qlever.cs.uni-freiburg.de/pathSearch/>
SELECT ?vertex (MIN(?d) AS ?depth) WHERE {
  { { BIND(wd:Q9682 AS ?vertex) . BIND (0 AS ?d) }     # Binding at depth 0 is still needed
    UNION
    { SERVICE pathSearch: {
        _:p pathSearch:algorithm  pathSearch:allPaths ;
            pathSearch:source wd:Q9682 ;
            pathSearch:maxDepth 5; 
            pathSearch:start ?predecessor ;  
            pathSearch:end ?vertex ;
            pathSearch:pathColumn ?pc ;
            pathSearch:edgeColumn ?edge .
        { SELECT * WHERE { ?predecessor wdt:P40 ?vertex . } } }   # Defines "path"
        BIND(?edge + 1 AS ?d) } }
} GROUP BY ?vertex ORDER BY ?depth

This query ran in shorter time and returned the same 27 results.

You could simplify this query if you don't need depth=0 binding, if you can accept edge = depth -1 , or if all possible paths (versus shortest path) are sufficient.

Note Note: You must define the traversed edge for the path. In GAS, you do this by specifying the gas:linkType. In QLever, specify the predicate of a subquery nested in the SERVICE request[7].

Traversal direction

The following parameters define traversal direction in a GAS query:

  • gas:traversalDirection "Forward"
  • gas:traversalDirection "Reverse"
  • gas:traversalDirection "Undirected"

To achieve the equivalent results using SPARQL 1.1, change the property path expression. The corresponding paths are:

  • Forward:
    • start_QID wdt:P40* ?vertex
    • or start_QID wdt:P40/…/wdt:P40 ?vertex
  • Reverse:
    • start_QID ^wdt:P40* ?vertex
    • or start_QID ^wdt:P40/…/^wdt:P40 ?vertex,
    • or handle by reversing the subject and object[8] - ?vertex wdt:P40* start_QID)
  • Undirected:
    • start_QID (wdt:P40|^wdt:P40)* ?vertex
    • or start_QID (wdt:P40|^wdt:P40)/…/(wdt:P40|^wdt:P40) ?vertex

As noted above, the property path * always includes the source node.

To achieve the results using Path Search, the nested subquery is changed. The corresponding subqueries are:

  • Forward: { SELECT * WHERE { ?predecessor wdt:P40 ?vertex . } }
  • Reverse: { SELECT * WHERE { ?vertex wdt:P40 ?predecessor . } }
  • Undirected: { SELECT * WHERE { { ?predecessor wdt:P40 ?vertex } UNION { ?vertex wdt:P40 ?predecessor } } }

Predecessor approximation

In BFS, a "predecessor" is the parent vertex that causes another node to be included in the traversal path (e.g., the node through which the new vertex was first encountered).

Using GAS, one defines a request for predecessors by adding gas:out2 ?predecessor ; to the query from above, as well as adding ?predecessor to the SELECT variables.

The results for this modified query are shown below (still 27 results):

vertex predecessor depth
wd:Q9682 0
wd:Q43274 wd:Q9682 1
wd:Q151754 wd:Q9682 1
wd:Q154920 wd:Q9682 1
wd:Q153300 wd:Q9682 1
wd:Q344908 wd:Q151754 2
wd:Q165709 wd:Q153330 2
wd:Q36812 wd:Q43274 2
wd:Q147663 wd:Q151754 2
wd:Q165657 wd:Q153330 2
wd:Q550183 wd:Q154920 2
wd:Q680304 wd:Q154920 2
wd:Q152316 wd:Q43274 2
wd:Q13590412 wd:Q36812 3
wd:Q106153177 wd:Q147663 3
wd:Q62938826 wd:Q152316 3
wd:Q18002970 wd:Q36812 3
wd:Q107125551 wd:Q152316 3
wd:Q131934987 wd:Q165657 3

SPARQL 1.1 can't produce equivalent results in all cases. It can, however, produce a close "approximation". We need approximations when the property path traversal can encounter a node several times: at different "depths", with different predecessors. As noted, GAS returns the first encounter[9].

To create the most precise "approximation", you must define the equivalent SPARQL 1.1 query with an embedded SELECT statement. This returns the first occurrence of a node (which is accomplished with the MIN(...) binding). Then, use SAMPLE to guarantee that you return a single predecessor (because again, there could be duplicates). The situation is further complicated because you need to return a single predecessor from the minimum depth. To do this, add a FILTER constraint to force the depth at which the predecessor is selected to be the same as the minimum depth.

Restating the above, Blazegraph BFS picks one predecessor per visited vertex (the one that first caused the visit). But, the SPARQL SAMPLE predecessor returns one of any of "the predecessors at minimum depth". This is valid as first-discovery semantics, but may differ from Blazegraph's choice when multiple parents tie at the minimum depth.

Taking all this into consideration, the final SPARQL query is written as: 

SELECT ?vertex ?depth (SAMPLE(?pred) AS ?predecessor) WHERE {
    { SELECT ?vertex (MIN(?d1) AS ?depth) WHERE {
        {{ BIND(wd:Q9682 AS ?vertex) . BIND(0 AS ?d1) }
         UNION { wd:Q9682 wdt:P40 ?vertex . BIND(1 AS ?d1) }
         UNION { wd:Q9682 wdt:P40/wdt:P40 ?vertex . BIND(2 AS ?d1) }
         UNION { wd:Q9682 wdt:P40/wdt:P40/wdt:P40 ?vertex . BIND(3 AS ?d1) }}
      } GROUP BY ?vertex          # Get minimum depth per vertex
    }
    {{ BIND(wd:Q9682 AS ?vertex). BIND (0 AS ?d2). }
     UNION { wd:Q9682 wdt:P40 ?vertex . BIND(1 AS ?d2) . BIND(wd:Q9682 AS ?pred) }
     UNION { wd:Q9682 wdt:P40 ?v1 . ?v1 wdt:P40 ?vertex . 
                    BIND(2 AS ?d2) . BIND(?v1 AS ?pred) }
     UNION { wd:Q9682 wdt:P40/wdt:P40 ?v2 . ?v2 wdt:P40 ?vertex .
                    BIND(3 AS ?d2) . BIND(?v2 AS ?pred) }
    }      # Get all paths 3 levels deep
    FILTER(?d2 = ?depth)      # Filter paths that are not the minimum depth
  } GROUP BY ?vertex ?depth ORDER BY ?depth

Which returns the same 27 values in the same order.

How would we rewrite a query when the traversal direction is "Reverse"? When the GAS query is reversed, it's especially valuable to include a maxIterations limit to bound the results. (In the following example, we'll use 3 for ease of rewriting the queries). This makes sense if we consider the intent of the query: in the forward direction, the request is for the children of Queen Elizabeth II (a small, bounded group). But, in the reverse direction, it asks about Elizabeth II’s complete ancestry path (not a small group!).

This GAS query outputs 15 results up to depth 3.

When rewritten, the query can take one of two forms depending on whether you use the inverse property path (^), or reverse the order of the subject/object values of the triples:

  • For the first case (using ^), the query is the same, but wdt:P40 is replaced by ^wdt:P40. This outputs the same 15 results.
  • In the second case (reversing the subject/object variables), the query becomes:
SELECT ?vertex ?depth (SAMPLE(?pred) AS ?predecessor) WHERE {
 { SELECT ?vertex (MIN(?d1) AS ?depth) WHERE {
     {  { BIND(wd:Q9682 AS ?vertex) . BIND(0 AS ?d1) }
      UNION { ?vertex wdt:P40 wd:Q9682 . BIND(1 AS ?d1) }
      UNION { ?vertex wdt:P40/wdt:P40 wd:Q9682 . BIND(2 AS ?d1) }
      UNION { ?vertex wdt:P40/wdt:P40/wdt:P40 wd:Q9682 . BIND(3 AS ?d1) } }
   } GROUP BY ?vertex
 }
 {  { BIND(wd:Q9682 AS ?vertex) . BIND(0 AS ?d2) }
  UNION { ?vertex wdt:P40 wd:Q9682 .
          BIND(1 AS ?d2) . BIND(wd:Q9682 AS ?pred) }
  UNION { ?vertex wdt:P40 ?v1 . ?v1 wdt:P40 wd:Q9682 .
          BIND(2 AS ?d2) . BIND(?v1 AS ?pred) }
  UNION { ?vertex wdt:P40 ?v1 . ?v1 wdt:P40 ?v2 . ?v2 wdt:P40 wd:Q9682 .
          BIND(3 AS ?d2) . BIND(?v1 AS ?pred) }
 }
 FILTER(?d2 = ?depth)
} GROUP BY ?vertex ?depth ORDER BY ?depth

This may seem equivalent, but the variable ?v1 is bound as the predecessor at all depths of 2 or more! Consider the semantics: at depth 3:

  • With ^: The predecessor is ?v2, where the chain is Q9682 → v1 → v2 → vertex and BFS depths are 0, 1, 2, 3.
  • Without ^: The chain is vertex → v1 → v2 → Q9682 and BFS depths run 3, 2, 1, 0. The predecessor of the ?vertex node is always ?v1 (and this is true for all depths >= 3).

The second syntax (reversing the subject/object) is typically more performant than using the inverse property path (^). However, it can be difficult as a query author to remember to consider the direction of traversal.

When performing the rewrite using Path Search, we don't need MIN() and SAMPLE(), since a node can have several distinct parents among its paths.

Using Path Search, the "forward" direction query is structurally similar to the SPARQL 1.1 definition: 

PREFIX pathSearch: <https://qlever.cs.uni-freiburg.de/pathSearch/>
SELECT DISTINCT ?vertex ?depth (SAMPLE(?pred) AS ?predecessor) WHERE {
   { SELECT ?vertex (MIN(?d1) AS ?depth) WHERE {
       { SERVICE pathSearch: {
           _:p pathSearch:algorithm pathSearch:allPaths ;
                 pathSearch:source wd:Q9682 ;
                 pathSearch:maxDepth 3;  
                 pathSearch:start ?pred ; 
	    pathSearch:end ?vertex ;
                 pathSearch:pathColumn ?pc ; 
	    pathSearch:edgeColumn ?edge .
            { SELECT * WHERE { ?pred wdt:P40 ?vertex . } } }
         BIND(?edge + 1 AS ?d1) 
      }
      UNION { BIND(wd:Q9682 AS ?vertex) BIND(0 AS ?d1) }
    } GROUP BY ?vertex }
   { { SERVICE pathSearch: {
         _:p pathSearch:algorithm pathSearch:allPaths ;
               pathSearch:source wd:Q9682 ;
               pathSearch:maxDepth 3; 
               pathSearch:start ?pred ; 
	  pathSearch:end ?vertex ;
               pathSearch:pathColumn ?pc ; 
	  pathSearch:edgeColumn ?edge .
          { SELECT * WHERE { ?pred wdt:P40 ?vertex . } } }
       BIND(?edge + 1 AS ?d2) 
    }
    UNION { BIND(wd:Q9682 AS ?vertex) BIND(0 AS ?d2) } }  
  FILTER(?d2 = ?depth)
} GROUP BY ?vertex ?depth ORDER BY ?depth

For the query above, note the following:

  • Reporting the predecessor is "free" in Path Search since it is the pathSearch:start variable.
  • It isn't necessary to explicitly define intermediate nodes (Q9682 → ?v1 → ?v2 → …), because Path Search carries each edge's source.
  • The starting/source node has no predecessor in the GAS service results. Therefore, the depth-0 UNION branch only binds the variables, ?out and ?d2, but leaves the ?pred variable unbound; SAMPLE(?pred) yields null for Q9682.
  • Although the above is complex, both SERVICE pathSearch definitions are exactly the same, making the rewrite straightforward.

As an added benefit, we don't need to worry about the "reverse" query, since it is constructed by switching the subject and object variables in the nested subquery (?vertex wdt:P40 ?pred).

Considering GAS target

An additional, possible parameter to the above GAS BFS queries is gas:target. This addition returns only those paths that include the "target" node(s) - leading from the ‘target’ back to the "in"/starting node.

In SPARQL 1.1, it's not possible to define a traversal path from a source to a specific target, because we can't stop query execution at a given target. Searching for a target (or multiple targets) has to be performed after the query has completed and returned its results.

Filtering for a specific target relies entirely on the predecessor results. We must do this on the client-side by following these steps:

  1. Execute the rewritten query specified above.
  2. Check whether the TARGET node appears in the results.
  3. If yes, start at the TARGET.
  4. Repeatedly follow the predecessor nodes until you reach the starting node.
  5. Keep only those vertices.

For example, if you have a result that appears as:

?vertex ?depth ?predecessor
A 0
B 1 A
C 1 A
D 2 B
E 2 C
F 3 D
G 4 F

If gas:target is F, the path to the target is: A -> B -> D -> F, and the reported nodes would be A, B, D, F.

Working backwards from F in a SPARQL result set, starts at the ?vertex variable = F, ?predecessor = D. Then, ?vertex = D, ?predecessor = B. Then, ?vertex = B, ?predecessor = A (the starting node).

You can define multiple gas:targets. If you do that, you would need to repeat the 5 steps above for each target.

To perform this on QLever, use the pathSearch:target parameter. It performs the same role as gas:target plus gas:maxIterationsAfterTarget, stopping the search when execution reaches the target endpoint (if the target is encountered within the specified maxIterations/maxDepth limit).

GAS multiple frontiers

GAS "frontier" is the set of nodes that participate in the next round of gather/apply/scatter steps. Basically, it is the algorithm’s working set. GAS initial frontiers are the nodes defined by service parameter gas:in. There may be more than one.

Examining a sample Blazegraph query using the gas:service with multiple frontiers: 

SELECT ?out ?depth WHERE {
    SERVICE gas:service {
      gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ;
                  gas:in wd:Q9682 ;        # Where to start
                  gas:in wd:Q42 ;        
                  gas:linkType wdt:P40 ;   # What property to follow 
                  gas:out ?out ;           # The next vertex (FORWARD traversal)
                  gas:out1 ?depth }
 } ORDER BY ?depth

This query returns the following 29 results:

out depth
http://www.wikidata.org/entity/Q42 0
http://www.wikidata.org/entity/Q9682 0
http://www.wikidata.org/entity/Q43274 1
http://www.wikidata.org/entity/Q151754 1
http://www.wikidata.org/entity/Q14623683 1
http://www.wikidata.org/entity/Q154920 1
http://www.wikidata.org/entity/Q153330 1
http://www.wikidata.org/entity/Q344908 2
http://www.wikidata.org/entity/Q165709 2
http://www.wikidata.org/entity/Q36812 2
http://www.wikidata.org/entity/Q147663 2
http://www.wikidata.org/entity/Q165657 2
http://www.wikidata.org/entity/Q550183 2
http://www.wikidata.org/entity/Q680304 2
http://www.wikidata.org/entity/Q152316 2
http://www.wikidata.org/entity/Q13590412 3
http://www.wikidata.org/entity/Q106153177 3
http://www.wikidata.org/entity/Q62938826 3
http://www.wikidata.org/entity/Q18002970 3
http://www.wikidata.org/entity/Q107125551 3
http://www.wikidata.org/entity/Q131934987 3
http://www.wikidata.org/entity/Q3077944 3
http://www.wikidata.org/entity/Q38668629 3
http://www.wikidata.org/entity/Q28536747 3
http://www.wikidata.org/entity/Q63676181 3
http://www.wikidata.org/entity/Q5921597 3
http://www.wikidata.org/entity/Q119133052 3
http://www.wikidata.org/entity/Q105597990 3
http://www.wikidata.org/entity/Q108703114 3


The results above illustrate that this query is useful for retrieving a list of all descendants, but doesn't provide any information on the family tree (the starting node) to which the descendent belongs. This is important when there are multiple starting nodes. Also, the query results don't indicate if a descendant occurs in both trees, since GAS returns only the first encounter.

Adding a ?predecessor variable helps, but past the first generation, it still requires work to assemble the complete tree.

Rewriting the query as follows provides an equivalent query and also indicates the initial/starting node: 

SELECT ?fromSeed ?out (MIN(?d) AS ?depth) WHERE {
    VALUES ?fromSeed { wd:Q9682 wd:Q42 }             # Specifying the gas:in seeds
    {{ VALUES ?fromSeed { wd:Q9682 wd:Q42 } BIND(?fromSeed AS ?out) . BIND(0 AS ?d) }
     UNION { ?fromSeed wdt:P40 ?out . BIND(1 AS ?d) }
     UNION { ?fromSeed wdt:P40/wdt:P40 ?out . BIND(2 AS ?d) }
     UNION { ?fromSeed wdt:P40/wdt:P40/wdt:P40 ?out . BIND(3 AS ?d) }}
} GROUP BY ?fromSeed ?out ORDER BY ?depth

Note Note: It's still necessary to limit and explicitly define the query depth.

It is important to note that the VALUES statement is repeated in the query since a variable within a UNION branch cannot see a binding (or VALUES for it) defined outside the UNION. You must bring the variable into the branch's scope.

A portion of the result set (29 members) is shown below:

?vertex ?out ?depth
Q9682 Q9682 0
Q42 Q42 0
Q9682 Q43274 1
Q42 Q14623683 1
Q9682 Q151754 1
Q9682 Q153330 1
Q9682 Q154920 1
Q9682 Q165709 2
Q9682 Q680304 2
Q9682 Q550183 2
Q9682 Q36812 2
Q9682 Q344908 2
Q9682 Q165657 2
Q9682 Q152316 2
Q9682 Q147663 2
Q9682 Q105597990 3
Q9682 Q18002970 3

The query rewrite above gives additional results, since it reports per-seed values. So, a descendant reachable from both of the seeds (Q42 and Q9682) would appear twice, once per seed. (Given that the seeds are Elizabeth II and Douglas Adams, this is very unlikely.) GAS results would merge the trees and report each descendant once with one of the predecessors. In this case, the rewrite intentionally produces a more-informative per-seed output.

Similarly, this query can be written using Path Search. The rewrite is: 

PREFIX pathSearch: <https://qlever.cs.uni-freiburg.de/pathSearch/>
SELECT ?fromSeed ?out (MIN(?d) AS ?depth) WHERE {
  { SERVICE pathSearch: {
       _:p pathSearch:algorithm  pathSearch:allPaths ;
             pathSearch:source wd:Q9682 ;       # Two sources
             pathSearch:source wd:Q42 ; 
             pathSearch:maxDepth 3; 
             pathSearch:start  ?fromSeed ;     
             pathSearch:end ?out ;
             pathSearch:pathColumn ?pc ; 
             pathSearch:edgeColumn ?edge .
       { SELECT * WHERE { ?fromSeed wdt:P40 ?out . } } }
    BIND(?edge + 1 AS ?d) }
  # Each source at depth 0
  UNION { VALUES ?fromSeed { wd:Q9682 wd:Q42 }
                 BIND(?fromSeed AS ?out) . BIND(0 AS ?d) }
} GROUP BY ?fromSeed ?out ORDER BY ?depth

It returns the same 29 results.

Footnotes

  1. ↑ Reification-Done-Right uses Blazegraph’s "quoted-triple" syntax - <<?s ?p ?o>> - to reference a triple statement and then define properties of that statement (such as starting date). For example, <<wd:Q43274 wdt:P26 wd:Q9685>> pq:P580 "1981-07-29T00:00:00Z" can be translated as "the statement that Charles married Diana has a start date of 29 July 1981". Alternatively, Wikidata only uses standard reification practices to define a statement and then the properties of that statement - e.g., wd:Q43274 p:P26 stmt_IRI . stmt_IRI ps:P26 wd:Q9685 . stmt_IRI pq:P580 "1981-07-29T00:00:00Z".
  2. ↑ If a query supplies gas:target without gas:maxIterationsAfterTargets, the algorithm runs until termination and then prunes the results, walking backwards from each target to a seed, retaining only vertices along those paths. (This acts as a post-processing filter.) With maxIterationsAfterTargets, the algorithm actively terminates if the target is encountered.
  3. ↑ Dropped as it is incompatible with QLever algorithm.
  4. ↑ If multiple start AND target QIDs are defined, these should be paired and pathSearch:cartesian false added as a parameter to limit an explosion in the number of paths.
  5. ↑ edge != depth because (a) an edge is a hop between two node-depths, off by one from the starting node, and (b) edgeColumn defines the position in each path. To recover BFS-style depth, two corrections are needed: take the end node's edge + 1, then MIN(...) over all paths to the node.
  6. ↑ The initial gate depth is 5. This value may be changed in the future, and/or larger depth values allowed for authorized users. If a value >= 6 is specified, it is reset to 5.
  7. ↑ Although the subquery can be more complex than a single triple pattern, only a single triple is needed for equivalency with Blazegraph’s single gas:linkType parameter.
  8. ↑ Reversing the subject and object may improve performance but can cause semantic complications - as discussed next. This needs to be taken into consideration.
  9. ↑ However, with a change to the underlying RDF triples, the first encounter also has the possibility to change.
Retrieved from "https://wikitech.wikimedia.org/w/index.php?title=Wikidata_Query_Service/Migration/Rewrite_of_GAS&oldid=2456502"