olpa (olpa) wrote,

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://user.rol.ru/~satura/sxp-prototype.scm -- больше не существует.


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:

(see Section 2 of that article).

A zipper is a way to "mutate" a complex data structure declaratively. ...
Tags: papers
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.