[Bug 12534] [DM] Definition of 'tree' missing and apparently non-standard

https://www.w3.org/Bugs/Public/show_bug.cgi?id=12534

--- Comment #5 from C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com> ---
Michael Kay is right, I think, to suggest that it is not uncommon for the term
"tree" to be used to refer to trees that are not parts of other trees; he is
wrong, I think, to suggest that that is "the usual usage".  (For one thing, if
the usual usage of the term "tree" entails maximality, what on earth can a
phrase like "a tree that is not part of a larger tree" possibly mean?  And how
is it possible for MK to use such a phrase with such confidence that any
competent technical reader will understand what he's saying?)

When we maintain a tree as a data structure for certain kinds of information,
it is not at all uncommon for what GF and MK call the maximal tree to be the
most common topic of interest.  A reference, in context, to that data structure
as "the tree" does not in any way entail the proposition that trees are not
recursive, or that no node in that tree is a node in any other tree.  All that
a reference to "the tree" entails is (as is usual in English) that the reader
can be expected to know which tree is meant -- there is no implication that no
other trees exist, nor that the tree denoted has no proper subtrees.

For this reason, I think that none of MK's examples entail the claim that the
word "tree" as used in the QT specs has any particular connotation of
maximalness.  Each of the trees mentioned (the tree of entities of an XML
document, the syntax tree for a regular expression, the element tree of an XML
document, the tree constructed to hold all the information in an infoset, the
element tree for the infoset of a document) are uniquely identified by their
qualities.  That doesn't mean they don't contain other trees as subtrees; it
only means that the phrases "the entity tree", "the syntax tree" and so on
serve to identity single trees, not groups of trees.  A subtree of the entity
tree is still a tree (and a node in that subtree is a node both in that subtree
and in the full entity tree) -- it just happens not to be the tree denoted by
the phrase "the entity tree".  

There are actually very few occurrences of the word "tree" in the QT specs that
require being read as meaning "maximal tree constructed from the parent axis"
to make sense.  As I believe has been suggested before, they could easily be
reworded not to require such a special reading of the word "tree", or the Data
Model spec could observe, when introducing the concept that XDM nodes are
arranged in trees, that occasionally an unqualified reference to "the tree"
containing a certain node is a reference to the maximal tree constructed from
the parent axis.  (That is, the spec could define its use of the term "tree".)

Conjectures about what is common usage are best supported by reference to data.

I have already pointed, in other branches of this slow-motion discussion, to
the usage in the handbooks of data structures and computer programming on my
shelves.  Those who wish to argue that the usage of Aho, Hopcroft, Knuth,
Gonnet, Baeza-Yates, Wirth, and others is atypical of technical writing about
computer programming really should provide some examples that support their
claim.  And in light of the examples cited in comment 4, it should probably be
pointed out that to examples of the term "tree" which happen to denote a tree
which is in some sense maximal do not in themselves support the claim that
"tree" is commonly used to denote a non-recursive data structure:  to support
that claim, the example must be incompatible with the recursive interpretation
of the term.  None of the examples in comment 4 have that latter property: 
they are all perfectly compatible with the definitions of "tree" quoted in the
bug report, as well as with the definitions to be found in the computing
literature, which have I believe already been cited in this discussion.

If this issue is now being discussed with a view to closing it, can we not
adopt the wording change that led to the closure of bug 12535?

-- 
You are receiving this mail because:
You are the QA Contact for the bug.

Received on Saturday, 23 February 2013 01:44:22 UTC