Issue 4598 and Action-310 (was RE: Questions on normal forms

Reading through multiple mail threads on this topic, we propose the following clarifications to resolve issue 4598.

a) Clarification 1 - David H wants to clarify the distributive rule:

s/wsp:All distributes over wsp:ExactlyOne./wsp:All is distributive over wsp:ExactlyOne. That is, a wsp:All element containing only wsp:ExactlyOne child elements is equivalent to an wsp:ExactlyOne element containing, for each possible combination of one child element from each of the wsp:ExactlyOne element over which being distributed, a wsp:All element containing that combination./

b) Clarification 2 - David H wants to add an example (to the bottom of Section 4.3.3) to illustrate the case (where a combination of Optional=false and Distributive rules apply) that David and Asir discussed on the mailing list:

Consider another example, given the following compact policy expression:

(01) <wsp:Policy
        xmlns:sp="http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702"<http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702>
        xmlns:wsp="http://www.w3.org/ns/ws-policy"<http://www.w3.org/ns/ws-policy> >
(02)   <sp:RequireDerivedKeys />
(03)   <wsp:ExactlyOne>
(04)     <sp:WssUsernameToken10 />
(05)     <sp:WssUsernameToken11 />
(06)   </wsp:ExactlyOne>
(07) </wsp:Policy>

Applying Section 4.3.1 Optional Policy Assertions to @wsp:Optional="false" in Line (02), and distributing wsp:All over wsp:ExactlyOne per Section 4.3.3 Policy Operators for the assertions in Lines (04-05) yields:

(01) <wsp:Policy
        xmlns:sp="http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702"<http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702>
        xmlns:wsp="http://www.w3.org/ns/ws-policy"<http://www.w3.org/ns/ws-policy> >
(02)   <wsp:ExactlyOne>
(03)     <wsp:All>
(04)       <sp:RequireDerivedKeys />
(05)     </wsp:All>
(06)   </wsp:ExactlyOne>
(07)   <wsp:ExactlyOne>
(08)     <wsp:All>
(09)       <sp:WssUsernameToken10 />
(10)     </wsp:All>
(11)     <wsp:All>
(12)       <sp:WssUsernameToken11 />
(13)     </wsp:All>
(14)   </wsp:ExactlyOne>
(15) </wsp:Policy>

Note that the assertion listed in Line (02) in the first listing expands into an alternative in Lines (03-05) in the second listing.

Finally, noting that wsp:Policy is equivalent to wsp:All, and distributing wsp:All over wsp:ExactlyOne yields the following normal form policy expression:

(01) <wsp:Policy
        xmlns:sp="http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702"<http://docs.oasis-open.org/ws-sx/ws-securitypolicy/200702>
        xmlns:wsp="http://www.w3.org/ns/ws-policy"<http://www.w3.org/ns/ws-policy> >
(02)   <wsp:ExactlyOne>
(03)     <wsp:All>
(04)       <sp:RequireDerivedKeys />
(05)       <sp:WssUsernameToken10 />
(06)     </wsp:All>
(07)     <wsp:All>
(08)       <sp:RequireDerivedKeys />
(09)       <sp:WssUsernameToken11 />
(10)     </wsp:All>
(11)   </wsp:ExactlyOne>
(12) </wsp:Policy>

Note that the first alternative listed in Lines (03-05) in the second listing is combined with the two alternatives listed in Lines (08-13) in the second listing to create two alternatives in the normalized policy, Lines (03-06) and (07-10).

Regards,

Asir S Vedamuthu
Microsoft Corporation


From: David Hull [mailto:dmh@tibco.com]
Sent: Wednesday, June 06, 2007 10:16 AM
To: Asir Vedamuthu
Cc: public-ws-policy@w3.org
Subject: Re: Questions on normal forms

Asir Vedamuthu wrote:
> All we have to go on is "All distributes over ExactlyOne"

If you like this sentence to be clarified, may I request to propose a concrete change?
Your request is already granted: http://lists.w3.org/Archives/Public/public-ws-policy/2007Jun/0015.html


Regards,

Asir S Vedamuthu
Microsoft Corporation


From: David Hull [mailto:dmh@tibco.com]
Sent: Wednesday, June 06, 2007 8:32 AM
To: Asir Vedamuthu
Cc: public-ws-policy@w3.org<mailto:public-ws-policy@w3.org>
Subject: Re: Questions on normal forms

Aha.  In other words, the distributive rule doesn't apply directly at all.  First you apply the optional=false rule, which performs the same role as the "promotion" rule I hypothesized.

On the other hand, given what's in the text, why not apply the distributive rule directly and get



<wsp:All>

 <wsp:ExactlyOne>

  <A/>

 </wsp:ExactlyOne>

 <B/>

</wsp:All>
=> (All distributes over ExactlyOne; it doesn't distribute over lone assertions)



<wsp:ExactlyOne>

 <wsp:All>

  <A/>

 </wsp:All>

 <B/>

</wsp:All>
and continue as you previously had to get



<wsp:ExactlyOne>

 <wsp:All><A/></wsp:All>

 <wsp:All><B/></wsp:All>

</wsp:ExactlyOne>


That seems equally valid.  All we have to go on is "All distributes over ExactlyOne" and a few suggestive examples.


Asir Vedamuthu wrote:

In any case, I don't see how the distributive rule

applies where you say it does.





Let's break down the last step into smaller or sub steps ...



<wsp:All>

 <wsp:ExactlyOne>

  <A/>

 </wsp:ExactlyOne>

 <B/>

</wsp:All>



a) Apply the wsp:Optional=false rule to <B/>



<wsp:All>

 <wsp:ExactlyOne>

  <A/>

 </wsp:ExactlyOne>

 <wsp:ExactlyOne>

  <wsp:All>

   <B/>

  </wsp:All>

 </wsp:ExactlyOne>

</wsp:All>



b) Applying the distributive rule



<wsp:ExactlyOne>

 <wsp:All>

  <A/>

  <wsp:All>

   <B/>

  </wsp:All>

 </wsp:All>

</wsp:ExactlyOne>



c) Applying the idempotent rule



<wsp:ExactlyOne>

 <wsp:All>

  <A/>

  <B/>

 </wsp:All>

</wsp:ExactlyOne>



We hope this helps.



Regards,



Asir S Vedamuthu

Microsoft Corporation















From: David Hull [mailto:dmh@tibco.com]

Sent: Tuesday, June 05, 2007 11:48 PM

To: Asir Vedamuthu

Cc: public-ws-policy@w3.org<mailto:public-ws-policy@w3.org>

Subject: Re: Questions on normal forms



First, note that the third form you give is identical to the initial form.  How do we know not to loop around again?



In any case, I don't see how the distributive rule applies where you say it does.  If it does apply, why is the result what you give? Why would it be that and not, say



<wsp:ExactlyOne><!-- Distribute All over ExactlyOne and leave the other child alone -->

  <wsp:All>

   <A/>

  <wsp:All>

  <B/>

</wsp:ExactlyOne>

This brings up broader concerns about the distributive rule, which I was going to mention separately since as far as I could tell that rule didn't apply here.  But that's the problem: how do you tell?



The section on the distributive rule makes two apparently normative statements, one very vague:

* wsp:All distributes over wsp:ExactlyOne

* Distributing wsp:All over an empty wsp:ExactlyOne is equivalent to no alternatives

There are also several examples.  In all examples the surrounding All element contains only ExactlyOne children, as one would expect from the first statement.  There is nothing to suggest that the rule would apply in the case of an All with (for example) one child an assertion and one ExactlyOne.



Examples are generally non-normative anyway.  It's hard to see how these particular ones could be normative.  Read literally they might say "All containing ExactlyOne containing two arbitrarily named alternatives is equivalent to ExactlyOne containing All containing the same two alternatives," and so forth, but this is clearly not what is meant.



Read more intuitively, they suggest a general Cartesian product rule, by which (informally speaking) the general form



<All>

  <ExactlyOne>expr-1-1 expr1-1-2 ... expr-1-n1</ExactlyOne> <!-- n1 >= 0 -->

  <ExactlyOne>expr-2-1 expr1-2-2 ... expr-1-n2</ExactlyOne> <!-- n2 >= 0 -->

  ...

  <ExactlyOne>expr-m-1 expr-m-2 ... expr-m-nm</ExactlyOne> <!-- m >= 1, nm >= 0 -->

</All>



is equivalent to



<ExactlyOne>

  <All>expr-1-1 expr2-1 ... expr-m-1</All>

  <All>expr-1-2 expr2-1 ... expr-m-1</All>

  ...

  <All>expr-1-n1 expr2-1 ... expr-m-1</All>

  ...

  <All>expr-1-1 expr2-2 ... expr-m-1</All>

  <All>expr-1-2 expr2-2 ... expr-m-1</All>

  ...

  <All>expr-1-n1 expr2-2 ... expr-m-1</All>

  ...

  <All>expr-1-1 expr2-1 ... expr-m-nm</All>

  <All>expr-1-2 expr2-1 ... expr-m-nm</All>

  ...

  <All>expr-1-n1 expr2-1 ... expr-m-nm</All>

</ExactlyOne>



(The text suggests that this is generally the result of "repeatedly distributing", but what are the intermediate forms and how would the rule produce them?)



This is a specification, and indeed one that takes the unusually formal approach of defining a set of axioms.  One should not have to infer rules from examples.  One should certainly not have to refer to existing implementations to clarify rules.  The whole point is to capture abstractly the behavior of existing or future implementations.



I would strongly suggest formalizing the examples given into a normative rule using the term "Cartesian product", limiting its applicability to cases matching the form given above (i.e, All containing only ExactlyOne children) and adding a "Promotion" rule (or whatever the WG wants to call it) for bringing loose assertions into the fold.



As I understand it, this would

* Be specific where the existing text is vague.

* Cover (in conjunction with the other rules) all combinations of All, ExactlyOne and loose assertions.  It would even be possible to prove this by the usual case analysis.

* Capture the de facto standard behavior.















Asir Vedamuthu wrote:

Let's look at your second example. The second example with the Policy wrapper is:



<wsp:Policy>

 <wsp:All>

  <wsp:ExactlyOne>

   <A/>

  </wsp:ExactlyOne>

  <B/>

 </wsp:All>

</wsp:Policy>



Policy is equivalent to All. That is,



<wsp:All>

 <wsp:All>

  <wsp:ExactlyOne>

   <A/>

  </wsp:ExactlyOne>

  <B/>

 </wsp:All>

</wsp:All>



Applying the idempotent rule,



<wsp:All>

 <wsp:ExactlyOne>

  <A/>

 </wsp:ExactlyOne>

 <B/>

</wsp:All>



Applying the distributive rule,



<wsp:ExactlyOne>

  <wsp:All>

   <A/>

   <B/>

  <wsp:All>

</wsp:ExactlyOne>



We checked with a few online policy tools and our command line tool. They all consistently produced the above result. We hope this helps.



Regards,



Asir S Vedamuthu

Microsoft Corporation









From: public-ws-policy-request@w3.org<mailto:public-ws-policy-request@w3.org> [mailto:public-ws-policy-request@w3.org] On Behalf Of David Hull

Sent: Tuesday, May 29, 2007 12:52 PM

To: public-ws-policy@w3.org<mailto:public-ws-policy@w3.org>

Subject: Questions on normal forms



As far as I can tell, the following are valid compact expressions.

1. What are their normal forms?

2. By what rules are those normal forms computed?

<wsp:ExactlyOne>

  <wsp:All><A/></wsp:All>

  <B/>

</wsp:ExactlyOne>



<wsp:All>

  <wsp:ExactlyOne><A/></wsp:ExactlyOne>

  <B/>

</wsp:All>

Received on Tuesday, 12 June 2007 01:21:01 UTC