SQL, category tree with multiple parents

I need to make a category tree where some leafs can have multiple parents, for exaple

g
 \--b
 \--a
c
 \--d
 \--a

above category 'a' has two parents(g and c)

My first attempt was to create the following table

create table catalogcategories2 (
  id serial,
  name text not null,
  pid int null,
  primary key(id,pid),
  CONSTRAINT catalogcategories_fk FOREIGN KEY (pid)
  REFERENCES catalogcategories2(id)
);

where both parent id and id are primary keys but I get the following error


there is no unique constraint matching given keys for referenced table "catalogcategories2"

Some reflections, a separation of tree[1] structure and content is most likely the way to go. I.e. remove name from catalogcategories2. Now nodes that don't have a parent does not have to exist in this table. I.e. you can make pid not null.

The current foreign key is invalid since the primary key which it references consists of two columns.

A sketch:

CREATE TABLE CATEGORIES
(  ID ... NOT NULL PRIMARY KEY
,  NAME ... NOT NULL
,   );

CREATE TABLE CATEGORY_DAG -- [1]
(  ID ... NOT NULL
,  PID ... NOT NULL
,    PRIMARY KEY (ID, PID)
,    FOREIGN KEY (ID) REFERENCES CATEGORIES (ID)
,    FOREIGN KEY (PID) REFERENCES CATEGORIES (ID)
);

[1] What you describe is a Direct Acyclic Graph (DAG), not a tree.

StackExchange Database Administrators Q#140313, answer score: 4