W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > July to September 2004

RE: Limited complexity requirement?

From: Jim Hendler <hendler@cs.umd.edu>
Date: Thu, 15 Jul 2004 14:30:17 -0400
Message-Id: <p06110415bd1c7a026b97@[]>
To: "Rob Shearer" <Rob.Shearer@networkinference.com>
Cc: public-rdf-dawg@w3.org

>I tend to agree with the general philosophy (a tiny turing-incomplete
>subset of XQuery would be great, with the point being that support for
>full XQuery is a sensible extension in those environments where it is
>useful), but frankly the fact that you can't express the halting problem
>doesn't solve any of the implement/deploy/secure/optimize issues. My
>frequent refrain is "people don't generally publicize full SQL
>interfaces", and there are good reasons that they don't. It is quite
>easy to string together enough joins in SQL to form a practically
>insoluble query; DOS attacks and the like are possible in even very tiny

Thinking further on what Dan wrote, and getting pedantic again, I 
should point out that TimBL is wrong in his design document, and Rob 
is right above in saying that  SQL is not Turing complete 
(actually,the technical term is Turing equivalent, Turing complete is 
actually slightly different, but most people use the two terms 
interchangeably).   However, that is the original SQL -- SQL 3 is 
"almost" Turing equivalent (depending whether you allow recursion) - 
but as TimBL notes, it is usually not used that way.   I should also 
note that programming a TC langauge is not necessarily harder than 
doing a non-TC one - for example, the Lisp 1.5 interpreter (Turing 
Equiv) is much easier to implement than a compliant SQL 3 system (Not 
Turing Equiv).   So Dan's goal of easy to implement is different than 
the goal of "hard o create a query that takes forever" is different 
than "not Turing equivalent"

I assume Dan that you were aiming for easy to implement as the main 
point (i.e. implementational complexity over computational 
complexity) and particularly easy to evaluate whether the system did 
the right thing?  I'm still okay with your wording (again, assuming 
we drop the last sentence) but wanted to be clear you mean the 
complexity of languge implementation over the complexity of the 
computation allowed -- i.e. relational databases are limited in 
expressivity to keep things polynmial in most cases, even though SQL 
is a bear to implement in full, in part because of this.  We would 
aim for the opposite - ease in design and implementation, as opposed 
to guarantee of efficient computation (which, given the expressivity 
of RDF we provably could not gaurantee without putting new 
restrictions on the RDF graphs)

>>  -----Original Message-----
>>  From: public-rdf-dawg-request@w3.org
>>  [mailto:public-rdf-dawg-request@w3.org] On Behalf Of Dan Connolly
>>  Sent: Thursday, July 15, 2004 7:54 AM
>>  To: public-rdf-dawg@w3.org
>>  Subject: Limited complexity requirement?
>>  While thinking about xquery-based designs, I realized I have been
>>  assuming the following requirement. What do other folks think?
>>  3.X Limited complexity
>>  Less expressive languages are easier to implement, deploy,
>>  secure, and
>>  optimize (cf the Principle of Least Poser in an essay on design
>>  principles for the Web[1]). Since a large and interesting class of
>>  applications can be addressed with query languages that are less
>>  expressive than programming languages, this design should not
>>  involve a
>>  turning-complete query evaluator. The halting problem must not be
>>  expressible in this query language design.
>>  [1] http://www.w3.org/DesignIssues/Principles
>>  --
>>  Dan Connolly, W3C http://www.w3.org/People/Connolly/
>>  mobile: tel:+1-816-616-6576

Professor James Hendler			  http://www.cs.umd.edu/users/hendler
Director, Semantic Web and Agent Technologies	  301-405-2696
Maryland Information and Network Dynamics Lab.	  301-405-6707 (Fax)
Univ of Maryland, College Park, MD 20742	  240-277-3388 (Cell)
Received on Thursday, 15 July 2004 14:30:59 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:00:44 UTC