W3C home > Mailing lists > Public > semantic-web@w3.org > December 2012

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

From: Ivan Shmakov <oneingray@gmail.com>
Date: Thu, 13 Dec 2012 01:04:08 +0700
To: semantic-web <semantic-web@w3.org>
Cc: Ivan Shmakov <oneingray@gmail.com>
Message-ID: <86r4mvp2p3.fsf@gray.siamics.net>
>>>>> 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

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:38 UTC