php - 如何在没有 CTE 的情况下从 sql 查询生成分层结果(谱系)？

Question

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

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

table 是动物

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

我尝试只获取一代，就像加载子类别一样，但这只是当有两个 parent 时的一方面。

我已经尝试过这个解决方案，但无法让我的头脑集中在每个 sibling 的两个 parent 身上。 How do I select only one generation of a hierarchical tree using an table parent child relation with SQL?

示例表

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

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

Answer 1

为了防止通过迭代调用滥用数据库，请仅选择整个表一次，然后让 php 对结果集执行所有递归工作。

修正:由于收集约 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，则返回空数组
• 如果存在匹配的 akc_reg_num，则循环 haystack 并递归所有找到的父级。我正在过滤掉“死端”，以保持结果数组小而干净。
• 如果在给定的一代中找到了两个父代，则中断循环以防止不必要的迭代。
• 递归应继续，直到代数超过 4 或没有更多的父级可供收集。

代码:(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,
            ),
        ),
    ),
)