Сортировка и фильтрация зависимостей

Question

Сортировка и фильтрация зависимостей

Я оптимизирую SQL-запрос системы отчетов, где пользователь может выбирать столбцы, но таблицы являются фиксированными:

-- Dynamically generated
SELECT t1.c4, t4.c8
-- Static
FROM t1
INNER JOIN t2 ON t1.id=t2.t1_id
INNER JOIN t3 ON t1.id=t3.t1_id
INNER JOIN t4 ON t2.id=t4.t2_id
INNER JOIN t5 ON t4.id=t5.t4_id
/*...*/;

Я хочу удалить ненужные таблицы и сделать весь запрос динамически генерируемым:

-- Dynamically generated
SELECT t1.c4, t4.c8
FROM t1
INNER JOIN t2 ON t1.id=t2.t1_id
INNER JOIN t4 ON t2.id=t4.t12_id;

Чтобы выяснить зависимости, я искал в Packagist и нашел marcj / topsort а также топологическая сортировка, который работает как рекламируется:

$sorter = new StringSort();
$sorter->add('t1');
$sorter->add('t2', array('t1'));
$sorter->add('t3', array('t1'));
$sorter->add('t4', array('t2'));
$sorter->add('t5', array('t4'));
print_r($sorter->sort());

Array
(
[0] => t1
[1] => t2
[2] => t3
[3] => t4
[4] => t5
)

Но что мне действительно нужно, так это метод, который берет действительно необходимые таблицы первого уровня и определяет минимальный набор таблиц, который соответствует зависимостям, как в:

// Sample interface and expected output
$query->getRequiredTables(array('t1', 't4'));

Array
(
[0] => t1
[1] => t2
[2] => t4
)

Я не могу просто кормить ->add() только с таблицами первого уровня, потому что я получу ElementNotFoundException,

Вот где я потерялся. Является ли топологическая сортировка правильным инструментом?

1

algorithm dependency-injection php php-5.3 topological-sort

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Сначала создайте дерево зависимостей для ваших таблиц. Например, в вашем случае это будет:

Выберите любую из таблиц из списка обязательных таблиц как root.
Например, если вам нужны таблицы 2 и 3, вы можете выбрать 2 в качестве корня и получить следующее дерево:

Теперь пройдитесь по дереву от корня и, когда вы нажмете любую из необходимых таблиц (в нашем случае 3), добавьте все таблицы из стека к результату. Например, когда вы находитесь в узле 3, ваш стек равен [2, 1, 3], вы добавляете все эти узлы в свой результат.

Скажем, с тем же деревом зависимостей пользователь запрашивал таблицы 1, 3 и 4. В этом случае вы оставляете 1 в качестве корня, и когда вы попадаете на узел 4, ваш стек равен [1, 2, 4], а когда вы попадаете на узел 3, ваш стек [1, 3]. Результат [1, 2, 3, 4].

Пример кода для обхода дерева (не на каком-либо конкретном языке, просто в качестве примера).

function dfs(node) {
bool include = requiredTables.contains(node)
for each child of node {
if dfs(child) {
include = true;
}
}
if (include) result.add(node);
return include;
}

1