ISSUE-9 (CQA RDFS): REPORTED: Conjunctive Query Answering complexity status in RDFS

ISSUE-9 (CQA RDFS): REPORTED: Conjunctive Query Answering complexity status in RDFS

http://www.w3.org/2007/OWL/tracker/issues/

Raised by: Peter Patel-Schneider
On product: 

Reported by baget.jf, Jun 29, 2007

About OWL 1.1, Tractable fragment, part 6 (RDF/S):

we are surprised to see the complexity of Conjunctive Query Answering 
(CQA) in RDFS presented as "open" for query complexity and combined 
complexity. We guess both versions are NP- complete (unless we missed 
something in your definition of CQA)

First, the problem is clearly in NP. For completeness:
 * (Combined complexity) Entailment in RDF is known to be NP- complete 
   for combined complexity. This result has for instance been shown in 
   [Baget 2005], where RDF entailment is recast as a labeled graph 
   homomorphism. As mentioned in [Baget 2005], this result can be easily 
   extended to RDFS entailment using Pat Hayes transformation rules. For 
   those reading French, there is a former paper from Baget that details 
   the extension to RDFS [Baget 04].
   Using the rewriting as a labeled graph homomorphism problem, RDFS 
   entailment can be reduced to CQA.
   Another close reduction to CQA is from the deduction problem for 
   simple conceptual graphs (deduction being computed by a homomorphism, 
   called "projection": see [Chein Mugnier 92] for the first proof of 
   NP-completeness, and [Baget Mugnier 02] for a synthetic presentation 
   of complexity results).

* (Query complexity) Now, if we consider query complexity, there is a 
  reduction from the H-coloring problem of graph theory: "given a graph 
  G, is there a homomorphism from G to H?" where H is a fixed graph. As 
  H is not part of the input, the complexity of this problem corresponds 
  to the query complexity of CQA, with G representing the query and H 
  the fact base. This problem is known to be NP-complete [Hell, 
  Nesetril, 90] for undirected or directed graphs (thus for labeled 
  graphs as well, if labels comparison can be done polynomially).

Marie-Laure Mugnier (mugnier@lirmm.fr) & J.-François Baget (baget@lirmm.fr)

 References

(Baget, 04) Jean-François Baget. Homomorphismes d'hypergraphes pour la 
subsomption en RDF/RDFS, in: Actes 10^e conférence sur langages et 
modèles à objets (LMO), Langages et modèles à objets 2004 (actes 10e 
conférence), RSTI - L'objet (numéro spécial) 10(2-3):1-275, 2004), 
pp203-216, 2004.

(Baget, 05) Jean-François Baget. RDF Entailment as a Graph 
Homomorphism, Proc. Of the 4th International Semantic Web Conference 
(ISWC 2005), LNCS 3729, pp. 82-96, Springer, 2005.

(Baget, Mugnier, 02) Jean-François Baget et Marie-Laure Mugnier.
Extensions of Simple Conceptual Graphs: the Complexity of Rules and 
Constraints, Journal of Artificial Intelligence Research (JAIR), vol.
16, 2002, pages 425-465. http://www.jair.org/abstracts/baget02a.html

(Chein, Mugnier, 92) Michel Chein et Marie-Laure Mugnier. /Conceptual
Graphs: Fundamental Notions, Revue d'Intelligence Artificielle, volume 
6-4, pages 365-406, 1992.
http://www.lirmm.fr/~mugnier/ArticlesPostscript/RIA92ChMu.ps

(Hell Nesetril, 90) Pavol Hell, Jaroslav Nesetril 
http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/n/
Nesetril:Jaroslav.html
On the complexity of H-coloring. J. Comb. Theory, Ser. B 48 
http://www.informatik.uni-trier.de/%7Eley/db/journals/jct/
jctb48.html#HellN90
92-110 (1990)


Comment 1 by bparsia, Jun 29, 2007

Two points:

   1) The RDFS fragment is clearly underspecified since it doesn't say anything about BNodes and whether they 
are interpreted nominally (as in SPARQL) or existentially. OWL DL allows for certain (tree) patterns of BNodes 
in the ABox...I believe OWL 1.1 intended all OWL DL ontologies to be OWL 1.1, so this would carry over.
   2) However, given the LogSpace datacomplexity, I presume that BNodes were neglected. But then the 
complexity results seem new:
     http://www.eswc2007.org/pdf/eswc07-munoz.pdf

So, there is clearly a bunch of work to be done on this fragment's description.

Received on Wednesday, 24 October 2007 20:58:55 UTC