Algorithm for resolving foreign key dependencies?

[Philip Pemberton]

Hi,
  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:
  tableinfo['thetable']['fieldname']['refs']
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`)
) ENGINE=InnoDB

CREATE TABLE `Parts` (
  `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`)

) ENGINE=InnoDB

And my database contains:
Manufacturers:
  idManufacturername
  123   Any Company Inc.

Parts:
  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 
instead:

  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...


Thanks,
--
Phil.
usene...@philpem.me.uk
http://www.philpem.me.uk/
If mail bounces, replace 08 with the last two digits of the current year.


--
MySQL General Mailing List
For list archives: http://lists.mysql.com/mysql
To unsubscribe:http://lists.mysql.com/mysql?unsub=arch...@jab.org

Re: Algorithm for resolving foreign key dependencies?

[Philip Pemberton]

Andy Shellam wrote:

Am I missing something here?  (It is late after a long day, I admit!)


Only something I forgot to mention.

All the foreign keys are set up as ON DELETE RESTRICT, meaning MySQL's 
response to a foreign key violation is to spit out an error message to the 
effect of I'm sorry, Dave, I can't let you do that.


The problem is, the target platform doesn't use foreign keys for performance 
reasons. I want to use foreign keys in development as a bug-trapping method -- 
I'd rather see an FK violation error in development than get an angry email 
from a customer asking why there's a part listed that doesn't seem to have a 
manufacturer.


The plan was to write a code-generator that would generate all the database 
code for me, then I could deal with the page templates and display logic 
myself (thus eliminating ~80% of the boring, repetitive work). I want the 
generated code to handle foreign keys itself, rather than relying on the database.


As I said above, if foreign key constraints didn't slow things down markedly, 
I'd use them in production. Based on the (admittedly limited) testing I've 
done, application-side FK enforcement is considerably faster than using ON 
DELETE CASCADE and letting MySQL deal with the foreign keys.


I don't like writing database code by hand (it all follows a standard 
template), so I figured I'd write a program to do it for me. Work smarter not 
harder and all that :)


Thanks,
--
Phil.
usene...@philpem.me.uk
http://www.philpem.me.uk/
If mail bounces, replace 08 with the last two digits of the current year.


--
MySQL General Mailing List
For list archives: http://lists.mysql.com/mysql
To unsubscribe:http://lists.mysql.com/mysql?unsub=arch...@jab.org