Subject: Re: Hashing, and Ted's concerns about wastefulness

From: Graham Klyne <[email-masked]>
Date: Tue, 02 Feb 1999 19:33:50 +0000

Ted,

(long-ish message -- sorry)

At 12:35 01/02/99 -0800, Ted Hardie wrote (quoting me, quoting Larry,
quoting Ted...)
[...]
>> #   (h.<URI>="<hash>")
>> 
>> within a capability expression (this conforms to current syntax rules),
>> where <hash> is calculated over the body of a notional auxiliary predicate:
>> 
>> #   (h.<URI>) :- 
>> #       (| (& (pix-x=640) ...)
>
>I think this is workable, but we will need to be very careful in presenting
>this to ensure that there is no confusion between g.<URI> h.<URI>;

After debating with myself whether this really matters, I agree.

>... we also
>need to specify exactly what you get if you retrieve h.<URI>.

I think that what you get is a copy of the hashed feature expression.

>> >> I suppose we can create a feature that is, in fact, a request for fh
>> >> to be disaggregated.  
>> >
>> >I think that's mixing descriptive information and protocol in
>> >an unfortunate way. I think disaggregation is likely to be
>> >protocol dependent, even though the semantics of "fh" is
>> >protocol independent.
>> 
>> Again, I agree.
>> 
>> If two expressions contain the same sub-expression:
>> 
>> #    (h.<hash>
>> or
>> #    (h.<URI>="<hash>")
>> 
>> then they are known to match at that point without disaggregation.  OTOH,
>> if they have different hash values then disaggregation is needed to
>> determine whether or not they truly match.  No additional "feature" is
>> required to trigger the disaggregation mechanism;  simply some kind of
>> "lazy evaluation" component in the feature set matching process.

>I think that we have a problem here related to the "directionality" issue
>Larry brought up with my previous message.

I'm not so sure... one reason is that I don't really agree with your later
statement:

>[...] I mean simply
>that we have to have some idea of what the disaggregation mechanisms are
>to get a solution that will work across protocols.

In this context, I regard "disagregation" as the process whereby the
feature set reference is replaced by the feature set expression;  i.e.
dereferencing.

I think the specific disaggregation mechanism is properly specified by the
application/protocol specification that uses the feature expressions.  The
feature set expressions have a defined meaning:  in the case of
(h.<URI>="<hash">), the meaning is identical to the equivalent feature
expression that hashes to <hash>.  How that substitution is performed does
not affect the meaning.

As for the directionality issue:  the feature set matching process is not
directional.  In order to establish communication between parties A and B,
then one of the parties must get a feature set expression from the other
and compare with what it has to hand.  The outcome of feature set matching
is not affected by which party does the matching (and any associated
fetching that may be required).  Thus, an application can choose how and
where feature matching is finalized:

For internet fax, current proposals have the recipient capabilities
presented to the sender who then selects an appropriate document format for
transmission.  HTTP has models that can work either way (client Accept-*
headers, server Vary headers, if I recall correctly).

>Think about it this way: This system works based on set intersection.
>If either party presents information about their set using a hash, the
>other party must be able to either recognize the predicates implied or
>disaggregate the hash in order to determine whether the sets
>intersect.  There are a couple of ways to do this, and they loosely
>fit different scenarios.

But, I submit, they both/all work with the feature set matching model.

>...  Send along the hash with the predicates, and
>you can use the hash in place of repeating elements without worrying
>that the other party won't understand it.

This is easy, and can just about be done with the current spec:  simply
carry an auxiliary predicate:

    ( <feature expression using sub-expression (h.<URI>=<hash>) )
    WHERE
        (h.<URI>) :- ( <expression> )
    END

>...  Refer to the hash with a
>URI that contains the disaggregated form, and the parties will
>sometimes be able to retrieve the disaggregated forms.

That would be the above case, omitting the WHERE clause.

>...  Indicate a
>failure to recognize and rely on in-bound communication to carry the
>disaggregated forms from the other party to the party expressing the
>failure.

I see cases 2 and 3 being essentially the same, in that they would rely
upon some application-specific "mechanism" to dereference unknown feature
expression tags.

>I strongly believe that we need to do 1 if we do anything at all.  I
>believe that 2 has value, but that the value is limited unless we
>specify pretty strictly how the disaggregated predicates are
>represented at the URI;

Sure.  I would say the -feature-syntax- does most of the work there.  Some
small amount of profiling would be needed, I think.

>... I am also worried that there are problems both
>with specifying a particular URL scheme for this and with not
>specifying one.  For 3, Larry and I seem to disagree on the utility of
>specifying a method for naming the failure as an "understanding the
>hash" issue, and I think we need to hear other voices on that part of
>the problem.

I don't think the method here is a one size fits all type of solution.  Any
given application would need to indicate an appropriate method.  For
example:  in WWW, retreive the resource indicated by the URI;   in e-mail
use the tag in a directory search or RESCAP (aka MAILCAP) resolution.

>None of this is to say that lazy evaluation isn't a good thing; I mean simply
>that we have to have some idea of what the disaggregation mechanisms are
>to get a solution that will work across protocols.

I think my comment about "lazy evaluation" may have been slightly at
cross-purposes.  I was saying that I did not think a specific feature to
trigger dereferencing was required.  I think you are discussing the
mechanism used to perform dereferencing.

>> Further, using my second proposal, two different tags:
>> 
>> #    (h.<URI1>="<hash>")
>> #    (h.<URI2>="<hash>")
>> 
>> can be assumed to match if the hash values are the same (e.g. for rebadged
>> versions of the same mobile phone).
>> 
>> An attractive property of this approach is that it can be used with the
>> current specification (with registration of the 'h.' facet), in many cases
>> will yield the correct result, and will never yield a false feature set
>> match.  Agents with additional knowledge can reconcile the apparently
>> different feature tags (this is also behaviour consistent with the current
>> specification.)
>> 
>
>Can someone (Bill, Graham, Larry) write up one of these proposals as
>an ID, so we can have something to discuss concretely?

I'd be happy to have a go at the (h.<URI2>="<hash>") proposal, if that
doesn't pre-empt anything that Bill is planning.  I would be more
comfortable if we had some consensus on scenarios and goals so that it can
be seen to address the perceived problem.

#g

------------
Graham Klyne
([email-masked])

---

From: Ted Hardie <[email-masked]>
Date: Tue, 2 Feb 1999 12:59:25 -0800 (PST)

Graham,
	Thanks for your message; I've snipped extensively in the reply,
just to keep this from becoming totally unreadable.  My apologies if
it get's hard to follow.

> After debating with myself whether this really matters, I agree.

Great.  I think there is a large chance naive users will confuse the
URI at which a feature is described and the URI at which a list of
features and their values is given, just because the syntax will
look so similar.  Anything we can do to make that as clear as possible
will be useful.

> I think that what you get is a copy of the hashed feature expression.

Yes, but we need to specify exactly how that is represented.  Remember
that most hashes on files care about every bit of whitespace and every
control character; if we don't specify the representation very well,
we will end up with conflicting hashes on equivalent feature expressions.

> feature set reference is replaced by the feature set expression;  i.e.

This is what I meant by disagregation; I'll adopt "dereferencing", if
you prefer. 

> That would be the above case, omitting the WHERE clause.

Only if you assume all the steps which are involved in retrieving the
dereferenced/disaggregated forms.  This is why I don't agree that the
mechanism of dereferencing/disaggregation can be dealt with *solely*
on a protocol by protocol basis. Remember that one of the goals of
this system is that feature information presented in it ought to be
usable across protocols and through protocol gateways.  If we leave
the dereferencing/disaggregation step totally within the purview of a
specific protocol, the http-based ones may well use
(h.http://www.foo.com/featurepredicates.txt=<HASH>) where directory
services based systems might use
(h.ldap://ldap.server.com/dn=featurepredicates,o=foo,c=us)=<HASH>)

As long as the <HASH> is the same, we don't have a problem. If a
lookup is needed and the "wrong" url scheme is used, the match fails
for lack of information.  Inband error reporting and retrieval may fix
that in some cases, but it remains a concern.  

> use the tag in a directory search or RESCAP (aka MAILCAP) resolution.

I don't want to be tarred with a "one-size" fits all brush here; I
want, instead, to say we have to make all the suits out of the same
materials.  That may mean that we say, for example, directory lookups
for these should be able to key on the <HASH>, rather than only on the
<h.URI>, but we don't specify what directory we use.  

> be seen to address the perceived problem.

Any concrete proposal would be good, and two may well be better at this
early stage.
		best regards,
				Ted Hardie

---

From: Bill Newman <[email-masked]>
Date: Tue, 2 Feb 1999 15:16:26 -0800 (PST)

Ted wrote (quoting Graham)

> we will end up with conflicting hashes on equivalent feature expressions.

How bad a problem is this? Is it is worth trying to assign the same
hash values to differently-represented-but-ultimately-equivalent
feature sets? It is a feature, but it adds complexity to the
specification and to each implementation.

Do you anticipate a pattern of usage where this feature would 
significantly increase efficiency?

> Any concrete proposal would be good, and two may well be better at this

Currently I'm inclined to just put my original proposal, modulo
incremental corrections and cleanups, into Internet Draft form.
However, I'll be rereading and rethinking the discussion at least one
more time before I make my proposal, so my thinking might change.

I'd be happy to see a concrete form of the h.<URI2>="<hash>" proposal
from Graham, or any other counterproposal from anyone else for that
matter, whether I'm pre-empted or post-empted.

  Bill Newman
  [email-masked]

---

From: Al Gilman <[email-masked]>
Date: Tue, 02 Feb 1999 20:46:03 -0500

>look so similar.  Anything we can do to make that as clear as possible

Can you give a concrete example of where someone could conceivably
mis-apply what they obtained on dereferencing such an URI, no matter what
the reference syntax is?

On the one hand (list of features and their values) one is following a
reference which supplies propositions about the current entity.

On the other hand, (tag definition reference) one is following a reference
which supplies propositions about any entity to which a property is applied
in association with this tag.  Including the current entity.

What if the cited document makes it clear whether it states propositions
about <self> or about <tagID>?

There is at least the option to distinguish these things in the [semantics
of the] cited document as opposed to in the citation.  Both of the examples
discussed here are qualifiers which serve to impose a subtype reduction on
the current entity.  Either one introduces new knowledge into the current
context.  What is the difference that must be denoted by syntax?  Assigning
a value may be treated as the ultimate subtype reduction.

Al

>(h.http://www.foo.com/featurepredicates.txt=) where directory