Re: [ontolog-forum] Data, Silos, Interoperability, and Agility

[Michael Brunnbauer <brunni@xxxxxxxxxxxx>]

Hello John,    (01)

On Tue, Sep 24, 2013 at 12:14:20PM -0400, John F Sowa wrote:
> On 9/24/2013 8:51 AM, Kingsley Idehen wrote:
> > The WHERE CLAUSE of SQL isn't a nirvana. It's a slot.
> 
> More precisely, it has the expressive power of FOL.    (02)

Isn't it possible to use aggregate functions whithin WHERE ? Aggregate 
functions are not part of Relational Algebra, which is already FOL.    (03)

If this does not make SQL more expressive than FOL, recursive queries do:
Recursive queries from SQL:1999 are widely implemented (e.G. in the Open 
Source RDB Postgres). So we have First-order logic with a transitive closure 
operator: http://en.wikipedia.org/wiki/Descriptive_complexity    (04)

SPARQL 1.0 has the expressive power of Relational Algebra, and therefore of
FOL: http://www.dcc.uchile.cl/cgutierr/ftp/expressive-power-sparql.pdf    (05)

The equivalent of recursive queries in SPARQL 1.1 are Property Paths.    (06)

So what is the point of your statement that SQL WHERE is as expressive as FOL ?
SPARQL does not seem to fall behind this. BTW - Have a look a this paper:     (07)

 http://www.theoinf.uni-bayreuth.de/download/pods12submission.pdf    (08)

On page 11, there is a table that says that SPARQL 1.1 evaluation with current
W3C semantics is NP-complete in some cases. I guess this does not automatically
make SPARQL 1.1 as expressive as Existential second-order logic but it is
interesting.    (09)

Regards,    (010)

Michael Brunnbauer    (011)

-- 
++  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@xxxxxxxxxxxx
++  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    (012)

pgpQiwMUu3x3T.pgp
Description: PGP signature

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J    (01)