List:General Discussion« Previous MessageNext Message »
From:Philip Pemberton Date:February 3 2009 9:40pm
Subject: Algorithm for resolving foreign key dependencies?
View as plain text  
   First of all, I apologise in advance for any mind-altering, or 
headache-inducing effects this question may have. I've spent the past two days 
trying to figure it out, and all I've got to show for it is a mostly-working 
recursive depth-first-search routine and an empty packet of painkillers.

MySQL version: 5.0.67-0ubuntu6

I'm trying to write a code generator (in Python) that reads in a MySQL 
database, enumerates all the tables, then produces INSERT, DELETE and UPDATE 
code in PHP. The INSERT and UPDATE code generation was fairly easy, and works 
quite well. What I'm having trouble with is the DELETE code generator -- more 
specifically, resolving foreign key references.

Basically, what I have is a tree built in memory, so I can go:
And get a complete list of all the tables (and the fields within that table) 
that reference 'fieldname' in 'thetable'.

What I want is an answer to the question: "If all my foreign keys were set to 
'ON DELETE CASCADE', what would I need to do to delete row 'X' in table 'Y' 
without violating any foreign key constraints?"

Here's an example. Let's say I've got these tables:

CREATE TABLE `Manufacturers` (
   `idManufacturer` int(11) NOT NULL auto_increment,
   `name` varchar(255) NOT NULL,
   PRIMARY KEY  (`idManufacturer`)

   `idPart` int(11) NOT NULL auto_increment,
   `idManufacturer` int(11) NOT NULL,
   `partnumber` int(11) NOT NULL,
   PRIMARY KEY  (`idPart`),
   KEY `Parts_idManufacturer_FKIndex` (`idManufacturer`),
   CONSTRAINT `Parts_ibfk_1` FOREIGN KEY (`idManufacturer`) REFERENCES 
`Manufacturers` (`idManufacturer`)

And my database contains:
   idManufacturer    name
   123               Any Company Inc.

   idPart  idManufacturer  partnumber
   1       123             12345

Now, let's say I want to do this:
   DELETE FROM Manufacturers WHERE idManufacturer=123

Because I have a part that references Manufacturer #123, I have to do this 
   DELETE FROM Parts WHERE idManufacturer=123
   DELETE FROM Manufacturer WHERE idManufacturer=123

What I want is something I can feed the table definitions to, and the name of 
the table I want to delete a row from (in this case 'Manufacturers'), and 
generate a list of the DELETE commands that would allow me to delete that row 
while enforcing FK dependencies.

I figure this is going to have to work something like mathematical expression 
evaluation -- build up a list of dependencies, then deal with the deepest 
dependency first. Catch being I can't see an obvious way to deal with 
generating the necessary DELETE commands without having to write a massive "if 
recursion_level = 0 then generate_a_straight_delete else if recursion_level = 
1 then..." statement...

If mail bounces, replace "08" with the last two digits of the current year.

Algorithm for resolving foreign key dependencies?Philip Pemberton3 Feb
  • Re: Algorithm for resolving foreign key dependencies?Andy Shellam3 Feb
    • Re: Algorithm for resolving foreign key dependencies?Philip Pemberton3 Feb
      • Re: Algorithm for resolving foreign key dependencies?ddevaudreuil4 Feb
        • Re: Algorithm for resolving foreign key dependencies?Peter Brawley4 Feb
  • Re: Algorithm for resolving foreign key dependencies?Andrew Garner3 Feb