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
