getting all offsprings (with x generations) from a given id

Tanja · February 5, 2017

i want to find all offsprings for a given id.
Information in database is stored with id, father_id, mother_id.
$parentID will come over a session variable, for gender too.
I call database with

function findDescendants($parentId, &$descendants)
{include(INCLUDE_DIR.'xxx'); //database connect
    $res = "
	SELECT CONCAT(dog.id, '#', dog.dogname, '#',dog.father_id, '#',dog.mother_id ) AS id FROM dog 
	WHERE mother_id= :parentId
	OR father_id = :parentId
	ORDER BY dog.id DESC
	";
	
				$stmt = $conn->prepare($res);
				$stmt->bindParam(':parentId', $parentId, PDO::PARAM_INT);
				$stmt->execute();	
	
	while($row = $stmt->fetch(PDO::FETCH_ASSOC))
	 {
        $descendants[] = $row['id'];
	
		
        findDescendants($row['id'], $descendants);
    }
}

now i explode this array to get foreach

[id] => 14333
[name] => Chunami from Bandit's World
[father] => 3305
[mother] => 13425
[parents] => 3305,13425

In this way i get all descedants - but without generations.
This is what i want to get:

-Child A

-Child B

-Child C

--GrandChild C1

---GrandgrandChild C1 a
Child D

Maybe the first query isn´t correct for this ....
Actual i think to do it with arrays ...
Find first generation: filter all which have start id as mother / father, add this id as parent and generation

$firstgeneration = array_filter($newdescedants,function ($ar){
                    return ($ar['mother'] == 13425);
                });


foreach ($firstgeneration as &$val) $val['parent'] = '13425';
foreach ($firstgeneration as &$val) $val['generation'] = '1';

Now i have an array with all childrens like this

[id] => 14333
[name] => Chunami from Bandit's World
[father] => 3305
[mother] => 13425
[parents] => 3305,13425
[parent] => 13425
[generation] => 1

For next generation my head bangs ....

Jacques1 · February 5, 2017

Traversing an entire family tree requires a recursive query, and MySQL doesn't have that.

There are workarounds, though:

If you can define a maximum number of generations (e. g. 3), you can join the tables with itself that many times: dog AS children LEFT JOIN dog AS grandchildren ... LEFT JOIN dog AS grandgrandchildren ....
You can run the query multiple times. This will be inefficient, but it may be acceptable for small amounts of data.
There are hacks with stored procedures (not recommended).

So is there a fixed limit?

Edited February 5, 2017 by Jacques1

Tanja · February 5, 2017

Maybe it could be a compromise to limit generation and have full information....

Yes MySQL is here the looser - so i tried with arrays ....

Barand · February 5, 2017

Use one query to put the dogs into an array, each dog having an array of pups.

Then use a recursive function on the array. More efficient than recursive queries

$sql = "SELECT 
            id
          , dogname
          , mother_id as dam
          , father_id as sire
          , gender
        FROM dog
        ORDER BY id";
$dogs = [];
$dogs[0] = ['name' => 'N/A', 'gender' => 'N/A', 'pups' => [] ];
$res = $db->query($sql);
$results = $res->fetchAll();
//
// get the dogs
//
foreach ($results as $d) {
    if (!isset($dogs[$d['id']])) {
        $dogs[$d['id']] = [ 'name' => $d['dogname'], 'gender' => $d['gender'], 'pups' => [] ];
    }
}

//
// assign their pups
//
foreach ($results as $d) {
    $dogs[$d['dam']]['pups'][] = $d['id'];
    $dogs[$d['sire']]['pups'][] = $d['id'];
}



function descendants($id, &$dogs, $level=0)
{
    if (!isset($dogs[$id])) return;
    $indent = str_repeat(' ----- ', $level); 
    echo "$indent{$dogs[$id]['name']} ({$dogs[$id]['gender']})<br>";
    if (!empty($dogs[$id]['pups'])) {
        foreach ($dogs[$id]['pups'] as $pupid) {
            descendants($pupid, $dogs, $level+1);
        }
    }
}

//
// CALL THE RECURSIVE FUNCTION
//
        $dog_id = 8032;
        descendants($dog_id, $dogs, 0);

Jacques1 · February 5, 2017

For the record: This loads the entire table into the application and builds the entire tree of every single dog that has ever been registered.

Barand · February 5, 2017

For the record

My method

Get and store all dogs data  : 0.467 seconds
Output                       : 0.001 seconds

Jaques' method

mysql> SELECT
    ->     d1.id
    ->   , d1.dogname as name1
    ->   , d1.gender
    ->   , d2.dogname as name3
    ->   , d3.dogname as name3
    ->   , d4.dogname as name4
    ->   , d5.dogname as name5
    -> FROM dog d1
    -> LEFT JOIN dog d2 ON d1.id IN (d2.mother_id, d2.father_id)
    -> LEFT JOIN dog d3 ON d2.id IN (d3.mother_id, d3.father_id)
    -> LEFT JOIN dog d4 ON d3.id IN (d4.mother_id, d4.father_id)
    -> LEFT JOIN dog d5 ON d4.id IN (d5.mother_id, d5.father_id)
    -> WHERE d1.id = 8032;

411 rows in set (1 min 46.40 sec)

Tanja · February 5, 2017

I edit the query to "my" pdo with special dog

$parent= 13425;
$sql = "SELECT 
            id
          , dogname
          , mother_id as dam
          , father_id as sire
          , gender
        FROM dog
		WHERE mother_id= :parent
		OR father_id = :parent
        ORDER BY id";
$dogs = [];
$dogs[0] = ['name' => 'N/A', 'gender' => 'N/A', 'pups' => [] ];

$stmt = $conn->prepare($sql);
$stmt->bindParam(':parent', $parent, PDO::PARAM_INT);
$stmt->execute();

$results = $stmt->fetchAll();

Rest from Barands code i copied - it give me on calling

$dog_id = 13425;
descendants($dog_id, $dogs, 3);

only the direct childrens, but also in array the children for the used males (in this case 13425 is a female and was mated with two different males) - this is not really neccessary here....

If i change the level it will only change from descendants($dog_id, $dogs, 3);

----- ----- ----- ----- Chunami from Bandit's World (female)

to descendants($dog_id, $dogs, 1);

----- ----- Chunami from Bandit's World (female)

and two undefined index on name and gender in echo "$indent{$dogs[$id]['name']} ({$dogs[$id]['gender']})<br>";

Tanja · February 5, 2017

Oh, without special dog the result is right!

Why?

Barand - you are my hero!

Edited February 5, 2017 by Tanja

Barand · February 5, 2017

I am not sure what you are saying. Using

$dog_id = 13425;
descendants($dog_id, $dogs);  // 3rd parameter used internally to track generation depth (indent)

I get

Alka Volání Karpat (female)
 ----- Connor from Bandit's World (male)
 -----  ----- A.- Magnus the Wolf I. Lord of Lasvegas (male)
 -----  ----- A.- Marny the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Melody the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Mercedes the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Merlin the Wolf I.Lord of Lasvegas (male)
 -----  ----- A.- Milena the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Miles the Wolf I. Lord of Lasvegas (male)
 -----  ----- A.-Minerva the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Mirabell the Wolf I. Lady of Lasvegas (female)
 -----  ----- A.- Morgan the Wolf I. Lord of Lasvegas (male)
 -----  ----- Basilea the Wolf I. Lady of Lasvegas (female)
 -----  ----- Beatrix the Wolf I. Lady of Lasvegas (female)
 -----  ----- Ben the Wolf I. Lord of Lasvegas (male)
 -----  ----- Bogdan the Wolf I. Lord of Lasvegas (male)
 -----  ----- Bonita the Wolf I. Lady of Lasvegas (female)
 -----  ----- Bozena the Wolf I. Lady of Lasvegas (female)
 -----  ----- Brix the Wolf I. Lord of Lasvegas (male)
 -----  ----- Brixius Jack the Wolf I. Lord of Lasvegas (male)
 -----  ----- Camilo the Wolf I. Lord of Lasvegas (male)
 -----  ----- Cedric the Wolf I. Lord of Lasvegas (male)
 -----  ----- Chrysanthus the Wolf I. Lord of Lasvegas (male)
 -----  ----- Chandra the Wolf I. Lady of Lasvegas (female)
 -----  ----- Can the Wolf I. Lord of Lasvegas (male)
 -----  ----- Conan the Wolf I. Lord of Lasvegas (male)
 -----  ----- El Cid Grey Diamond (male)
 -----  ----- Eddi the Wolf I. Lord of Lasvegas (male)
 -----  ----- Elvis the Wolf I. Lord of Lasvegas (male)
 -----  ----- Ezra the Wolf I. Lord of Lasvegas (male)
 -----  ----- Emmi the Wolf I. Lady of Lasvegas (female)
 -----  ----- Esma the Wolf I. Lady of Lasvegas (female)
 ----- Chunami from Bandit's World (female)
 -----  ----- Djumana from Bandit's World (female)
 -----  ----- Delphi from Bandit's World (female)
 -----  -----  ----- Gangster from Bandit's World (male)
 -----  -----  ----- Gaucho from Bandit's World (male)
 -----  -----  ----- Gauner from Bandit's World (male)
 -----  -----  ----- Ganove from Bandit's World (male)
 -----  -----  ----- Greedy from Bandit's World (male)
 -----  -----  ----- Gwendy from Bandit's World (female)
 -----  -----  ----- Gil from Bandit's World (female)
 -----  -----  ----- Genesis from Bandit's World (female)
 -----  ----- Dynamite from Bandit's World (female)
 -----  ----- Dunbar from Bandit's World (male)
 -----  ----- Excalibur from Bandit's World (male)
 -----  ----- Efia-Eliska from Bandit's World (female)
 -----  ----- Feivel from Bandit's World (male)
 -----  ----- Fabulous from Bandit's World (male)
 -----  ----- Floyd from Bandit's World (male)
 -----  ----- Fraser from Bandit's World (male)
 -----  ----- Fiasco from Bandit's World (male)
 -----  ----- For Me from Bandit's World (female)
 -----  -----  ----- Heartbreaker from Bandit's World (male)
 -----  -----  ----- Hero from Bandit's World (male)
 -----  -----  ----- Highlander from Bandit's World (male)
 -----  -----  ----- Hashtag Houston from Bandit's World (female)
 -----  ----- Fanny from Bandit's World (female)
 ----- Chica from Bandit's World (female)
 ----- Cherina from Bandit's World (female)
 ----- Chandra from Bandit's World (female)
 ----- Cazan from Bandit's World (male)
 ----- Aiyana from Bandit's World  (female)
 ----- Akela from Bandit's World  (female)
 ----- Amy from Bandit's World  (female)
 ----- Bakira from Bandit's World  (female)
 ----- Balko from Bandit's World  (male)
 ----- Bayana from Bandit's World  (female)
 ----- Blaidd from Bandit's World  (female)
 ----- Bruce from Bandit's World  (male)

Barand · February 5, 2017

I couldn't even get your query from reply #7 to run - you need two variables but you only provide one. It would need to be

$parent= 13425;
$sql = "SELECT 
            id
          , dogname
          , mother_id as dam
          , father_id as sire
          , gender
        FROM dog
        WHERE mother_id= :parent1
        OR father_id = :parent2
        ORDER BY id";
$dogs = [];
$dogs[0] = ['name' => 'N/A', 'gender' => 'N/A', 'pups' => [] ];

$stmt = $db->prepare($sql);
$stmt->bindParam(':parent1', $parent, PDO::PARAM_INT);
$stmt->bindParam(':parent2', $parent, PDO::PARAM_INT);
$stmt->execute();

However, that is academic as you wouldn't want that query anyway.

Jacques1 · February 5, 2017

For the record

I don't think you understand the post.

What I recommend is to abandon toy database systems like MySQL in favor of more serious software like PostgreSQL. Then we can all stop wasting our time with workarounds.

If MySQL is the only choice available, I recommend picking the workaround carefully. Your quick hacks are often good enough for amateur applications which never grow. But sometimes applications do grow, and that's when the PHPMySQL duct tape comes off.

Jacques1 · February 5, 2017

The version without Barand's MySQL gymnastics:

$familyTreeStmt = $database->prepare('
    WITH RECURSIVE
        family_tree (dog_id, dogname, generation, ancestors)
    AS (
        SELECT
            id,
            dogname,
            1,
            ARRAY[id]::int[]
        FROM
            dog
        WHERE
            :dog_id IN (dog.father_id, dog.mother_id)
        UNION ALL
        SELECT
            dog.id,
            dog.dogname,
            family_tree.generation + 1,
            family_tree.ancestors || dog.id
        FROM
            family_tree
            JOIN dog ON family_tree.dog_id IN (dog.father_id, dog.mother_id)
    )
    SELECT
        *
    FROM
        family_tree
    ORDER BY
        ancestors
');
$familyTreeStmt->execute([
    'dog_id' => 1,
]);

foreach ($familyTreeStmt as $dog)
{
    echo str_repeat('-', $dog['generation']).$dog['dogname'].'<br>';
}

Output

-dog-1
--dog-1-1
---dog-1-1-1
--dog-1-2
-dog-2
-dog-3

Yes, that's a single query and a single loop which fetches the exact subtree which is needed (as opposed to the whole table).

Edited February 5, 2017 by Jacques1

Tanja · February 6, 2017

i will give it a try after work ....

requinix · February 6, 2017

Anyone want to mention nested sets?

Jacques1 · February 6, 2017

Mentioning isn't the problem. I think none of us is masochistic enough to implement them. :happy-04:

Anyway, I would really switch to a database system which can handle hierarchical data. Right now, every single task requires yet another workaround from this forum, turning her application more and more into an unmaintainable black box.

PostgreSQL actually has an extension specifically for tree structures:

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');

To get all descendants of the “Science” category:

SELECT path FROM test WHERE path <@ 'Top.Science';

                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)

Looks fairly promising.

Tanja · February 6, 2017

Seems, that (my) MySQL isn´t already right for this ....

Barands version will crash if dog has many generations of descedants

Edited February 6, 2017 by Tanja

Sign In

getting all offsprings (with x generations) from a given id

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Important Information