Re: [xdi] Change Request toward B4 (was Re: [xdi] XDI Grapher)

Thank you for writing such a clear message about what you perceive the problem is. This same issue became clear to me when working on the box graphing (which I propose to rename to “cell graphing” because it’s a better metaphor for dealing with data relationships).

Unfortunately I believe that defining $has relations to be strictly left associative actually introduces a logical inconsistency for which I know of no solution, and which would be fatal to our goal of making sure XDI is logically consistent. However, the alternative of defining $has relations as neither left nor right associative, but just associative (per the definition from Wikipedia below) avoids this logical inconsistency, thereby solving this problem and keeping XDI semantics consistent.

Let me first provide the definition of associativity from Wikipedia, then explain my reasoning in more detail.

Formally, a binary operation $*\!\!\!$ on a set S is called associative if it satisfies the associative law:

The evaluation order does not affect the value of such expressions, and it can be shown that the same holds for expressions containing any number of $*\!\!\!$ operations. Thus, when $*\!\!\!$ is associative, the evaluation order can therefore be left unspecified without causing ambiguity, by omitting the parentheses and writing simply:

However, it is important to remember that changing the order of operations does not involve or permit moving the operands around within the expression; the sequence of operands is always unchanged.

A very different perspective is obtained by rephrasing associativity using functional notation:

f (f (x, y), z) = f (x, f (y, z))

: when expressed in this form, associativity becomes less obvious.

Associativity can be generalized to n-ary operations. Ternary associativity is (abc)de = a(bcd)e = ab(cde), i.e. the string abcde with any three adjacent elements bracketed. N-ary associativity is a string of length n+(n-1) with any n adjacent elements bracketed^[1].

What I am proposing is that the definition of $has relations in the spec (i.e., the definition currently at http://wiki.oasis-open.org/xdi/XdiOne/RdfGraphModel#A.24hasand.24is.24has) should be clarified to be just associative as defined above, and NOT either left associative or right associative. The rest of this message explains why.

First, let me explain the logical inconsistency that either left or right associativity introduces. I’ll start by saying that I believe the source of misunderstanding in this area is the XDI use of parentheses (XRI cross-references). The problem is that in mathematics, parenthese are only used to group mathematical operations. Other than precedence, they have no other meaning.

In both XRI and XDI, however, parentheses are 100% significant. They are part of the identifier. Only in XDI do we define equivalence rules between XDI addresses that specify that certain XDI addresses that include parentheses are equivalent to others that do not. In fact these rules apply ONLY to $has statements, and they follow these very strict equivalence rules:

Again, it’s very important to clarify that the parentheses in the center XDI statement above are NOT OPTIONAL. They are required or else the equivalence is broken. In other words, +a/$has/+b is NOT equivalent to +a/+b and +a/+b is NOT equivalent to +a+b.

I think the only reason of considering +a/$has/+b+c and +a+b/$has/+c as producing the same statement +a+b+c was that it was not very clear how the $has operator work. But after our last phc we agreed that $has is a LEFT associative operator. This is enough to tell a parser that when a +a+b/$has/+c is encountered, the a+b+c statement is produced. Whereas when it finds +a/$has/+b+c, then the +a(+b+c) statement must be produced.

Here’s why it is impossible for +a/$has/+b+c to produce (i.e., be equivalent to) +a(+b+c). Following our own rules for $has statements, +a(+b+c) expands (is equivalent to):

…which, as I explained above, is a complete contradiction, since +b+c and (+b+c) are NOT equivalent.

This is why example B4 in the box graphing examples that you refer to asserts that all of the following XDI statements are equivalent:

The reason they are all equivalent is that if you apply these two simple transformation rules…

To me, this is logically consistent with full associativity. For example, in the following sequence of numbers related by addition….

….you get the same result no matter where you place parentheses, or how many parentheses you add. That’s because the addition operation is not left associative, or right associative, but fully associative.

I also believe it is graphically consistent. By this I mean that if you picture each $has relation as creating a directed path…

…then, just like the addition operation above, any way you group the segments of this path while maintaining the same overall order, once you put these groups back together, you end out with the same overall path.

Now, with all that said, let me finally turn to your point about English language analogies. You suggest that the statement “Markus parking slot” only follows from asserting “Markus parking has a slot” and NOT from “Markus has a parking slot”.

In English, I would assert that phrase resulting from a logical sequence of three or more nouns, where each noun describes the next, is full associative, meaning that like the set of numbers being added above, it can be grouped in any set of sequences, each of which makes its own logical unit, that when fully combined in the same sequence, creates the same final logical unit.

So, to be clear, I am not asserting that the individual logical unit groupings are identical, only the final result is identical. Here are three examples:

I would assert that the relationship between two nouns in the English language – without any special punctuation – is the same as the $has relation in XDI. And that the addition of quotes grouping two or more of the above words is roughly the equivalent of what parentheses do in XDI. For example…

This illustrates that in English, as in XDI, the addition of quotes to the sequence of words changes the semantics, i.e., the same sequence of English words with and without the quotes are NOT equivalent.

I hope this helps. It is such an important point that we’ll make it the first agenda item in tomorrow’s telecon (I’m sending the agenda next).

I think the answer is whether or not the XRI can be simplified by
contracting $has statements.

In B4, all of the following statements simplify to the same maximally
contracted XRI: +a+b+c .

(+a/+b)/$has/+c
((+a/+b)/+c)
(+a+b/+c)
+a/$has/(+b/+c)
(+a/(+b/+c))
(+a/+b+c)
+a+b+c

To me, this is a risk because it creates inconsistency in the semantic model.
As you know, I've highlighted this in a previous email:

Consider now: contract markus' signature

1) contract Markus has signature: you are asserting that a "specific" MARKUS (contract Markus) has a signature
2) contract has Markus' signature: you are asserting that CONTRACT has a specific SIGNATURE (Markus' signature)

only 2) seems to make sense to me.

Drummond answered that:

Now, in this case, you added particulr punctuation used in the English language: the possessive apostrophe. The use of that punctuation creates a conjunction between "markus" and "signature" that cannot be broker apart. This has a direct analog in XDI RDF - using a cross-reference to bind the two XRIs into one. In other words, instead of saying +a+b+c which is three XRI subsegments, you are saying +a(+b+c) which is two XRI subsegments.

I was not sure of this, as in other cases, when the possessive statement appears as subject-predicate, like "Drummond's friend", we do not use at all cross references and we simply express this using the $has statement: =drummond+friend

But, the very argument is that this may happen also in other kind of statements, not necessarily involving the possessive apostrophe.

Condider the following example where:

+a is =Markus
+b is +parking
+c is +slot

1. (+a/(+b/+c)) (=Markus/(+parking/+slot)) (=Markus/+parking+slot) =Markus/$has/+parking+slot, +parking/$has/+slot

2. ((+a/+b)/+c) ((=Markus/+parking)/+slot) (=Markus+parking/+slot) =Markus/$has/+parking, =Markus+parking/$has/+slot

Despite they look similar, they are asserting DIFFERENT concepts.
Bullet 1. says that markus owns a parking slot. Furthermore it asserts that a parking has a slot.
Bullet 2. says that markus owns a whole parking, not a parking slot. Furthermore it is saying that Markus's parking (i.e. one specific parking) has a slot.

I think the only reason of considering +a/$has/+b+c and +a+b/$has/+c as producing the same statement +a+b+c was that it was not very clear how the $has operator work. But after our last phc we agreed that $has is a LEFT associative operator. This is enought to tell a parser that when a +a+b/$has/+c is encountered, the a+b+c statement is produced. Whereas when it finds +a/$has/+b+c, then the +a(+b+c) statement must be produced.

I propose an AP for a CR on example B4 and consequently on the definition of $has given in:

http://wiki.oasis-open.org/xdi/XdiOne/RdfGraphModel#A.24hasand.24is.24has

Kind Regards,
Giovanni

PS: Markus's visual tool is great! Congratulation, Markus! :-)

On Wed, Jan 6, 2010 at 12:50 AM, Giovanni Bartolomeo <giovanni.bartolomeo@uniroma2.it> wrote:

Dear Drummond, Markus,

I want to come back on point B4.

I think the answer is whether or not the XRI can be simplified by
contracting $has statements.

In B4, all of the following statements simplify to the same maximally
contracted XRI: +a+b+c .

(+a/+b)/$has/+c
((+a/+b)/+c)
(+a+b/+c)
+a/$has/(+b/+c)
(+a/(+b/+c))
(+a/+b+c)
+a+b+c

To me, this is a risk because it creates inconsistency in the semantic model.
As you know, I've highlighted this in a previous email:

Consider now: contract markus' signature

1) contract Markus has signature: you are asserting that a "specific" MARKUS (contract Markus) has a signature
2) contract has Markus' signature: you are asserting that CONTRACT has a specific SIGNATURE (Markus' signature)

only 2) seems to make sense to me.

Drummond answered that:

Now, in this case, you added particulr punctuation used in the English language: the possessive apostrophe. The use of that punctuation creates a conjunction between "markus" and "signature" that cannot be broker apart. This has a direct analog in XDI RDF - using a cross-reference to bind the two XRIs into one. In other words, instead of saying +a+b+c which is three XRI subsegments, you are saying +a(+b+c) which is two XRI subsegments.

I was not sure of this, as in other cases, when the possessive statement appears as subject-predicate, like "Drummond's friend", we do not use at all cross references and we simply express this using the $has statement: =drummond+friend

But, the very argument is that this may happen also in other kind of statements, not necessarily involving the possessive apostrophe.

Condider the following example where:

+a is =Markus
+b is +parking
+c is +slot

1. (+a/(+b/+c)) (=Markus/(+parking/+slot)) (=Markus/+parking+slot) =Markus/$has/+parking+slot, +parking/$has/+slot

2. ((+a/+b)/+c) ((=Markus/+parking)/+slot) (=Markus+parking/+slot) =Markus/$has/+parking, =Markus+parking/$has/+slot

Despite they look similar, they are asserting DIFFERENT concepts.
Bullet 1. says that markus owns a parking slot. Furthermore it asserts that a parking has a slot.
Bullet 2. says that markus owns a whole parking, not a parking slot. Furthermore it is saying that Markus's parking (i.e. one specific parking) has a slot.

I think the only reason of considering +a/$has/+b+c and +a+b/$has/+c as producing the same statement +a+b+c was that it was not very clear how the $has operator work. But after our last phc we agreed that $has is a LEFT associative operator. This is enought to tell a parser that when a +a+b/$has/+c is encountered, the a+b+c statement is produced. Whereas when it finds +a/$has/+b+c, then the +a(+b+c) statement must be produced.

I propose an AP for a CR on example B4 and consequently on the definition of $has given in:

http://wiki.oasis-open.org/xdi/XdiOne/RdfGraphModel#A.24hasand.24is.24has

Kind Regards,
Giovanni

PS: Markus's visual tool is great! Congratulation, Markus! :-)

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

---------------------------------------------------------------------
To unsubscribe from this mail list, you must leave the OASIS TC that
generates this mail. Follow this link to all your TCs in OASIS at:
https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php

xdi message