Subject: [Simple] XCAP Issue 5 Interim Summary: selecting multiple elements

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 10 Jun 2004 02:33:59 -0400

On the list, we had made some progress in coming up with an algorithm 
for executing the insertion request as a series of individual 
insertions. THe key trick was to make sure the entire operation was 
idempotent.

I did some further work during the interim, and found some additional 
problem cases in the algorithm, notably when you have a mix of ways of 
selecting an element. I presented this problem case. Lets say you start 
with this document:

<foo>
   <bar id=“1”/>
   <bar id=“2”/>
</foo>

and then you do this:

PUT http://server/xcap-root/auid/users/joe/foo/bar[@id=“1”]|foo/bar[3]

<bar id=“1”>test</bar>
<bar id=“1”>Uh oh</bar>

If you execute each of the two components in order, you get the 
following document:

<foo>
   <bar id=“1”>test</bar>
   <bar id=“2”/>
   <bar id=“1”>Uh oh</bar>
</foo>

If you then do the GET back to the same URI:

GET http://server/xcap-root/auid/users/joe/foo/bar[@id=“1”]|foo/bar[3]

It returns an error, since foo/bar[@id="1"] now selects multiple 
elements. Thus, its not idempotent.

As such, I proposed two algorithms for the server side algorithm:

(1) basically, the server needs to look at the request, and prove 
idempotency before executing. It will need to check for all of these 
conditions that could cause the request to not be idempotent.

(2) the server keeps a copy of the document before the operation. It 
then tries the PUT. Once done, it pretends that the client did a GET 
back to the same URI, and it sees what comes back. If its the same as 
was in the body of the PUT, the operation was idempotent, and the PUT is 
accepted. If not, the server goes back to the document before the 
operation was done, and rejects the PUT request. This can be summarized 
as "try it and see if it works".

Neither seemed particularly compelling, and there was a push from 
several participants, including myself, to just drop this functionality 
in this version of the spec. This ties back into the discussion around 
issue 2 on positional insertions.

We discussed the impact on application usages. Hisham identified a 
problem in CPCP, where you want to add a user to the ACL and PCL at the 
same time. It was suggested to make a schema change, so that the URI 
only appears once. The other idea was that, if you were concerned about 
the latency of doing multiple operations, you could instead pipeline the 
HTTP PUT operations. So long as you don't need the etag from the 
previous operation, this would work. Its bandwidth overhead is almost 
the same as multiple insertions that we've been proposing, and the 
latency is just about the same thing too.

I suggested that I could include some guidelines on schema design to 
avoid the need for mutliple insertions. There seemed to be support for 
this position. The guidelines I will include are basically this:

(1) if you think you need multiple insertions because you think a common 
operation will require making two separate changes to the document, try 
"inverting" the schema so that this doesnt happen. For example, if you have:

<A-list>
   <foo/>
   <bar/>
</A-list>
<B-list>
   <foo/>
   <bar/>
</B-list>

and adding <baz> requires it to go in <A-list> and <B-list>, try doing 
the schema like this:

<widgets>
   <foo>
     <On-A-list/>
     <On-B-list/>
   </foo>
   <bar>
     <On-A-list/>
     <On-B-list/>
   </bar>
</widgets>

(2) if you think you need multiple inserts because you want to add 
multiple entries to a list in one operation, then design the schema to 
facilitate pipelined PUT. Specifically, make sure that each entry in the 
list has a unique ID as an attribute, such that no other client is going 
to choose the same id. Secondly, make sure your schema is such that the 
path from the document root to this list is "unique". That means that 
its not possible to change the document such that this path expression 
remains valid, but points to a different list. This is typically done by 
making each element in the path mandatory to appear in the document, or 
if its not mandatory, is identified by a unique attribute that would not 
be re-assigned.

Any objections?

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: Jari Urpalainen <[email-masked]>
Date: Thu, 10 Jun 2004 15:22:56 +0300

> as "try it and see if it works".

model (2) is almost what i have implemented for the following reason:

first you have a document like
<foo>
   <bar id="1"/>
</foo>

and then a client might try to e.g. add foo/bar[@id="5"] with content
<bar id="3">. First, as we don't find any node with the request, it is
an appending request and without any error-checking you may end up with
an end document like

<foo>
   <bar id="1"/>
   <bar id="3"/>
</foo>

Clearly this is an error in the client and IMO the server has to detect
this. The easy way that I chose to check this error-condition is that I
check that the last XPATH location step will return the correct node. So
my point is that not only the multi-inserts need this checking. 

Jonathan, I have still this question in another thread, where
idempotency is easily broken during replace (or modify) with single
nodes too. Btw. could someone explain how DELETE can be idempotent
(rfc2616) ?

> latency is just about the same thing too.

I'd rather say that pipelining could work in some cases, but it is NOT a
solution for doing atomic conditional multi-insertions/deletions which I
still would like to see in XCAP. 

> if its not mandatory, is identified by a unique attribute that would not 

When I implemented XCAP resource-lists, I have used entry-nodes to
represent other users with some additional information and then I have
added corresponding entry-ref's to subcribeable lists e.g. "friends",
"home", etc... So, it happens easily that if you e.g. remove a user you
have to do multiple deletes or if you change user-names (which I used to
use as keys) you have to change several entry-ref's. From the clients
perspective, it is far easier (and cleaner) if I can do these changes
with atomic conditional requests rather than doing either safe multiple
single requests in sequence or IMO ugly blind pipelined requests.

BR,
Jari

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 10 Jun 2004 14:10:45 -0400

I think leaving out multiple inserts, and telling people how to cope with 
the absence is MUCH better than the complications we are going to get by 
trying to include multiple inserts.

Thank you,
Joel

At 02:33 AM 6/10/2004 -0400, Jonathan Rosenberg wrote:
>[problem statement with non idempotent multiple insert]
>
>[Proposals for enforcing idempotentence]
>....
>[Suggestion that we leave out multiple inserts.]
>I suggested that I could include some guidelines on schema design to avoid 
>the need for mutliple insertions. There seemed to be support for this 
>position. The guidelines I will include are basically this:
>
>[Guidelines for avoiding the need for multiple inserts.]
>
>Any objections?
>
>Thanks,
>Jonathan R.
>

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 29 Jun 2004 16:59:29 -0400

responses inline. But first, I will say that there was really strong 
consensus during the interim to omit this feature in the first version 
of the specification. As such, unless others speak out in favor of 
adding it, I think that we can declare that the consensus in the interim

Jari Urpalainen wrote:

>>(2) the server keeps a copy of the document before the operation. It=20
>>then tries the PUT. Once done, it pretends that the client did a GET=20
>>back to the same URI, and it sees what comes back. If its the same as=20
>>was in the body of the PUT, the operation was idempotent, and the PUT i= 
>>accepted. If not, the server goes back to the document before the=20
>>operation was done, and rejects the PUT request. This can be summarized=
>>=20
>    <bar id=3D"1"/>
> and then a client might try to e.g. add foo/bar[@id=3D"5"] with content
> <bar id=3D"3">. First, as we don't find any node with the request, it is
>    <bar id=3D"1"/>
>    <bar id=3D"3"/>
> my point is that not only the multi-inserts need this checking.=20

You are right that this problem can happen even in the single-insert 
cast. However, there, its much, much easier to check. You merely need to 
make sure that the attribute predicate in the r-uri applies to the 
element in the body of the request. That can be done before the 
insertion operation even takes place, thus avoiding the need for any 
kind of roll-back.

> nodes too. 

Different from the above issue? Can you please restate it?

> Btw. could someone explain how DELETE can be idempotent
> (rfc2616) ?

Its a mystery to me. The second DELETE will generate a 404, since the 
previous one did a good job of deleting the resource.

>>HTTP PUT operations. So long as you don't need the etag from the=20
>>previous operation, this would work. Its bandwidth overhead is almost=20
>>the same as multiple insertions that we've been proposing, and the=20
>>=20
> still would like to see in XCAP.=20

Well, again it comes back to what xcap is trying to do. It is not meant 
to be a general XML database protocol. I think its a feature of the 
design that it can be pushed towards that by adding features like 
multiple-inserts, but really its not our goal.

Also, I'll note that if you want a sequence of insertions AND deletions 
to be done atomically, you can't do that with the multiple-inserts 
appraoch, since that only works with a single PUT (no DELETE). Thus, you 
would need proper transaction semantics that allow you to lock the 
document, make a bunch of changes, and cancel/rollback or commit when 
done, and that is, I think, well beyond what we want here.

> 
> 
>>I suggested that I could include some guidelines on schema design to=20
>>avoid the need for mutliple insertions. There seemed to be support for=20
>>=20
>>(1) if you think you need multiple insertions because you think a commo=
> 
> n=20
> 
>>operation will require making two separate changes to the document, try=
> 
> =20
> 
>>"inverting" the schema so that this doesnt happen. For example, if you =
> 
> have:
> 
>>=20
>><A-list>
>>   <foo/>
>>   <bar/>
>></A-list>
>><B-list>
>>   <foo/>
>>   <bar/>
>></B-list>
>>=20
>>and adding <baz> requires it to go in <A-list> and <B-list>, try doing=20
>>the schema like this:
>>=20
>><widgets>
>>   <foo>
>>     <On-A-list/>
>>     <On-B-list/>
>>   </foo>
>>   <bar>
>>     <On-A-list/>
>>     <On-B-list/>
>>   </bar>
>></widgets>
>>=20
>>(2) if you think you need multiple inserts because you want to add=20
>>multiple entries to a list in one operation, then design the schema to=20
>>facilitate pipelined PUT. Specifically, make sure that each entry in th=
> 
> e=20
> 
>>list has a unique ID as an attribute, such that no other client is goin=
> 
> g=20
> 
>>to choose the same id. Secondly, make sure your schema is such that the=
> 
> =20
> 
>>path from the document root to this list is "unique". That means that=20
>>its not possible to change the document such that this path expression=20
>>remains valid, but points to a different list. This is typically done b=
> 
> y=20
> 
>>making each element in the path mandatory to appear in the document, or=
> 
> =20
> 
>>if its not mandatory, is identified by a unique attribute that would no=
> 
> t=20
> 
>>be re-assigned.
>>=20
>>Any objections?
>>=20
>>Thanks,
>>Jonathan R.
>>=20
> 
> 

In this specific case, though, the entry-ref might point to an entry in 
a different document altogether. Multiple-inserts can only take place 
within the same document, so a client probably needs to do this as 
multiple operations anyway.

-Jonathan R.

---

From: Jari Urpalainen <[email-masked]>
Date: Wed, 30 Jun 2004 21:44:23 +0300

ext Jonathan Rosenberg wrote:

>>> was in the body of the PUT, the operation was idempotent, and the 
>>> PUT i= accepted. If not, the server goes back to the document before 
>>> the=20
> cast. However, there, its much, much easier to check. You merely need 
> to make sure that the attribute predicate in the r-uri applies to the 

well, IMO my approach is easier it you consider also the following 
examples. Also when doing schema checking I'll also need some temporary 
storage of the resource.

> Different from the above issue? Can you please restate it?
first you'll have
<foo a="bar">
then you want to modify this foo-node with a r-uri
.../foo[@a="bar"]  and with new content <foo a="foobar">. So we would 
find a single node and would replace the foo-node with new content and 
therefore you can't get this new content with the same r-uri anymore. Of 
course this can be avoided with a request like .../foo[1]. The bad thing 
here is that the request looks ok (unambiguous) but it is not idempotent 
and you really need error-checking in the server.

This will happen also with attribute updates like
put .../foo[@a="bar"]/@a with content "foobar"

>> Btw. could someonce explain how DELETE can be idempotent
>> (rfc2616) ?
>
>
> Well, again it comes back to what xcap is trying to do. It is not 
> meant to be a general XML database protocol. I think its a feature of 
> the design that it can be pushed towards that by adding features like 
> Also, I'll note that if you want a sequence of insertions AND 
> deletions to be done atomically, you can't do that with the 
> multiple-inserts appraoch, since that only works with a single PUT (no 
> DELETE). Thus, you would need proper transaction semantics that allow 
> you to lock the document, make a bunch of changes, and cancel/rollback 
> or commit when done, and that is, I think, well beyond what we want here.
>
I am not fully following here. In my implementation I will effectively 
do a locking for the resource before doing any xml-operations, because 
simultaneous requests (multithreaded implementation) would crash the 
whole system. So with multi-inserts also the lock is held between all 
the requests, which will be applied sequentially one by one. After this 
adding some additional checking is needed to fulfil an unambiguos 
request, first I'll check that I will still find the same nodes that I 
inserted and  if that is satisfied I'll check that nodes are not 
related. To me this looks still very simple and is also trivial to 
implement.

br,
Jari