Modeling Hierarchical Data in Postgres

hierarchy data

Hierarchical data has historically been a challenge with relational databases. There are well-known solutions for implementing a hierarchy in a purely relational fashion, but their complexity and performance are not generally desirable. To overcome this, some modern RDBMSs have a special data type for hierarchical values. In the case of Postgres, this data type is the ltree.

The ltree data type allows for storing paths similar to filesystem paths or DNS records, and provides the ability to perform hierarchical queries which are much cleaner and more efficient than their purely relational counterparts. But often we want to have further constraints, such as requiring the existence of all ancestors in each path, and this requires additional work. Here we develop a complete implementation of the common use case of an entity hierarchy with the same properties as a filesystem directory tree.

ltree Basics

The ltree documentation refers to each ltree value as a path, and each component of the path as a label. A path is a series of labels separated by dots, as in DNS, but with the root on the left-hand side, as in a filesystem path. The ltree implementation requires the following for an ltree value to be valid:

  • Each label must contain only the characters A-Za-z0-9_ and be less than 256 bytes long.
  • Each path must be less than 65 kB in size and can contain 0 to 256 labels.

ltree is implemented as a Postgres extension, so this extension must be added to any database where it is to be used.

CREATE EXTENSION "ltree";

The ltree extension provides operators for hierachical queries such as testing if one ltree is an ancestor of another (@>), a descendant (<@), concatenating ltrees (||), and pattern matching (~). In addition to the ltree type itself, the extension also defines a type called lquery that is used for ltree pattern matching. Below are some basic examples of using these types and operators.

db=> SELECT 'com'::ltree @> 'com.pinnsg'::ltree AS "isAncestor";
 isAncestor
------------
 t
(1 row)

db=> SELECT 'com'::ltree <@ 'com.pinnsg'::ltree AS "isDescendant";
 isDescendant
--------------
 f
(1 row)

db=> SELECT 'com.pinnsg'::ltree || 'www'::ltree AS "concatenation";
 concatenation
----------------
 com.pinnsg.www
(1 row)

db=> SELECT 'com.pinnsg.www'::ltree ~ 'com.*.www'::lquery AS "isCompanyWww";
 isCompanyWww
--------------
 t
(1 row)

db=> SELECT 'com.pinnsg.www'::ltree ~ 'com.*.mail'::lquery AS "isCompanyMail";
 isCompanyMail
---------------
 f
(1 row)

An * in an lquery matches zero or more labels, so com.*.www matches com.www, com.pinnsg.www, and com.pinnsg.intranet.www. To restrict this to a set number of labels, use *{n}, or *{n,m} to restrict to a range.

Example Project Requirements

For this example, we specify the following properties for our hierarchial entity.

  1. Every instance has a unique location in the hierarchy.
  2. There is a single root instance, which is an ancestor of all other instances.
  3. For every node in the path of any given instance, another instance with that path must exist. Attempts to delete a node with descendants will be restricted, not cascaded.
  4. Any subtree may be moved to another location in the hierarchy by simply moving the root of the subtree. The relabeling will be cascaded so that explicitly relabeling every node in the subtree is not required.

In short, we want our entity hierarchy to work like a filesystem directory tree. But unlike a filesystem or DNS, we do not intend the paths to be user-consumable. They exist simply to define the hierarchal relationship. This allows us to use the entity’s primary key values as labels in the path.

For a specific example, we will create a hierarchy of organizations having a UUID primary key. Since dashes are not valid in ltree labels, it will be necessary to remove those. For the root of the hierarchy, we use the nil UUID.

CREATE EXTENSION "uuid-ossp";

SELECT replace(uuid_nil()::text, '-', '') AS "pathRoot";
\gset

CREATE TABLE "Organization" (
    "id"            uuid        DEFAULT uuid_generate_v4(),
    CONSTRAINT      "pkOrganization"
            PRIMARY KEY ("id"),
    "path"          ltree       NOT NULL,
    CONSTRAINT      "chkPathValid"
            CHECK (
                "path" = :'pathRoot' OR
                "path" ~ (:'pathRoot' || '.*.' || replace("id"::text, '-', ''))::lquery
            ),
    "name"          text        NOT NULL
);

CREATE INDEX "ndxOrganizationPathGist" ON "Organization" USING gist("path");
COMMENT ON COLUMN "Organization"."path" IS 'Hierarchy with labels which are IDs of Organizations with dashes removed.  Nil is the root of this hierarchy.';

Note that there is no unique constraint on the path attribute. In order for the most useful hierarchical query operators to work, we must use a GiST (Generalized Search Tree) index on the path, which does not support unique constraints. We could have a B-tree index in parallel in order to enforce uniqueness on the path, but that would be unnecessary overhead in this case. By requiring that the primary key be used as the final label in the path, the unique constraint on the primary key guarantees that our paths are unique. So the check constraint we have placed on the path is fulfilling requirements 1 and 2.

We will use a trigger to implement requirements 3 and 4. The specific cases that the trigger must handle are:

  1. Prevent deletion of instances with descendants.
  2. Verify that the parent instance exists on insert and update.
  3. Recursively update the path of all descendants when an instance path is updated.

In our example the path cannot be NULL, but our trigger function will allow for NULL paths to make it more broadly applicable.

CREATE FUNCTION "checkPath"() RETURNS TRIGGER AS $$
DECLARE
    n      bigint;
    nlevel integer;
    child  record;
BEGIN
    CASE TG_OP
    WHEN 'DELETE'
    THEN
        IF OLD.path IS NOT NULL
        THEN
            -- Verify that no descendants exist.
            EXECUTE format('SELECT * FROM %I.%I WHERE "path" <@ $1 AND "path" != $1 LIMIT 1', TG_TABLE_SCHEMA, TG_TABLE_NAME) USING OLD.path;             GET DIAGNOSTICS n = ROW_COUNT;             IF n > 0
            THEN
                RAISE EXCEPTION 'Cannot delete path % with descendants.', OLD.path;
            END IF;
        END IF;

        RETURN OLD;
    WHEN 'INSERT', 'UPDATE'
    THEN
        IF NEW.path IS DISTINCT FROM OLD.path
        THEN
            -- Verify that parent of new path exists.
            IF NEW.path IS NOT NULL
            THEN
                nlevel := nlevel(NEW.path);
                IF nlevel = 1
                THEN
                    RAISE NOTICE 'Inserting root path %.', NEW.path;
                ELSE
                    EXECUTE format('SELECT * FROM %I.%I WHERE "path" = subpath($1, 0, nlevel($1) - 1)', TG_TABLE_SCHEMA, TG_TABLE_NAME) USING NEW.path;
                    GET DIAGNOSTICS n = ROW_COUNT;
                    IF n = 0
                    THEN
                        RAISE EXCEPTION 'Cannot set path % with no parent.', NEW.path;
                    END IF;
                END IF;
            END IF;

            IF OLD.path IS NOT NULL
            THEN
                RAISE NOTICE 'Updating children of % to %.', OLD.path, NEW.path;

                nlevel := nlevel(OLD.path);

                -- Only do children, because this trigger will fire on each child to do other descendants.
                FOR child IN EXECUTE format('SELECT * FROM %I.%I WHERE "path" ~ ($1::text || ''.*{1}'')::lquery', TG_TABLE_SCHEMA, TG_TABLE_NAME) USING OLD.path
                LOOP
                    IF NEW.path IS NULL
                    THEN
                        EXECUTE format('UPDATE %I.%I SET "path" = NULL WHERE "id" = $1', TG_TABLE_SCHEMA, TG_TABLE_NAME) USING child.id;
                    ELSE
                        EXECUTE format('UPDATE %I.%I SET "path" = $1 || subpath($2, $3) WHERE "id" = $4', TG_TABLE_SCHEMA, TG_TABLE_NAME) USING NEW.path, child.path, nlevel, child.id;
                    END IF;
                END LOOP;
            END IF;
        END IF;

        RETURN NEW;
    END CASE;
END;
$$ LANGUAGE plpgsql VOLATILE;

CREATE CONSTRAINT TRIGGER "checkPath"
AFTER DELETE OR INSERT OR UPDATE OF "path" ON "Organization"
FOR EACH ROW
EXECUTE PROCEDURE "checkPath"();

Testing

Everything is now in place and we are ready to try out our new Organization entity. The following SQL script includes statements to test all of the properties we specified.

\echo '## Table should initially be empty.'
SELECT * FROM "Organization";

\echo '## The following should fail with chkPathValid error.'
INSERT INTO "Organization" ("id", "path", "name") VALUES ('e6712037-9a7e-437c-841d-3c57204bc7fa', 'e67120379a7e437c841d3c57204bc7fa', 'Foo');

\echo
\echo '## The following should emit an "Inserting root" notice.'
INSERT INTO "Organization" ("id", "path", "name") VALUES (uuid_nil(), replace(uuid_nil()::text, '-', '')::ltree, 'root');

\echo
\echo '## The following should fail with a "no parent" error.'
INSERT INTO "Organization" ("id", "path", "name") VALUES ('6029414c-89d0-4378-9758-c7e9a4ca2149', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149', 'Acme West');

\echo
\echo '## The following inserts should succeed.'
INSERT INTO "Organization" ("id", "path", "name") VALUES ('1305233e-347a-4341-aae2-ed7322b48a7f', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f', 'Acme');
INSERT INTO "Organization" ("id", "path", "name") VALUES ('9e59d251-0895-43bd-ad55-843ec038b7d2', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2', 'Acme East');
INSERT INTO "Organization" ("id", "path", "name") VALUES ('d6bbc68c-205b-4792-8349-a5690e8d1111', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111', 'Acme New York City');
INSERT INTO "Organization" ("id", "path", "name") VALUES ('7644f10f-3184-4f0d-974b-b2fa92c15d64', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64', 'Acme Manhattan');
INSERT INTO "Organization" ("id", "path", "name") VALUES ('6029414c-89d0-4378-9758-c7e9a4ca2149', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149', 'Acme West');
INSERT INTO "Organization" ("id", "path", "name") VALUES ('a37fef63-b6c3-45a2-b795-005c39f4d655', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655', 'Acme Arizona');

SELECT * FROM "Organization";

\echo '## The following delete should fail with a descendants error.'
DELETE FROM "Organization" WHERE "id" = uuid_nil();

\echo
\echo '## Add Acme New York State and then move Acme New York City under it.'
INSERT INTO "Organization" ("id", "path", "name") VALUES ('3818d838-5164-4104-aece-c05a82dfd96e', '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e', 'Acme New York State');

UPDATE "Organization" SET
    "path" = '00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111'
WHERE
    "id" = 'd6bbc68c-205b-4792-8349-a5690e8d1111';

SELECT * FROM "Organization";

\echo '## Renaming the path of Acme should work and change descendent paths.'
UPDATE "Organization" SET
    "id"   = '9208b9dc-8123-420e-ae34-f5c3251f4b30',
    "path" = '00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30'
WHERE
    "id" = '1305233e-347a-4341-aae2-ed7322b48a7f';

SELECT * FROM "Organization";

\echo '## The following deletes should succeed.'
DELETE FROM "Organization" WHERE "id" IN ('7644f10f-3184-4f0d-974b-b2fa92c15d64');
DELETE FROM "Organization" WHERE "id" IN ('d6bbc68c-205b-4792-8349-a5690e8d1111');
DELETE FROM "Organization" WHERE "id" IN ('3818d838-5164-4104-aece-c05a82dfd96e');

SELECT * FROM "Organization";

The output of this script is

## Table should initially be empty.
 id | path | name
----+------+------
(0 rows)

## The following should fail with chkPathValid error.
psql:test-path.pg.sql:10: ERROR:  new row for relation "Organization" violates check constraint "chkPathValid"
DETAIL:  Failing row contains (e6712037-9a7e-437c-841d-3c57204bc7fa, e67120379a7e437c841d3c57204bc7fa, Foo).

## The following should emit an "Inserting root" notice.
psql:test-path.pg.sql:14: NOTICE:  Inserting root path 00000000000000000000000000000000.
INSERT 0 1

## The following should fail with a "no parent" error.
psql:test-path.pg.sql:18: ERROR:  Cannot set path 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149 with no parent.
CONTEXT:  PL/pgSQL function "checkPath"() line 38 at RAISE

## The following inserts should succeed.
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
      id                  |                                                                                 path                                                                                 |        name
--------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------
 00000000-0000-0000-0000-000000000000 | 00000000000000000000000000000000                                                                                                                                     | root
 1305233e-347a-4341-aae2-ed7322b48a7f | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f                                                                                                    | Acme
 9e59d251-0895-43bd-ad55-843ec038b7d2 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2                                                                   | Acme East
 d6bbc68c-205b-4792-8349-a5690e8d1111 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111                                  | Acme New York City
 7644f10f-3184-4f0d-974b-b2fa92c15d64 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64 | Acme Manhattan
 6029414c-89d0-4378-9758-c7e9a4ca2149 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149                                                                   | Acme West
 a37fef63-b6c3-45a2-b795-005c39f4d655 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655                                  | Acme Arizona
(7 rows)

## The following delete should fail with a descendants error.
psql:test-path.pg.sql:32: ERROR:  Cannot delete path 00000000000000000000000000000000 with descendants.
CONTEXT:  PL/pgSQL function "checkPath"() line 17 at RAISE

## Add Acme New York State and then move Acme New York City under it.
INSERT 0 1
psql:test-path.pg.sql:41: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111 to 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.
psql:test-path.pg.sql:41: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64 to 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64.
UPDATE 1
      id                  |                                                                                                 path                                                                                                  |        name
--------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------
 00000000-0000-0000-0000-000000000000 | 00000000000000000000000000000000                                                                                                                                                                      | root
 1305233e-347a-4341-aae2-ed7322b48a7f | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f                                                                                                                                     | Acme
 9e59d251-0895-43bd-ad55-843ec038b7d2 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2                                                                                                    | Acme East
 6029414c-89d0-4378-9758-c7e9a4ca2149 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149                                                                                                    | Acme West
 a37fef63-b6c3-45a2-b795-005c39f4d655 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655                                                                   | Acme Arizona
 3818d838-5164-4104-aece-c05a82dfd96e | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e                                                                   | Acme New York State
 d6bbc68c-205b-4792-8349-a5690e8d1111 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111                                  | Acme New York City
 7644f10f-3184-4f0d-974b-b2fa92c15d64 | 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64 | Acme Manhattan
(8 rows)

## Renaming the path of Acme should work and change descendent paths.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2 to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111 to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64 to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149 to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149.
psql:test-path.pg.sql:50: NOTICE:  Updating children of 00000000000000000000000000000000.1305233e347a4341aae2ed7322b48a7f.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655 to 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655.
UPDATE 1
      id                  |                                                                                                 path                                                                                                  |        name
--------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------
 00000000-0000-0000-0000-000000000000 | 00000000000000000000000000000000                                                                                                                                                                      | root
 9208b9dc-8123-420e-ae34-f5c3251f4b30 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30                                                                                                                                     | Acme
 9e59d251-0895-43bd-ad55-843ec038b7d2 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2                                                                                                    | Acme East
 3818d838-5164-4104-aece-c05a82dfd96e | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e                                                                   | Acme New York State
 d6bbc68c-205b-4792-8349-a5690e8d1111 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111                                  | Acme New York City
 7644f10f-3184-4f0d-974b-b2fa92c15d64 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2.3818d83851644104aecec05a82dfd96e.d6bbc68c205b47928349a5690e8d1111.7644f10f31844f0d974bb2fa92c15d64 | Acme Manhattan
 6029414c-89d0-4378-9758-c7e9a4ca2149 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149                                                                                                    | Acme West
 a37fef63-b6c3-45a2-b795-005c39f4d655 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655                                                                   | Acme Arizona
(8 rows)

## The following deletes should succeed.
DELETE 1
DELETE 1
DELETE 1
      id                  |                                                                path                                                                 |     name
--------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------+--------------
 00000000-0000-0000-0000-000000000000 | 00000000000000000000000000000000                                                                                                    | root
 9208b9dc-8123-420e-ae34-f5c3251f4b30 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30                                                                   | Acme
 9e59d251-0895-43bd-ad55-843ec038b7d2 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.9e59d251089543bdad55843ec038b7d2                                  | Acme East
 6029414c-89d0-4378-9758-c7e9a4ca2149 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149                                  | Acme West
 a37fef63-b6c3-45a2-b795-005c39f4d655 | 00000000000000000000000000000000.9208b9dc8123420eae34f5c3251f4b30.6029414c89d043789758c7e9a4ca2149.a37fef63b6c345a2b795005c39f4d655 | Acme Arizona
(5 rows)

Application Integration

Now that we have a database that provides the functionality for hierarchical queries, we will most likely want to use it from an application. This will require mapping our SQL data type to a data type in the application. ltrees can be fully represented as strings, but there is benefit, especially in strongly typed languages, to having an ltree data type in the application.

For Scala with Anorm, you can find an ltree class here that implements the validity requirements of ltrees as well as Anorm integration to facilitate the mapping from the database to Ltree objects in Scala. This class also provides the operators @>, <@, and || for use on Scala Ltree objects.

scala> import com.cnz.play.anorm.Ltree
import com.cnz.play.anorm.Ltree

scala> val isAncestor = Ltree("com") @> Ltree("com.pinnsg")
isAncestor: Boolean = true

scala> val isDescendant = Ltree("com") <@ Ltree("com.pinnsg") isDescendant: Boolean = false scala> val concatenation = Ltree("com.pinnsg") || Ltree("www")
concatenation: com.cnz.play.anorm.Ltree = com.pinnsg.www

scala> val invalid = Ltree("com.e-xample.www")
java.lang.IllegalArgumentException: requirement failed: Invalid ltree specified: com.e-xample.www
  at scala.Predef$.require(Predef.scala:281)
  at com.cnz.play.anorm.Ltree.(Ltree.scala:31)
  ... 36 elided

With Scala’s functionality for defining DSLs (Domain-Specific Languages), we were able to closely mimic the ltree syntax used in Postgres. Compare the above examples in the Scala shell to the SQL examples at the beginning of this article.