W3C home > Mailing lists > Public > www-rdf-interest@w3.org > June 2003

Re: Proposal: "Canonical" RDF/XML

From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Date: Sun, 29 Jun 2003 21:39:39 +0100
Message-ID: <3EFF4E8B.7020100@hplb.hpl.hp.com>
CC: Charles McCathieNevile <charles@w3.org>, rdf-i <www-rdf-interest@w3.org>


(Although I've not read the whole thread)
Yes - the ordering of the subjects depends on any bnode IDs and the bnode 
IDs are arbitrary.
The most obvious way to assign them is in an increasing numeric sequence, 
but then which comes first - the ordering of the triples (which depends on 
the bnode IDs) or the bnodeIDs which depend on the ordering of the triples.

All in all, any solution that allows RDF canonicalization in general, must 
  permit the comparison between two arbitrary rdf graphs. Since arbitrary 
unlabelled undirected graphs can be embedded in RDF, two such graphs can be 
comapred. This is known as the graph isomorphism GI problem, so any 
complete solution for RDF canonicalization solves GI for which no 
polynomial time solutions are known.

I have explored this issue in detail, and believe, and argue in a paper 
that I will present in ISWC2003 (I will try and get a pdf available soon), 
that despite this a practical solution is achievable.

More tomorrow.

Jeremy
Received on Sunday, 29 June 2003 16:40:59 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:51:59 GMT