Hacker News Reader

Comment by zozbot234 | Hacker News Reader

Correct me if I'm wrong, but AIUI known algorithms for graph canonicalization are NP hard. (Graph isomorphism has been found to be likely lower in complexity, but canonicalization is not the same problem as graph isomorphism). Given blank nodes, the problem of finding a canonical form for RDF is at least as hard as graph canonicalization. So this is a non-starter for general RDF graphs, you'd have to severely restrict the use of blank nodes to make this practical and the way you do this will likely be application-dependent.

View on HN

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

[2]: https://www.w3.org/TR/2023/CR-rdf-canon-20231031/#dataset-po...

[3]: https://w3c.github.io/vc-data-integrity/

"W3C RDF Dataset Canonicalization: A Standard RDF Dataset Canonicalization Algorithm" > "4.3 Blank Node Identifier Issuer State" https://w3c-ccg.github.io/rdf-dataset-canonicalization/spec/...

IIRC ld-signatures (-> ld-proofs -> Data Integrity) specified URDNA many years ago?

If you search for “isomorphism” in the doc, they state that most real world cases will have unique IDs for nodes and that make this efficient in practice and that implementations can detect if a case is difficult (likely aborting).

https://www.w3.org/wiki/BnodeSkolemization

rdf-concepts/#section-blank-nodes: https://www.w3.org/TR/rdf-concepts/#section-blank-nodes

Rdflib docs on Skolemization: https://rdflib.readthedocs.io/en/stable/persisting_n3_terms.... :

> Skolemization is a syntactic transformation routinely used in automatic inference systems in which existential variables are replaced by ‘new’ functions - function names not used elsewhere - applied to any enclosing universal variables. In RDF, Skolemization amounts to replacing every blank node in a graph by a ‘new’ name, i.e. a URI reference which is guaranteed to not occur anywhere else. In effect, it gives ‘arbitrary’ names to the anonymous entities whose existence was asserted by the use of blank nodes: the arbitrariness of the names ensures that nothing can be inferred that would not follow from the bare assertion of existence represented by the blank node.

SPARQL has UUID() and BNODE() functions: https://www.w3.org/TR/sparql11-query/#func-bnode :

> The BNODE function constructs a blank node that is distinct from all blank nodes in the dataset being queried and distinct from all blank nodes created by calls to this constructor for other query solutions. If the no argument form is used, every call results in a distinct blank node. If the form with a simple literal is used, every call results in distinct blank nodes for different simple literals, and the same blank node for calls with the same simple literal within expressions for one solution mapping.

Blank node: https://en.wikipedia.org/wiki/Blank_node

Reply on news.ycombinator.com