Subject: [Simple] XCAP issue 7: uniqueness in intermediate hops

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 11 May 2004 13:29:28 -0400

Joel Halpern raised an excellent question during the tutorial in Seoul 
that requires some discussion.

The question was whether xcap requires that, at each step in the node 
selector (that is, each "path segment" between the "/") that a single 
node is selected, or just that the final expression selects a single 
node. A concrete example (courtesy of Joel):

<aTags>
    <aTag>
       <bTags>
          <bTag at1="1"> content </bTag>
          <bTag at1="2"> content </btag>
       </bTags>
       <othertags at2="x"> content </othertags>
    </aTag>
    <aTag>
        <bTags>
          <bTag at1="3"> content </bTag>
          <bTag at1="4"> content </btag>
       </bTags>
       <othertags at2="y"> content </othertags>
    </aTag>
</aTags>

is it legal to have an XCAP reference of the form
.../document/aTags/aTag/bTags/bTag[@at1="1"]

The above expression does indeed select a single bTag element, but you 
don't know that this element is the one in the top tree until you get to 
the last selector.

XPath allows this kind of thing. We have the option of disallowing it or 
allowing it.

It is my inclination to disallow it, entirely from a "keep it simple" 
perspective. I think that introducing this restriction (each step 
selects a single element) is likely to result in a much leaner 
implementation, as you can easily traverse the tree in a simple way, 
each step selecting a single next node. Without this, you need to 
maintain a set of "candidates", and evaluate each next step against the 
current candidate set.

 From a performance perspective, without this limitation, its possible 
that the operation of selecting the target node can be O(N) where N is 
the number of nodes in the tree, vs. O(log(N)) which, for a balanced 
tree, would be the case where a single element is selected at each step.

Do other agree that we should introduce the restriction that each step 
in the processing result in a unique node?

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: "Joel M. Halpern" <[email-masked]>
Date: Tue, 11 May 2004 14:10:06 -0400

I agree that based on operational complexity we should restrict the system 
to stepwise uniqueness.  It will mean that folks wanting to be able to use 
XCAP will need to make sure that intermediate elements have unique 
attribute values  (since this is one case where .= can not be used.)  That 
seems a reasonable price to pay for significant simplification of 
implementation.

Yours,
Joel M. Halpern

At 01:29 PM 5/11/2004 -0400, Jonathan Rosenberg wrote:
>selector (that is, each "path segment" between the "/") that a single node 
>is selected, or just that the final expression selects a single node.

...

>Do other agree that we should introduce the restriction that each step in 
>the processing result in a unique node?
>
>Thanks,
>Jonathan R.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 11 May 2004 14:10:06 -0400

Yours,
Joel M. Halpern

...

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 11 May 2004 23:59:08 -0400

Joel M. Halpern wrote:

> I agree that based on operational complexity we should restrict the 
> system to stepwise uniqueness.  It will mean that folks wanting to be 
> able to use XCAP will need to make sure that intermediate elements have 
> unique attribute values  (since this is one case where .= can not be 
> used.)  That seems a reasonable price to pay for significant 
> simplification of implementation.

Its also possible to use the positional selectors in this case too.

Thanks,
Jonathan R.

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 11 May 2004 23:59:08 -0400

Thanks,
Jonathan R.

---

From: Jari Urpalainen <[email-masked]>
Date: Wed, 12 May 2004 09:58:27 +0300

> in the processing result in a unique node?

In practice, this problem is only when new nodes are appended if we
forget performance issues you raised. However, you described in another
thread an implementation model for XPATH selections the model of which i
have also implemented, i.e. first a full search is being done, if
nothing is found look for the parent node and append or do an indexed
insert. If there are many parent siblings to which should we add ? It is
IMO fairly stupid if the client hasn't given an unique predicate but I
am still somewhat uncertain that we should introduce this restriction as
it might also imply that we have to check that indeed the query within
each step is unique. So I am inclined to support the case where clients
SHOULD give unique predicates in location steps (but I am not severely
against this restriction if it is introduced)

BR,
Jari

---

From: Jari Urpalainen <[email-masked]>
Date: Wed, 12 May 2004 09:58:27 +0300

BR,
Jari

---

From: Jonathan Rosenberg <[email-masked]>
Date: Mon, 17 May 2004 02:31:26 -0400

inline.

Jari Urpalainen wrote:

> forget performance issues you raised.

I dont think the performance issue is non-trivial...

> However, you described in another
> insert. If there are many parent siblings to which should we add ? 

We would have to specify where in order to make this deterministic. I 
think its easier just to avoid this case altogether.

It is
> each step is unique.

I think this raises a difference in implementation approaches. I believe 
the restriction makes things a lot easier if you are not using a full 
xpath implementation. If you are, then it introduces another step which 
you would need to do, since xpath wouldn't normally check this.

  So I am inclined to support the case where clients
> against this restriction if it is introduced)

SHOULD doesnt help too much here, since it doesnt eliminate the need on 
the server to implement this, or for us to specify a deterministic 
insertion point in such cases.

-Jonathan R.

---

From: Jonathan Rosenberg <[email-masked]>
Date: Mon, 17 May 2004 02:31:26 -0400

inline.

It is

-Jonathan R.