This apparently trivial difference has some interesting and profound consequences.
Transformations of a tree in which many branches of the tree remain unchanged become much more efficient,
because (in an environment where in-situ update is not allowed) copying a subtree has zero cost.
To give a specific and simple example
1. Sharing a subtree (between two trees) in a binary search tree has
time complexity just O(log(N)) -- the time needed to find the node in
a BST of N nodes. Compare to having to create a complete copy of the
tree (which is necessary if a node can have no more than one parent)
-- O(N). The same for creating a tree to which just one node has been
changed (replaced) -- all tree nodes can be shared with the exception
of the nodes on the path from the original root to the node that must
be changed.
2. Sharing a subtree between M trees (or creating a tree from the
original one in which M nodes have to be changed) -- O(M(logN)).
Compare this to creating M complete copies of the tree (which is
necessary if a node can have no more than one parent) -- O(M*N).
To put it simply, the difference in performance is similar to that
between Quicksort and BubbleSort: O(N*log(N)) / O(N^2)
The same for space complexity.
Cheers,
Dimitre
On Sun, Apr 10, 2016 at 2:20 PM, Michael Kay <mike@saxonica.com> wrote:
I was sorry to read that XQuery 3.1 is not considering JSON data as a tree: JSON is treated as a "complex" atomic type, from my point of view.
You can regard the output of parse-json() as a tree (of maps, arrays, etc), but it is different from the tree representation of XML. The main difference is that the maps, arrays, etc produced by parse-json() have no parent.
This corresponds closely to the way JSON data is handled in other programming languages.
This apparently trivial difference has some interesting and profound consequences. Transformations of a tree in which many branches of the tree remain unchanged become much more efficient, because (in an environment where in-situ update is not allowed) copying a subtree has zero cost. However, the lack of upwards or sideways navigation means that during a recursive descent of the tree, you need to pass a lot more context.
For an exploration of the effect of these differences on some transformation use cases, see my XML Prague 2016 paper.
Michael Kay
Saxonica
_______________________________________________________________________
XML-DEV is a publicly archived, unmoderated list hosted by OASIS
to support XML implementation and development. To minimize
spam in the archives, you must subscribe before posting.
[Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
subscribe: xml-dev-subscribe@lists.xml.org
List archive: http://lists.xml.org/archives/xml-dev/
List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
