How to generate hierarchical result (pedigree) from sql query without CTE?

Question

I have a database of dogs. Each dog has a sire and dam parent. I am not able to use CTE for this due to an issue with phpmyadmin and MariaDB 10.0.

I updated to MariaDB 10.2.20 to use CTE. Still getting "Unrecognized Statement type. (near WITH) in phpMyAdmin

Table is animal

Columns I am working with are: id, akc_reg_num, akc_parent_sire, akc_parent_dam

I have tried to get just one generation as I would for loading subcategories, but this is only one side when there are two parents.

I have attempted this solution, but can't get my head wrapped around the two parents of each sibling. How do I select only one generation of a hierarchical tree using an table parent child relation with SQL?

Example Table

CREATE TABLE  `animal` ( 
    `id` INT(11) NOT NULL AUTO_INCREMENT ,
     `akc_reg_num` VARCHAR(20) NOT NULL ,
     `akc_parent_sire` VARCHAR(20) NOT NULL ,
     `akc_parent_dam` VARCHAR(20) NOT NULL ,
     PRIMARY KEY (`id`)
) ENGINE = MyISAM;

INSERT INTO `animal` (`id`, `akc_reg_num`, `akc_parent_sire`, `akc_parent_dam`) VALUES
(NULL, '1', '2', '3'), 
(NULL, '2', '5', '6'), 
(NULL, '3', '9', ''), 
(NULL, '5', '', ''), 
(NULL, '6', '7', '8'), 
(NULL, '7', '', ''), 
(NULL, '8', '', ''), 
(NULL, '9', '10', '11'), 
(NULL, '10', '', ''), 
(NULL, '11', '12', ''), 
(NULL, '12', '', '');

Code:

include_once("db_conx.php");   

function getPedigree($node) { 
    // look up the parent of this node  
    $sql =  'SELECT akc_parent_sire, akc_parent_dam FROM animals WHERE akc_reg_num="'.$node.'";';
    $query = $db->prepare($sql);          
    $query->execute();
    $path = array();    
    while($row=$query->fetch(PDO::FETCH_ASSOC)){    
        if ($row['akc_parent_sire']!='') { 
            $path[] = $row['akc_parent_sire']; 
            echo $row['akc_parent_sire'];
            $path = array_merge(getPedigree($row['akc_parent_sire']), $path); 
        } 
        if ($row['akc_parent_dam']!='') { 
            $path[] = $row['akc_parent_dam']; 
            echo $row['akc_parent_dam'];
            $path = array_merge(getPedigree($row['akc_parent_dam']), $path); 
        } 
    }       
    return $path; 
} 
print_r(getPedigree('vvv'));

I need to loop through each generation so I can return a json array and then use javascript to tie the results to DOM elements. I only need to query for 4 generations however my concern is the expense of cpu cycles. Once I have a few hundred thousand animals in the database how efficient will this same query be?

Answer 1

To prevent abusing your database with iterated calls, SELECT the whole table just once and let php do all of the recursive work on the result set.

AMENDMENT: Since collecting the ~100,000 rows is too much heavy lifting, here is alternative advice... Rather than making up to 31 individual trips to the database within a recursive process, I'll recommend that you build a filtered array based on up to 5 trips to the database.

The following snippet is NOT tested:

$generation = 1;
$needles = [1];
$animals = [];
while ($needles && $generation < 6) {
    $sth = $db->prepare("SELECT * FROM animals WHERE akc_reg_num IN (" . implode(',', array_fill(0, count($needles), '?')) . ")");
    $sth->execute($needles);
    if ($results = $sth->fetchAll(\PDO::FETCH_ASSOC)) {
        $needles = array_filter(array_merge(array_column($results, 'akc_parent_sire'), array_column($results, 'akc_parent_dam')));
        $animals[] = array_merge($animal, $results);
    } else {
        $needles = null;
    }
    ++$generation;
}
// $animals is ready to pass to the php recursion

From an $animals result set like this:

$animals = [
    ['id' => 1, 'akc_reg_num' => 1, 'akc_parent_sire' => 2, 'akc_parent_dam' => 3],
    ['id' => 2, 'akc_reg_num' => 2, 'akc_parent_sire' => 5, 'akc_parent_dam' => 6],
    ['id' => 3, 'akc_reg_num' => 3, 'akc_parent_sire' => 9, 'akc_parent_dam' => 0],
    ['id' => 4, 'akc_reg_num' => 5, 'akc_parent_sire' => 0, 'akc_parent_dam' => 0],
    ['id' => 5, 'akc_reg_num' => 6, 'akc_parent_sire' => 7, 'akc_parent_dam' => 8],
    ['id' => 6, 'akc_reg_num' => 7, 'akc_parent_sire' => 0, 'akc_parent_dam' => 0],
    ['id' => 7, 'akc_reg_num' => 8, 'akc_parent_sire' => 0, 'akc_parent_dam' => 0],
    ['id' => 8, 'akc_reg_num' => 9, 'akc_parent_sire' => 10, 'akc_parent_dam' => 11],
    ['id' => 9, 'akc_reg_num' => 10, 'akc_parent_sire' => 0, 'akc_parent_dam' => 0],
    ['id' => 10, 'akc_reg_num' => 11, 'akc_parent_sire' => 12, 'akc_parent_dam' => 0],
    ['id' => 11, 'akc_reg_num' => 12, 'akc_parent_sire' => 0, 'akc_parent_dam' => 0]
];

Itemized tasks:

• Search your array for the row of the targeted akc_reg_num, then remove that row from the "haystack" to prevent the possibility of infinite recursion, then break the search loop for best efficiency
• If there is no matching akc_reg_num in the haystack, return an empty array
• If there is a matching akc_reg_num, loop the haystack and recurse all found parents. I am filtering out "deadends" to keep the result array small and clean.
• If both parents are found in a given generation, break the loop to prevent needless iterations.
• The recursion should continue until the generation count exceeds 4 or there are no more parents to collect.

Code: (Demo)

function buildPedigree($haystack, $akc_reg_num, $generation = 0) {
    ++$generation;
    foreach ($haystack as $index => $row) {
        if ($row['akc_reg_num'] == $akc_reg_num) {
            $result = ['sire' => $row['akc_parent_sire'], 'dam' => $row['akc_parent_dam']];
            unset($haystack[$index]);             // reduce the haystack to improve efficiency and avoid infinite loop
            break;                                // stop searching
        }
    }
    if (!isset($result)) {
        return [];  // $akc_reg_num not found
    }

    foreach ($haystack as $row) {
        if ($row['akc_reg_num'] == $result['sire']) {
            $result['sire_parents'] = array_filter(buildPedigree($haystack, $row['akc_reg_num'], $generation));  // recurse and purge empty parent arrays
            if (array_key_exists('dam_parents', $result)) {
                break;  // both parents found in generation, stop this loop
            }
        } elseif ($row['akc_reg_num'] == $result['dam']) {
            $result['dam_parents'] = array_filter(buildPedigree($haystack, $row['akc_reg_num'], $generation));  // recurse and purge empty parent arrays
            if (array_key_exists('sire_parents', $result)) {
                break;  // both parents found in generation, stop this loop
            }
        }
    }
    return $generation <= 4 ? $result : [];
} 

var_export(buildPedigree($animals, 1));

Output:

array (
    'sire' => 2,
    'dam' => 3,
    'sire_parents' => array (
        'sire' => 5,
        'dam' => 6,
        'dam_parents' => array (
            'sire' => 7,
            'dam' => 8,
        ),
    ),
    'dam_parents' => array (
        'sire' => 9,
        'sire_parents' => array (
            'sire' => 10,
            'dam' => 11,
            'dam_parents' => array (
                'sire' => 12,
            ),
        ),
    ),
)