6

I'm dealing with a set of relationships where the child can be removed, but I obviously don't want to lose the connection between the grandchild and the parent. I did think about marking the child as "deceased" (to use relevant terminology for this post), but then I would be stuck with a bunch of deceased children in my DB eventually and who wants that (just for the purpose of preserving the relationship)?

ERD of the relationships

If a parent is deleted, all its descendants are deleted. Furthermore, it works like a "normal" relationship, where the grandchild and child always have the same top level parent. The hierarchy is fixed in 3 levels (as shown above). Finally, the Parent, Child, and Grandchild are all of different types (e.g. we're not talking about 3 "humans", they don't have the same base).

However, it feels a bit odd to have the grandchild track the parent since that relationship can usually be derived from the parent-child relationship. Though, I cannot think of another way of doing it.

Is this model valid? Or is there a different way of doing it?

  • 5
    The requirements are not very clear. What should happen if a parent is deleted? Should all his children and grandchildren be deleted too? Can grandchild be related directly to parent A directly and to a different parent (B) through his child relationship? Can a grandchild be related to two or more parents? Or just one? To two or more children or just one? Is the hierarchy fixed in 3 levels (Parent, Child, Grandchild) or you may want to expand it later into more levels? – ypercubeᵀᴹ Mar 16 '18 at 10:58
  • 1
    Also: which DBMS is this for? Multiple cascading paths for example are not allowed in SQL Server while they work in Postgres. So the answers have to take care of the details. – ypercubeᵀᴹ Mar 16 '18 at 11:13
  • Added more details according to your questions, as well as tagged it with the DBMS I am using (PostgreSQL). – fgblomqvist Mar 16 '18 at 17:42
  • 2
    I've updated my answer slightly, however once 48 hours has elapsed from the time you posted your answer, you can "accept" it as the correct answer, which I would encourage you to do. – Max Vernon Mar 16 '18 at 18:07
8

This answer is based upon your question as it stood before the clarification about each level being a different type. Since you have identified the need for different types, I agree with my answer as it originally appeared, and your self-answer documenting how you've approached this problem. Adding a single column to the grandchild table, referencing the top-most table, seems the simplest approach.

I'm leaving the below details in-place in case it helps a future visitor.


I would implement this with a cross reference table.

Below is a SQL Server-specific example; this table contains columns about the entities, including name, etc:

CREATE TABLE dbo.Entities
(
    EntityID int NOT NULL
        CONSTRAINT PK_Entities
        PRIMARY KEY CLUSTERED
        IDENTITY(1,1)
    , EntityName varchar(30) NOT NULL
);

This table describes their relationships:

CREATE TABLE dbo.EntityRelationships
(
      EntityIDParent int NOT NULL
        CONSTRAINT FK_EntityRelationships_Parent
        FOREIGN KEY
        REFERENCES dbo.Entities (EntityID)
    , EntityIDChild int NOT NULL
        CONSTRAINT FK_EntityRelationships_Child
        FOREIGN KEY
        REFERENCES dbo.Entities (EntityID)
    , CONSTRAINT PK_EntityRelationships
        PRIMARY KEY CLUSTERED (EntityIDParent, EntityIDChild)
    , CONSTRAINT CK_EntitytRelationships
        CHECK ((EntityIDParent <> EntityIDChild))
);

Each relationship must be unique, that is any given parent can only be related to any given child once.

Next, we create an INSTEAD OF DELETE trigger on the Entities table that will handle deletes properly, by reparenting any relationships necessary, prior to removing the deleted Entity:

CREATE TRIGGER EntityRelationshipDelete
ON dbo.Entities
INSTEAD OF DELETE
AS
BEGIN
    SET NOCOUNT ON;

    INSERT INTO dbo.EntityRelationships (EntityIDParent, EntityIDChild)
    SELECT erp.EntityIDParent
        , erc.EntityIDChild
    FROM deleted d
        INNER JOIN dbo.EntityRelationships erp ON d.EntityID = erp.EntityIDChild
        INNER JOIN dbo.EntityRelationships erc ON d.EntityID = erc.EntityIDParent
    EXCEPT --don't create duplicate entries
    SELECT er.EntityIDParent, er.EntityIDChild
    FROM dbo.EntityRelationships er;

    DELETE
    FROM dbo.EntityRelationships 
    FROM dbo.EntityRelationships er
        INNER JOIN deleted d ON er.EntityIDChild = d.EntityID OR er.EntityIDParent = d.EntityID;

    DELETE 
    FROM dbo.Entities
    FROM dbo.Entities e
        INNER JOIN deleted d ON e.EntityID = d.EntityID;
END;
GO

Here we'll test that setup:

INSERT INTO dbo.Entities (EntityName)
VALUES ('Grandparent')
    , ('Parent')
    , ('Child');

INSERT INTO dbo.EntityRelationships (EntityIDParent, EntityIDChild)
VALUES (1, 2)
    , (2, 3);

SELECT Parents.EntityName
    , Children.EntityName
FROM dbo.EntityRelationships er
    INNER JOIN dbo.Entities Parents ON er.EntityIDParent = Parents.EntityID
    INNER JOIN dbo.Entities Children ON er.EntityIDChild = Children.EntityID;

The results of the select above:

╔═════════════╦════════════╗
║ EntityName  ║ EntityName ║
╠═════════════╬════════════╣
║ Grandparent ║ Parent     ║
║ Parent      ║ Child      ║
╚═════════════╩════════════╝

Here, we'll delete the "Parent" entity, and re-query the relationships:

DELETE 
FROM dbo.Entities
WHERE dbo.Entities.EntityName = 'Parent';

SELECT Parents.EntityName
    , Children.EntityName
FROM dbo.EntityRelationships er
    INNER JOIN dbo.Entities Parents ON er.EntityIDParent = Parents.EntityID
    INNER JOIN dbo.Entities Children ON er.EntityIDChild = Children.EntityID;

The result:

╔═════════════╦════════════╗
║ EntityName  ║ EntityName ║
╠═════════════╬════════════╣
║ Grandparent ║ Child      ║
╚═════════════╩════════════╝

Note that running DELETE FROM dbo.Entities (with no WHERE clause) will delete all rows from both tables.

To show a slight more complex example; imagine you have 2 grandparents, 2 parents, and single child:

INSERT INTO dbo.Entities (EntityName)
VALUES ('Grandparent 1')
    , ('Grandparent 2')
    , ('Parent 1')
    , ('Parent 2')
    , ('Child');

INSERT INTO dbo.EntityRelationships (EntityIDParent, EntityIDChild)
VALUES (1, 3)
    , (2, 3)
    , (1, 4)
    , (3, 5)
    , (4, 5);

SELECT Parents.EntityName
    , Children.EntityName
FROM dbo.EntityRelationships er
    INNER JOIN dbo.Entities Parents ON er.EntityIDParent = Parents.EntityID
    INNER JOIN dbo.Entities Children ON er.EntityIDChild = Children.EntityID;
╔═══════════════╦════════════╗
║  EntityName   ║ EntityName ║
╠═══════════════╬════════════╣
║ Grandparent 1 ║ Parent 1   ║
║ Grandparent 1 ║ Parent 2   ║
║ Grandparent 2 ║ Parent 1   ║
║ Parent 1      ║ Child      ║
║ Parent 2      ║ Child      ║
╚═══════════════╩════════════╝

If we remove Parent 1 from the Entities table:

DELETE 
FROM dbo.Entities
WHERE dbo.Entities.EntityName = 'Parent 1';

we see this:

╔═══════════════╦════════════╗
║  EntityName   ║ EntityName ║
╠═══════════════╬════════════╣
║ Grandparent 1 ║ Parent 2   ║
║ Grandparent 1 ║ Child      ║
║ Grandparent 2 ║ Child      ║
║ Parent 2      ║ Child      ║
╚═══════════════╩════════════╝

This performs a cleanup of our test data:

IF OBJECT_ID(N'dbo.EntityRelationships', N'U') IS NOT NULL
DROP TABLE dbo.EntityRelationships;

IF OBJECT_ID(N'dbo.Entities', N'U') IS NOT NULL
DROP TABLE dbo.Entities;
GO
  • I think your solution is pretty elegant, kudos for the very detailed example. Although, I'm not sure if it's generic enough for a scenario where Grandparent, Parent, and Child can be of 3 different types (unless you skip foreign keys and go with triggers, or define a base type that they all inherit from, even though it doesn't make any sense in a lot of cases). In my case, I also use an ORM and I can't imagine configuring the ORM to accept this configuration (without having everything be so abstract that it becomes hard to work with). But yeah, still a great solution for many scenarios. – fgblomqvist Mar 16 '18 at 5:26
7

PostgreSQL and ltree

If you're using PostgreSQL, you can check out ltree which does this and keeps things sane and indexable.

CREATE EXTENSION ltree; -- required if you don't have it.

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');

Now you can delete Top.Science.Astronomy, and still easily query all relations that are descendants of Top.Science with @>

DELETE FROM test
WHERE path = 'Top.Science.Astronomy';

SELECT *
FROM test
WHERE 'Top.Science' @> path;
3

I just wanted to share which configuration I actually ended up choosing and why (since it varies from the current solutions):

Simply adding a foreign key to the Grandchild that tracks its Parent.

Example PostgreSQL code:

CREATE TABLE Parent (
  id INT PRIMARY KEY
);

CREATE TABLE Child (
  id INT PRIMARY KEY,
  parent_id INT REFERENCES Parent(id) NOT NULL ON DELETE CASCADE
);

CREATE TABLE Grandchild (
  id INT PRIMARY KEY,
  child_id INT REFERENCES Child(id),
  parent_id INT REFERENCES Parent(id) NOT NULL ON DELETE CASCADE
);

Finally, a trigger could be used to make sure the grandchild has the same Parent as its Child.

I know this probably denormalizes the DB design, but it is seemingly much much simpler to implement than the other answers here and it also works perfectly fine with an ORM right out of the box. If your parent's grandparent can never change, this is imho a perfectly fine compromise (in regards to the denormalization).

I'll happily listen to any suggestions/remarks about this solution.

  • Well, for starters it only works for one level. So in essence, yes, you can delete the parent, but you can't delete the grand parent. It also makes moving nodes harder (because you have to rewrite two links instead of one). – Evan Carroll Mar 16 '18 at 6:53
  • Updated it. And yeah, a trigger would have to be used, which is maybe not ideal. But it would work. – fgblomqvist Mar 16 '18 at 17:56

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.