W3C home > Mailing lists > Public > semantic-web@w3.org > June 2007

Re: semantic web reasoning and efficiency

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Fri, 08 Jun 2007 08:49:43 -0400 (EDT)
Message-Id: <20070608.084943.93383183.pfps@research.bell-labs.com>
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

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
See http://www.inf.unibz.it/krdb/events/dl-2007/ for information on the
workshop.  Another good paper in this area is

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

This archive was generated by hypermail 2.4.0 : Tuesday, 5 July 2022 08:45:01 UTC