Transitive Reflexive Closure And Its Discontents

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 */

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.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter_at_gmail.com

The only truly new ideas [the right] has come up with in the last
twenty years are:(1) 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