Приветствую!
Имеется следующая структура элементов (уроков) в таблице БД.
Каждый урок имеет два "служебных" поля: ключевой навык (строка), необходимые навыки (массив строк).
Задача: реализовать метод, который для указанного конкретного урока строит все возможные цепочки предков.
Принцип поиска.
Берем урок, смотрим его "необходимые навыки". Для каждого "необходимого навыка" находим в базе уроки, для которых данный навык указан как "ключевой навык". Процесс повторяется для каждого найденного урока.
В целом, похоже на обычное дерево. За небольшими исключениями.
Текущие мысли: рекурсивный метод, да еще и рекурсивные запросы в БД.
В общем -- жуть :(
Есть идеи, какой алгоритм позволил бы быстро решать поставленную задачу?
В задачу входит не только быстрое получение необходимых данных, но также их создание и обновление (т.е. добавление и редактирование новых уроков).
Теперь немного об инструментах.
Использую PHP. Данные хранятся в PostgreSQL, работаю с ними через Doctrine.
Готов рассмотреть другую БД, например, для хранения связей или маршрутов отдельно.
Приведу несколько схем.
На данной схеме видна зависимость между уроками и навыками. Т.е. слой уроков формируется через промежуточный слой навыков. Но в конечном "дереве" будут лишь слои уроков (схема 2).
На данной схеме показан вариант конечного "дерева" уроков.
Т.е. аргументом функции, которую мы создаем, будет узел "a". А результатом функции должен быть, например, массив маршрутов (для указанного примера):
[
["l", "e", "b", "a"],
["m", "e", "b", "a"],
["m", "f", "b", "a"],
["n", "f", "b", "a"],
["g", "c", "a"],
["h", "c", "a"],
["i", "c", "a"],
["p", "a"],
["j", "d", "a"],
["p", "k", "d", "a"],
["p", "o", "k", "d", "a"]
]