Remove Orphaned Items In A Hierarchy

Question

I have a list of items in MySQL, connected through a column "parent_id".

Let's assume the columns are: id, name, parent_id

If one of my users deletes an item high in the hierarchy, I need to delete all of its children. So, two part question:

1) Is there an effective and efficient MySQL call that will return ID's for all items where its parent no longer exists?

2) In PHP, I'm thinking I can get these orphaned ID's from MySQL into an array, then run a foreach loop and delete each?

Much thanks for your help.

Answer 1

If you are using InnoDB, you should look into Foreign Key Constraints which take care of this for you by using the ON DELETE CASCADE option when you are setting your foreign key relationships.

An example from the docs:

CREATE TABLE parent (id INT NOT NULL,
                     PRIMARY KEY (id)) ENGINE=INNODB;

CREATE TABLE child (id INT, parent_id INT,
                    INDEX par_ind (parent_id),
                    FOREIGN KEY (parent_id) REFERENCES parent(id)
                    ON DELETE CASCADE) ENGINE=INNODB;

With that in place, if you were to do add a parent and a matching child row like this:

INSERT INTO parent (id) VALUES (1);
INSERT INTO child (id, parent_id) VALUES (1,1);

And then removed the parent like this:

DELETE FROM parent WHERE id = 1;

You will find the matching child record to be gone. This is, in my opinion, the best way to do it.

EDIT: To do this within 1 table, you would do something like this:

CREATE TABLE parent (
    id INT NOT NULL,
    name varchar(250) not null,
    parent_id INT NULL,
    FOREIGN KEY (parent_id) REFERENCES parent(id) ON DELETE CASCADE,
    PRIMARY KEY (id)
) ENGINE=INNODB

Then if you add two rows, one referencing the other:

INSERT INTO parent (id,name,parent_id)
VALUES ('1', 'Test 1', NULL), ('2', 'Test 2', '1')

Then delete the parent row of the two:

DELETE FROM parent WHERE id = 1;

You will find that it deletes the child row with parent_id of 1.

Answer 2

RIGHT JOINS are usually used to find orphans in other databases. But this is possible also with a LEFT JOIN.

Here is a very nicely layed out article about getting orphan rows in MySQL

Answer 3

Another option (if you are not using InnoDB, +1 Paolo) is to use Delete Triggers on the parent MySQL table.

Remember, when using a delete trigger, the deleting row is referenced by OLD. Here is an example trigger.

DELIMITER //

CREATE TRIGGER delete_clean BEFORE DELETE ON Parent
FOR EACH ROW
BEGIN
  DELETE * FROM Parent WHERE Parent.parent_id = OLD.id;
END //

DELIMITER ;

Answer 4

If your data is linearly hierarchical (only one parent relation per node), and high-read, low-write, you might consider migrating it to a Modified Preorder Tree Traversal structure. It sounds scary, but it's actually very neat. There's a great article on it here: http://www.sitepoint.com/article/hierarchical-data-database/1/

Not only is retrieving data from such a structure extremely efficient (single SELECT and you get all the children), you'll be able to delete a whole branch of the tree in a single DELETE statement as well.