- From: Jim Hendler <hendler@cs.umd.edu>
- Date: Thu, 15 Jul 2004 14:30:17 -0400
- 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 >languages. 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) -JH > >> -----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