Hierarchical query

[David Cressey]

Not so fast. An enumeration of the paths in a tree does not always
give you enough information to reconstruct the tree, so you would be
losing expressive power. Never mind that you ignore the order, which
may be a factor for the scope of declarations.

I don't understand why enumerating the paths ignores the order.

 

[Jan Hidders]

I don't understand why enumerating the paths ignores the order.

Take the trees a( b( c ), d ) and a( d, b( c) ). The *set* of paths is
in both cases: { a, a.b, a.b.c, a.d }.

Of course, making it a list and making sure you notice the end of
subtrees solves that problem. So the tree a( b( c ), b( c )) would
generate the list [a, a.b, a.b.c, a.b, a.b.c] and a( b( c, c)) would
generate the list [a, a.b, a.b.c, a.b.c].

-- Jan Hidders

 

[Vadim Tropashko]

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

 

[Vadim Tropashko]

A set of strings


I was going to define tree query in pure language settings, be it
regular languges, context free grammars, or else.


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).

Alternatively, one can build transitively closed relationship of all
the token precedences, then finding all the tokens nested inside some
pair of parenthesis is expressed via 2 joins query.

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

 

[Joe Kesselman]

Reminder: The best comparison for a database query, in the XML world, is
XQuery -- a synthesis of XPath and XSLT. It's structural rather than
relational, but many of the concepts are the same and XQuery is probably
the best spec to study if you want to see how they map into each other.

(The XSLT 2.0 spec, by the way, is literally generated from the same
source files as the XQuery spec; it drops a few features, adds a few
features, and uses slightly different syntax but the underlying
semantics are intended to be identical.)

 

[Jan Hidders]

A set of strings


I was going to define tree query in pure language settings, be it
regular languges, context free grammars, or else.

?? How does one query a set of strings in a "pure language setting"?
Of course you might select certain strings from the set with something
that accepts strings from a certain language, but that is clearly
inadequate because you cannot take the "context" of the node into
account. So what did you have in mind?

-- Jan Hidders

 

[Vadim Tropashko]

?? How does one query a set of strings in a "pure language setting"?
Of course you might select certain strings from the set with something
that accepts strings from a certain language, but that is clearly
inadequate because you cannot take the "context" of the node into
account.

And what the node's "context" would be? A set of attributes? If so,
then we are in pure relational world. I don't feel comfortable,
however, that we use the two completely different mechanics: languges
for parsing and building the derivation tree, and relations for
querying.

The question is if all these attributes are not redundant and can't be
collapsed into a single attribute. Then language approach would become
possible.

 

[Jan Hidders]

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

 

[Jan Hidders]

And what the node's "context" would be?

The nodes around it, the preceding siblings, the following sibling, et
cetera. How do I ask for an "a" node that is immediately preceded by a
"b" node?

-- Jan Hidders

 

[Aloha Kakuikanu]

The nodes around it, the preceding siblings, the following sibling, et
cetera. How do I ask for an "a" node that is immediately preceded by a
"b" node?

No you don't need that many, only two. One is the absolute position of
the node in the hierarchy, for example path, or 4 integers
corresponding to the matrix encoding. The second one is the node
payload -- grammar token in this case. They have completely different
structure, so I'm most likely wrong expecting to be able to operate a
single attribute.

 

[Marshall]

My hope is that this post will stimulate an educated and informative
discussion of the relative merits of different approaches to
tree traversal, not neglecting to differentiate among the needs
of diverse use cases.

Hey, it could happen.

Or, you know, not.


Marshall