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:14:08 -0400
Message-Id: <p06110414bd1c786a0bdd@[10.0.0.11]>
To: Dan Connolly <connolly@w3.org>, public-rdf-dawg@w3.org

At 7:54 -0700 7/15/04, Dan Connolly wrote:
>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 - while I agree with the goal of this, I'm not sure the wording 
is correct - that is, I don't think what you're after has to do w/the 
ability to express the halting problem, and I suspect that given that 
RDF graphs, being actually "pseudo graphs" (since they can have 
multiple links between same nodes) and allowing cycles, it is 
possible to express queries even in simple languages that could have 
halting issues - remember that decidability is in the problem, not in 
the language used to express it (I can give you trivial problems that 
are undecidable, for example stacking one block on another when each 
block has a separate controller) -- I think if we simply drop the 
last sentence it is closer to what you actually want to say (Turing 
completeness is in the language, decidability/halting is in the 
problem) so "yes" to:

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.

  -JH
p.s. Sorry, going on 20 years as a Professor of Computer Science has 
made me overly literal on these things.
-- 
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:14:58 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:20 GMT