List:General Discussion« Previous MessageNext Message »
From:Andrew Garner Date:February 3 2009 10:58pm
Subject:Re: Algorithm for resolving foreign key dependencies?
View as plain text  
Sounds like you want to walk tables in order of their fk dependencies
- a topological ordering.  You might want to take a look at SQLAlchemy
which has some methods to do just this in sqlalchemy.sql.util:

def sort_tables(tables, reverse=False):
    """sort a collection of Table objects in order of their
foreign-key dependency."""


On Tue, Feb 3, 2009 at 3:40 PM, Philip Pemberton <usenet08@stripped> wrote:
> 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`)
> 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`)
> And my database contains:
> Manufacturers:
>  idManufacturer    name
>  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.
> usenet08@stripped
> If mail bounces, replace "08" with the last two digits of the current year.
> --
> MySQL General Mailing List
> For list archives:
> To unsubscribe:
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