Re: Hierarchies in the relational model

"Paul" <pbrazier_at_cosmos-uk.co.uk> wrote in message news:51d64140.0310200434.68c75a5f_at_posting.google.com...
> If we are speaking theoretically, how would our ideal DBMS deal with
> Does a transitive closure operator cover
> all hierarchy-based problems? Are there some other examples of common
> problems that require second-order logic and can't be solved with a
> transitive closure operator?

It doesn't seem so. One of the problem not solved even with transitive closure is enumerating all the paths in a graph like this

Edges:
tail head
---- ----
1 2
1 3
2 4
3 4

Paths:
# tail head
- ---- ----

1    1     2
2    1     2
2    2     4
3    1     3
4    1     3
4    3     4
5    2     4
6    3     4

The big(?) problem seem to be that for a transitevely derived edge, e.g. 1->4, there is more than one path, so that one have problem identifying all the paths in the first place.

It's impossible to write a query returning all the paths in datalog or SQL (with recursive syntax), because the output will be of size exponential in the size of the input, and it's well-known that datalog and SQL (meaning: RA+recursion+aggregation+arithmetic) cannot do it.

The answer was kindly provided in private email exchange by Leonid Libkin. Received on Mon Oct 20 2003 - 22:54:25 CEST