note: this question has been updated to reflect that we are currently using MySQL, having done so, I would like to see a how much easier it would be if we switched to a CTE-supporting database.
I have a self-referencing table with a primary key, id
and a foreign key parent_id
.
+------------+--------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+------------+--------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| parent_id | int(11) | YES | | NULL | |
| name | varchar(255) | YES | | NULL | |
| notes | text | YES | | NULL | |
+------------+--------------+------+-----+---------+----------------+
Given a name
, how can I query the top-level parent?
Given a name
, how can I query all of the id
's associated with a record of name = 'foo'
?
context: I am not a dba, but am planning to ask a dba to implement this type of hierarchical structure and would like to test some queries. The motivation for doing so is described by Kattge et al 2011.
Here is an example of the relationships among ids in the table:
-- -----------------------------------------------------
-- Create a new database called 'testdb'
-- -----------------------------------------------------
SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0;
SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0;
SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='TRADITIONAL';
CREATE SCHEMA IF NOT EXISTS `testdb` DEFAULT CHARACTER SET latin1 COLLATE latin1_swedish_ci ;
USE `testdb` ;
-- -----------------------------------------------------
-- Table `testdb`.`observations`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `testdb`.`observations` (
`id` INT NOT NULL ,
`parent_id` INT NULL ,
`name` VARCHAR(45) NULL ,
PRIMARY KEY (`id`) )
ENGINE = InnoDB;
SET SQL_MODE=@OLD_SQL_MODE;
SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS;
SET UNIQUE_CHECKS=@OLD_UNIQUE_CHECKS;
-- -----------------------------------------------------
-- Add Example Data Set
-- -----------------------------------------------------
INSERT INTO observations VALUES (1,3), (2,5), (3,NULL), (4,10),
(5,NULL), (6,1), (7,5), (8,10), (9,10), (10,3);
Best Answer
You definitely have to script this via MySQL Stored Procedure Language
Here is a Stored Function called
GetParentIDByID
to Retrieve a ParentID given an ID to Search ForHere is a Stored Function called
GetAncestry
to Retrieve a List of ParentIDs starting from the First Generation all the up the hierarchy given an ID to start with:Here is something to generate sample data:
Here is what it generates:
Here are what the functions generate for each value:
MORAL OF THE STORY : Recursive data retrieval must be scripted in MySQL
UPDATE 2011-10-24 17:17 EDT
Here is the reverse of GetAncestry. I call it GetFamilyTree.
Here is the algorithm:
I believe from my Data Structures and Algorithms classes in College, this is called something like preorder/prefix tree traversal.
Here is the code:
Here is what each row produces
This algorithm works cleanly provided there are no cyclic paths. If there exists any cyclic paths, you would have to add a 'visited' column to the table.
Once you add visited column, here is the algorithm blocking cyclic relationships:
UPDATE 2011-10-24 17:37 EDT
I created a new table called observations and populated your sample data. I changed the stored procedures to use observations instead of pctable. Here is your output:
UPDATE 2011-10-24 18:22 EDT
I changed the code for GetAncestry. There was
WHILE ch > 1
it should beWHILE ch > 0
Try it now !!!