如何在没有 CTE 的情况下从 sql 查询生成分层结果（谱系）？

Question

我有一个狗的数据库。每只狗都有父亲和母亲 parent。我不是由于 phpmyadmin 和 MariaDB 10.0 的问题，能够为此使用 CTE。

Table 是 animal

我正在使用的列是： id、akc_reg_num、akc_parent_sire、akc_parent_dam

我曾尝试像加载子类别那样只获取一代，但当有两个 parent 时，这只是一侧。

我已经尝试过这个解决方案，但无法理解每个兄弟姐妹的两个 parent。 How do I select only one generation of a hierarchical tree using an table parent child relation with SQL?

示例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', '', '');

代码：

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'));

我需要遍历每一代，这样我就可以 return 一个 json 数组，然后使用 javascript 将结果绑定到 DOM 元素。我只需要查询 4 代，但我担心的是 cpu 周期的开销。一旦数据库中有几十万只动物，同样的查询效率会有多高？

Answer 1

为了防止重复调用滥用您的数据库，SELECT 整个 table 只需一次，让 php 对结果集执行所有递归工作。

AMENDMENT：由于收集 ~100,000 行的工作量太大，这里有替代建议......而不是在递归中对数据库进行多达 31 次单独访问过程中，我建议您基于最多 5 次访问数据库来构建过滤数组。

以下代码段未经过测试：

$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

来自这样的 $animals 结果集：

$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]
];

逐项任务：

在数组中搜索目标 akc_reg_num 的行，然后从 "haystack" 中删除该行以防止无限递归的可能性，然后打破搜索循环以获得最佳效率
如果大海捞针中没有匹配的akc_reg_num，return一个空数组
如果有匹配的akc_reg_num，则大海捞针循环并递归所有找到的parents。我过滤掉 "deadends" 以保持结果数组小而干净。
如果在给定的世代中都找到 parents，则中断循环以防止不必要的迭代。
递归应继续进行，直到生成计数超过 4 或不再有 parents 可收集为止。

代码：(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));

输出：

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,
            ),
        ),
    ),
)

如何在没有 CTE 的情况下从 sql 查询生成分层结果（谱系）？

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

php

recursion

pdo

hierarchy

mariadb