2

In a tree structure, is there a standard term (in software engineering industry practice, Computer Science or Mathematics), for the predicate f(x, y) defined in human language as "x is an ancestor of or identical to y"?

Example:

Given the tree:

    A
   / \
  B   E
 / \
C   D

Then f(x, C) is satisfied by x in {A, B, C} but not D or E.

The best term I can find is "ancestor or self", but I am doubtful that is a standard term because I can find so few references to it.

9
  • Thanks, that sounds perfect. Seeing good reference docs here and here.
    – Will
    Apr 2, 2020 at 16:15
  • 2
    This is actually true for most relations in mathematics and computer science, I think. The fundamental relation is always <=, and we derive all others from it (a == b is a <= b && b <= a, a < b is a <= b && !(a == b)), and so on, and when we want to refer to the strict relation specifically, we explicitly name it "proper" or "strict", e.g. "strictly less-than" or "proper subset". Apr 2, 2020 at 19:07
  • 1
    I would remark that "AncestorOrSelf" (or some other formulation) would be best in any software-related context, because although "ancestor" may have a defined meaning in a mathematical context, it's entirely (without any exception) contrary to the English meaning of the word and to any normal understanding of the genealogical metaphor.
    – Steve
    Apr 2, 2020 at 22:09
  • 1
    "Think convenience ... or maybe laziness." The term 'ancestor' applies perfectly well to every node other than A, which is the only exception. Thus we need not burden our coversation with this exactly-one "odd man out." It's implicitly understood ... and, irrelevant ... that A's "ancestor" is (as the case might be) either "itself" or NULL. Apr 3, 2020 at 1:18
  • 1
    AncestorOrSelf sounds good to me, especially if it is understandable within the domain you're working in. I.e., if people that will be using/reading your code (your target audience) is likely to understand what this means when they see it, then it's a good name. Apr 3, 2020 at 7:26

3 Answers 3

5

The usual mathematical diction is just to use "ancestor". If the nonequality condition is actually important, you can say "proper ancestor", but often it isn't.

1

It is difficult to give an answer that does not involve personal taste or personal experience. But we can resort to authorities:

In XPath, the language for navigating in XML document trees, the concept is named "ancestor-or-self". This indicates to me that no "better" name for the concept has been around (in the context of computing). After all, XPath was specified by the W3C consortium - which also set the standard for HTML, CSS and so on.

1

Be aware that in computer science the term ancestor is strongly associated with inheritance relationships in the context of object orientation. We do speak of inheritance trees but only in an OO-context.

For tree structures like folders with files in it or more abstract linked entities we speak of parents, childs and siblings.

The difference is that in the first case there is a clear passing on of traits where in the latter case it is just an indication of a path, of the way nodes are connected.

You may want to take into account the semantics of your model before you pick your nomenclature and talk to a software engineer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.