W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > April 2012

regular path expressions

From: William Waites <wwaites@tardis.ed.ac.uk>
Date: Thu, 19 Apr 2012 14:59:04 +0100 (BST)
Message-Id: <20120419.145904.507194630.wwaites@tardis.ed.ac.uk>
To: lee@thefigtrees.net, public-rdf-dawg-comments@w3.org
Cc: jorge.perez.rojas@gmail.com, marcelo.arenas1@gmail.com, sconca87@gmail.com, martens.wim@gmail.com
I was happy to see the revisions earlier in the week to the SPARQL 1.1
working draft that saw the default semantics of the *, + and ?
operators changed from counting to existential.

Is it to be expected that a similar revision will be forthcoming for
the simple walk vs. regular path problem signalled by Wim Martens et

As I understand it, the non-standard W3C simple-walk semantics mean
that evaluating path expressions containing those operators is
intractable even with counting semantics. See Wim's earlier mail at

I understand that the WG is already over time and there is pressure to
carve the spec into stone, but it seems to me better to be late than
to release something containing a known serious error especially when
the fix is clear.

I would also like to point out -- and this is the reason I call the
simple-walk semantics non-standard -- that basic things like the
equivalence of "aa*" and "a+" are not true under the current
draft. Apart from questions of tractability, this could be quite
confusing to users.


[1] http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2012Feb/0029.html

Received on Thursday, 19 April 2012 13:59:15 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:52:12 UTC