From: hidders@REMOVE.THIS.uia.ua.ac.be (Jan Hidders)
Subject: Re: double linked list
Followup-To: comp.databases.theory
Date: 29 Jan 2003 14:48:56 +0100
Organization: University of Antwerp
Lines: 23
Message-ID: <3e37dbc8$1@news.uia.ac.be>
References: <2ee07259.0301280744.582e4b7c@posting.google.com>
	<c0d87ec0.0301281554.581797ee@posting.google.com>
	<2ee07259.0301290412.5eb3290a@posting.google.com>
Reply-To: hidders@uia.ua.ac.be (Jan Hidders)
Originator: hidders@hcoss.uia.ac.be (Jan Hidders)
To: pgsql-sql@postgresql.org

Juergen wrote:
>
>However, I dont store a consistent tree structure. The table at hand
>is more a kind of a collection of graphs where I want to find all
>possible paths between a given starting point and a given end point

A collection of graphs? As you presented the problem it was simply a single
graph.

That's not possible in a single SQL statement without using some form of
recursion such as the CONNECT BY in Oracle that was already mentioned or the
recursive queries as are possible in RDB. Another "poor man's solution" could for
example be to add a table Reachable(node, from_a, to_b) with 'from_a' and
'from_b' boolean field that indicate that the node is reachable from a and
that b is reachable from this node. You could compute this relation by
repeating a certain SQL update statement that:
1. sets from_a of node n to true if there is a node n' that is reachable
   from a and there is an edge from n' to n, and
2. set to_b of node n to tur if there is a node n' that leads to b and there
   is an edge from n to n'.
You repeat that until no more flags are changed. Then you select only those
edges for which the begin and node have both flags set to true.