Re: Hierarchical query

On Jun 13, 3:47 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
> On 13 jun, 23:56, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
>
>
>
> > [...] Then, your reply was a critical for me
> > understanding that the tree structure is unnecessary, the derivation
> > is essentially a language -- a set of words (which includes both
> > terminals and nonterminals) and this set of words can be quieried
> > solely with the language theory means. Formally, a query is a language
> > intersection.
>
> Of course, all computation, including RDBMS and XML querying and
> transformation, is ultimately just string manipulation. Doesn't mean
> that Turing Machines are always the most appropriate formalism for
> describing them, does it? :-)

You seem to imply that language theory reduces to trivial string manipulation. I expected you to request clarification why a query is a language intersection; is there any nonvacuous idea behind this statement? And insist on demonstating that the reg exp method does work:-)

Consider a simple expression grammar

expr :
  expr '+' expr
| '(' expr ')'
| '1'

and the string

(1 + 1) + 1

When we ask if this string belongs to the language defined by the grammar, we are interested to know if the intersection of the infinite language defined by the above expression grammar and finite language coonsisting of a single string is empty.

The derivation that proves that a string belongs to a language is a chain of inequalities (where inequality is understood to be the usual language subset relation):

(1 + 1) + 1 < (expr + 1) + 1 < ... < (expr + expr) + expr < expr + expr < expr

Now we have derivation tree:

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

Next if we encode tree nodes as paths of the grammar symbols, then not only the order is lost (as you correctly observed), but the duplicate paths are collapsed:

1 --> expr

1.1 --> expr expr
1.1.1 --> expr expr (
1.1.2 --> expr expr expr
1.1.2.1 --> expr expr expr expr
1.1.2.1.1 --> expr expr expr expr expr
1.1.2.2
1.1.2.3
1.1.2.3.1
1.1.3
1.2
1.2 --> expr expr   (same as 1.1!)
1.2.1