Handling Tree structures in a relational manner is a chore. At least, that's what it looks like at the beginning. Let's try to use (semi) modern SQL to make our lives easier.

Modeling Tree Structures in a Database Using a Transitive Closure

The problem

We all know and love our relational databases. Sure, SQL is an aquired taste, but so is beer. And, just like beer, it's great once you "get" the taste, and there's absolutely nothing nothing nothing that can go wrong if you have a little too much of it.

Inser image about postgresql elephant and say (it's also just like elephants and nothing can go wrong if you keep it caged)

Until you find yourself in the need of representing a tree-like structure. Note that I'm refraining myself from using the word graph because I don't want to get my hands dirty with circular references (or cycles). A tree-like structure has nodes (in this case, row or tuples since we are in relational-land) that may have children rows. Recursively, each children row may have children on their own, ad infinitum. It's not a simple Parent-Children relationship, but rather a genealogical tree with:

  • Nodes: Any entity in our relationships
  • Roots: Nodes that have no parent
  • Siblings: Nodes that share a common direct parent
  • Leaves: Nodes that have no children

For this rest of this article let's try to model the next tree:

0 -> Category 1
|
| 1 -> SubCategory 1-1
| |
| | 2 -> SubSubCategory 1-1-1
| 1 -> Subcategory 1-2
| |
| | 2 -> SubSubCategory 1-2-1
| | 2 -> SubSubCategory 1-2-2

Finding a solution

A very usual pattern to try to deal with this situation is using a self reference column, such that each row-node knows who his parent is. Let's use this category table as an example of a tree structure:

CREATE TABLE "public"."category" (
"categoryid" int4 DEFAULT nextval('productcategory_productcategoryid_seq'::regclass) NOT NULL,
"name" varchar(50) COLLATE "default" NOT NULL,
"parentcategoryid" int4
)
ALTER TABLE "public"."category" ADD PRIMARY KEY ("categoryid");
ALTER TABLE category

ADD CONSTRAINT fkcategoryparentcategoryid FOREIGN KEY (parentcategoryid) REFERENCES category (categoryid) MATCH SIMPLE ON UPDATE NO ACTION ON DELETE NO ACTION;

Pretty much like a linked list, you can traverse back, and know what are a node's ancestors:

WITH ccategory AS (
    SELECT C.*
    FROM category C
    WHERE C.categoryid = 1 --or whatever node's id we want to know the acenstors of

    UNION ALL
    SELECT C.*
    FROM category C
    INNER JOIN ccategory CC
    ON CC.parentcategoryid = C.categoryid
)
SELECT * FROM ccategory;

This recursive common table expression let's us know all the way up to the root from one node. In this category examples, it let us know all the parent categories that embed category 1. It doesn't, however, tell us about node 1's siblings. That, we can know it easily too:

SELECT C.*
FROM category C
ON C.parentcategoryid = 1;

But that will only let us know the direct children of an specific parent, at a determinate depth and nothing else about ancestors.

This is ok. But we can do better.

Transitive Clojure Table

A transitive closure table is a table that presents every relationship on our tree-like relational structure. In this case, each row still holds a reference to its parent row, but it also contains the depth.

Ok ok, come think about it, managing (CRUD and the logic behind it) for an extra column for "depth of node" will be awkward. Clumsy, to say the list. But, alas!, we don't have to do it by ourselves when our database already know this information although implicitly.

Let's create a view which will let us also know the depth (and root) of every node, besides its parent.

WITH categories_tc AS ( --"_tc" is for transitive closure

SELECT C.*, 
     C.categoryid AS _root,
     0 as _depth
FROM category AS C
WHERE C.parentcategoryid IS NULL --roots

UNION ALL

SELECT C.*,
    C_TC._root AS _root,
    C_TC._depth + 1 AS _depth
FROM category AS C
INNER JOIN categories_tc AS C_TC
    ON C.parentcategoryid = C_TC.categoryid
)
SELECT C.*
FROM
Posted by: fabzter
Last revised: 04 Dec, 2014 12:49 PM History

Comments

Your Comments

Used for your gravatar. Not required. Will not be public.
Posting code? Indent it by four spaces to make it look nice. Learn more about Markdown.

Preview