Re: Computing transitive closure of a table

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,

--
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

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

On Mon, Jun 19, 2006 at 13:43:17 -0600,
Chris Smith <cdsmith(at)twu(dot)net> 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.

I believe this is covered by the following on the TODO list:
Add SQL:2003 WITH RECURSIVE (hierarchical) queries to SELECT

I think someone did some work on this a while ago, but that not much has
happened recently.

Oleg Bartunov wrote:
> Chris,
>
> have you seen contrib/ltree ?

I hadn't. Thanks! I will look into it further, but I'm currently a bit
concerned by the word "tree" in the title. Many of the problems I'm solving
are not trees, though nearly all are DAGs.

--
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

There was a thread last November entitled "Transitive closure of a
directed graph" on the [HACKERS] list. There may be some information of
use there.