[Bug 12535] New: [DM] Definition of 'tree' missing and apparently non-standard

http://www.w3.org/Bugs/Public/show_bug.cgi?id=12535

           Summary: [DM] Definition of 'tree' missing and apparently
                    non-standard
           Product: XPath / XQuery / XSLT
           Version: Working drafts
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Data Model 3.0
        AssignedTo: ndw@nwalsh.com
        ReportedBy: cmsmcq@blackmesatech.com
         QAContact: public-qt-comments@w3.org


The XDM 3.0 draft of 14 December 2010 says, in section 2.1

    Nodes form a tree that consists of a root node plus all the
    nodes that are reachable directly or indirectly from the root
    node via the dm:children, dm:attributes, and dm:namespace-nodes
    accessors. Every node belongs to exactly one tree, and every
    tree has exactly one root node.

The same words occur in XDM 2.0 2E, published on the same date; 
bug 12534 has been opened against that spec; its description is
essentially the same as given here

Ideally, I'd be inclined to want an explicit definition in the XDM
spec of what is meant by 'tree' here.  

I suppose an argument might be made that it's never possible to
define absolutely everything; some notions end up being taken either
as primitive undefined notions that can't be defined because they
are primitives, or as well understood ideas that don't need to be
defined because the spec is using them in the same sense they have
in ordinary technical language.  This argument has a major problem,
though: the XDM spec cannot possibly be using 'tree' in any of the
ordinary senses, because they are incompatible with the words quoted
above.

In mathematics, a tree is (in the words of Wolfram MathWorld [1]),
"a simple, undirected, connected, acyclic graph (or, equivalently, a
connected forest)".  (Actually, in graph theory, 'tree' is routinely
given any of several different definitions, and it is an exercise in
elementary graph theory to prove that the different definitions are
all equivalent.  But Wolfram's definition will do.)  

But it is a direct consequence of the mathematical definition of
tree that any node belongs to multiple trees (in most practical
cases, to an infinite number of trees), because an undirected graph
is just a set of nodes with a relation defined over the set of
nodes, and any object that can be a member of a set is a member of
multiple sets, unless it is the only object in the universe of
discourse.  When a universe of discourse has an infinite number of
objects, any object will be a member of an infinite number of sets,
and for each of those sets there will be at least one relation on
the objects that defines a tree.

It is also a fact that in ordinary mathematical discourse trees are
not necessarily rooted; the trees XDM is interested in are directed
graphs, not undirected graphs, and all the trees have roots.

When 'tree' is used as the name of a data structure, it usually
involves the notions of directedness and rootednees.  But here, too,
any node can belong to multiple trees, and almost always will;
exceptions again involve universes of discourse with only one
object.  Even if we assume that a given parent : child relation is
given and fixed (and if the reader is expected to assume that, this
reader at least would really like to be told), the definition of
'tree' as a data structure is, in ordinary usage, formulated so as
to guarantee that any tree with multiple nodes has a number of
subtrees, each of which is by definition a tree.  The discussion of
trees as a datastructure in Wikipedia [2], for example, says
explicitly that any subtree is a tree.

So: either XDM is intending to use the term 'tree' in one of its
ordinary senses, or it's intending to use the term in a non-ordinary
sense.  In the former case, the statement about any node belonging
to a single tree is simply false and needs to be deleted or restated
in a way that isn't bogus.  In the latter case, this reader would
like to know what definition is intended.

My apologies for not noticing this problem earlier.


[1] Weisstein, Eric W. "Tree." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/Tree.html

[2] [Anonymous.]  "Tree (data structure)."  Wikipedia, last modified
18 April 2011.  http://en.wikipedia.org/wiki/Tree_(data_structure)

-- 
Configure bugmail: http://www.w3.org/Bugs/Public/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.

Received on Wednesday, 20 April 2011 13:29:25 UTC