Re: Hierarchical query

On 14 jun, 01:47, Marshall <marshall.spi..._at_gmail.com> wrote:
>
> It seems clear enough, the idea of regarding an XML document
> as a syntax tree, and the DTD as a grammar. In which case,
> *XML*parsing is then the analog of ... what? Converting an
> ascii version of a syntax tree into a binary syntax tree?
> Sort of like parsing s-expressions?

Sure, ordered node-labeled trees, S-expressions, XML documents, recursively nested terms, et cetera, are all more or less the same thing. Of course the typical use cases are different, which justifies having diferent transformation / update / query / selection languages and formalisms.

> If that analysis is valid, then I'd be interested to continue to
> a comparison with other techniques for accomplishing the
> same thing, particularly from the standpoint of expressive
> power, but also from the standpoint of convenience and
> generality.
>
> Other techniques I can think of are:
>
> 1) ad hoc traversal of an object graph in an OO language
> 2) pattern matching over abstract data types, as introduced
> by SML. (The gold standard.)
> 3) "Tree walking" a la Terrance Parr / Antlr (the upstart.)

Yep, Tree automata, Tree transducers, Attribute grammars, XQuery, XSLT... all have their typical use cases. Is that what you are interested in?

> 2) I would be very interested to hear a comparison with
> pattern matching from someone who is familiar with both
> techniques. One thing I can see immediately is that XPath
> expressions allow one to address only some specific
> part of a tree that one is interested in, whereas pattern
> matching requires whole-tree analysis. How much of an
> issue is this in practice?

I think that question needs more context in order to be meaningful. The pattern matching mechanism is usually embedded in another languages (some functional programming language like Caml, XSLT or XQuery). Depending upon that language it may or may not be a problem if your pattern matching mechanism lacks certain expressive power.

> > Btw., if you forget about sequence order, document order and value
> > comparisons for a moment, the core of XPath is actually a relatively
> > neat calculus of binary relations:
> > - p_1/p_2 is the concatenation of binary relations
> > - p_1[p_2] is the selection of pairs in p_2 whose right-hand side
> > matches a left-hand side in p_2 (semijoin anyone?)
> > - p_1 union p_2 is the set union of two binary relations
> > - p_1 intersect p_2 is the set intersection of two binary relations
> > - p_1 except p_2 is the set difference between binary relations
>
> > Did I mention Tarski already? :-) Of course we had to wait until
> > XPath2.0 until the three set operations were all allowed everywhere,
> > but we have them now.
>
> I guess we're talking about Relation Algebra here? I don't know
> enough about it to know if this is just an interesting comparison
> of if there's some specific result being alluded to.

Yep.

<http://staff.science.uva.nl/~marx/talks/2005/screen_icdt.pdf>

Page 12.

• Jan Hidders