Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Hayes, P.: RDF Semantics. W3C Recommendation (2004), http://www.w3.org/TR/2004/REC-rdf-mt-20040210/
ter Horst, H.J.: Extending the RDFS Entailment Lemma. In: McIlraith, S.A., Plexousakis, D., van Harmelen, F. (eds.) ISWC 2004. LNCS, vol. 3298, pp. 77–91. Springer, Heidelberg (2004)
Hahn, G., Tardif, C.: Graph homomorphisms: structure and symmetry. Graph Symmetry. NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci. 497, 107–166 (1997)
Chein, M., Mugnier, M.L.: Conceptual Graphs: fundamental notions. Revue d’Intelligence Artificielle 6, 365–406 (1992)
Montanari, U.: Networks of Constraints: Fundamental Notions and Application to Picture Processing. Information Sciences 7, 95–132 (1974)
Corby, O., Dieng, R., Hebert, C.: A Conceptual Graph Model for W3C Resource Description Framework. In: International Conference on Conceptual Structures, pp. 468–482 (2000)
Baget, J.F.: Homomorphismes d’hypergraphes pour la subsomption en RDF/RDFS. In: 10e conférence sur langages et modèles à objets (LMO), vol. 10, pp. 203–216 (2004)
Genest, D.: Extensions du modèle des graphes conceptuels pour la recherche d’informations. PhD thesis, Université de Montpellier II (2000)
Hayes, J., Guttiérrez, C.: Bipartite Graphs as Intermediate Model for RDF. In: McIlraith, S.A., Plexousakis, D., van Harmelen, F. (eds.) ISWC 2004. LNCS, vol. 3298, pp. 47–61. Springer, Heidelberg (2004)
Baget, J.F.: Simple conceptual graphs revisited: hypergraphs and conjunctive types for efficient projection algorithms. In: ISWC 2003. LNCS, vol. 2870, pp. 195–208. Springer, Heidelberg (2003)
Mugnier, M.L.: Knowledge Representation and Reasonings Based on Graph Homomorphism. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS, vol. 1867, pp. 172–192. Springer, Heidelberg (2000)
Mugnier, M.L., Chein, M.: Polynomial algorithms for projection and matching. In: Pfeiffer, H.D., Nagle, T.E. (eds.) Conceptual Structures: Theory and Implementation. LNCS (LNAI), vol. 754. Springer, Heidelberg (1993)
Freuder, E.: A sufficient condition for backtrack-free search. Journal of the ACM 29, 24–32 (1982)
Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural decomposition methods (1999)
Guinaldo, O., Haemmerlé, O.: Knowledge querying in the conceptual graphs model: the RAP module. In: Mugnier, M.-L., Chein, M. (eds.) ICCS 1998. LNCS (LNAI), vol. 1453, pp. 287–294. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baget, JF. (2005). RDF Entailment as a Graph Homomorphism. In: Gil, Y., Motta, E., Benjamins, V.R., Musen, M.A. (eds) The Semantic Web – ISWC 2005. ISWC 2005. Lecture Notes in Computer Science, vol 3729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11574620_9
Download citation
DOI: https://doi.org/10.1007/11574620_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29754-3
Online ISBN: 978-3-540-32082-1
eBook Packages: Computer ScienceComputer Science (R0)