- From: Jim Hendler <hendler@cs.umd.edu>
- Date: Thu, 15 Jul 2004 14:14:08 -0400
- 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 UTC