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

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 10 Jun 2004 01:53:37 -0400

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

---

From: "Drage, Keith (Keith)" <[email-masked]>
Date: Fri, 11 Jun 2004 01:02:54 +0100

I concur with the conclusion.

However, we should also leave the issue of future extensions on the table until we get to that point. At that point we may still decide it is a level of complexity where we do not want XCAP to go (for the reason that there are other valid XML database alternatives for people that need this complexity).

regards

Keith

> -----Original Message-----
> From: Jonathan Rosenberg [mailto:[email-masked]]
> Sent: 10 June 2004 06:54
> To: Simple WG
> Subject: [Simple] XCAP Issue 2 Interim Summary: Positional Insertions
> 
> 
>

---

From: [email-masked]
Date: Mon, 21 Jun 2004 09:37:38 +0300

Hi,

I would prefer including positional inserts in XCAP. 

As far as I have understood, the additional implementation complexity is quite small, and they provide some efficiency benefit in certain situations. I don't think this is an issue for initial usages of XCAP, but once XCAP has been implemented e.g. for cellular devices, people may want to use it for other purposes too. I don't think it is realistic to assume something like XUpdate being available in this way. 

Markus 

> From: [email-masked] 
> [mailto:[email-masked]]On Behalf
> Of ext Jonathan Rosenberg
> Sent: 17 June, 2004 15:07
> To: Khartabil Hisham (Nokia-TP-MSW/Helsinki)
> Cc: [email-masked]
> Subject: Re: [Simple] XCAP Issue 2 Interim Summary: Positional
> Insertions
> 
> 
> 
> 
> [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.
> 
> --