1

I have a companies table:

CREATE TABLE companies (
 id bigserial,
 name varchar(255) NOT NULL
 PRIMARY KEY (id)
)

I want companies to have parents and childs. A company might have many parent and many child companies, so I created the following table:

CREATE TABLE parent_companies (
 id bigserial,
 parent_company_id bigint,
   CONSTRAINT parent_companies_parent_company_id_fkey
   FOREIGN KEY (parent_company_id)
   REFERENCES companies(id),
 child_company_id bigint,
   CONSTRAINT parent_companies_child_company_id_fkey
   FOREIGN KEY (child_company_id)
   REFERENCES companies(id)
 PRIMARY KEY (id)
)

I want parent and child to be unique, so I added the following constraint:

CREATE UNIQUE INDEX parent_companies_parent_company_id_child_company_id_index ON parent_companies (parent_company_id, child_company_id)

This will not allow the same parent and child to be created twice in the database. However, I would like to also prevent a child company being saved as a parent of its parent company. For example, I would to prevent this from happening:

-[ RECORD 1 ]-----+--------------------
id                | 1
parent_company_id | 1
child_company_id  | 2
-[ RECORD 2 ]-----+--------------------
id                | 2
parent_company_id | 2
child_company_id  | 1

Since in record 1 it's defined that company 1 is the parent of company 2, I want a way of preventing company 2 being recorded as parent of company 1.

I thought it could be the case of using the EXCLUDE or the CHECK constraints, but I couldn't figure out a way of making either work.

2
  • 2
    Do you want to allow cyclic paths with length > 2? Eg. (1, 2), (2,3), (3,1) ? Jun 14, 2021 at 6:48
  • @ypercubeᵀᴹ Oh, I hadn't thought of that case, but yeah I think it makes sense to not allow it if we're are not allowing the cyclic path with length 1.
    – bruno
    Jun 15, 2021 at 3:25

3 Answers 3

0

What you describe is a many-to-many relationship between a table and itself (with additional restrictions). See:

Could be implemented like this:

CREATE TABLE company (
  id   integer GENERATED ALWAYS AS IDENTITY PRIMARY KEY
, name text NOT NULL
)

CREATE TABLE hierarchy (
  parent_id integer NOT NULL REFERENCES company
, child_id  integer NOT NULL REFERENCES company
, PRIMARY KEY (parent_id, child_id)
, CONSTRAINT no_1step_loop CHECK (child_id <> parent_id)
);

CREATE UNIQUE INDEX hierarchy_no_2step_loop ON hierarchy (LEAST(child_id, parent_id), GREATEST(child_id, parent_id);

The unique index hierarchy_no_2step_loop rules out loops over two steps like you addressed in your question. Related:

The CHECK constraint no_1step_loop rules out loops over one step (rows referencing themselves directly).

But ruling out loops over more steps is not as simple. You could have a trigger follow the chain of links to the root and raise an exception if a loop is detected. That's more expensive and inherently unsafe against concurrent write operations, though. To make it bullet-proof, you'd have to operate with elevated transaction isolation (like SERIALIZABLE) or write locks on all rows in the chain. But that is very susceptible to deadlocks under heavy write load ...

0

So you want some kind of "anti-foreign key"?

CREATE FUNCTION chk_parent_companies(bigint) RETURNS boolean LANGUAGE SQL
AS $$
SELECT NOT EXISTS(SELECT 1 FROM parent_companies WHERE id = $1);
$$;

ALTER TABLE companies ADD CONSTRAINT chk_parent_companies CHECK(chk_parent_companies(id));

Is that what you're trying to achieve?

2
  • Thanks for the answer. It seems this is checking the id of the parent_companies table? Not sure how that would be helpful. If company B is a child company A, we shouldn't allow the creation of a record that represents company B being the parent of company A. In other words, if there is a record in the parent_companies table with parent_company_id: 1 and child_company_id: 2, I would like to prevent a record with parent_company_id: 2 and child_company_id: 1 from being created. Not sure how feasible that is. The cycle could be larger as ypercubeᵀᴹ mentioned.
    – bruno
    Jun 15, 2021 at 3:32
  • Yes. Such constraint will prevent creation of company with the same id as already exists in parent_companies. So no company could be both "child" and "parent". If you need something more complex than I suppose you need to go for single and self-referencing column and more complex constraint function. Presumably something with recursive query. Need to think about it. I suggest you prepare a DB fiddle wtih samples of data
    – Alex Yu
    Jun 15, 2021 at 6:30
0

Could you not do this with a single table and a self-referencing column?

CREATE TABLE companies (
   id         bigserial,
   name       varchar(255) NOT NULL,
   parent_id  bigint           NULL REFERENCES companies (id)

   PRIMARY KEY (id)
);

Then you can write some data:

INSERT INTO companies (name, parent_id)
VALUES ('Big Parent Company', NULL),
       ('Smaller Company', 1),
       ('Tokyo Subsidiary', 1),
       ('Zurich Subsidiary', 1),
       ('Zurich Manufacturer', 4),
       ('Zurich Distributor', 4),
       ('Another Big Company', NULL),
       ('Spanish Subsidiary', 7);

And you'll see that a subsidiary record can only have one parent record:

id  name                parent_id
--  --------------—---  --------- 
1   Big Parent Company       NULL
2   Smaller Company             1
3   Tokyo Subsidiary            1
4   Zurich Subsidiary           1
5   Zurich Manufacturer         4
6   Zurich Distributor          4
7   Another Big Company      NULL
8   Spanish Subsidiary          7

If every company needs to have a unique name (so that you don't have two subsidiaries with the same name), then another constraint can be added ... though this might create some unfortunate consequences elsewhere.


Note: Updated after a bit of clarification in the comments.

If a company can somehow have multiple parent organisations, then perhaps a second table could be used like this:

CREATE TABLE company_parent (
   company_id bigint       NOT NULL REFERENCES companies (id),
   parent_id  bigint       NOT NULL REFERENCES companies (id),

   ... { additional attributes } ...

   PRIMARY KEY (company_id, parent_id)
);

This would ensure uniqueness for any company_id+parent_id combination, but will not (by itself) ensure correctness of the data.

Of course, any company that does not have any record in the company_parent table could be considered the top-level organisation.

2
  • Thanks for your answer! Definitely appreciate alternative modeling suggestions like this. At some point I thought of doing it the way you described, and it seems like a good and somewhat standard way of approaching this problem (I've seen it somewhere before). Ideally, though, as I mentioned in the description, a company can have more than one parent, and it seems this way of modeling wouldn't allow that. Does that make sense?
    – bruno
    Jun 15, 2021 at 3:24
  • needs create unique index nodupes on companies( greatest(id,parent_id), least(id,parent_id)); to prevent update companies set parent_id = 2 where id=1;
    – Jasen
    Jun 16, 2021 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.