SQL, category tree with multiple parents
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
,  &lt;additional attributes&gt; );

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.