Folks,

I'm reading over Vadim Tropashko's SQL Design Patterns book, and
trying to figure out how to maintain transitive reflexive closure,
using PostgreSQL.

Let's assume, for the purposes of this discussion, that I've looked
over all the alternatives to representing graphs as adjacency
relations and decided to go ahead with adjacency relations.

For simplicity I'm using two tables: edges and
transitive_reflexive_closure.

CREATE TABLE edges (
tail INTEGER NOT NULL,
head INTEGER NOT NULL,
PRIMARY KEY(tail, head),
CHECK (tail <> head)
);

CREATE UNIQUE INDEX one_way_edges ON edges(
least(tail,head),
greatest(tail,head)
); /* Yes, this should probably be expressible as a constraint, but
it's not yet in PostgreSQL */

CREATE TABLE transitive_reflexive_closure (
tail INTEGER NOT NULL,
head INTEGER NOT NULL,
weight INTEGER NOT NULL,
CHECK(weight > 0),
PRIMARY KEY(tail, head),
FOREIGN KEY(tail, head) REFERENCES edges(tail,head)
);

To populate transitive_reflexive_closure initially, I'd use
PostgreSQL's arrays:

INSERT INTO transitive_reflexive_closure(tail, head, weight)
WITH RECURSIVE t (tail, head, chain) AS (
SELECT tail, head, ARRAY[tail,head]
FROM edges
WHERE NOT EXISTS ( /* Start from only "roots" */
SELECT 1 FROM edges e WHERE e.head = edges.tail
)
UNION ALL
SELECT t1.tail, t1.head, t.chain || t1.head
FROM
edges t1
JOIN
t ON t.head = t1.tail
AND t1.tail <> ANY(t.chain) /* No cycles */
)
SELECT tail, head, count(*)
FROM t
GROUP BY tail, head;

I'd like to see whether continuing along this line will allow for
"graph constraints" like "must be tree" or "must be DAGs."

Does this seem like a valid approach?

Cheers,
David.
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

The only truly new ideas [the right] has come up with in the last
twenty years are1) supply side economics, which is a way of
redistributing the wealth upward toward those who already have more
than they know what to do with, and; (2) creationism, which is a
parallel idea for redistributing ignorance out from its fundamentalist
strongholds to those who know more than they need to.
Barbara Ehrenreich

On Jul 21, 2:11*pm, da... (AT) fetter (DOT) org (David Fetter) wrote:
For DAGs why do you want to start with roots? Two more minor
observations: the query doesn't seem to include identity relation (so
the its not reflective), and in case of more than one path from node A
to B it seems to violate transitive_reflexive_closure primary key
constraint.

Just to avoid any confusion, if you are referring to transitive
closure method you seems to have outlined only half of it. The second
step is transitive closure maintenance, that is what edges to insert
into the transitive closure table when an adge is added into the
source table.

Tree constraint is easy to express: no two edges should have the same
tail (pp 208-209). The DAG constraint is also easy to express on the
transitive closure table. Every cycle in the graph is represented in
transitive closure by a reflective edge. (If your variation of
transitive closure breaks cycles early then, the condition of not
having cycles in an original agjacency relation becomes a self-join
query upon transitive closure table asserting that any two nodes A and
B are not connected by both edges(A,B) and (B,A) ).