Re: Hierarchical query

On 14 jun, 19:13, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On Jun 14, 9:41 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com>
> wrote:
>
>
>
> > On Jun 14, 2:47 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> > > Are you saying that anything for
> > > which one would typically use XPath can be done just as well with
> > > regular expressions assuming that the tree is somehow encoded in a
> > > string?
>
> > A set of strings
>
> > > This is clearly not the case for the encoding you gave. Or are
> > > you going to extend that? Perhaps also extend the regular expressions
> > > a little?
>
> > I was going to define tree query in pure language settings, be it
> > regular languges, context free grammars, or else.
>
> > > Or did you just have a particular query in mind?
>
> > Let's start from scratch again with simpler example. Given a grammar
>
> > expr :
> > expr '+' expr
> > | '(' expr ')'
> > | '1'
>
> > and derivation tree find all the '1's that are nested within a pair of
> > brackets. In the example
>
> > 1 expr
> > 1.1 expr
> > 1.1.1 (
> > 1.1.2 expr
> > 1.1.2.1 expr
> > 1.1.2.1.1 1
> > 1.1.2.2 +
> > 1.1.2.3 expr
> > 1.1.2.3.1 1
> > 1.1.3 )
> > 1.2 +
> > 1.2 expr
> > 1.2.1 1
>
> > the query should return nodes 1.1.2.1.1 and 1.1.2.3.1
>
> Actually, this query is easy in the relational world. For an open
> parenthesis node, find a parent, and then all the descendants such
> that ... One may use nested sets encoding, or nested intervals in
> matrix encoding (where finding parent is much more transparent).

Indeed. In fact, there are close and interesting connections between XPath and first order logic, presuming that the ancestor-descendant relation is given to you (and not only the parent-child relation) and the sibling-order relation.

> So, I have hard time to define a concept of query in pure language
> settings...

It's probably not the direction where you wanted to go, but the real connection with formal language theory lies in tree automata which are a generalization of finite automata for trees. Strings are after all just a special kind of node-labeled tree where each node has at most one child.

• Jan Hidders