Subject: Regarding Graphs

From: Danny Ayers <[email-masked]>
Date: Sun, 9 Jan 2005 13:23:04 +0100

There were a couple of points made in recent discussions that might
have been misleading. One was that Atom is a tree. The XML may use
that structure, and in it's simplest form the information being
represented may be tree-shaped, but that isn't necessary  the case.
For example:

<feed xmlns...>
   <head>
       <link href="http://example.org/feed"/>
...
   </head>  
   <entry>
      <id>http://example.org/entry</id>
      <link rel="related" href="http://example.org/feed" />   
...
   </entry>
</feed>

If resources are view as nodes, then http://example.org/feed has two
parents. The containment tree is violated.

From one or two other recent posts a casual bystander might have
concluded that it is necessary to know graph theory to use RDF. This
isn't really the case. A similar suggestion has been used in the past
[1,2,3] to imply RDF is harder than it actually is. In that sense,
it's completely unfounded.

All you need to know is that RDF data can be visualized as a node and
arc (edge) graph. The arcs have a direction, i.e. it's a directed
graph. The same information can be represented either as a circle &
arrow kind of diagram, as a list of statements (triples) or in one of
the serialization formats like RDF/XML or the more human-friendly
Turtle.

Viewed as a list of statements, the information in the Atom snippet
above could be expressed something like:

feed hasHref http://example.org/feed
feed hasChild entry
entry hasID http://example.org/entry
entry hasRelated http://example.org/feed

Anyone working on the Web is dealing with graphs all the time. There's
the Web itself, with pages as nodes and links as arcs. Gopher might
have evolved into the World Wide Tree, but didn't. Trees are a
constrained subset of graphs, so they can be assimilated in a hugely
interconnected environment like the Web (resistance is futile!).

Anyone programming is likely to be using considerably more complex
graphs than what's usually found in RDF. The relationships between
entities in, say, the Java class libraries can get very twisty. (You
can use similar visualization, using something like UML).

This isn't to suggest that the containment tree of XML isn't useful,
far from it. It's a very good fit for most documents we have to deal
with, and a considerable amount of data. Other data can be more
table-shaped, which can be done in XML but the syntax starts to look a
little strained. But many real-world data structures (like the Web)
don't fall neatly into trees or tables, and the more general graph can
be useful. XML can be used effectively for serialization formats,
pretty much irrespective of the data structure. But the syntax may get
ugly if the data model is too far removed from Tree.

Generally the graph data structure is our friend, and should be
welcomed with open arms (or angle brackets).

Cheers,
Danny.

[1] http://static.userland.com/userLandDiscussArchive/msg007482.html
[2] http://www.xent.com/aug00/0371.html
[3] http://archive.scripting.com/2004/07/16

-- 

http://dannyayers.com

---

From: "S. Mike Dierken" <[email-masked]>
Date: Sun, 9 Jan 2005 10:59:01 -0800

> parents. The containment tree is violated.

I'm pretty sure the discussion was related to the content of a single XML
document instance, rather than to resources distributed across a network.
Once a piece of software traverses outside of an XML document instance, it
is no longer containment.

> But many real-world data structures (like the Web)
> be useful.
I don't consider the Web a data structure. But that's more likely just a
choice of wording.

> XML can be used effectively for serialization formats,

I think you've nailed the issue - serialization of structure .vs. markup of
information.

---

From: Danny Ayers <[email-masked]>
Date: Sun, 9 Jan 2005 20:17:31 +0100

> is no longer containment.

How about something like:

<feed xmlns...>
...
   <entry>
      <id>http://example.org/entryA</id>
      <link rel="next" href="http://example.org/entryB" />
...
   </entry>
   <entry>
      <id>http://example.org/entryB</id>
      <link rel="previous" href="http://example.org/entryA" />
...
   </entry>
</feed>

Cheers,
Danny.

-- 

http://dannyayers.com

---

From: "S. Mike Dierken" <[email-masked]>
Date: Sun, 9 Jan 2005 11:57:27 -0800

>       <link rel="previous" href="http://example.org/entryA" />

Maybe if you had the following instance you might be able to say one
document is a graph.
<feed >
 <entry id="entryA">
    <link href="#entryB" />
 </entry>

 <entry id="entryB">
    <link href="#entryA" />
 </entry>
</feed>

Otherwise you just have three resources (including the example itself as an
un-identified resource) and even then http://example.org/entryA might or
might not reference back into the un-identified resource (that the example
xml comes from).

I really didn't mean to sidetrack the original discussion. These are not the
droids you're looking for. Nothing to see here. Move along.

---

From: "Roy T. Fielding" <[email-masked]>
Date: Sun, 9 Jan 2005 15:20:56 -0800

> represented may be tree-shaped, but that isn't necessary  the case.

No, the element containment hierarchy that establishes default
relationships between data and metadata is a tree.

> parents. The containment tree is violated.

Nonsense.  The containment tree tells us what the tail of the link
is, not the target of those links.  The information is going to
have far more relationships just by virtue of the content text,
and thus the information will be a graph even if the relations
are not made explicit via links. Their containment is only a
very small subset of those relationships and cannot be violated
by the mere presence of other types of links.

The reason this topic came up was because people wanted to
know how the format is extensible given the implicit relationship
between feed, entry, and entry elements.  Containment is the only
answer needed because all other relationships are explicitly
targeted by a URI.

Personally, what I would change in the format is elimination
of head and make feed a recursive element.  Then there would be
no doubt as to the hierarchical relations and feed vacuums can
compose multiple feeds to their heart's delight without changing
the entries at all.

....Roy

---

From: Henry Story <[email-masked]>
Date: Mon, 10 Jan 2005 00:38:15 +0100

Well on this one at least we have some agreement. I have been arguing 
that for reasons of elegance for some time now that feed should be a 
subclass of Entry [1], and recently that the head is really hardly any 
different from an Entry [2].
But my Pace never seems to have got picked up in the editorial process.

Henry Story

[1] see the UML diagrams here
     http://www.imc.org/atom-syntax/mail-archive/msg04494.html
[2] http://www.intertwingly.net/wiki/pie/PaceEntriesAllTheWayDown2

---

From: Danny Ayers <[email-masked]>
Date: Mon, 10 Jan 2005 12:31:16 +0100

On Sun, 9 Jan 2005 15:20:56 -0800, Roy T. Fielding <[email-masked]> wrote:

> are not made explicit via links. 

Well yes, that was really what I was trying to say, that there are
more relationships than those expressed by the tree.

Their containment is only a
> by the mere presence of other types of links.

If you restrict the set of entities and relationships under discussion
to those directly involved in containment relationships, then sure,
containment will not be violated.

> answer needed because all other relationships are explicitly

Other relationships can be targetted by a URI, and this with
containment can be enough to describe all the relationships needed.
But my original point was that it wasn't being made explicit.

> compose multiple feeds to their heart's delight without changing

I think this approach was suggested fairly early on, I'm not sure why
it didn't make it through, possibly the argument that flatter is
simpler (for non-Functional developers). The (recursive) nesting
approach can certainly work well, I've seen striped RDF/XML that looks
like this, even the overstretched OPML (sometimes) works because of
it.

I'm not sure how you'd deal with multiple occurrences of the same
entry/feed in different layers. I suppose they could be referred to
through their URIs.

Cheers,
Danny. 

-- 

http://dannyayers.com