[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: aliased bases

Robert Streich wrote:

> > I think the parts we have done are complementary though.  What you describe seems to be
> > the part that dereferences information from the base when the base fails, the part
> > I have done dereferences when the alias is a candidate.
> The problem here is that unless you add another search filter, the alias entries
> will most likely not be among the candidates.

I am not sure how this applies to search filters.  If the base is aliased then the search
would fail, but that is a distinct part of the deref process.  You will need both deref types
to deal with the different deref options.  There needs to be a base deref and an object deref,
that is why I think the two parts were complementary.

> We only have this issue in one-level and subtree searches. I wrote the algorithms
> below that should work.

I think that in the case where the base is itself the alias you will need to deref in the base

> One-level algorithm--here all we are concerned about are aliases that are children
> of base:
>     alias_list = fetch_aliases() /* Get all alias entries from the db */
>     /* Collect all aliases that are children of base */
>     foreach i in alias_list
>         if dn_parent(alias_list[i]) == base
>             if alias_list[i].aliasedObjectName notin child_list
>                 insert(child_list, alias_list[i].aliasedObjectName)
>             fi
>             delete alias_list[i]
>         fi
>     done
>     /* Then resolve any alias chains */
>     do
>         found = false
>         foreach i in alias_list
>             foreach j in child_list
>                 if alias_list[i] == child_list[j]
>                     if alias_list[i].aliasedObjectName notin child_list
>                         insert(child_list, alias_list[i].aliasedObjectName)
>                     fi
>                     delete child_list[j]
>                     delete alias_list[i]
>                     found = true
>                 fi
>             done
>         done
>     while found = true
> I'd leave all the existing code in place and just fetch any entries in child_list,
> test them against the filter, and either add them to the results or discard them.
> Subtree algorithm ("vertex_list" is the list of all of the scoping vertices in the
> tree that is initialized with the search "base")--here we have to convert the single
> vertex base into a list of vertices:
>     alias_list = fetch_aliases() /* Get all alias entries from the db */
>     insert(vertex_list, base);
>     do
>         found = false;
>         foreach i in alias_list
>             foreach j in vertex_list
>                 if dn_issuffix(alias_list[i], vertex_list[j])
>                     foreach k in vertex_list
>                         /* dn_issuffix() returns true if the two are equal also. */
>                         if not dn_issuffix(alias_list[i].aliasedObjectName, vertex_list[j])
>                             insert(vertex_list, alias_list[i].aliasedObjectName)
>                         fi
>                     done
>                     found = true;
>                     remove element i from alias_list
>                 fi
>             done
>         done
>     while found = true
> Then you have to test each candidate to see if it has a parent in the vertex_list.
> The rest of the code is intact.
> I can't use an array for the vertex_list as the algorithms imply. That would make
> the time complexity exponential. I'll have to add the code for a more optimal
> data structure.
> I think these are right. If anyone sees any errors, please let me know. I didn't
> spend all that much time on them for the first pass.

I don't quite understand all of the terms used in the algorithm.  By fetch_aliases do you mean
fetch all possible aliases for the given base or all aliases period? That could be quite a big

There are a couple of other problems I think, one is that it makes no allowance for the
different deref options.  For example, derefFinding and derefSearching require different deref
behaviour, one impacts the base and the other the subordinates.

If you have some code I would like to see it as I may be missing something in my reading of
the algorithm.   I've fleshed out my alias code and it works by using two functions:
derefAlias and derefDN. The derefAlias fully dereferences a given alias object.  The derefDN
determines the real DN given a possibly aliased DN.

The search code then applies the derefDN if one of the two relevant options (derefAlways or
derefFinding) applies.  The base is then a "real" base and the candidates can be found.  The
candidates are then derefed if either derefAlways or derefSearching applies and they are alias

I will clean up the code as time permits and post it.

> I know, but I think this is wrong. I've been going through X.511 and X.518
> this morning and I can't find any prohibition against cycles. Given that
> and Mark Wahl's response to the simple case of an alias that points to
> itself, I don't believe that it is an error to have a cycle in your
> DIT (DIG?). It becomes the responsibility of the search mechanism to remove
> the cycles.

Yes, there is no problem in creating them.  However, there is a problem in searching.  The
deref has to be able to report the problem.  I see this a little like the symbolic links in
UNIX.  You can create links that result in loops, but accessing one should return an error.  I
don't think the loops should be "removed".

> My interpretation is that you dereference it and then return the alias itself
> (if it matches the search criteria that is).

Well, I don't see how you can do that for full deref.  On full deref you should not return an
alias object since all aliases have to be dereferenced.   The draft indicates that derefs
should be full derefs

             If multiple aliases are chained, the alias for the first
             object MUST resolve to the last entry in the chain. For
             example, A, B, and C are alias objects. If A points to B which
             points to C which points to D, A resolves to D when
             dereferencing the alias.

> Interestingly enough, X.501 (93 anyway) specifically allows dangling aliases:
>   9.5 ...Note--The name within the aliasedEntryName is said to be pointed
>       to by the alias. It does not have to be the distinguished name of
>       any entry.

Yes, as Harald pointed out there would be serious permission problems in trying to keep
danglers out.

Will Ballantyne     GEMS Technical Architect