[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: RE: [xdi] Change Request toward B4 (was Re: [xdi] XDI Grapher)
Hi Drummond,
I don't remember when we added the (+a/+b) part of:
+a/$has/+b <==> (+a/+b)
<==> +a+b
Can you refresh my memory on the need for doing that? I do remember
+a/$has/+b <==> +a+b
If we eliminated that element from the equivalence then your counter-example becomes
Following our own rules for $has statements, +a(+b+c) expands (is equivalent to):
+a/$has/(+b+c) <==> +a(+b+c)
If that is true, and you are saying at the same time that…
+a/$has/+b+c <==> +a(+b+c)
…then it would follow that…
+a/$has/+b+c <==> +a/$has/(+b+c)
which to me makes sense. If we consider the english version with the following: +a => =Markus +b => +friend +c => =Drummond and translating the XDI XRI fragment +friend=Drummond as being Drummond is the object of predicate +friend, which from our previous conversations means =Drummond is a =friend.
then I'd say....
(1) =Markus/$has/(+friend=Drummond) => /Markus/ /has/ /a friend Drummond/ and (2) =Markus/$has/+friend=Drummond => /Markus/ /has/ /a friend/ AND /a friend of Markus/ /is/ /Drummond/
I think this would mean there's an implied context there, making (2) shorthand for =Markus +friend / $has =Drummond
Also I have always considered parenthesis to be both part of the identifier in XRI and a grouping mechanism in XDI, because according to XRI spec resolution must treat the contents of an XRef as a single entity, which to
me seems to require an implication of grouping..
Kind regards,
Bill Barnhill
Booz Allen Hamilton - Rome, NY
315-330-7386 | william.barnhill.ctr@rl.af.mil |
barnhill_william@bah.com
From: drummond.reed@gmail.com [drummond.reed@gmail.com] On Behalf Of Drummond Reed [drummond.reed@xdi.org] Sent: Thursday, January 07, 2010 3:59 AM To: Giovanni Bartolomeo Cc: Markus Sabadello; OASIS - XDI TC Subject: Re: [xdi] Change Request toward B4 (was Re: [xdi] XDI Grapher) Giovanni,
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.
***** FROM http://en.wikipedia.org/wiki/Associative ******* Formally, a binary operation on a set S is called associative if it satisfies the associative law: Using * to denote a binary operation performed on a set An example of multiplicative associativity 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: xyz, 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]. ******** END WIKIPEDIA EXCERPT ********
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:
+a/$has/+b <==> (+a/+b) <==> +a+b
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.
So, let’s now turn to your example:
******* EXCERPT FROM GIOVANNI’S MESSAGE ********
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.
******* END EXCERPT ******
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):
+a/$has/(+b+c) <==> (+a/(+b+c)) <==> +a(+b+c)
If that is true, and you are saying at the same time that…
+a/$has/+b+c <==> (+a/(+b+c)) <==> +a(+b+c)
…then it would follow that…
+a/$has/+b+c <==> +a/$has/(+b+c)
…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:
(+a/+b)/$has/+c +a+b/$has/+c +a/$has/+b+c
The reason they are all equivalent is that if you apply these two simple transformation rules…
1) All XDI statements [x1]/$has/[x2] TRANSFORM TO ([x1]/[x2]) 2) All XDI statements ([x1]/[x2]) TRANSFORM TO [x1][x2]
…to all nine XDI statements above, then all nine reduce to:
+a+b+c
To me, this is logically consistent with full associativity. For example, in the following sequence of numbers related by addition….
7 + 8 + 3 + 4
….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…
+a -----> +b -----> +c -----> +d
…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:
Markus ball cover Markus ball cover Markus ball cover
car engine fan blade car engine fan blade car engine fan blade car engine fan blade
Asia continent jetstream direction indicator Asia continent jetstream direction indicator Asia continent jetstream direction indicator Asia continent jetstream direction indicator Asia continent jetstream direction indicator
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…
Asia “continent jetstream” direction indicator
…can only be parsed into:
Asia “continent jetstream” direction indicator Asia “continent jetstream” direction indicator Asia “continent jetstream” direction indicator Asia “continent jetstream” direction indicator
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).
=Drummond
******* BELOW IS GIOVANNI’S ORIGINAL MESSAGE ********
On Wed, Jan 6, 2010 at 12:50 AM, Giovanni Bartolomeo <giovanni.bartolomeo@uniroma2.it> wrote: Dear Drummond, Markus, I think the answer is whether or not the XRI can be simplified by
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.
On Wed, Jan 6, 2010 at 12:50 AM, Giovanni Bartolomeo
<giovanni.bartolomeo@uniroma2.it> wrote:
Dear Drummond, Markus, |
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]