W3C home > Mailing lists > Public > semantic-web@w3.org > December 2013

Re: SPARQL 1.1 computational complexity and/or optimisation

From: Axel Polleres <axel@polleres.net>
Date: Tue, 3 Dec 2013 09:19:27 +0100
Cc: Steve Hargreaves <steve.harg@gmail.com>, semantic-web@w3.org
Message-Id: <3FA13C2D-4E6C-43C6-A883-DA3B5E77F325@polleres.net>
To: Michael Brunnbauer <brunni@netestate.de>
> Katja Losemann, Wim Martens, 2012
> The Complexity of Evaluating Path Expressions in SPARQL
> http://www.theoinf.uni-bayreuth.de/download/pods12submission.pdf


FWIW, this paper does not reflect the final semantics of property paths.
In fact, the results there, based on a working draft of the spec, have 
been considered in the final recommendation, cf.
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2012Apr/0004.html

best regards,
Axel

--
Prof. Dr. Axel Polleres
Institute for Information Business, WU Vienna
url: http://www.polleres.net/  twitter: @AxelPolleres

On Dec 3, 2013, at 9:08 AM, Michael Brunnbauer <brunni@netestate.de> wrote:

> 
> Hello Steve,
> 
> how about this one:
> 
> Katja Losemann, Wim Martens, 2012
> The Complexity of Evaluating Path Expressions in SPARQL
> http://www.theoinf.uni-bayreuth.de/download/pods12submission.pdf
> 
> Regards,
> 
> Michael Brunnbauer
> 
> On Mon, Dec 02, 2013 at 06:24:01PM +0000, Steve Hargreaves wrote:
>> Dear list,
>> 
>> Apologies if this has come up before (my searches so far have drawn a 
>> blank), but I'm wondering if anyone can point me to any research papers 
>> which attempt to determine the computational complexity of SPARQL 1.1 or 
>> which suggest methods for optimising SPARQL 1.1 queries.
>> 
>> I'm specifically looking for 1.1 related material - I can find plenty of 
>> papers for the original SPARQL, e.g.
>> 
>> Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009. Semantics and 
>> complexity of SPARQL. /ACM Trans. Database Syst./ 34, 3, Article 16 
>> (September 2009), 45 pages. DOI=10.1145/1567274.1567278 
>> http://doi.acm.org/10.1145/1567274.1567278
>> 
>> Michael Schmidt, Michael Meier, and Georg Lausen. 2010. Foundations of 
>> SPARQL query optimization. In /Proceedings of the 13th International 
>> Conference on Database Theory/ (ICDT '10), Luc Segoufin (Ed.). ACM, New 
>> York, NY, USA, 4-33. DOI=10.1145/1804669.1804675 
>> http://doi.acm.org/10.1145/1804669.1804675
>> 
>> but I'm particularly interested in 1.1-specific features such as 
>> subqueries and aggregate functions.
>> 
>> 
>> Best regards,
>> 
>> Steve Hargreaves
>> 
>> 
>> Centre for Digital Music
>> Electronic Engineering
>> Queen Mary University of London
>> Mile End Road
>> London E1 4NS
>> UK
> 
> -- 
> ++  Michael Brunnbauer
> ++  netEstate GmbH
> ++  Geisenhausener Straße 11a
> ++  81379 München
> ++  Tel +49 89 32 19 77 80
> ++  Fax +49 89 32 19 77 89 
> ++  E-Mail brunni@netestate.de
> ++  http://www.netestate.de/
> ++
> ++  Sitz: München, HRB Nr.142452 (Handelsregister B München)
> ++  USt-IdNr. DE221033342
> ++  Geschäftsführer: Michael Brunnbauer, Franz Brunnbauer
> ++  Prokurist: Dipl. Kfm. (Univ.) Markus Hendel
Received on Tuesday, 3 December 2013 08:19:57 UTC

This archive was generated by hypermail 2.4.0 : Tuesday, 5 July 2022 08:45:35 UTC