mIwE mIwE - 2 months ago 4
MySQL Question

Recursive function to find all the dependencies of a MySQL table

I have a database with a couple of tables related between them. For example, the table User contains all the users in the system.
Then I have an index table named User_friend with the relation between a user an it's friends.

I have a function loadObject($class, $id) which is called like:

loadObject('User', 1);


and returns the User with id = 1 as an array with the following format:

array(
'id' => 1,
'username' => 'My user',
// the following array contains all the entries in User_invited
'friends' => [2, 3, 4, 5],
// same for comments
'comments' => [6, 7]
'type' => 'User'
);


I'm trying to come up with a recursive function that checks the User with id = 1, finds all the friends (inside the 'friends' array) and then loops through each value, find those Users and it's friends until it reaches the end of the chain without duplicating any entries.

This seems pretty straight forward. The problem is that apart from friends we can have other relations with Comments, Events and many other tables.

The tricky part is that this function should not only work with the 'User' class, but also with any class we define.

What I'm doing is using some sort of Indexed array to define which index tables refer to which main tables.

For example:

$dependencies = [
'friends' => 'User'
];


This means that, when we find the 'friends' key, we should query the 'User' table.

Here's my code:

<?php
$class = $_GET['class'];
// if we receive a collection of ids, find each individual object
$ids = explode(",", $_GET['ids']);

// load all main objects first
foreach($ids as $id) {
$error = isNumeric($id);
$results[] = loadObject($class,$id);
}

$preload = $results;
$output = [];

$output = checkPreload($preload);
print json_encode($output);

function checkPreload($preload)
{
$dependencies = [
'comment' => 'Comment',
'friend' => 'User',
'enemy' => 'User',
'google' => 'GoogleCalendarService',
'ical' => 'ICalCalendarService',
'owner' => 'User',
'invited' => 'User'
];

foreach($preload as $key => $object)
{
foreach($object as $property => $values)
{
// if the property is an array (has dependencies)
// i.e. event: [1, 2, 3]
if(is_array($values) && count($values) > 0)
{
// and if the dependency exists in our $dependencies array, find
// the next Object we have to retrieve
// i.e. event => CatchAppCalendarEvent
if(array_key_exists($property, $dependencies))
{
$dependentTable = $dependencies[$property];
// find all the ids inside that array of dependencies
// i.e. event: [1, 2, 3]
// and for each ID load th the object:
// i.e. CatchAppCalendarEvent.id = 1, CatchAppCalendarEvent.id = 2, CatchAppCalendarEvent.id = 3
foreach($values as $id)
{
$dependantObject = loadObject($dependencies[$property], $id);
// if the object doesn't exist in our $preload array, add it and call the
// function again
if(!objectDoesntExist($preload, $dependantObject)) {
$preload[] = $dependantObject;
reset($preload);
checkPreload($preload);
}
}
}
}
}
}
return $preload;
}

// 'id' and 'type' together are unique for each entry in the database
function objectDoesntExist($preload, $object)
{
foreach($preload as $element)
{
if($element['type'] == $object['type'] && $element['id'] == $object['id']) {
return true;
}
}
return false;
}


I'm pretty sure I'm close to the solution but I'm not able to understand why is not working. Seems to get stuck in an infinite loop even if I'm using a function to check if the object has been inserted in the $preload array. Also, sometimes doesn't check the next set of elements. Could it be because I'm appending the data to the $preload variable?

Any help is more than welcome. I've been trying to find algorithms for resolving dependencies but nothing applied to MySQL databases.

Thanks

Answer

After some failed tests I've decided to not use a recursive approach but an iterative approach.

What I'm doing is start with one element and put it in a "queue" (an array), find the dependencies for that element, append them to the "queue" and then step back and re-check the same element to see if there are any more dependencies.

The function to check the dependencies is a bit different now:

/**
 * This is the code function of our DRA. This function contains an array of dependencies where the keys are the 
 * keys of the object i.e. User.id, User.type, etc. and the values are the dependent classes (tables). The idea
 * is to iterate through this array in our queue of objects. If we find a property in one object that that matches
 * the key, we go to the appropriate class/table (value) to find more dependencies (loadObject2 injects the dependency
 * with it's subsequent dependencies)
 * 
 */
function findAllDependenciesFor($element)
{
    $fields = [
        'property' => 'tableName',
        ...
    ];

    $output = [];

    foreach($element as $key => $val) {
        if(array_key_exists($key, $fields)) {
            if(is_array($val)) {
                foreach($val as $id) {
                    $newElement = loadObject($fields[$key], $id);
                    $output[] = $newElement;
                }
            }
            else {
                // there's been a field conversion at some point in the app and some 'location'
                // columns contain text and numbers (i.e. 'unknown'). Let's force all values to be
                // and integer and avoid loading 0 values.
                $val = (int) $val;
                if($val != 0) {
                    $newElement = loadObject($fields[$key], $val);
                    $output[] = $newElement;
                }
            }

        }
    }

    return $output;
}

I'm also using the same function as before to check if the "queue" already contains that element (I have renamed the function to be "objectExists" instead of "objectDoesntExist". As you can see I check the type (table) and the id because the combination of these two properties is unique for the whole system/database.

function objectExists($object, $queue)
{
    foreach($queue as $element) {
        if($object['type'] == $element['type'] && $object['id'] == $element['id']) {
            return true;
        }
    }
    return false;
}

Finally, the main function:

// load all main objects first
foreach($ids as $id) {
    $error = isNumeric($id);
    $results[] = loadObject($class,$id);
}

$queue = $results;
for($i = 0; $i < count($queue); $i++)
{
    // find all dependencies of element
    $newElements = findAllDependenciesFor($queue[$i]);
    foreach($newElements as $object) {
        if(!objectExists($object, $queue)) {
            $queue[] = $object;

            // instead of skipping to the next object in queue, we have to re-check
            // the same object again because is possible that it included new dependencies
            // so let's step back on to re-check the object
            $i--;
        }
    }
    $i++;
}

As you can see, I'm using a regular "for" instead of a "foreach". This is because I need to be able to step forward/backward in my "queue".

Comments