Re: [xml-dev] YPath, ZPath?

[Dimitre Novatchev <dnovatchev@gmail.com>]

> 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



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
To achieve the impossible dream, try going to sleep.
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they
write all patents, too? :)
-------------------------------------
Sanity is madness put to good use.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.