2011/1/12 Alvaro Herrera <alvherre@commandprompt.com>:
> FWIW this idea fails when you consider stuff such as circular foreign
> keys (and I suppose there are other, more common cases). If you really
> want something general you need to break those apart. (This is the
> explanation for the “break the loop” code in pg_dump I imagine)
Good point.
Yes, the algorithm must be able to "break the loop", i.e. remove the
edges causing the loops.
This has already been properly solved in pg_dump, but I frankly don't
really understand exactly how this is done, at least not the "general
rule" on how to do it, even after spending hours studying the source
code.
Also, circular dependencies seems impossible for some object classes,
such as functions, views, constraints and triggers. None of them can
possibly refer to them self. If you only need to create/drop objects
of these classes (like in my case within the pov-project), it's not
important to "break the loop" in a clever way, i.e. simply removing
any of the edges, not necessarily the best suited one, will do for my
purpose.
I have updated the example with two circular relations:
-- Circular dependencies:
CREATE TABLE tselfref ( id int not null PRIMARY KEY, parentid int not
null REFERENCES tselfref(id) );
CREATE TABLE tcircular ( id int not null PRIMARY KEY, id2 int not
null REFERENCES tselfref(id) );
ALTER TABLE tselfref ADD COLUMN id2 int not null REFERENCES tcircular ( id );
I have also updated pd_depend.[sql|dot|png|svg] and
pg_depend_actual.[dot|png|svg] with the circular references.
The dotted edges in pg_depend_actual are the edges which must be
removed to "break the loop".
Any ideas on how to design an algorithm to transform the digraph
pg_depend into pg_depend_actual are highly appreciated.
--
Best regards,
Joel Jacobson
Glue Finance