W3C home > Mailing lists > Public > public-ws-policy@w3.org > May 2007

AI: Suggestions for explanation of normalization

From: David Hull <dmh@tibco.com>
Date: Thu, 24 May 2007 00:07:10 -0400
Message-ID: <46550F6E.4000904@tibco.com>
To: "public-ws-policy@w3.org" <public-ws-policy@w3.org>
I believe I have an action from today's call to suggest possible
improvements in the explanation of policy expression normalization. 
Before I do that, I would like to once again thank the WG for their time
and attention, and also take the opportunity to thank Maryann for an
excellent job of scribing.  At one point I was in the process of typing
in a clarification for the IRC log, only to see it appear almost
verbatim in the notes before I could finish typing it.  It doesn't get
much better than that.

With that said, here are some suggestions that come to mind.  For the
most part I believe they can be implemented or rejected independently.

    * Reverse the sense of the mapping described in 4.1.  That is,
      instead of saying that a normal-form expression enumerates the
      alternatives of a policy, etc. -- which implies a mapping from
      policies to equivalence classes of normal-form expressions modulo
      re-ordering -- say that the policy expressed by a normal-form
      expression contains an alternative for each <All> element, which
      in turn consists of an assertion for each child.  This defines a
      function from expression to policy, which makes it clear that each
      normalized expression, at least, has a unique meaning (the policy
      it maps to).  The equivalence classes are then the inverse images
      of policies, or in English: Expressions are equivalent if they
      express the same policy.
    * Look for ways to use XSLT to describe the rewrite rules.  I
      wouldn't be surprised if this has been considered already, in
      which case there's probably no need to re-visit. I'm also a bit
      surprised it didn't occur to me sooner.  XSLT is a widely-used,
      well-understood and executable formal notation for XML
      transformations, so it seems like a natural fit.  However, I'm not
      an XSLT guru.  There may be good reasons this isn't as feasible as
      it might seem.
    * Replace the description of "Comutative" with text on the order of
      "Re-ordering:  As policies and alternatives are unordered
      collections, the order of the child elements of <ExactlyOne>,
      <All> and <Policy> elements is not significant.  Normalized
      expressions which differ only in ordering express the same policy,
      and compact expressions which differ only in ordering will reduce
      to equivalent normal forms (and thus represent the same policy)." 
      The last sentence may be overkill, but it seems worth
      considering.  In other words, say "order is not significant" here
      as in section 3 instead of saying "commutative" here.
    * Re-reading, I see that the second example under commutative has
      comments reading "assertion" under <ExactlyOne>.  This should
      probably read "alternative".
    * Replace the "Associative" and "Idempotent" rules with a single
      rule, say "Absorption", on the order of "Absorption: An
      <ExactlyOne> child of an <ExactlyOne> element may be replaced by
      its children, and likewise for an <All> child of an <All>
      element."  This seems a particularly good candidate for XSLT.
    * The distributive rule is only defined informally by example,
      leaving it unclear how to handle cases like
      <All><A/><ExactlyOne><B/><C/></All>.  I believe this normalizes to
      <ExactlyOne><All><A/><B/></All><All><A/><C/></All></ExactlyOne>. 
      In general, distribution appears to compute the Cartesian product
      of its children, loose assertions acting as singletons.  If so, it
      would be good to mention this.  Failing that, it's still possible
      to define the "one from column A, one from column B ..." semantics
      rigorously and in such a way as to pick up the empty <ExactlyOne/>
      case as a special case.  I have a wonderful proof of this, but
      unfortunately this bullet point is too small to contain it :-). 
      Fermat jokes aside, I'd be glad to write up a definition if
      anyone's interested.
    * Add an explicit rule for nested policies.  I believe it would be
      <A><Policy><ExactlyOne>alt1 alt2 ...
      altn</ExactlyOne></Policy></A> => <ExactlyOne>
      <All><A><Policy>alt1<Policy></A></All>
      <All><A><Policy>alt2</Policy></A></All> ...
      <All><A><Policy>altn</Policy></A></All> </ExactlyOne>, assuming
      the nested policy is in normal form.  If not it would be good to
      know what it is.  This would probably be another good candidate
      for XSLT.  The text as it stands seems a bit informal.
    * If the previous changes are too much, rephrase "Associative"
      "Idempotent" and "Distributive" as reductions (replace X with Y)
      instead of equivalences (X is equivalent to Y).  While it's
      unlikely that anyone would try replacing
      <ExactlyOne><All><A/><B/></All></ExactlyOne> with
      <ExactlyOne><ExactlyOne><All><All><A/><B/></All></All></ExactlyOne></ExactlyOne>,
      it's not immediately clear that you'd never have to do something
      similar as a intermediate step in normalizing something more
      complex.  AFAICT, you never would, and normalization is a one-way
      process in which you are either in normal form (and can stop) or
      there is at least one application of the three rules available and
      applying any applicable rule will make progress.  A lot like
      beta-reduction and such except halting is guaranteed.  Note that
      "Commutative" should be left as an equivalence as it's defining
      equivalence classes, not reductions.

While checking this over, I noticed an apparent discrepancy in section
3.1.  This section defines a policy assertion and mentions that an
assertion may contain a policy /expression/ as one of its [children]. 
This implies that an assertion is an infoset.  That seems mostly OK in
and of itself, since we're interested in things like an assertion's
QName and maybe its attributes.  However, if we're nesting /policies/
then the thing nested inside an assertion should be a policy, not a
policy expression.  Further, the normalization rules dictate that in a
normalized expression, each nested policy has exactly one alternative,
while 3.1 appears to allow for any expression at all to be nested.  If
normalized expressions are meant to map closely to policies, then the
nested policy (expression?) should be restricted to contain only a
single alternative (or the restriction on multiple alternatives in
normalized expressions should be relaxed).
Received on Thursday, 24 May 2007 04:07:33 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:38:34 UTC