Re: Feedback on SPARQL 1.1 support for aggregates (was Re: W3C Seeks Feedback on Early Draft of SPARQL 1.1)

Dear Emanuele,

we still owe you an official response to your original mail. We have discussed the issue of aggregates in depth at the group's recent F2F meeting. Although the general spirit of your alternative proposal is interesting, the group will at this stage go forward with the current design for aggregates.

Note especially, that in the presence of aggregates all variables that are projected need to be either be subject to a GROUP BY clause or an aggregation:

"In aggregate queries and sub-queries only expressions which have been used as GROUP BY expressions, or aggregated expressions (i.e. expressions where all variables appear inside an aggregate function) can be projected."

That is, the following of your examples (slight simplification) would *not* be allowed syntactically since ?auth and ?name are not grouped in the outer query.

PREFIX : <http://books.example/> SELECT  ?auth ?name (AVG(?numberOfBooks) AS ?averageNumberOfBooks) WHERE { ?auth :name ?name

   {
           SELECT ?auth (COUNT(?book) AS ?numberOfBooks)
           WHERE {
                   ?auth :wrote ?book .
                 }
           GROUP BY ?auth
          HAVING (?numberOfBooks > 5)

}


best regards,

Axel, on behalf of the WG

On 9 Feb 2010, at 09:27, Emanuele Della Valle wrote:

> Dear Axel & Lee,
> 
> we [1] would like to comment on the support for aggregates in SPARQL
> 1.1. In the last two years we have been working on an extension to
> SPARQL for continuous querying over streams of RDF (namely C-SPARQL
> [2]). Central to stream processing is support for aggregates. For this
> reason we have defined and implemented  [3] our own support for
> aggregates in SPARQL which is orthogonal to the other stream processing 
> features of C-SPARQL. We believe such extension can be of general
> interest for SPARQL 1.1 WG.
> 
> In the rest of the mail we first introduce support for aggregates in
> C-SPARQL, then we compare C-SPARQL and SPARQL 1.1 support for
> aggregates. We show that:
> 1. C-SPARQL syntax for aggregates appears more compact and handy than
> the SPARQL 1.1 one,
> 2. all SPARQL 1.1 queries with aggregates can be expressed in C-SPARQL, and
> 3. there are queries that can be expressed in C-SPARQL but it is unclear
> whether they can be expressed in SPARQL 1.1.
> 
> This text is also available (in a much more readable form) at
> http://wiki.larkc.eu/c-sparql/sparql11-feedback
> 
> == Support For Aggregates In C-SPARQL ==
> 
> Aggregation clauses in C-SPARQL are added at the end of the query, and
> have the following syntax:
> 
> AggregateClause --> ( "AGGREGATE {(" var "," Function "," Group ")"
> [Filter] "}" )*
> Function --> "COUNT" | "SUM" | "AVG" | "MIN" | "MAX"
> Group --> var | "{" var ( "," var )* "}"
> 
> Every aggregation clause has the following three parts:
> 
> * The first part is a new variable (i.e., a variable not in the WHERE
> clause or in other aggregation clauses).
> * The second part is an aggregation function (one of: COUNT, MAX, MIN,
> SUM, AVG); COUNT may have no argument, while the other functions take
> one of the variables occurring in the WHERE clause as argument.
> * The third part is a set of one or more variables, which are chosen
> among those occurring in the WHERE clause.These variables express the
> grouping criteria.
> 
> Every clause may also have an optional fourth part, a FILTER clause.
> 
> == Example Of Simple Support For Aggregates In C-SPARQL And SPARQL 1.1 ==
> 
> Data:
> 
> @prefix : <http://books.example/> .
> :auth1  :name "Alice Foo", :writesBook :book1; :book2 .
> :auth2  :name "Bob Bar", :writesBook :book2 .
> 
> The following query counts the number of books written by an author and
> returns the name and the number of books.
> 
> SELECT ?name ?book ?numberOfBooks
> WHERE {
>    ?auth :name ?name .
>    ?auth :writesBook ?book .
> }
> AGGREGATE { (?numberOfBooks, COUNT, {?auth} ) }
> 
> The semantics of a query containing aggregates consists in adding new
> variable bindings computed by the WHERE clause to the existing regular
> variable bindings. For each of the new variables introduced by the
> AGGREGATE clauses, one new variable binding is added. The query result
> constructed in this way may be further filtered by a standard FILTER
> clause, which may refer to all the variables introduced in the WHERE and
> AGGREGATE clauses.
> 
> Our C-SPARQL extension is based on the conviction that in the context of
> RDF, knowledge should be extended rather than shrunk. Therefore, we
> propose to generate additional variable bindings and use them to
> annotate any existing variable binding that contributed to the aggregate
> value.
> 
> Results:
> ?name       | ?numberOfBooks
> ------------------------------
> "Alice Foo" |            "2"
> "Bob Bar"   |            "1"
> 
> This is in contrast to the conventional SQL grouping semantics that
> replaces all aggregated tuples with a single tuple representing the
> aggregate value. In this respect, we believe that our approach to
> aggregation is more aligned with the baseline of the SPARQL semantics.
> 
> Judging fro the example in Section 10 of the SPARQL 1.1 draft, the query
> above can be expressed in SPARQL 1.1 in the following way:
> 
> SELECT ?name ?numberOfBooks
> WHERE {
>     ?auth :name ?name .        {
>             SELECT ?auth (COUNT(?book) AS ?numberOfBooks)
>             WHERE {
>                     ?auth :writesBook ?book .
>             }
>             GROUP BY ?auth
>     }
> }
> 
> In the C-SPARQL language all the variables used in AGGREGATE clauses
> must appear also in the SELECT clause, since aggregation happens after
> standard SPARQL query evaluation. In SPARQL 1.1 the constraint is not
> specified.
> 
> Wrapping up, queries of this kind can be expressed both in SPARQL 1.1
> and C-SPARQL, but C-SPARQL syntax appears more compact and handy.
> 
> == Aggregates Supported In SPARQL 1.1 Are Also Supported In C-SPARQL ==
> 
> Given the current SPARQL 1.1 support for aggregates, it appears that all
> SPARQL 1.1 queries with aggregates can be expressed in C-SPARQL.
> 
> For instance, the following query is the example of SPARQL 1.1 support
> for aggregates appearing in Section 9 of the current draft.
> 
> PREFIX  <http://books.example/>
> SELECT (SUM(?lprice) AS ?totalPrice)
> WHERE {
>  ?org :affiliates ?auth .
>  ?auth :writesBook ?book .
>  ?book :price ?lprice .
> }
> GROUP BY ?org
> HAVING (SUM(?lprice) > 10)
> 
> Such a query in C-SPARQL will be written as follows.
> 
> PREFIX  <http://books.example/>
> SELECT ?totalPrice
> WHERE {
>  ?org :affiliates ?auth .
>  ?auth :writesBook ?book .
>  ?book :price ?lprice .
> }
> AGGREGATE { (?totalPrice, SUM(?lprice), {?org}) FILTER ( ?totalPrice >
> 10) }
> 
> == Queries That Can Be Expressed In C-SPARQL But It Is Unclear Whether
> They Can Be Expressed In SPARQL 1.1 ==
> 
> Given the current SPARQL 1.1 support for aggregates, it is unclear
> whether the following C-SPARQL queries can be expressed in SPARQL 1.1
> 
> Query: the average number of books written by authors that wrote at
> least 5 books.
> 
> SELECT ?name ?book ?numberOfBooks ?averageNumberOfBooks
> WHERE {
>    ?auth :name ?name .
>    ?auth :wrote ?book .
> }
> AGGREGATE { (?numberOfBooks, COUNT, {?auth} ) FILTER (?numberOfBooks > 5) }
> AGGREGATE { (?averageNumberOfBooks, AVG, {?numberOfBooks} ) }
> 
> A possible way to express it in SPARQL 1.1 is illustrated hereafter, but
> no examples in the current draft show that this is possible.
> 
> SELECT ?name ?surname ?book ?numberOfBooks (AVG(?numberOfBooks) AS
> ?averageNumberOfBooks)
> WHERE {
>     ?auth :hasSurname ?surname .
>     ?auth :hasName ?name .
>     {
>             SELECT ?auth (COUNT(?book) AS ?numberOfBooks)
>             WHERE {
>                     ?auth :wrote ?book .
>    }
>             GROUP BY ?auth
>            HAVING (?numberOfBooks > 5)
> }
> 
> More complex sequences of aggregation are supported in C-SPARQL, such as
> * computing the number of books per author
> * keeping only the authors who have published at least 5 books
> * computing the total number of books grouping by affiliation
> * filtering the affiliation with less than 50 books published
> 
> SELECT ?name ?surname ?book ?numberOfBooks ?averageNumberOfBooks
> WHERE {
>    ?auth :name ?name .
>    ?auth :surname ?surname .
>    ?auth :wrote ?book .
>    ?auth :affiliated ?organization .
> }
> AGGREGATE { (?numberOfBooks, COUNT, {?auth} ) FILTER (?numberOfBooks > 5) }
> AGGREGATE { (?affiliationBooks, SUM(?numberOfBooks), {?organization} )
> FILTER (?affiliationBooks > 50)}
> 
> A possible way to express it in SPARQL 1.1 is illustrated hereafter, but
> as above no examples in the current draft show that this is possible.
> 
> SELECT ?name ?surname ?book ?numberOfBooks
> WHERE {
>   ?auth :hasSurname ?surname .
>   ?auth :hasName ?name .
>   {
>    SELECT ?affiliation (SUM(?numberOfBooks) as ?affiliationBooks)
>    WHERE {
>     ?auth :affiliated ?organization .
>     {
>      SELECT ?auth (COUNT(?book) AS ?numberOfBooks)
>      WHERE {
>       ?auth :wrote ?book .
>      }
>      GROUP BY ?auth
>     HAVING (?numberOfBooks > 5)
>    }
>    GROUP BY ?organization
>   HAVING (?affiliationBooks > 50)
>   }
> 
> In C-SPARQL, evaluation of multiple aggregation with filtering clauses
> is possible. For instance, one can ask for the research topics for which
> the Italian authors are more than the Swiss ones.
> 
> SELECT ?topic ?numberOfSwissAuthors ?numberOfItalianAuthors
> WHERE {
>    ?auth :name ?name .
>    ?auth :wrote ?book .
>    ?book :topic ?topic .
>    ?auth :hasNationality ?nat .
> }
> AGGREGATE { FILTER(?nat = 'IT') (?numberOfItalianAuthors, COUNT,
> {?topic} ) }
> AGGREGATE { FILTER(?nat = 'CH') (?numberOfSwissAuthors, COUNT, {?topic}
> ) FILTER(?numberOfItalianAuthors>?numberOfSwissAuthors)}
> 
> Given the current draft of SPARQL 1.1, two alternative formulations
> appear possible, one using a FILTER and one using an HAVING. However,
> both require the SPARQL 1.1 engine to decide the order of execution,
> whereas in C-SPARQL the order is given explicitly.
> 
> SPARQL 1.1 version that uses the FILTER clause (see line 24):
> 
> 1. SELECT ?topic ?numberOfSwissAuthors ?numberOfItalianAuthors
> 2. WHERE {
> 3.     ?auth :hasName ?name .
> 4.     {
> 5.             SELECT ?auth (COUNT(?book) AS ?numberOfSwissAuthors)
> 6.             WHERE {
> 7.                     ?auth :wrote ?book .
> 8.                     ?book :topic ?topic .
> 9.                     ?auth :hasNationality ?nat .
> 10.                     FILTER(?nat = 'CH') .
> 11.             }
> 12.             GROUP BY ?topic
> 13.     }
> 14.     {
> 15.             SELECT ?auth (COUNT(?book) AS ?numberOfItalianAuthors)
> 16.             WHERE {
> 17.                     ?auth :wrote ?book .
> 18.                     ?book :topic ?topic .
> 19.                     ?auth :hasNationality ?nat .
> 20.                     FILTER(?nat = 'IT') .
> 21.             }
> 22.             GROUP BY ?topic    23.     }
> 24.     FILTER(?numberOfItalianAuthors>?numberOfSwissAuthors)    25. }
> 
> SPARQL 1.1 version that uses the HAVING clause (see line 23):
> 
> 1. SELECT ?topic ?numberOfSwissAuthors ?numberOfItalianAuthors
> 2. WHERE {
> 3.     ?auth :hasName ?name .
> 4.     {
> 5.             SELECT ?auth (COUNT(?book) AS ?numberOfSwissAuthors)
> 6.             WHERE {
> 7.                     ?auth :wrote ?book .
> 8.                     ?book :topic ?topic .
> 9.                     ?auth :hasNationality ?nat .
> 10.                     FILTER(?nat = 'CH') .
> 11.             }
> 12.             GROUP BY ?topic
> 13.     }
> 14.     {
> 15.             SELECT ?auth (COUNT(?book) AS ?numberOfItalianAuthors)
> 16.             WHERE {
> 17.                     ?auth :wrote ?book .
> 18.                     ?book :topic ?topic .
> 19.                     ?auth :hasNationality ?nat .
> 20.                     FILTER(?nat = 'IT') .
> 21.             }
> 22.             GROUP BY ?topic  23.            
> HAVING(?numberOfItalianAuthors>?numberOfSwissAuthors)
> 24.     }   25. }
> 
> Therefore, we believe that there are queries that can be expressed in
> C-SPARQL but not in SPARQL 1.1.
> 
> == Computing Multiple Independent Aggregates At The Same Time ==
> 
> As we explained in the introduction, C-SPARQL was explicitly designed
> for processing RDF streams. The transient nature of streams poses the
> requirement to compute multiple (possibly independent) aggregates at the
> same time in the same query, because assuring that two independent
> queries process exactly the same data is very difficult. Therefore,
> multiple independent aggregations are also allowed within the same
> C-SPARQL query, with different grouping criteria and different
> partitions over the same set of bindings, thus pushing the aggregation
> capabilities beyond those of SQL.
> 
> The following query counts the number of books written by an author,
> counts the number of authors per book and returns the name, the book,
> the number of books and the number of authors.
> 
> SELECT ?name ?book ?numberOfBooks ?numberOfAuthors
> WHERE {
>    ?auth :name ?name .
>    ?auth :wrote ?book .
> }
> AGGREGATE { (?numberOfBooks, COUNT, {?auth} ) }
> AGGREGATE { (?numberOfAuthors, COUNT, {?book} ) }
> 
> Results:
> 
> ?name       | ?book | ?numberOfBooks | ?numberOfAuthors
> ---------------------------------------------------------
> "Alice Foo" |    b1 |            "2" |              "1"
> "Alice Foo" |    b2 |            "2" |              "2"
> "Bob   Bar" |    b2 |            "1" |              "2"
> 
> Judging from SPARQL 1.1 draft, the query above can be expressed in
> SPARQL 1.1 in the following way:
> 
> SELECT ?name ?surname ?book ?numberOfBooks ?numberOfAuthors
> WHERE {
>     ?auth :hasSurname ?surname .
>     ?auth :hasName ?name .
>     {
>             SELECT ?auth (COUNT(?book) AS ?numberOfBooks)
>             WHERE {
>                     ?auth :wrote ?book .
>             }
>             GROUP BY ?auth
>     }
>     {
>             SELECT  ?auth (COUNT(?auth) AS ?numberOfAuthors)
>             WHERE {
>                    ?auth :wrote ?book .
>             }
>             GROUP BY ?book
>     }
> }
> 
> == Conclusion ==
> 
> Clearly, the C-SPARQL notation is less cumbersome and more concise than
> the SPARQL 1.1 one. It is therefore, easier to express and understand
> aggregates in C-SPARQL than in the current draft of SPARQL 1.1, which we
> believe is an important factor in language design and adoption.
> 
> == References ==
> 
> [1] http://dbgroup.elet.polimi.it/
> [2] http://wiki.larkc.eu/c-sparql
> [3]
> http://www.larkc.eu/wp-content/uploads/2008/01/larkc_d33-description-of-strategy-and-design-for-data-stream-management-approaches_final.pdf
> 
> 
> Axel Polleres ha scritto:
> > The SPARQL WG has published  a First Public Working Draft "SPARQL 1.1
> > Property Paths"
> > (http://www.w3.org/TR/2010/WD-sparql11-property-paths-20100126/) which
> > defines a more succinct way to write parts of basic graph patterns and
> > also extend matching of triple pattern to arbitrary length paths. The
> > group also published six updates listed below:
> >
> > * SPARQL 1.1 Query (new working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-query-20010126/) - Adds support
> > for aggregates, subqueries, projected expressions, and negation to the
> > SPARQL query language.
> > * SPARQL 1.1 Update (new working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-update-20010126/) - - Defines an
> > update language for RDF graphs.
> > * SPARQL 1.1 Protocol for RDF (new working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-protocol-20010126/) - Defines an
> > abstract interface and HTTP bindings for a protocol to issue SPARQL
> > Query and SPARQL Update statements against a SPARQL endpoint.
> > * SPARQL 1.1 Service Description (new working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-service-description-20010126/) -
> > Defines a vocabulary and discovery mechanism for describing the
> > capabilities of a SPARQL endpoint.
> > * SPARQL 1.1 Uniform HTTP Protocol for Managing RDF Graphs (new
> > working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-http-rdf-update-20010126/) -
> > Describes the use of the HTTP protocol for managing named RDF graphs
> > on an HTTP server.
> > * SPARQL 1.1 Entailment Regimes (new working draft:
> > http://www.w3.org/TR/2010/WD-sparql11-entailment-20010126/) - Defines
> > conditions under which SPARQL queries can be used with entailment
> > regimes such as RDF, RDF Schema, OWL, or RIF.
> >
> > The working group is seeking feedback on these drafts from, especially
> > on those points currently marked with ISSUEs currently under
> > discussion, cf. [1]. If you wish to make comments regarding these
> > documents, please send them to
> >     public-rdf-dawg-comments@w3.org
> >
> > with best regards,
> > Axel Polleres & Lee Feigenbaum (on behalf of the SPARQL WG)
> >
> > 1. http://www.w3.org/2009/sparql/track/issues/open
> >  
> 
> 
> 
> 
>

Received on Wednesday, 31 March 2010 21:17:45 UTC