Jean-François Baget, RDF Entailment as a Graph Homomorphism, in: Proc. 4th conference on international semantic web conference (ISWC), Galway (EI), (Yolanda Gil, Enrico Motta, Richard Benjamins, Mark Musen (eds), The semantic web - ISWC 2005, Lecture notes in computer science 3729, 2005), pp82-96, 2005
Semantic consequence (entailment) in RDF is ususally computed using Pat Hayes Interpolation Lemma. In this paper, we reformulate this mechanism as a graph homomorphism known as projection in the conceptual graphs community. Though most of the paper is devoted to a detailed proof of this result, we discuss the immediate benefits of this reformulation: it is now easy to translate results from different communities (e.g. conceptual graphs, constraint programming,... ) to obtain new polynomial cases for the NP-complete RDF entailment problem, as well as numerous algorithmic optimizations.
RDF, RDFS, Inférence