# Re: Hierarchical query

Date: Thu, 14 Jun 2007 11:06:25 -0700

Message-ID: <1181844385.603603.53480_at_q19g2000prn.googlegroups.com>

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