Thread: [ltree] Should `SELECT LCA('1.2', '1.2.3');` return '1.2' instead of '1'?

Operating system: Ubuntu 17.04 PostgreSQL version: 9.6.6 At the moment, both SELECT LCA('1.2', '1.2'); and SELECT LCA('1.2', '1.2.3'); return ‘1’. According to the Wikipedia1 definition of LCA: “[…] the lowest common ancestor (LCA) of two nodes v and w […] is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).” So, in my understanding, both SELECT LCA('1.2', '1.2'); and SELECT LCA('1.2', '1.2.3'); should return ‘1.2’. What do you think about it? By the way, the ltree structure is really great, thank you! Julien Grillot

On Fri, Dec 1, 2017 at 8:32 AM, Julien Grillot wrote: > At the moment, both SELECT LCA('1.2', '1.2'); and SELECT LCA('1.2', > '1.2.3'); return ‘1’. > > According to the Wikipedia1 definition of LCA: > “[…] the lowest common ancestor (LCA) of two nodes v and w […] is the > lowest (i.e. deepest) node that has both v and w as descendants, where we > define each node to be a descendant of itself (so if v has a direct > connection from w, w is the lowest common ancestor).” > > So, in my understanding, both SELECT LCA('1.2', '1.2'); and SELECT > LCA('1.2', '1.2.3'); should return ‘1.2’. What do you think about it? > ​If indeed one defines "each node to be a descendant of itself" then you are correct. Unfortunately your example indicates that this implementation does not define ancestry that way. While you may not agree with the definition at this point changing the existing function's behavior in this manner seems highly undesirable - too much existing code would silently break. Adding a leading (due to varargs) boolean argument that specifies "end node is ancestor of itself" behavior might be a workable solution. Regardless, the docs should be clarified on this point, though, and maybe add a code comment somewhere. David J.

2017-12-01 17:17 GMT+01:00 David G. Johnston : > ​[…] Adding a leading (due to varargs) boolean argument that specifies > "end node is ancestor of itself" behavior might be a workable solution. > > Regardless, the docs should be clarified on this point, though, and maybe > add a code comment somewhere. > I understand the importance not to break existing usages. It would be perfect to have a boolean to specify that – and to clarify the docs, since the example given does not reveal this behavior https://www.postgresql.org/docs/9.1/static/ltree.html#LTREE-FUNC-TABLE I digged inside the source code and ended at `contrib/ltree/ltree_op.c:406` but I don't feel able to do the patch.

"David G. Johnston" <david.g.johnston@gmail.com> writes:
> On Fri, Dec 1, 2017 at 8:32 AM, Julien Grillot <julien.grillot@gmail.com>
> wrote:
>> So, in my understanding, both SELECT LCA('1.2', '1.2'); and SELECT
>> LCA('1.2', '1.2.3'); should return ‘1.2’. What do you think about it?

> If indeed one defines "each node to be a descendant of itself" then you
> are correct.  Unfortunately your example indicates that this implementation
> does not define ancestry that way.  While you may not agree with the
> definition at this point changing the existing function's behavior in this
> manner seems highly undesirable - too much existing code would silently
> break.  Adding a leading (due to varargs) boolean argument that specifies
> "end node is ancestor of itself" behavior might be a workable solution.

> Regardless, the docs should be clarified on this point, though, and maybe
> add a code comment somewhere.

This came up again today; I've now adjusted the docs to reflect reality.

If we were to do something about the lack of a function that behaves
the other way, I'd suggest calling it lcp() for "longest common prefix".
Trying to deal with it with an optional argument is going to create
overloading problems.

            regards, tom lane