sql - How can I create a closure table using data from an adjacency list?

Question

I have a database containing a hierarchy of categories stored using the adjacency list model.

The hierarchy is 3 levels deep (not including an imaginary root node) and contains approx 1700 nodes. Nodes in the 2nd and 3rd levels can have multiple parents. A additional table is used for the many-to-many relationship as below:

CREATE TABLE dbo.Category(
    id int IDENTITY(1,1) NOT NULL,
    name varchar(255) NOT NULL,
)

CREATE TABLE dbo.CategoryHierarchy(
    relId int IDENTITY(1,1) NOT NULL,
    catId int NOT NULL,
    parentId int NOT NULL,
)

If I move to using the transitive closure table method (for the sake of data integrity etc) is there a relatively easy query I can execute that would generate the values for the closure table? (using SQL Server 2005)

I've look through articles and presentations such as Bill Karwin's Models for hierarchical data but that only has insertion queries for a single node and it would take forever for me to create my tree like that.

Thanks.

EDIT:
RelID in the CategoryHierarchy table is purely for the sake of a primary key, it has no bearing on the node ids of the Category table.

Also by closure table, I mean a table like this:

CREATE TABLE ClosureTable (
    ancestor int NOT NULL,
    descendant int NOT NULL,
    [length] int NOT NULL,
)

Where the first two columns are a compound primary key, and are individually foreign keys to Category.id.

Answer 1

I was trying to figure out the same thing, but wanted it in a recursive CTE. This wouldn't have worked for you (SQL Server 2008+), but here's what I ended up with for anyone else looking.

The key is that the anchors aren't your root nodes (where parent_id IS NULL), but instead all your zero depth rows-to-be in the closure table.

Table

CREATE TABLE dbo.category (
    id         INT IDENTITY(1, 1) NOT NULL,
    parent_id  INT                    NULL
)

Data

INSERT INTO dbo.category (id, parent_id)
VALUES
    (1, NULL),
    (2, 1),
    (3, 1),
    (4, 2)

CTE

WITH category_cte AS
(
    SELECT
        id AS ancestor,
        id AS descendant,
        0  AS depth
    FROM dbo.category

    UNION ALL

    SELECT
        CTE.ancestor  AS ancestor,
        C.id          AS descendant,
        CTE.depth + 1 AS depth
    FROM dbo.category AS C
    JOIN category_cte AS CTE
        ON C.parent_id = CTE.descendant
)
SELECT * FROM category_cte

Result

ancestor descendant depth
-------- ---------- -----
1        1          0     <- anchor query
2        2          0
3        3          0
4        4          0
2        4          1     <- first recursive query
1        2          1
1        3          1
1        4          2     <- second recursive query