Re: Computing transitive closure of a table

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(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83