- From: claudio gutierrez <cgutierr@dcc.uchile.cl>
- Date: Thu, 4 Dec 2003 15:52:57 -0300 (CLST)
- To: "Peter F. Patel-Schneider" <pfps@research.bell-labs.com>
- Cc: <lsp@is.pku.edu.cn>, <www-rdf-logic@w3.org>
> Entailment in RDF and RDFS is decidable, although I do not believe that
> there is a direct proof of this in the RDF documents. However, if you
> transform RDFS into FOL you end up using a lot of the power of FOL.
>
> As far as complexity of reasoning in RDFS goes, I'm not aware of any formal
> results in this area, but I haven't been looking for anything in this
> area.
It is not difficult to show --using the characterization of
entailment by maps-- that entailment between simple RDF graphs is
NP complete [codify subgraph iso problem; Witness: the map.]
For RDFS entailment, asymptotic complexity is the same. Recall that RDFS
entailment can also be characterized by maps between closures of graphs
(any closure works --warning: RDFSemantics doc. speaks of "the" closure,
but there could be many different. Fortunately any of them works). The
size of the closure is poly in the size of the original graph (no more
than V^3 triples, where V is the vocabulary of the graph plus rdfs
vocabulary).
For practical purposes the upper bounds are better. Complex part of
entailment (think of maps) really depends on the number of blank
nodes, which ususally are smaller than the total number of nodes in
real-life RDf specifications [Am I right in this? I haven't found any
statistic for this claim, but the rdf specifications i have worked with
have this property]. The bound is something like (size of graph)^{Number
Blank Nodes}, i.e. "poly" with exponent number of blank nodes.
claudio
Received on Thursday, 4 December 2003 13:53:03 UTC