Re: Well Behaved RDF - Taming Blank Nodes, etc.

>>>>> David Booth <david@dbooth.org> writes:

[…]

 > For example, one key limitation would be in the use of blank nodes,
 > which severely complicate what could otherwise be simple tasks, such
 > as comparing two RDF graphs for equality.  With unrestricted blank
 > nodes, this becomes a difficult graph isomorphism problem instead of
 > a simple text comparison.  Some have suggested eliminating blank
 > nodes entirely, but a more modest restriction would be to limit them
 > to common idioms that do not cause such complexity problems:

 > A Well-Behaved RDF graph is an RDF graph that can be serialized as
 > Turtle without the use of explicit blank node identifiers.  I. e.,
 > only blank nodes that are implicitly created by the bracket "[ ... ]"
 > or list "( ... )" notations are permitted.

 My suggestion would be to only disallow cycles composed entirely
 of blank nodes.

 As it seems, an RDF graph following this restriction could be
 “canonicalized” quite easily, just by ordering all Subject
 nodes, and the arcs they belong to, in a particular way.  E. g.,
 in Turtle:

## order by subject first
:b
  ## order by predicate then
  :arel :c ;
  ## order by object at last
  :brel :d ;
  :brel :e ;
  ## URI's come first
  :crel :a ;
  :crel :bar ;
  ## then literals
  :crel "abc" ;
  :crel "def" .

## blank nodes come last
_:0
  :arel :foo .

## _:1 goes after _:0 because :brel goes after :arel
_:1
  :brel :bar .

## _:2 goes after _:1 because blank nodes go after URI's
_:2
  :brel _:0 .

 Obviously, cyclic paths are problematic a bit, but as long as
 the non-blank nodes are considered, we can choose the “least”
 node to be the path's starting point.  On the other hand, we
 cannot tie identifiers' ordering to something that lacks
 “inherent” identifiers, such as, for instance, blank nodes.

 To put it short, we order the arcs as we'd order
 (Subject, Predicate, Object) tuples (i. e., one item would be
 the most significant one, etc.)  Then, we order blank nodes as
 we'd order “tuples of tuples” (with the “least tuple” being the
 most significant one, etc.), starting with “apex” blank nodes.

[…]

-- 
FSF associate member #7257

Received on Wednesday, 12 December 2012 18:04:42 UTC