Extending the Solution

We’re extending Stardog’s knowledge graph capabilities to include arbitrary graph algorithms that aren’t easily expressed in SPARQL. But first we have to fix SPARQL solutions.

Background

RDF is a flexible graph data model. Entities are represented by nodes in the graph. Entity properties and relationships between entities are represented as edges. Unlike relational databases where the data needs to conform to a predefined tabular structure, the graph model can represent heterogeneous data easily.

However, when we query RDF graphs with SPARQL we get the results either as a table (SELECT-queries) or as a graph with a fixed template (CONSTRUCT-queries). There’s no easy way to query a subgraph. The table representation can be the best thing, but in other cases its limitations hurt the usability of query results. As a result sometimes we need to write multiple queries to get results or spend more effort post-processing query results. The limitation can even mean writing more complicated queries than necessary.

Finding Paths

These limitations are most obvious in the case of a basic task for graphs: finding paths between nodes. SPARQL provides property paths so one can write queries that recursively traverse the RDF graph and find two nodes connected via a complex path of edges. But since the results need to be turned into a tabular format, the result of property path queries return only the start and end nodes of a path, not the intermediate nodes. In order to find intermediate nodes and edges additional and/or more complex queries are needed.

We need more flexible query results to support use cases where tabular results are not the right thing. This is exactly what we are working on right now to make future versions of Stardog go beyond tabular results for graph queries. We will next describe how we are extending SPARQL to make this possible.

Beyond Tables

SPARQL query results are defined as a list of solutions where a solution is a mapping from variable names to RDF terms. In this definition, variable names represent columns of a table and each solution corresponds to a row in the table. For example, consider a database that contains information about people, their birth dates and children. The following query returns the birth date of people along with their children:

SELECT ?person ?date ?child {
  ?person :birthDate ?date ;
          :child ?child
}

Stardog displays the results of this query in a tabular format like this:

?person | ?date      | ?child
-----------------------------------
:John   | 1974-02-17 | :Alice
:John   | 1974-02-17 | :Bob
:John   | 1974-02-17 | :Charlie
:Jane   | 1963-11-03 | :David
:Jane   | 1963-11-03 | :Eve

In these results the children of a single person are spread over multiple rows.

To go beyond tabular results we first need to change the definition of a solution such that a variable can be mapped to an array of values or to another solution. This means the definition of SPARQL solutions has to be recursive. Informally, such a definition would look like this:

(1) Solution := { (V -> Value)* }    // solution: mapping from variables to values (unchanged)
(2) Value := RDF-Term                // an RDF term is a value (unchanged)
(3) Value := Solution                // a solution is a value (extended definition)
(4) Value := [ Value* ]              // an array of values is a value (extended definition)

This definition almost exactly matches how JSON objects are defined. A JSON object is a collection of name-value pairs (see 1) where values can be atomic (see 2), an object (see 3) or an array of values (see 4).

Extending SPARQL Operators

We also need new operators in SPARQL that will generate these extended solutions. We will not perturb existing SPARQL queries. If a query does not use such operators then the results will be same as in original SPARQL definitions.

ARRAY of Values

This is the GROUP_CONCAT aggregate function done right. It outputs an array of values instead of a concatenated string, which is just horrifying to be honest!

Let’s consider the previous example of retrieving names. We can rewrite that query to group results by each person and output names as an array of solutions:

SELECT ?person (sample(?date) as ?bdate) (array(?child) AS ?children) {
  ?person :birthDate ?date ;
          :child ?child 
}
GROUP BY ?person

The result would look like this:

?person | ?bdate     | ?children
---------------------------------------------
:John   | 1974-02-17 | [:Alice, :Bob, :Charlie]
:Jane   | 1963-11-03 | [:David, :Eve]

In textual format, these results don’t look much different than what GROUP_CONCAT would produce. However, there is a big difference because now we have a structured array as the value of ?names. This means we can define functions that would operate over arrays:

• length(array): returns the number of elements in an array
• get(array, index): returns the element at the specified index in an array
• contains(array, values): returns true if the specified element exists in an array

Suppose we want to write a query that will return the eldest child for each person. Even though this sounds like an easy query it is not possible to use a combination of GROUP BY, ORDER BY and LIMIT to write this query. LIMIT defines a global limit over all solutions whereas here we want to limit the solutions for each group separately. But with arrays and functions that operate over arrays this query is simple. We can first order children by their birth date, group children by parent, and retrieve only the first child from the array of ordered children:

SELECT ?person (get(array(?child), 1) AS ?eldestChild)
{{ 
    SELECT * {
      ?person :hasChild ?child .
      ?child :birthDate ?date 
    }
    ORDER BY ?date
}}
GROUP BY ?person

From Solutions to Objects

We have seen that the array aggregate function can collect the bindings of a variable from a sequence of solutions and turn that into an array. We can also use this function to create an array of objects. This can be achieved by specifying multiple variables as input to the array function.

For example, consider we want to retrieve not only the children of a person but the birth dates of those children as well:

SELECT * {
   ?person :date ?bdate .
   { SELECT ?person (array(?child, ?date) AS ?children) {
       ?person :hasChild ?child .
       ?child :birthDate ?date 
     }
     GROUP BY ?person
   }
}

The array(?child, ?date) aggregate function constructs an object with two properties (child and date) from each row of the solutions and collects all those objects into an array that will be assigned to the children variable. It is not easy to represent these results in a tabular format so instead we illustrate how these results would look in a simplified JSON results format:

[
  {"person": ":John" ,
   "date": "1974-02-17" ,
   "children": [
        {"child": ":Alice", date: "1995-05-02"},
        {"child": ":Bob", date: "1999-09-22"},
        {"child": ":Charlie", date: "1999-09-22"}
   ]
  },     
  {"person": ":Jane" ,
   "bdate": "1963-11-03" ,
   "children": [
        {"child": ":David", date: "1992-08-12"},
        {"child": ":Eve", date: "1996-06-02"}
   ]
  }
]

Note that, as in regular SPARQL JSON results format each key represents a variable from the query, but now we have arrays and nested objects in the results.

Paths of Glory

We started this blog post by mentioning path finding in graphs. We will talk about path finding in more depth in my next blog post, but we will now briefly mention how extended solutions relate to path finding.

Suppose we are trying to find paths between people in our example graph using child relationship. The following query uses regular SPARQL property paths to check if Alice has a famous historical person as an ancestor:

SELECT * {
   :FamousHistoricalPerson :child+ :Alice
}

But, as we mentioned before, property path queries do not return intermediate nodes so you would need additional queries to find the people on the ancestral path. SPARQL property paths may be (ab)used for this purpose, but those workarounds fail when there are multiple paths between nodes and they are inherently inefficient.

Extended solutions provide an easy way to represent the results of path finding queries. Each edge of the path can be represented as an object and the path itself can be represented as an array of such objects. In our simplified JSON format, such paths would be represented as follows:

   "path": [
        {"parent": ":FamousHistoricalPerson", child: ":NotSoFamousPerson"},
        ... 
        {"parent": ":John", child: "Alice"}
   ]

Of course, we still need a special query construct that will produce paths between nodes. We will talk about such path finding extensions in my next blog post. Stay tuned.

Download Stardog today to start your free 30-day evaluation.