Subject: RE: BIND vs. non-movable resources in RFC3253

From: "Clemm, Geoff" <[email-masked]>
Date: Mon, 28 Oct 2002 13:09:24 -0500

Yes, if the "modeling" argument didn't carry the day,
I was planning on falling back on the "too expensive"
argument (:-).

But how does requiring that cyclic relationships be modeled
by properties instead of collection membership solve
anything, other than pushing the burden of cycle detection
onto the client instead of the server?

The problem introduced by cyclic bindings was that
PROPFIND needs to maintain a "visited resource" list,
in order to detect cycles.  For a server that supports 
bindings, maintaining such a list is straightforward
(since the DAV:resourceid property is required).

And even if one believes that modeling cyclic relationships
should be done with properties, in a versioned collection
context, there is no way to
avoid the cyclic binding problem.  A client could
create a collection A, add a collection B to A, add a
collection C to B, move C to be a member of A, and then
move B to be a member of C.  None of the states have
multiple bindings to a resource, much less a cycle binding.
But if a user selects the version of B that contains C,
and the version of C that contains B, they have created
a configuration with a cyclic binding.

Cheers,
Geoff

-----Original Message-----
From: Elias [mailto:[email-masked]]
Sent: Monday, October 28, 2002 11:54 AM
To: [email-masked]
Subject: Re: BIND vs. non-movable resources in RFC3253

Good morning all,

Perhaps you're already aware of this, but... The detection of cyclic 
bindings is reducable to the problem of finding a Hamiltonian Path in a 
graph, which is NP-Complete. I strongly object to placing any 
requirements upon a server which are NP-Complete problems.

Since detection of cycles is NP-Complete, it shouldn't be a MUST level 
requirement that servers detect them. Perhaps they SHOULD detect them, 
but even that seems too strong for my tastes... It's clear that cycles 
may be caused inadvertently by other namespace operations such as MOVE, 
so disallowing them also has the effect of making a server detect them.

The problem is analogous to that of having cyclic links in the *nix 
filesystem, is it not? Is there any reason we cannot follow the same 
approach taken there? The simplest way to avoid the whole mess is to 
specify that namespace operations do not follow BINDed (bound?) 
resources since they could end up in a cycle...

I'd be interested in seeing a use case for cyclic BINDings that cannot 
be satisfied with the judicious use of properties...

Elias

Julian Reschke wrote:

> [...] I see why a server that *does*
> support cyclic bindings need to signal them upon depth infinity operations
> (-> 506), but why would you want to require support for their creation?
> 
> Actually, I'm tempted to require servers to detect cyclic bindings upon
> creation and to reject those requests. What's the use case for cyclic
> bindings?

---

From: Elias Sinderson <[email-masked]>
Date: Wed, 30 Oct 2002 14:49:26 -0800

Clemm, Geoff wrote:

> [...] how does requiring that cyclic relationships be modeled
Recursive operations such as a depth infinity MOVE/COPY/PROPFIND will 
have problems if there is a cycle. I see two possible alternatives to 
address this problem:
a) model cyclic relationships as properties or
b) disallow following links during recursive operations in the same way 
that a filesystem does.

> [...] And even if one believes that modeling cyclic relationships
> context, there is no way to avoid the cyclic binding problem.  [...]
>
I have no problem with the creation of cyclic bindings. My primary 
concern is that the server should not be required to detect the 
existence of a cycle. Since there is no way to avoid the creation of 
cyclic bindings in a versioned collection context, option (a) won't buy 
us anything, so option (b) seems to be the only alternative. Is it 
reasonable to specify that recursive operations treat bindings 
differently than other resources?

Elias

---

From: "Julian Reschke" <[email-masked]>
Date: Thu, 31 Oct 2002 09:46:00 +0100

> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of Elias Sinderson
> Sent: Wednesday, October 30, 2002 11:49 PM
> To: Clemm, Geoff
> Cc: [email-masked]'
> ...
> Recursive operations such as a depth infinity MOVE/COPY/PROPFIND will have
> problems if there is a cycle. I see two possible alternatives to address
> this problem:
that
> a filesystem does.

A binding isn't a link. Filesystems that support the equivalent of bindings
(hard links) have the same problem. Programs that do recursive operations
need special treatment, that is:

- avoid getting into loops when there are multiple bindings to a collection
(the solution being to keep track of inode numbers that were visited) (*)
- optionally special-case multiple bindings to the same resource (I think
"cpio" can do that, but "tar" doesn't)

(*) In a Unix filesystem,  "." is a binding to the current directory, and
".." is a binding to the parent directory. If you do a "ls -l", you'll the
number of hard links to a file/folder, and the number of hard links for a
folder always always is something like 2 + the number of direct child
collections.

> I have no problem with the creation of cyclic bindings. My primary concern
> is that the server should not be required to detect the existence of a
> cycle. Since there is no way to avoid the creation of cyclic bindings in a
> versioned collection context, option (a) won't buy us anything, so option
> (b) seems to be the only alternative. Is it reasonable to specify that
> recursive operations treat bindings differently than other resources?

No. There is no difference (at least not in the general case, your
implementation may vary :-).

--
<green/>bytes GmbH -- http://www.greenbytes.de -- tel:+492512807760