ISSUE-9

2007-10-24 20:58:42: Created issue 'REPORTED: Conjunctive Query Answering complexity status in RDFS' nickname CQA RDFS owned by Peter Patel-Schneider on product , description '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. ' non-public [Peter Patel-Schneider]

2007-12-19 19:06:41: title changed to 'ACCEPTED: Conjunctive Query Answering complexity status in RDFS' [Ian Horrocks]

2007-12-19 19:06:41: Issue dissociated from any product [Ian Horrocks]

2008-04-18 13:32:23: Issue dissociated from any product

2008-04-18 13:32:23: Status changed to 'closed'