- From: <bugzilla@jessica.w3.org>
- Date: Wed, 20 Apr 2011 13:29:23 +0000
- To: public-qt-comments@w3.org

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