Re: Computing transitive closure of a table - Mailing list pgsql-general

From Oleg Bartunov
Subject Re: Computing transitive closure of a table
Date
Msg-id Pine.GSO.4.63.0606192358160.2921@ra.sai.msu.su
Whole thread Raw
In response to Computing transitive closure of a table  ("Chris Smith" <cdsmith@twu.net>)
List pgsql-general
Chris,

have you seen contrib/ltree ?

Oleg
On Mon, 19 Jun 2006, Chris Smith wrote:

> I am doing some preliminary work on the next major release of a piece of
> software that uses PostgreSQL.  As odd as this sounds, it seems that a huge
> percentage of the new features that have been requested involve computing the
> transitive closure of a binary relation that's expressed in a database table.
>
> For example:
>
> - Given a list of relationships of the form "X is a direct subgroup of Y",
> determine the full list of groups of which some group is a (not necessarily
> direct) subgroup.
>
> - Given a list of statements of the form "X must happen before Y", determine
> everything that needs to happen for some objective to be achieved.
>
> And the list goes on and on...  I'm aware that it's not possible to solve the
> transitive closure problem using a simple SQL query.  Anyone have any
> recommendations?  Are there any thoughts on implementing efficient transitive
> closures within PostgreSQL?  If I wanted to do it, are there preferences on
> syntax or other such things?
>
> My thoughts on an ideal feature would involve being able to create a sort of
> "transitive closure" index which could be kept up to date automatically by
> the database back end.
>
> Or should I just punt and let the queries be slow (not a good option, since
> the group thing is necessary for permission checking, which may happen up to
> a half-dozen times per HTTP request).
>
> Thanks,
>
>

     Regards,
         Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

pgsql-general by date:

Previous
From: "Chris Smith"
Date:
Subject: Computing transitive closure of a table
Next
From: Bruno Wolff III
Date:
Subject: Re: Computing transitive closure of a table