Subject: RE: [Simple] XCAP Issue 2 Interim Summary: Positional Insertions

From: [email-masked]
Date: Thu, 10 Jun 2004 11:43:15 +0300

Jonathan,

Thanks for the analysis.

Reading your analysis actually brings me to the opposite conclusion to the one you made. That is, we need positional insertions.  There are so many rules, restriction, and guide lines that need to be educated to current and future designers of XCAP friendly schemas. Wouldn't it be a much better investment if we allow positional insertions now and avoid schema misdesign?

You haven't explicitly listed the issues with positional insertions, but instead you listed the problems that it solves. Can you please educate the rest of us what the real problems are with positional insertions?

Thanks,
Hisham

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]]On Behalf
> Of ext Jonathan Rosenberg
> Sent: 10.June.2004 08:54
> To: Simple WG
> Subject: [Simple] XCAP Issue 2 Interim Summary: Positional Insertions
> 
> 
> The issue of positional insertions was discussed during the interim.
> There was a lot of disagreement on it. There were concerns that it
> raised the bar too high for implementation complexity. This was tied
> back into a more general question about our goal here. Is our goal to
> (1) create a general purpose XML database management 
> protocol, or (2) to
> create a simple tool for managing the set of documents 
> important to the
> SIMPLE group. If its (1), then positional insertions make sense, but
> this is going to be a much larger problem and work item than SIMPLE
> can/should tackle. There is a lot of work already on XML database
> protocols that we will have to look at.
> 
> We discussed the fact that many of the problems that would seem to
> necessitate positional insertions can be solved with proper
> schema design. It was also noted that even if
> you don't design your schema with xcap in mind, xcap will always work,
> it just may not be as efficient as you might like.
> 
> There was no consensus on it, but I took an action item to 
> describe the
> general cases that would appear to motivate the need for positional
> insertions, and suggest how it can be avoided with other approaches.
> Furthermore, I took an action to take a look at the current usages
> (authorization, list management, pidf-manipulation and cpcp) in that
> context.
> 
> What follows is a long-ish analysis. If you're not into it, 
> please skip 
> to the conclusions and recommendation at the end, which is to drop 
> positional insertions.
> 
> 
> 
> So, here were the problem cases I could come up with. There 
> are three of 
> them, problems 1, 2 and 3. In all cases, the problem is the 
> presence of 
> the <sequence> model in the schema:
> 
> (Problem 1) The schema includes a sequence of elements, and 
> position of 
> those
> elements within the parent has semantic significance, for 
> example, some
> kind of prioritization. Here, if you want to update the 
> document with a
> new element that has a specific priority, you'd need to put 
> it into the
> right place.
> 
> If we don't have positional insertions, you could replace the entire
> list with each operation. Or, you could design the schema so that it
> didnt use order as a semantically significant concept. Instead,
> introduce an attribute that contains the priority. Designing 
> the schema
> this way has other benefits. It would allow users to insert 
> new elements
> with a specific priority without having the list in memory.
> 
> (Problem 2) The schema defines an element A as a sequence of 
> elements X, 
> Y and
> Z, and the number of each such elements is unbounded. 
> Ordering of each of
> the elements of the same name is irrelevant, but schema validation
> requires that all X's come before all Y's which come before 
> all Z's. For
> example:
> 
> <A>
>   <X id="1"/>
>   <X id="2"/>
>   <Y/>
>   <Z/>
> </A>
> 
> 
> If there are no positional insertions, there are three solutions.
> 
> (a) The first is to replace all of A when you want to add a 
> new X, Y or Z.
> 
> (b) The other is to define the schema so that A is defined as 
> a sequence
> of X-list, Y-list and Z-list, where there is exactly one of each of
> these. Within X-list are a sequence of X. Within Y-list are a sqeuence
> of Y, and within Z-list is a sequence of Z. For example, you would
> instead do it like this:
> 
> <A>
>    <X-list>
>      <X id="1"/>
>      <X id="2"/>
>    </X-list>
>    <Y-list>
>      <Y/>
>    </Y-list>
>    <Z-list>
>      <Z/>
>    </Z-list>
> </A>
> 
> The reason this works is that the schema mandates that there 
> be exactly
> one of X-list, Y-list and Z-list. Thus, I never need to *insert* a new
> X-list, Y-list or Z-list, since they need to appear in the initial
> document in the first place. So, when I insert a new X with id=3, the
> URI would be A/X-list/X[@id="3"]. This approach has a side 
> effect, which
> is an easy way to change all of the X's without requiring the multiple
> insertions feature.
> 
> (c) change the schema so that it allows the X, Y and Z in any 
> order. As
> such, the schema would change from a sequence of X, Y and Z, to a
> sequence of a choice of X,Y, Z. This is the best solution.
> 
> 
> (Problem 3) The schema defines A as a sequence of X, Y, and 
> Z, but there 
> are constraints on the number of X, Y and Z. The ordering of the 
> elements has no semantic significance. This case normally 
> arises when X, 
> Y and Z can occur 0 or 1 times, i.e., the represent optional elements.
> 
> 
> This is the most problematic case. There are several solutions:
> 
> (a) As in problem 2, solution (a), replace the whole thing
> 
> (b) As in problem 2, solution (b), define another level in the 
> hierarchy. For the case where the X, Y and Z appear 0 or 1 
> times, this 
> is pretty inefficient.
> 
> (c) For elements that can occur 0 or 1 times, redefine the element so 
> that it must always appear, but define a value for it, or an 
> attribute, 
> which effectively indicates its absence. For example, if you want to 
> indicate, in the schema, whether or not feature "foo" is 
> turned on, one 
> could define the element <foo> as an empty element, which is present 
> when the feature is on, absent when off. An alternative design that 
> works better with xcap, is to define <foo> as always being 
> present, with 
> a value of true or false.
> 
> 
> 
> To summarize, the schema is problematic when it has 
> <sequence> element,
> and that sequence consists of multiple elements of different 
> names which
> can appear an unbounded number of times, or the sequence has multiple
> elements of the same name, and the application associates 
> meaning to the
> order, or the elements in the sequence can appear a variable 
> of times, 
> but bounded in size (ususally 0 or 1 is the most common case of this).
> 
> These were the only three problematic cases I could identify that
> motivated the positional insertions.
> 
> I have done an analysis of the current usages, and here is 
> what I found:
> 
> resource-list
> -------------
> 
> * Currently, the <resource-lists> element is a sequence that 
> starts with
> <mandatory-ns> and then has a sequence of list. This is problem 2. 
> However, we agreed to remove <mandatory-ns>, and so this 
> won't be an issue.
> 
> * The entry element is display-name followed by a sequence of elements
> from other namespaces. This is problem 3. This might be a problem 
> depending on those
> extensions. If they don't follow the guideliens I describe above, it
> might require a user to change the entire entry at once. I don't think
> there is actually anything we can do about it in the schema design; it
> needs to be described in text as a constraint in extensions.
> 
> common-policy
> -------------
> 
> * Currently, each <rule> is a sequence of 0 or 1 <conditions>, 0 or 1
> <actions>, and 0 or 1 <transformations>. This is problem 3. 
> fix This is 
> problematic if you
> start with a document that has conditions and actions, and you want to
> add transformations. The best fix is (a), to require exactly one of 
> these (in
> fact, I was surprised it didnt work this way).
> 
> presence-auth
> -------------
> 
> * The <tuples-whose> element in the inclusion set type is a 
> sequence of 
> rpid elements, each of which can appear an unlimited number of times. 
> Thus, this is problem 2. However, since the ordering is 
> irrelevant, this 
> could be changed to a sequence of choice with no negative 
> consequences. 
> That is, solution c.
> 
> * The inclusion-set type allows for either a value of 
> <all-tuples>, or a 
> sequence of <tuples-whose> followed by <any ##other>. 
> Currently, there 
> can only be one <tuples-whose>. Thus, changing this to a sequence of 
> choice would not allow enforcement of this maxOcc 
> restriction. There is, 
> however, no particular reason why there can be only one. If there is 
> more than one, they could just be unioned together. [[In any 
> case I hope 
> we can get rid of inclusion-set for the first pass at the 
> auth policies]]
> 
> CPCP
> ----
> 
> * The root element, <Conference>, is a sequence of things 
> (<Conference-Settings>, <Conference-Info>, etc.). 
> Fortunately, each of 
> these has to appear exactly once. So, they are always in the doc, and 
> there is no need to insert. No problem here.
> 
> * <Conference-Settings> is a sequence of <Conference-uri> and then 
> <Max-participant-count>. This is problem 3. If we want to 
> enforce the 0 
> or 1 constraint on <Max-participant-count>, and we want to 
> allow adding 
> of URI to the <Conference-uri> list, we have a problem 
> (problem 3). The 
> right fix seems solution (c). Make <Max-participant-count> to occur 
> exactly once, and define a large value as being "unbounded". Then, 
> replace <Conference-uri> with <Conference-uris>, which occurs 
> once, and 
> contains a sequence from 0 to unbounded of <Conference-uri>.
> 
> * <Conference-Info> is a sequence of elements, each of which 
> describes 
> some property of the conference. Each can appear 0 or 1 time. This is 
> problem 3. I'm inclined to go for solution A, which is, if 
> you want to 
> change one of these, you need to replace the whole Conference-Info. I 
> dont see them changing much, so it doesnt seem like a big deal.
> 
> * <Conference-occurrence> is a sequence of an optional <start-time> 
> followed by an optional <stop-time>. Thus, this is problem 3. I'd 
> suggest solution A, replace both if you want to change one of the 
> conference occurences.
> 
> * The ACL, PCL and DL all work well with xcap, being a sequence of 
> elements of the same name with an unbounded number of them, ordering 
> irrelevant. No problem here.
> 
> * The <SC> element has problem 2, because <SC-Target> can appear an 
> unbounded number of times. Recommended solution is solution 
> b, changing 
> <SC-Target> to <SC-Targets>, making that appear only once, 
> and defining 
> its children as a sequence of <SC-Target>
> 
> * Each <Floor> in <Conference-Floor-Policy> has problem 3, and 
> <Media-types> and <Algorithm> have problem 3. Since I don't 
> expect this 
> to change much, I suggest solving this with solution A; that is, you 
> update the information for the entire <Floor>.
> 
> * In <Media-Policy>, <Media-types> has problem 3, as in the 
> above case. 
> Here too, solution A seems best. Replace the whole thing.
> 
> 
> PIDF Manipulation
> -----------------
> 
> * The root <presence> element has problem 3. Since the schema 
> cannot be 
> changed, the only solution is solution A. That is, if you 
> want to insert 
> a new tuple or note, you will need to update the whole document.
> 
> * The <tuple> element has problem 3. Since the schema cannot 
> be changed, 
> the only solution is solution A. That is, if you want to insert a 
> contact, timestamp or note if there wasnt one before, or add 
> an optional 
> element, you need to replace the whole tuple.
> 
> * The <status> element has problem 3, but this will be a 
> problem mostly 
> depending on the extensions.
> 
> 
> 
> Conclusion
> -----------
> 
> The conclusion of my analysis is that:
> 
>    (1) it is possible to document a set of schema design 
> guidelines that 
> can make positional insertions not important for pretty much any 
> application usages, at the expense of (a) eliminating schema 
> validation 
> of the number of counts of an element, (b) increase in 
> document size, or 
> (c) increase in the number of cases in which the parent 
> element needs to 
> be replaced if a child needs to be inserted
> 
>    (2) for the currently defined application usages, the places where 
> insertion is MOST likely to occur commonly are places where there are 
> lists of things (buddy lists, PCLs in CPCP, etc.). Lack of a 
> positional 
> insertion is not a problem here. It is more problematic in 
> cases where 
> there are boolean elements that represent optional 
> information, mostly 
> in CPCP and PIDF. In those two cases, there are workarounds. 
> For CPCP, 
> none of the workarounds seemed bad. PIDF is the biggest problem since 
> the schema can't be changed. I expect that, in most cases, 
> the result is 
> that, if you want to add something (as opposed to changing 
> something), 
> you'll need to replace the parent, be it the whole document or the 
> tuple. However, I dont expect this to happen that often, and the cost 
> penality (more data sent over the network) is relatively 
> small because 
> pidf docs are small. The only real problem is if they should become 
> extremely large (ie., include images). Right now thats not the case.
> 
> 
> As such, my proposal is to drop positional insertions for this first 
> version, and include them in an extension to be developed downstream.
> 
> Thanks,
> Jonathan R.
> 
> -- 
> Jonathan D. Rosenberg, Ph.D.                600 Lanidex Plaza
> Chief Technology Officer                    Parsippany, NJ 07054-2711
> dynamicsoft
> [email-masked]                     FAX:   (973) 952-5050
> http://www.jdrosen.net                      PHONE: (973) 952-5000
> http://www.dynamicsoft.com
> 
> 
> 
> 
> _______________________________________________
> Simple mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/simple
> 

_______________________________________________
Simple mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/simple

---

From: Jari Urpalainen <[email-masked]>
Date: Thu, 10 Jun 2004 15:45:24 +0300

> You haven't explicitly listed the issues with positional insertions, but instead you listed the problems that it solves. Can you please educate the rest of us what the real problems are with positi…

I agree totally with Hisham here. Probably the only technical (?)
argument has been that XCAP is getting too complex. When I implemented
these positional inserts I did not find any peculiar difficulties in the
implementation. I find it really weird that xml Schemas has to be
defined so that XCAP has no difficulty when doing updates. I'll agree
that it's not bad if the situation is such, but I would not like to put
that as a requirement while we'll have a simple solution at hand, IMHO.

> > protocols that we will have to look at.

e.g. XUpdate will do these positional insertions but with different
semantics.

BR,
Jari

---

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 17 Jun 2004 08:07:08 -0400

[email-masked] wrote:

> Jonathan,
> 
> Thanks for the analysis.
> 
> Reading your analysis actually brings me to the opposite conclusion
> to the one you made. That is, we need positional insertions.  There
> are so many rules, restriction, and guide lines that need to be
> educated to current and future designers of XCAP friendly schemas.
> Wouldn't it be a much better investment if we allow positional
> insertions now and avoid schema misdesign?

I don't think any of the guidelines represent a schema mis-design.

> 
> You haven't explicitly listed the issues with positional insertions,
> but instead you listed the problems that it solves. Can you please
> educate the rest of us what the real problems are with positional
> insertions?

It was just complexity. Positional insertions would require us to 
support multiple predicates (i.e., more than one [] rule). We could 
restrict it to just two in our case, and indeed, restrict the first 
predicate to be a positional selector only. I think that might help the 
complexity a bit. However, there is definitely more logic and code 
required to support it than not. How much exactly? Depends on the 
implementation. I'll send a separate note in the next day or so with a 
pseudo-code view of what a minimal implementation would be, so folks can 
get a sense of it.

The meta-issue was that the whole idea with xcap is that what we are 
generally doing is reading and writing a document from a server (like a 
buddy list), but sometimes, you need to read or write a piece of it as 
an optimization, so we have the notion of sub-document addressing. When 
you view the design goal as reading and writing of entire documents with 
sub-document operations as a performance optimization, things like 
positional inserts teeter on the boundary between this view, and the 
view of xcap as an XML database protocol. I think that, if we are 
defining an XML database protocol, we would probably start from a 
different approach, along the lines of XUpdate.

I must say that, on the issue of positional inserts, I am on the fence. 
I do see the "keep it barebones simple" argument, especially as it 
relates to the view of xcap as an optimization around reading and 
writing of documents. On the other hand, from a code perspective, I 
don't think positional inserts is actually that complicated, and it 
does, as Hisham pointed out, remove a lot of "schema design guidelines" 
that I would otherwise need to introduce to deal with it.

Comments from others? Even a "do positional inserts" or "dont do it" 
response is helpful.

Thanks,
Jonathan R.

---

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 24 Jun 2004 06:22:59 -0400

I mentioned below that I would send some pseudocode that describes the 
scope of what you'd have to do to get positional inserts working. Here 
it is. Its really rough, but I think it captures the essence of it. As 
you can see, its not all that complicated.

Assume that the document is structed basically as a dom tree.

onGET() {

extract the node selector from the URI;
obtain the document defined by the document selector;

set the current context to the root of the document;
for each step in the node selector {
   create a linked list of the children of the current context
     whose name matches the one defined by the step;

   for each predicate in the step {
      if the predicate is a position {
         extract the nth element in the linked list, where
           n is the position;
      } else if the predicate is an attribute selector {
         for each element in the linked list {
            if the element has an attribute with the given name,
              extract it;
         }
      }

      if more than one element was extracted, its an error;
      if no element was selected, return 404;
      else set the current context to the extracted element;

    }

    return the extracted element;

}

doPUT {

   perform a doGET() on the URI;
   if the result is not 404 {
     // this is a modification
     replace the selected element with the body of the PUT;
     perform a doGET() on this modified document;
     if the result is the element we just inserted {
       return 200 OK;
     } else {
       return 409;
     }
   } else {
    // this is an insertion

    strip off the last step from the URI;
    perform doGET() on the result;
    if that result was a 404 {
      return 409;
    }
    get the children of the selected element as a linked list;
    set current element to the first child;
    set counter to 1;
    if first predicate is a positional one {
      do {
        if name of current element matches the step we extracted {

          if position equals counter {
            insert before current element;
            done;
          } else {
            increment counter;
          }

        }
     } else {
       insert as last element;
     }
     do a doGET() on the modified document;
     if the element that is returned doesnt match what we just inserted
       return 409;
     else
       return 200;
   }

}

-Jonathan R.

---

From: Avshalom Houri <[email-masked]>
Date: Thu, 24 Jun 2004 13:25:01 +0300

Prefer to keep a simple base of XCAP and do extensions later.

Avshalom

Jonathan Rosenberg <[email-masked]> 
Sent by: [email-masked]
17/06/2004 03:07 PM

To
[email-masked]
cc
[email-masked]
Subject
Re: [Simple] XCAP Issue 2 Interim Summary: Positional Insertions

Thanks,
Jonathan R.