Alexandru Berlea and Helmut Seidl. Binary Queries for Document Trees. Nord. J. Comput., 11(1):41-71, 2004.

Motivated by XML applications, we address the problem of answering $\mathnormal{k}$-ary queries, i.e. simultaneously locating $\mathnormal{k}$ nodes of an input tree as specified by a given relation. In particular, we discuss how binary queries can be used as a means of navigation in XML document transformations. We introduce a grammar-based approach to specifying $\mathnormal{k}$-ary queries. An efficient tree-automata based implementation of unary queries is reviewed and the extensions needed in order to implement $\mathnormal{k}$-ary queries are presented. In particular, an efficient solution for the evaluation of binary queries is provided and proven correct. We introduce fxgrep, a practical implementation of unary and binary queries for XML. By means of fxgrep and of the fxt XML transformation language we suggest how binary queries can be used in order to increase expressivity of rule-based transformations. We compare our work with other querying languages and discuss how our ideas can be used for other existing settings.

Download: PDF Reference: Bibtex