Latest XDI Graph Patterns and Statements docs with key revisions

[Drummond Reed <drummond.reed@xdi.org>]

I have uploaded new versions of both XDI Graph Patterns and the accompanying XDI Statements document (containing the XDI statement list for every graph pattern). The public URIs of the PDFs are:

  http://www.oasis-open.org/committees/download.php/41722/xdi-graph-patterns-2011-04-04.pdf
  http://www.oasis-open.org/committees/download.php/41724/xdi-statements-for-xdi-graph-patterns-2011-04-04.pdf

The only changes to these docs are proposed solutions to the two issues we discussed on last week's telecon:

1. Synonym expression.
2. Root context addressing.

Following are short explanations of the proposed solutions to both these issues that are documented in the two files above.

SYNONYM EXPRESSION

On last week's telecon there was consensus that XDI synonyms need to express full equivalence between two XRIs (i.e., that they identify the same resource), and that this equivalence should be expressed with $ relational arcs. That left the problem of how this should be best represented both visually in the graph, and in XDI statements.

The suggestion on the call was to represent the graph as a multigraph (http://en.wikipedia.org/wiki/Multigraph), i.e., allow multiple arcs between one parent node and one child node. However there are two drawbacks to this approach:

1. It breaks the "one XDI statement per XDI graph arc" rule that is currently leads to such a clean JSON serialization of an XDI graph and vice versa.
   
2. It leads to what I call "synonym explosion".

To illustrate synonym explosion, imagine an XDI graph where the first context node below the root context node has 3 synonyms from the root context node, a second context node below the first context node has 3 synonym arcs from the first context node, and a third context node below the second context node has 3 synonym from the second context node.

That means:

1. The first context node has 3 unique XDI addresses.
2. The second context node has 9 unique XDI addresses.
3. The third context node has 27 unique XDI addresses.
   

This would lead to disaster when it comes to being able to determine equivalence between two XDI addresses.

However there is a simple solution that prevents synonym explosion while still establishing synonyms as full equivalence relations. The first rule would be to NOT have the XDI graph be a multigraph -- in other words, to keep the one-arc-per-XDI statement rule--and require all synonyms to be expressed as a single $ relational arc from one synonym to another. The second rule is that any XDI context node that has a $ relational arc MUST NOT the the origin of any other arcs. In other words, a $ relational arc effectively terminates the XDI graph at the source context node and redirects any deeper addressing to the target node. The unique XRI identifying the target node can be called the canonical address of that node.

This rule allows the XDI address of any context node to be canonicalized into a single XRI, reducing the 27 unique addresses above to a single canonical address.

ROOT CONTEXT ADDRESSING

The second issue is how to address the root context node. Given the synonym solution above, it follows that a root context node cannot be identified via a synonym because it is already canonical. Thus the only way it can be identified is through a cross-reference from another context. Since this XRI cross-reference is an incoming contextual arc from the other context, it means the only valid way to express a root context address is an XDI statement in the form:

     ()/$()/(cross-reference-here)

This reads: "The root context of this XDI graph is considered a subcontext of another XDI graph in a different context".

The examples I provided in the XDI Graph Patterns document are:

    ()/$()/(http://example.com/ox/=!0999.a7b2.25fd.c609)

    ()/$()/(=!0999.a7b2.25fd.c609)

In the first case, the value of the XRI cross-reference would be the equivalent of the URI identifying an RDF named graph. In the second case, the value is only an XRI i-number which must be resolved into a URI. The standard form of that statement (using $uri as a complex predicate) would be:

    (=!0999.a7b2.25fd.c609)$uri/+http/!1
    (=!0999.a7b2.25fd.c609)$uri/!1/(data:,http://example.com/ox/=!0999.a7b2.25fd.c609)

This also resolves our open questions about XDI context discovery: the process of discovering an XDI endpoint from an XDI context address is just a matter of making a query for the complex property above.

Hope this helps,

=Drummond (with a reminder that I'm travelling this week, so we won't be having an XDI telecon this Thursday)