You are indeed correct that there are NP-hard problems associated with RDF dataset canonicalization. However, the earlier academic research by Aiden Hogen[1] de

You are indeed correct that there are NP-hard problems associated with RDF dataset canonicalization. However, the earlier academic research by Aiden Hogen[1] describes how it's unlikely to be a problem with real world datasets: ...in our evaluation we demonstrate that there indeed exist difficult synthetic cases, but we also provide results over 9.9 million RDF graphs that suggest such cases occur infrequently in the real world, and that both canonical forms can be efficiently computed in all but a handful of such cases. There are experimental results for this near the end of the paper. Aiden Hogen's algorithm isn't identical to the one which the RDF Dataset Canonicalization specification is attempting to standardise, but I believe it would be a fair assumption to say that a majority of RDF datasets would be unproblematic, and a future test could perhaps be performed to verify this assumption. There should be lots of anecdotal and even academic results coming soon as a result of this W3C Candidate Recommendation publication. In the case of malicious actors, there is a section for 'Dataset Poisoning'[2] in the RDF Dataset Canonicalization specification that warns implementers to watch out for those datasets that have been designed to cause processing to grind to a halt. I think I would agree with you that application-dependent datasets will be the most viable until some more research is done; indeed the majority of interest seems to come from the W3C Verifiable Credentials space with RDF data inside digital authorization documents[3], for instance as part of the proposals for a privacy-focused revision to the European Union Digital Identity Wallet. [1]: https://aidanhogan.com/docs/rdf-canonicalisation.pdf https://aidanhogan.com/docs/rdf-canonicalisation.pdf [2]: https://www.w3.org/TR/2023/CR-rdf-canon-20231031/#dataset-poisoning https://www.w3.org/TR/2023/CR-rdf-canon-20231031/#dataset-po... [3]: https://w3c.github.io/vc-data-integrity/ https://w3c.github.io/vc-data-integrity/