Re: Hierarchical query
Date: Thu, 14 Jun 2007 11:06:25 -0700
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>
> > 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
> > 184.108.40.206 expr
> > 220.127.116.11.1 1
> > 18.104.22.168 +
> > 22.214.171.124 expr
> > 126.96.36.199.1 1
> > 1.1.3 )
> > 1.2 +
> > 1.2 expr
> > 1.2.1 1
> > the query should return nodes 188.8.131.52.1 and 184.108.40.206.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.
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