Some other data points to maybe consider...
I believe some sip/sdp-related work on content negotiation looked at this
(RFC2533) and decided that they did not want to go with the full algebraic
complexity. So (I think) they took an approach of profiling the structure
to use a normal-form subset which is inherently easier to process. A
possible advantage of this approach is that it leaves a clear path to
introduce more general forms of expression of they are later found to be
needed. Sorry, I have no specific references for this.
On ordering, that may be a difficult dependency to evolve away from once it
has been introduced.
And finally, having some similarities with the RFC2533 approach, there has
been research into a topic known as "description logics" over the past
(approx) 15 years that takes a slightly different slice on the use of
logical expressions to describe things. The goal of this work has been to
balance expressive power with computational tractability. (It can be shown
that a fully generalized solution based on first order predicate logic is
not always decideable.) The key idea is being able to perform a
subsumption computation, finding a description that minimally subsumes two
or more given descriptions. I found a paper by Alex Borgida was a useful
introduction, though there are many others:
http://citeseer.nj.nec.com/borgida95description.html
or:
http://www.cs.rutgers.edu/~borgida/
(Look for "Description Logics in Data Management (1995)")
#g
--
At 09:48 03/06/03 -0600, Alex Rousskov wrote:
On Tue, 3 Jun 2003, Graham Klyne wrote:
> I don't know if it helps, but some similar issues to those you
> mention were addressed in the content negotiation work I did a while
> back (RFC2533).
Thanks for the pointer! It looks like your RFC may be very useful to
OCP implementors, especially if we decide to support complex feature
expressions like "(A2 and (B1 or B2)) or (A1 and B1)" as opposed to
simple (but, as you note, potentially very long) "normal" AND/OR
lists. My undestanding is that RFC 2533 outlines a way to
pragmatically match [complex] feature expressions in negotiation
offers with available/desired capabilities, also a [complex] feature
expression. A how-to document replacing a dry book on boolean algebra,
sort of.
My current intention is to use very simple expressions. I convinced
myself that it is the right starting point after looking at what
negotiation mechanisms are offered by a few existing protocols that
are somewhat similar to OCP (BEEP, PPP, IKE*, etc). I did not find
anything that supports negotiation using really complicated feature
expressions. Yet, these protocols "work". Thus, I decided it would be
OK to start with something simple and extend the interface only of
actual need is detected.
I also agree that ordering dependency may lead to suboptimal
negotiations. However, again, it looks like our environment is simple
and structured enough to marginalize that risk.
Your application domain is probably different -- it already has a
pressing need for complicated content descriptions.
Thank you,
Alex.
P.S. RFC 2533 is the first RFC I have seen that mentions Prolog,
nice work!
-------------------
Graham Klyne
<GK(_at_)NineByNine(_dot_)org>
PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E