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

RE: Questions on normal forms

From: Asir Vedamuthu <asirveda@microsoft.com>
Date: Wed, 6 Jun 2007 10:11:41 -0700
To: David Hull <dmh@tibco.com>
CC: "public-ws-policy@w3.org" <public-ws-policy@w3.org>
Message-ID: <C9BF0238EED3634BA1866AEF14C7A9E543155014A0@NA-EXMSG-C116.redmond.corp.microsoft.com>
> 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?

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
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 Wednesday, 6 June 2007 17:12:04 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:20:52 GMT