Abstract
The Resource Description Framework (RDF) describes graphs of statements about resources. RDF is a fundamental lower layer of the semantic web. This paper explores the equality of two RDF graphs in light of the graph isomorphism literature. We consider anonymous resources as unlabelled vertices in a graph, and show that the standard graph isomorphism algorithms, developed in the 1970’s, can be used effectively for comparing RDF graphs. The techniques presented are useful for testing RDF software.
Chapter PDF
Similar content being viewed by others
Keywords
- Resource Description Framework
- Current Classification
- Graph Isomorphism
- Uniform Resource Identifier
- Graph Equality
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ora Lassila, Ralph R. Swick: Resource Description Framework (RDF) Model and Syntax Specification. World Wide Web Consortium (1999) http://www.w3.org/TR/1999/REC-rdf-syntax-19990222.
Tim Bray, Jean Paoli, C.M. Sperberg-McQueen, Eve Maler: Extensible Markup Language (XML) 1.0 (Second Edition). World Wide Web Consortium (2000) http://www.w3.org/TR/2000/REC-xml-20001006.
T. Berners-Lee, R. Fielding, U.C. Irvine, L. Masinter: Uniform Resource Identifiers (URI): Generic Syntax. RFC 2396. IETF (1998).
Patrick Hayes (ed): RDF Model Theory. W3C Working Draft (2001) http://www.w3.org/TR/rdf-mt/
Art Barstow, Dave Beckett (eds): RDF Test Cases. W3C Working Draft (2001) http://www.w3.org/TR/rdf-testcases/
Reinhard Diestel: Graph Theory. 2nd edition, Springer (2000).
J. Köbler, U Schöning, J. Torán: The Graph Isomorphism Problem, Its Structural Complexity. Birkhauser (1993).
Steve Skiena: The Algorithm Design Manual. Springer (1998).
Scott Fortin: The Graph Isomorphism Problem. Technical Report TR 96-20. Department of Computer Science, University of Alberta (1996). ftp://ftp.cs.ualberta.ca/pub/TechReports/1996/TR96-20/TR96-20.ps.gz
Ronald C. Read, Derek G. Corneil: Graph Isomorphism Disease. Journal of Graph Theory 1 (1977) 339–363.
Brian McBride, Jeremy Carroll, Ian Dickenson, Dave Reynolds, Andy Seaborne: Jena 1-3-0. Hewlett-Packard Labs (2002) http://www.hpl.hp.com/semweb/jena-top.html
Brendan D. McKay: Practical Graph Isomorphism. Congressus Numerantium 30 (1981) 45–87. http://cs.anu.edu.au/~bdm/papers/pgi.pdf
Brendan D. McKay: Nauty. (1994) http://cs.anu.edu.au/~bdm/nauty/
Jeremy Carroll: ModelMatcher.java found in [11] (2001)
Aaron Swarz: Test Case Results. http://lists.w3.org/Archives/Public/w3c-rdfcore-wg/2001Sep/0001.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carroll, J.J. (2002). Matching RDF Graphs. In: Horrocks, I., Hendler, J. (eds) The Semantic Web — ISWC 2002. ISWC 2002. Lecture Notes in Computer Science, vol 2342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48005-6_3
Download citation
DOI: https://doi.org/10.1007/3-540-48005-6_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43760-4
Online ISBN: 978-3-540-48005-1
eBook Packages: Springer Book Archive