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


---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

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

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

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

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

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


---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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.

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match