Re: Is "connect by" equivalent to "recursive with" (was Re: Is nonlinear recursion...)

Mikito Harakiri wrote:
> Therefore, the question still is "Is connect-by less expressive than
> recursive-with"?

For linear Datalog programs (=ANSI SQL?) it seems to be.

Datalog program is called linear if each recursiuve clause has at most one of the predicates from the ones appeared in the heads of the rule. Therefore, rules could be partitioned into classes like that

p <- a_11,...,a_k1, p , a_(k1+1), ..., a_n1 p <- a_21,...,a_k2, p , a_(k2+1), ..., a_n2 ...
p <- b_1,...,b_m1
p <- b_2,...,b_m2
...

where all As and Bs are predicates that can't appear in any rule heads. Then, let

U be an answer for

U <- b_1,...,b_m1
U <- b_2,...,b_m2
...

which is relationally nothing more than a union of select-project-join queries.

Next, let

A_1k <- a_11,...,a_k1
A_1n <- a_(k1+1), ..., a_n1
...

and

A_1k^*(length)
A_1n^*(length)

be relational closures of these. Substituting all these we finally express p nonrecursively:

p <- A_1k^*(length), U , A_1n^*(length)
p <- A_2k^*(length), U , A_2n^*(length)

Nothing more than straightforward generalization of Mikito's "reverse-same-generation" example.

Is everything correct in this "proof"? Don't variables (which were skipped for simplicity) pose any subtle problem? Received on Wed Feb 25 2004 - 19:31:31 CST