- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Fri, 08 Jun 2007 08:49:43 -0400 (EDT)
- To: dc03ddt@yahoo.co.uk
- Cc: semantic-web@w3.org
From: Kumar T <dc03ddt@yahoo.co.uk> Subject: semantic web reasoning and efficiency Date: Fri, 8 Jun 2007 11:56:37 +0100 (BST) > Dear List members, > > I keep getting this argument that, when you use semantic web reasoning > (ontology + reasoner working on them = application), then the > resultant system will be slower (throughput). Can anybody provide me > some articles discussing this? > > Many thanks, > > DT The question is, slower with respect to what? Don't expect RDBMS speeds out of an ontology reasoner over an expressive ontology language. However, ontology reasoners can be quite fast in practice. There are lots of papers on the (worst-case) complexity of various operations in expressive ontology languages. For such ontology languages, the worst-case complexity is quite bad. The current Description Logic workshop (which I am at right now) has some papers in this area, for example Inverse Roles Make Conjunctive Queries Hard, by Carsten Lutz available at http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS//Vol-250/paper_3.pdf See http://www.inf.unibz.it/krdb/events/dl-2007/ for information on the workshop. Another good paper in this area is http://lat.inf.tu-dresden.de/~clu/papers/archive/ijcai07c.pdf There are Description Logics (and thus ontology languages), notably DL-Lite, where querying has the same worst-case complexity as query answering in relational DBs and can even be implemented by (multiply) querying in a relational DBMS. There are papers on this topic at the current Description Logics workshop. Of course, you have to give up expressive power to achieve these guarantees. Peter F. Patel-Schneider Bell Labs Research
Received on Friday, 8 June 2007 12:51:20 UTC