Re: Transforming RDF into (non-binary!) trees

On 2014-07 -06, at 16:46, Paul Tyson <phtyson@sbcglobal.net> wrote:

> On Sat, 2014-07-05 at 22:35 +0300, Victor Porton wrote:
>> I think we should write some code which would transform RDF into a tree
>> (not necessarily binary! utilize nameless nodes as nodes with N
>> childs) and also check the number of branches of a certain kind
>> (usually 0..1 or 1..1).
>> 
>> Has anyone done a similar job?
> 
> I have not done that in RDF, but recently I had to generate optimal
> spanning trees [1] from a directed acyclic graph (DAG). It occurred to
> me that a similar technique could be applied to RDF if you first omitted
> cycles from the RDF graph (perhaps by introducing blank nodes).
> 
> One approach would be to put the spanning tree (however you choose to
> define it) in one named graph, and all the other "non-tree" triples in
> another named graph.
> 
> This would make it easier to apply conventional block-and-line layout
> styles (using XSL or CSS) to the spanning tree, and use the non-tree
> links to "decorate" the format (e.g. using hyperlinks or other
> interactive behavior).
> 
> Your use case might be quite different than mine. I am motivated by the
> problem of applying formatting style to RDF graphs. Since conventional
> layout techniques for screen and paper have a tree-based target model
> (pages/screens,blocks,lines,characters), somewhere in the process you
> must find or make a tree from your graph-based data. By specifying how
> to construct one or more useful (i.e., "meaningful for formatting")
> spanning trees from a given RDF graph, you achieve greater flexibility
> and transparency in the process.

Any serializer to turtle, etc, produces a tree in the process.

For example, the serializer in rdflib.js uses the same algorithm for serializing turtle/N3, rdf/xml and also a form of graphical HTML layout the tabulator project uses for a "data view" of rdf resource. This latter also represents quoted graphs of N3 as rounded-corner bubbles around the graph, and is useful for vizualising at rule files.
https://github.com/linkeddata/rdflib.js
and specifically
https://github.com/linkeddata/rdflib.js/blob/master/serialize.js
for the serializer and 
https://github.com/linkeddata/tabulator/blob/master/js/panes/dataContentPane.js
for the code which generates the graphical view.


In general, a graph may have disconnected parts and so may have to be serialized to more than one tree.

(Note that if you allow N3's  reverse arc syntax  (   <#a> is :child of  <#b> ) the you can serialize any acyclic graph to turtle without having to generate arbitrary identifiers for blank nodes, just using the turtle [ ]  syntax.   That is one reason why it was a shame that the reverse syntax was omitted from Turtle.    The serializer above does not use the reverse link syntax in its output, so it generates a tree of forward links.  This goes against a  maxim of mine that forward links are not treated special over backward links in RDF... but I digress.)



> 
> I suppose such a system could be implemented with SPARQL, but it would
> be nice to have a non-SPARQL declarative syntax for specifying the
> spanning tree. RIF might work.
> 
> Regards,
> --Paul
> 
> [1] http://en.wikipedia.org/wiki/Spanning_tree
> 
>> 
>> I am working for bindings librdf for Ada2012. I could write such code
>> directly in Ada (so it may be easier), but better would be to make C
>> interface for this. I may write in Ada and leave TODO note "port it to
>> C".
>> 
>> Any response?
>> 
>> --
>> Victor Porton - http://portonvictor.org
>> 
> 
> 
> 
>