Re: equivalence chat transcript ( was RE: [xdi] Definition of $has metag

Subject: Re: equivalence chat transcript ( was RE: [xdi] Definition of $has metagraph predicate)

On Thu, Jan 14, 2010 at 2:11 PM, Barnhill, William [USA] <barnhill_william@bah.com> wrote:

Please change your name from 'anonymous' using the Settings button anonymous morphed into =bill.barnhill anonymous morphed into Drummond Drummond: The one problem with SoapHub is that you can't do multi-line messages markus : =markus +friend =giovanni markus : =markus +friend =giovanni =bill.barnhill: <b>foo</foo> markus : =markus +friend =giovanni =bill.barnhill: <b>foo</b> markus : =markus +friend =giovanni markus asked for a victim, I choose... Drummond =bill.barnhill tests =bill.barnhill: how did you do bold? markus : type /victim =bill.barnhill: oh, was /me Unknown/malformed action: /help Check ?help Unknown/malformed action: /? Check ?help -- Short-cuts -- /info [msg|-] - set/clear the room info message /me text - send some action text /nick name - change your name ?attendees - display members that have been in the room ?help - display this text ?history - display all old messages ?info - display the room info message ?members - display the current list of members ?q - display the current queue +q [names*] - add yourself (or names) to queue -q [names*] - remove yourself (or names) to queue Room information was updated by: markus xdi is fun anonymous morphed into giovanni =bill.barnhill: welcome giovanni! giovanni : here i'm Drummond: ahh, great giovanni : now I'll try to reconnect to the phc Drummond: are you still on the phone as well? Drummond: okay =bill.barnhill: distortion is still really bad giovanni, i'd say just use chat Drummond: I was just saying that the question of $has predicate definition is not one that should be answered by anyone's personal preference, but by uncovering the underlying principles/logic of the graph giovanni : I'm in the conf as well now Drummond: right, we can hear you, but the distortion is still really bad Drummond: so it sounds like today we'll have to use mostly chat giovanni : seems like there is some lag in delivery of my instant messages Drummond: yes, but not too much Drummond: I propose we look at Bill's last response in the email thread Drummond: and talk about that first giovanni : ok Drummond: Bill and I were discussing that equivalence is actually a very well defined concept in XDI because it is asserted by $is statements giovanni : ok. great, pls go on. I can hear you quite well Drummond: in other words, you +a can be equivalent to +b if there is either the statement +a/$is/+b or the inverse Drummond: Now, here is a really good question: can you say that +a/$is/(+a)? Drummond: Meaning, it is a valid statement that COULD be true? Drummond: My answer is no =bill.barnhill: So in my pas couple of messages I explained that I thought there are two versions of equivalence: logical equivalence represented by two XRI's either both resolving or neither resolving, ie one XRI being resolvable implies the other is as well; and resolution equivalence, that both XRIs resolve to a metadata graph (XDI graph) that contains the same statements. Drummond: the same node in the XDI RDF graph cannot be at the same time a subject in one context and the context that contains it Drummond: that is logically impossible Drummond: I am reading Bill's message now =bill.barnhill: I recommend we do not use the phrase equivalent without qualifying it as either resolution equivalence (ie alias), or logical equivalence... Drummond: So we're going to discuss the meaning of the word "equivalence" Drummond: Bill is going to give us his definitions of "logical equivalence" and "resolution equivalence" giovanni : there is an article on logical equivalence in wikipedia =bill.barnhill: So logical equivalence is defined by the function 'resolvability' R : XRI -> Boolean. Two XRIS are logically equivalent if and only if R(A) implies R(B) and vice versa giovanni : in other words we are saying that if +a/$has/+b is in the graph, then +a/+b should appear in the graph and viceversa. Note that this does NOT mean that +a+b (which is produced by +a/$has/+b) is the same node as +a/+b Drummond: giovanni, we're talking right now and not typing, so hold on to this question for a minute Drummond: Bill and I are agreeing that what he means by the term "resolution equivalence" is the same thing I have been meaning by the term "equivalence", which is that two XDI addresses are equivalent if they resolve to the same XDI graph Drummond: So we were just discussing that with respect to Web architecture, XDI is a mime type (actually, a family of mime types - XDI XML, XDI JSON, XDI X3 - and possibly several variants of X3) Drummond: but all of the XDI mime types are ways of serializing the same logical XDI RDF graph giovanni : I'm hearing you. Once agreed on "resolution equivalence" can we go now to "logical equivalence"? Drummond: Bill is noting that the words "the same logical XDI RDF graph" are accurate, but the way RDF people might put it is, "the same XDI model" Drummond: Answer to Giovanni: yes Drummond: Bill is pointing to his definition of "logical equivalence" now =bill.barnhill: So logical equivalence is defined by the function 'resolvability' R : XRI -> Boolean. Two XRIS are logically equivalent if and only if R(A) implies R(B) and vice versa giovanni : in other words we are saying that if +a/$has/+b is in the graph, then +a/+b should appear in the graph and viceversa giovanni : correct? Drummond: Bill is saying that logical equivalence is the same as bi-directional implication =bill.barnhill: spot on giovanni giovanni : great Drummond: yes, I agree as well, however I don't think that is the root of the problem we are having with the $has definition =bill.barnhill: I'm not sure because associativity is defined in terms of equivalence, so in order to define associativity we need to determine what we mean by equivalence giovanni : instead I think it is . This is about the second part: associativity giovanni : a smile =bill.barnhill: whats that symbol? Drummond: Yes, I propose that we have a shared definition of equivalence, and two terms: logical equivalence and resolution equivalence =bill.barnhill: Drummond: so now, we can tackle the question of reification and associativity Drummond: So the issue, in black and white, is: which of the following two is true: =bill.barnhill: If grouping and xref then saying XRI's are logically left-associative means that for all XRIs a,b,c,d the following hold true: abc <=> (ab)c dabc <=> ((da)b)c and for right-associative: abc <=> a(bc) dabc <=> d(a(bc)) etc. Note that right-associative or left-associative is not considered associative, that's considered the union of the two: abc <=> a(bc) <=> (ab)c dabc <=> d(a(bc)) <=> ((da)b)c etc. Drummond: Hold on that statement for a minute, Bill =bill.barnhill: <=> Drummond: First we need to agree on a notational symbol for logical equivalence Drummond: and that is? Drummond: there we have it <=> =bill.barnhill: and = for resolution eq. Drummond: okay, now I can pose the question again Drummond: which of the following is true Drummond: 1) +a/$has/+b <=> (+a/+b) or 2) +a/$has/+b <=> +a/+b Drummond: that is the question! Drummond: Now, as you know, I have been arguing only #1 Drummond: Bill is saying it might be both Drummond: For reasons I will explain, i don't think it can be both, but let's explore this now Drummond: Bill is going to take a moment to type in his reasoning =bill.barnhill: Ok, so let's assume we have a graph which asserts +a/+b. Ok? Drummond: Yes =bill.barnhill: If it asserts +a/+b then the statement +a/+b is in the graph, by definition. Drummond: Yes =bill.barnhill: So R(+a/+b) = True Drummond: Note: once again, we are about to run out of time just when we are getting to the real heart and soul of it Drummond: ARRRGHHH! =bill.barnhill: We can get the graph containing statements about any statement in the graph, and that graph will only exist if and only if the statement is in the graph. put more simply (+a/+b) is resolvable, or R(+a/+b) = True. Generalizing this we see that if R(X) = True then R((X)) = True, meaning X and (X) are logically equivalent Drummond: It seems the import of what you are saying is that +a <=> (+a) giovanni : resolution = your statement is true; fault = your statement is false =bill.barnhill: but not +a = (+a) Drummond: Yes! Drummond: A $is statement in an XDI graph establishes what Bill calls "resolution equivalence" giovanni : I think we can keep the second part of the discussion (associativity) for next week giovanni : bb!
Kind regards,

Bill Barnhill

Booz Allen Hamilton - Rome, NY

315-330-7386 | william.barnhill.ctr@rl.af.mil | barnhill_william@bah.com

From: Barnhill, William [USA] [barnhill_william@bah.com]
Sent: Thursday, January 14, 2010 4:04 PM
To: Drummond Reed
Cc: OASIS - XDI TC
Subject: RE: [xdi] Definition of $has metagraph predicate

Hi Drummond,

***** QUOTE *****

The problem I have is, what does it mean to "resolve to the same XDI document". The XRIs representing the XDI subjects +a and +b could both resolve to the same XDI document and they are not equivalent in any way. They are completely different nodes in the XDI RDF graph.

***** END QUOTE *****

They're different nodes in the XDI RDF graph, yes, and we don't know anything about their logical equivalence. If +B is resolvable in any graph in which +A is resolvable and vice versa then they are logically equivalent. If they resolve to the same node then they are aliases and are resolution equivalent. I think of resolution as a function, say D. If resolution of +A and !12 both resolve to http://example.org/foo.html (lets call this U) then D(+A) = U, D(!12) = U, D(+A) = D(!12). Resolvability can also be viewed as a function R.

***** QUOTE *****

I guess the problem I'm having is that when we talk about equivalence, I'm talking about a very simple and definitive test: does the XRI representing the XDI statement identify the same NODE in an XDI RDF graph? (Note: not the same DOCUMENT - that's the entire context for an XDI RDF graph - but the same NODE.)

***** END QUOTE *****

This seems to say to me that any XDI XRI will always resolve to an XDI graph as it's document. To me it can resolve to two things depending on the resolution result requested: and XDI graph (metadata about the document ) and an addressed document. A special case is when the document is an XDI graph in which case there's only one possible resolution result. Are you saying that by equivalence you mean the XDI graph returned by resolution of A contains the same statements as the graph returned by resolving B? To me that's wat it sounds like when you say 'the same node'.

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 14, 2010 3:39 PM
To: Barnhill, William [USA]
Cc: OASIS - XDI TC
Subject: Re: [xdi] Definition of $has metagraph predicate
[Sorry, hit the wrong key. Ignore the last message - it was incomplete.]

Bill,

You propose several terms which I can't understand. You say,

***** QUOTE *****
Two XRI's are aliases (what I've previously been calling equivalent (note NOT logically equivalent)) if and only if they are logically equivalent AND resolve to the same document. Another way of saying aliases might be resolution equivalent.

Given the above (+A/+B) and +A/+B are logically equivalent, but are not aliases.
***** END QUOTE *****

The problem I have is, what does it mean to "resolve to the same XDI document". The XRIs representing the XDI subjects +a and +b could both resolve to the same XDI document and they are not equivalent in any way. They are completely different nodes in the XDI RDF graph.

I guess the problem I'm having is that when we talk about equivalence, I'm talking about a very simple and definitive test: does the XRI representing the XDI statement identify the same NODE in an XDI RDF graph? (Note: not the same DOCUMENT - that's the entire context for an XDI RDF graph - but the same NODE.)

If two XRIs identify the same node in an XDI RDF graph, then they are equivalent. If they do not identify the same node, they are not equivalent.

I believe this test is at the heart of the issue we are discussing. If we want to give this test another name, that's fine with me, but I still believe it's the test that is relevant here.

=Drummond
On Thu, Jan 14, 2010 at 6:02 AM, Barnhill, William [USA] <barnhill_william@bah.com> wrote:
I think I may see the root of the problem. Drummond you say in the last email:

"First, let's tackle the question of equivalence of +a and (+a). On last week's telecon, Bill said that (+a) infers +a. While I agree that (+a) infers that +a exists, I was adamant that +a and (+a) could not identify the same node in an XDI RDF graph or the logic of XDI will be destroyed."

I agree and think that different meanings of equivalence are causing an issue.

From my standpoint an XRI has two value in relation to a graph:

(a) it exists in the graph, i.e. it is resolvable

(b) it provides an address to a resolvable document, which may be an XDI graph

Applying this to the semantics of XDI, an XRI assertion is true if it is present in the graph, i.e. if (a) is true. The semantic reasoning does not concern itself with the document an XRI addresses, except when it is another XDI graph. In that special case the XRIs in the document are a sub-graph that is part of the larger graph,so we're still really only concerned with a.

So two XRIs are logically equivalent if and only if they are both resolvable (logical true) or neither are resolvable (logical false).

Two XRI's are aliases (what I've previously been calling equivalent (note NOT logically equivalent)) if and only if they are logically equivalent AND resolve to the same document. Another way of saying aliases might be resolution equivalent.

Given the above (+A/+B) and +A/+B are logically equivalent, but are not aliases.

Does everyone agree?

Still doesn't solve the associativity issue, in fact it expands it to logical associativity and resolution associativity.

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 14, 2010 5:15 AM
To: Barnhill, William [USA]
Cc: OASIS - XDI TC
Subject: Re: [xdi] Definition of $has metagraph predicate
Bill,

You are correct that the problem you describe stems from the assumption you make that a $has statement implies a min cardinality of 1. This is contrary to the conclusion that we reached as a TC last spring, and which was documented in the wiki spec (http://wiki.oasis-open.org/xdi/XdiOne/RdfGraphModel#A.24hasand.24is.24has):

******* BEGIN EXCERPT ********

[TODO: add explanation that $has statements do not and cannot infer cardinality.]

******* END EXCERPT ********

In this message, I will: 1) explain what I believe the source of the problem is, and 2) show why it is logically disastrous for XDI to say that either (+x/+y) is equivalent to +x/+y (or for that matter to say that +a and (+a) are equivalent).

PART ONE: WHAT I BELIEVE THE SOURCE OF THE PROBLEM IS

I believe the source of the problem is the interpretation of what is currently the following text from our wiki draft spec:

******* BEGIN EXCERPT ********

The $has metagraph predicate describes the relationship between a node and an outgoing arc in the XDI RDF graph. The subject of a $has statement is the XRI of the node from which the arc originates, and the object is the XRI of the arc.

******* END EXCERPT ********

Reading this sentence, I completely understand how TC members are coming away with the understanding, "$has statements are saying there is an RDF arc on an RDF node". While this is in fact true, the problem is that this is not the complete semantics of a $has statement. The complete semantics are that a $has statement is identifying a relationship. In doing so, the $has statement is creating a new node in the XDI RDF graph. That node is an XDI context (an identifiable XDI RDF graph). That XDI RDF graph consists of a single XDI RDF subject node (the subject of the $has statement) with a single XDI RDF outgoing arc (the object of the $has statement).

What this means – and this is the reason the parentheses are so important – is that what is identified by the $has statement is not the XDI RDF subject node inside the graph, nor the XDI RDF arc inside the graph, but the XDI RDF context containing the graph.

That XDI RDF context by itself is another XDI RDF node. Just a node. The $has statement that identifies this node does not assert any arcs (either outgoing or incoming) on this new XDI RDF node. It only asserts that what defines this node is that: a) it is an XDI RDF context, and b) this XDI RDF context that contains a graph consisting of one node and one outgoing arc.

Since this can be difficult to visualize, I have added a new Appendix B to version 3 of the XDI RDF Cell Graphs PDF that I just uploaded tonight. The link is:

http://www.oasis-open.org/committees/download.php/35926/xdi-rdf-cell-graphs-v3.pdf

I'd like to go over Appendix B on tomorrow's call because I believe it can settle this question about the definition of $has once and for all.

PART TWO: WHY (+X/+Y) AND +X/+Y CANNOT BE EQUIVALENT

First, let's tackle the question of equivalence of +a and (+a). On last week's telecon, Bill said that (+a) infers +a. While I agree that (+a) infers that +a exists, I was adamant that +a and (+a) could not identify the same node in an XDI RDF graph or the logic of XDI will be destroyed.

The reason is that +a identifies a specific node withing an XDI RDF graph, while (+a) identifies THE GRAPH CONTAINING THE NODE +a, which we call its XDI context. I think we can all agree that the node and the graph containing the node cannot be the same thing, or else the entire concept of XDI contexts collapses.

The same is true of any form of reification in XDI RDF. Let's take the example of (+x/+y) and +x/+y. If they are equivalent – if they identify the same XDI RDF graph node, then they can be substituted for each other in XDI RDF statements. That would mean that the following two XDI statements would both be valid:

(+x/+y)/+z/+k

+x/+y/+z/+k

But the second statement is not valid XDI RDF. What makes the first statement valid XDI RDF is that the parentheses identify a single XDI RDF node – the graph CONTAINING the graph +x/+y – as the subject of the statement that has the predicate +z and the object +k. As soon as you take away those parentheses, to get the XDI RDF statement +x/+y, you no longer are identifying an XDI RDF subject. Rather you have an XDI RDF subject and an XDI RDF predicate, which means you can only add an XDI RDF object.

This is why the parentheses, representing reification, are so critical to XDI semantics. Just as an RDF statement and the reification of that RDF statement are not the same thing in RDF, an XDI RDF statement and the reification of that statement (enclosing it in parentheses) are not the same thing in XDI RDF.

Again, I believe the new Appendix B in the XDI RDF Cell Graphs document will help illustrate this. I look forward to discussing it on the call tomorrow (agenda going out now).

=Drummond
On Wed, Jan 13, 2010 at 6:01 AM, Barnhill, William [USA] <barnhill_william@bah.com> wrote:
Coments inline, look for =Bill.Barnhill+comment and =Bill.Barnhill+endcomment

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: Wednesday, January 13, 2010 4:43 AM
To: OASIS - XDI TC
Subject: [xdi] Definition of $has metagraph predicate
Giovanni's message raised the question of whether there is consensus on the TC about the definition of $has semantics that we reached last spring and documented on May 15 2009 the wiki spec (http://wiki.oasis-open.org/xdi/XdiOne/RdfGraphModel).

=Bill.Barnhill+comment

Based on the email threads I think we cannot have consensus yet.

=Bill.Barnhill+endcomment
In that definition, we say (emphasis in red added):

********** EXCERPT ***********

The $has metagraph predicate describes the relationship between a node and an outgoing arc in the XDI RDF graph. The subject of a $has statement is the XRI of the node from which the arc originates, and the object is the XRI of the arc.

The inverse predicate, $is$has, describes the same relationship, however the subject and object are reversed, i.e., the object is the XRI of the node from which the arc originates, and the subject is the XRI of the arc.

When used alone as a metagraph predicate, $has is an assertion that reifies this subject/predicate relationship so that this reification can serve as a new XDI RDF subject node. The XDI address of this new subject node is a direct concatenation of the XRI for the subject of the $has statement and the XRI for the object of the $has statement. For example:
        +x/$has/+y     ==>     (+x/+y)     ==>     +x+y
*********** END EXCERPT ************
=Bill.Barnhill+comment

I believe we may reached consense on the above. I think it would be helpful to hash out a list of axioms like this (the above would be 6 separate axioms and hold an informal recorded vote (OASIS voting process maybe but seems heavy weight).

=Bill.Barnhill+endcomment

Also, at the end of the $has and $is$has definition section, we said:

********** EXCERPT ***********

[TODO: add explanation that $has statements do not and cannot infer cardinality.]

=Bill.Barnhill+comment

I don't remember reaching consensus on this. I remember you and Markus have said that you believe the above must be the case. I think $has must infer a minCardinality of 1 and have said so in the past.

=Bill.Barnhill+endcomment

*********** END EXCERPT ************

The red highlighted section in the first excerpt documents, in my recollection, the realization we had that $has statements expressed a reification of a subject/predicate relationship. That's why the parentheses on (+x/+y) are necessary.

Secondly, the fact that a $has statement resulted in reification that produce a new XDI subject node explains why $has statements have no cardinality – a conclusion that as I recall clearly had consensus across all of us that were active in the discussion.

=Bill.Barnhill+comment

Drummond I do not see how the first part explains the second, can you or Markus do a contradiction proof that shows that if $has statements have a minCardinality of 1 then reification can't work?

Sounds like we didn't have enough people active in the discussion. Was the discussion on the mailing list?

=Bill.Barnhill+endcomment
To use an analogy to English, I can say "ball color", but that statement has no cardinality about ball colors – it is just defining a TYPE of color. Type has no cardinality.

If we wanted to talk about the specific colors a specific balls has, we would say, "a ball has a color" (i.e., a $has$a relationship). With a $has$a relationship, you can now add cardinality, i.e., "a ball has 3 colors".

But "ball color" as a concept (a noun in English), identifying a type of color, is very different than the statement "a ball has a color", which is not a noun, but a complete statement about the relationship of a ball (a noun) and "color" (another noun, representing a property). In XDI, I believe this is illustrated by the difference between the following:
        $HAS STATEMENT
        ball color

        +ball/$has/+color
        (+ball/+color)
        +ball+color

        $HAS$A STATEMENT
        ball has a color

        +ball/$has$a/+color
        +ball/+color
In conclusion, I believe the current definition of $has is what is currently documented in the spec, as specifically illustrated in the example:
        +x/$has/+y     ==>     (+x/+y)     ==>     +x+y
The only revision I would make to this example is that the arrows may imply the inferences are only unidirectional, while I think we all believe they are bidirectional. So the revised diagram would be:
        +x/$has/+y     <==>     (+x/+y)     <==>     +x+y
If this is true, then I believe it follows that $has statements cannot be either only left or only right associative, but only full associative, because if the inferences above are true, then both of the following are true:
        +x+y/$has/+z     <==>     (+x+y/+z)     <==>     +x+y+z
        +x/$has/+y+z     <==>     (+x/+y+z)     <==>     +x+y+z
Again, I believe this is entirely logically consistent, because it also means:
        +x+y+z/$is$a/+z
        +x+y+z/$is$a/+y+z
=Bill.Barnhill+comment

I changed my mind on this one and agree on fully associative

=Bill.Barnhill+endcomment
Now, it is important to point out (which we do not currently do in the spec – I think this should be fixed) that left or right associativity CAN be specified through the use of XDI reification (cross-references). In other words, to make +x+y+z either left or right associative, the XDI statements would be:
        (+x+y)/$has/+z     <==>     ((+x+y)/+z)     <==>     (+x+y)+z
        +x/$has/(+y+z)     <==>     (+x/(+y+z))     <==>     +x(+y+z)
=Bill.Barnhill+comment

To me the above just doesn't hunt as they say in the south. Or rather it does, but doesn't say what I think you mean to say. In english I would translate (+x+y)+z as saying the following: the statement +x+y has a metadata property +z.

This discussion and above example may mean we need to revisit discussion of a grouping operator, which kind of got dropped after the last face to face.

=Bill.Barnhill+endcomment

I believe this provides the expressivity that Giovanni believes is required to accurately reflect semantics where two XDI RDF nodes can only be considered in their own context (e.g., his "Markus contract sig" example, where "Markus contract" is to be treated as a unit).

The result, in my understanding, is a definition that has no logical inconsistencies or ambiguities.

So, the question to the TC is: does anyone disagree with these definitions? If so, why?

=Bill.Barnhill+comment

Yes, for the above reasons and the reasons in the previous email today. I think we can't address these definitions as a single unit. We need to look at each in turn starting with the most fundamental ones, get agreement, and build from there. I'd suggest starting with $has implying minCardinality of 1.

=Bill.Barnhill+endcomment

=Drummond

xdi message