From: hidders@REMOVE.THIS.uia.ua.ac.be
To: pgsql-sql@postgresql.org
Subject: Re: double linked list
Date: 29 Jan 2003 14:48:56 +0100
Message-ID: <3e37dbc8$1@news.uia.ac.be> (raw)
References: <2ee07259.0301280744.582e4b7c@posting.google.com>
<c0d87ec0.0301281554.581797ee@posting.google.com>
<2ee07259.0301290412.5eb3290a@posting.google.com>
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.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: hidders@REMOVE.THIS.uia.ua.ac.be
Subject: Re: double linked list
In-Reply-To: <3e37dbc8$1@news.uia.ac.be>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox