- From: Jim Hendler <hendler@cs.umd.edu>
- Date: Thu, 15 Jul 2004 16:59:38 -0400
- To: Enrico Franconi <franconi@inf.unibz.it>, RDF Data Access Working Group <public-rdf-dawg@w3.org>
At 20:39 +0200 7/15/04, Enrico Franconi wrote: >On 15 Jul 2004, at 20:30, Jim Hendler wrote: >> 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) > >Jim, can you better explain this statement on RDF? I thought >everything is worst case polynomial in RDF(S). >cheers >--e. Enrico- First, I'm pretty sure I remember that graph algorithms on cyclic, labeled pseudo graphs include some semidecidable things, but I could be wrong. More importantly, however, don't forget that RDF actually allows for RDF statements that change the semantics of RDF itself. For example, I can have a document that reads rdfs:class rdfs:subClassOf rdfs:subClassOf. and I'm suspecting that any language that allows such self-modification must allow me to do some really nasty stuff. I could be wrong, to be honest I have studied the RDF/S model theories well enough to know if anyone has put in things to prohibit creating nasty situations, so I apologize if I am wrong... but it is hard for me to imagine that a query language querying a graph that could have been modified in relatively arbitrary ways wouldn't have potential problems. I also recall that one of the differences between OWL DL and OWL Full was putting in some restrictions to prevent some of the RDF things that caused undecidability... but I'm not the expert on this stuff, Peter Patel-Schneider and Ian Horrocks were the ones who had the most decidability issues (note that technically we are talking semi-decidability) -- it's also possible that the problems were coming from the extra expressiveness of the OWL over the RDFS so, again, I could be wrong. -JH -- 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 17:00:15 UTC