On parent pointers in SXML trees

Обнаружил распечатку статьи "On parent pointers in SXML trees", её обсуждение и свои пометки. Речь идёт о том, как находить узлы-предки в случае, когда XML infoset представлен в виде лисповых s-expressions, не имеющих указателей "вверх по дереву".

Это довольно узкая тема, интересная немногим. Гораздо увлекательнее обсуждение (1, 2, 3, 4, 5), из которого я надёргал дальшейших ссылок.

Перезапись XPath.

Типа //p[../div] --> //div/p

XPath: Looking Forward
Dan Olteanu, Holger Meuss, Tim Furche, Fran[E7]ois Bry
Research Report PMS-FB-2002-4, 2002
The Electronic Library journal, volume 20, number 4, 275-287, 2002

Нахождение предков при вычислении XPath

Since SXPath already _violates_ the XPath evaluation context, we can at least make this _violation_ more suitable for the SXML data model. Instead of storing just a "root node" in the SXPath evaluation context, we can store the whole sequence of context node"s ancestors:

(context node's parent, context node's grandparent, ... , root node)

There is than no need in the expensive searching for a parent from the "root node".

Запоминание узлов, используемых в дальнейшем

It's a neat technique, conducive to high-performance XPath evaluations. XPath evaluation is an active research area -- for example, google for Dan Suciu.

http://www.cs.washington.edu/homes/suciu/

Прототипчик на основе обсуждения

http://user.rol.ru/~satura/sxp-prototype.scm -- больше не существует.

zippers

How interesting! Rather than adding parent-pointer annotations to the nodes in the source tree, you carry annotations in an "intermediary tree" -- the node list being passed from one SXPath step function to another.

...

The idea of "context" is quite remarkable. It reminded me of "zippers" that I learned of recently:

http://citeseer.nj.nec.com/hinze01web.html
(see Section 2 of that article).

A zipper is a way to "mutate" a complex data structure declaratively. ...