Tables are a common form of query results, notably in SPARQL. However, due to the at structure of tables, all structure from the RDF graph is lost, and this can lead to duplications in the table contents, and di culties to interpret the results. We propose an extension of SPARQL 1.1 aggregations to get nested results, i.e. tables where cells may contain embedded tables instead of RDF terms, and so recursively.
The SPARQL query language [
Table 1 shows an excerpt of the results of the following SPARQL query on DBpedia, which retrieves lms directed by Danny Boyle, along with their music composers and actors, and also the birth year of actors. It can be observed that the table contains a lot of redundancies. For instance, the birth year of an actor is repeated for each music composer. The number of rows for a lm is ? This research is supported by ANR project PEGASE (ANR-16-CE23-0011-08). ?? Copyright c 2020 for this paper by its authors. User permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). equal to its number of music composers times its number of actors. When ordering by birth year, one needs to order rst by lm so as to keep rows grouped by lm.
The key contribution of this paper is to allow table cells to contain smaller tables instead of RDF terms. Those nested tables are obtained by allowing variables to map to sets of solution mappings, in addition to RDF terms. Tables can be deeply nested, with tables containing tables that in turn contain tables, and so on. In practice, RDF terms and nested tables are not mixed randomly inside a table. For a given column, either all cells contain an RDF term or all cells contain a nested table. Moreover, all nested tables in a column are de ned on the same variables. This means that our nested tables follow a regular schema, although more complex than that of at tables.
Table 2 is the nested version of Table 1. The main table has a single row per lm, and two of its columns, \music composers" and \actors", contain nested tables. The former column contains one-column nested tables that contain the list of music composers of each lm. The latter column contains two-columns nested tables that contain the list of actors of each lm, along with their birth year. It can be observed that the nested table does not contain redundancies anymore, and that the dependencies between columns is made explicit. Music composers and actors are dependent on the lm, but not on each other. The birth year is dependent on the actor. 2
Nested tables were proposed and formalized in relational databases, where nesting is
not only used for query results but also for data tables [
A lot of work have proposed various forms of visualization of SPARQL results (e.g.,
maps, charts) in order to help their understanding [
Our proposal is to extend the algebra and grammar of SPARQL 1.1 with a new
aggregation construct [
In the above example, Table 1 can be seen as the global multiset of solutions, and Table 2 as the expected result after applying aggregations that compute nested tables instead of RDF terms. After grouping by lm, the nested tables in column \music composers" are obtained by projecting each solution group on variable \music composer", and by removing duplicates. Similarly for column \actors" by projecting on \actor" and \birth year", by removing duplicates, and by ordering rows by birth year. To sum up, the new aggregations need at least projecting on a subset of variables, removing duplicates, and ordering results. Those computations correspond to the category of solution modi ers, which are formalized as transformations between sequences of solution modi ers, and hence as table-to-table transformations. In addition to solution modiers, we allow groupings (clause GROUP BY) in the de nition of table aggregations, and hence aggregations in the de nition of table aggregations. This makes the de nition of aggregations recursive, which enables deeply nested tables.
The main impact of the extension is that a variable may now be bound to a nested table in addition to RDF terms. For the sake of simplicity, we consider that those variables can only be used as projection variables, and produce an error when used in other contexts (e.g., in an expression).
We now extend the grammar of SPARQL 1.1 [
Aggregate ::= : : : j 'f' SelectClause SolutionModi er 'g' The ellipsis stands for existing constructs like COUNT(DISTINCT ?x). Symbol SelectClause covers projection (SELECT) and removal of duplicates (DISTINCT, REDUCED). Symbol SolutionModi er covers ordering (ORDER BY), top-k results (LIMIT) and o set (OFFSET), grouping (GROUP BY), and ltering as a solution modi er (HAVING). This production is therefore enough to cover all needed features. We add braces to delimit the aggregation construct, and also by analogy with subqueries. Indeed, our table aggregations are syntactically and semantically equivalent to subqueries where the graph pattern (clause WHERE) is implicit.
In the example on lms, the query in the extended SPARQL that returns the nested table (Table 2) is the following.
({SELECT DISTINCT ?a ?y ORDER BY ?y} AS ?as) WHERE { ?f a dbo:Film ; dbo:director dbr:Danny_Boyle ; dbo:musicComposer ?mc ; dbo:starring ?a .
?a dbo:birthYear ?y . } GROUP BY ?f
Clause GROUP BY ?f de nes the groups of solutions over which the two table aggregations are evaluated. Variable ?mcs holds the list of distinct music composers for each lm, a one-column nested table. Variable ?as holds the list of distinct actors and their birth year, in increasing order of birth year, a two-column nested table.
Note that nothing forbids to combine term aggregations with table aggregations. For example, in the above query, one could add the term aggregation (COUNT(DISTINCT ?a) AS ?na) in order to add a column giving the number of actors, for each lm, in addition to their list. If those lists are too long, they can be bounded in size by adding a LIMIT clause in the table aggregations.
To illustrate deeply nested tables and top-k results, we extend the above query to get the lists of spouses of each actor as tables nested into the actor tables. We also add a LIMIT to get only the three top actors per lm.
WHERE { ?f a dbo:Film ; dbo:director dbr:Danny_Boyle ; dbo:musicComposer ?mc ; dbo:starring ?a .
?a dbo:birthYear ?y ; dbo:spouse ?sp } GROUP BY ?f
It can be observed in the above queries that the nesting schema is entirely expressed in the main SELECT clause (table aggregations can also be used in subqueries). This suggests that nested results can be obtained by post-processing the at results, without actually extending SPARQL. However, it would require to retrieve more answers than the number of desired answers, because of the redundancies induced by at results. In the example, 11 answers in the at results are used to generate 2 answers in the nested results. The relation between the two numbers is hard to predict, and can be of combinatorial nature. Integrating nested tables into SPARQL enables to control the number of returned results, and creates opportunities for optimization in query evaluation by trying to avoid redundancies altogether.
Another advantage of the SPARQL extension is to extend SPARQL's expressivity with a new class of aggregations that would be otherwise very di cult to express. The most interesting one is the combination of grouping and top-k results, like \the three youngest actors of each lm" or \the last two mayors of the three most populated cities of each country". 4
We have proposed an extension of SPARQL 1.1 aggregations that enables nested tables
as query results, i.e. tables that can contain tables in their cells, and so recursively.
Nested tables improve the readability of results by avoiding redundancies in their
contents, and by exhibiting the dependencies and independencies between their columns.
The proposed extension is fully backward compatible, and should be relatively easy to
implement in existing query engines. Nested results have been integrated into
Sparklis [