Теперь рассмотрим, в чем состоит ахиллесова пята языка Prolog: несогласованность между организацией поиска в глубину и деревьями поиска, которые включают повторяющиеся состояния и бесконечные пути. Рассмотрим следующую логическую программу, позволяющую определить, существует ли путь между двумя точками в ориентированном графе:

path(X,Z) :- link(X,Z).

path(X,Z) :-path(X,Y), link(Y,Z).

На рисунке а) приведен простой граф, состоящий из трех узлов, который описан с помощью фактов link (а, Ь) и link (Ь, с). При использовании этой программы запрос path (а, с) вырабатывает дерево доказательства, показанное на рисунке а). С другой стороны, если эти два выражения расположены в таком порядке:

path(X,Z) :-path(X,Y), link(Y, Z).

path(X,Z) :- link(X, Z).

то система Prolog следует по бесконечному пути, как показано на рисунке б). Поэтому система Prolog является неполной, как и программа автоматического доказательства теоремы для определенных выражений (как показано в этом примере, даже применительно к программам, соответствующим формату языка Datalog), поскольку для некоторых баз знаний эта система оказывается неспособной доказать высказывания, которые из них следуют. Следует отметить, что алгоритм прямого логического вывода не подвержен этой проблеме: сразу после вывода фактов path (а, b), path(b,с) и path (а, с) процесс прямого логического вывода останавливается.

Обратный логический вывод с поиском в глубину сталкивается также с проблемами, обусловленными излишними вычислениями. Например, при поиске пути от узла А₁ к узлу J₄ на рисунке б) система Prolog выполняет 877 этапов логического вывода, большинство из которых связано с поиском всех возможных путей к узлам, не   позволяющим достичь цели. Такая проблема аналогична проблеме повторяющихся состояний. Общее количество этапов логического вывода может определяться экспоненциальной зависимостью от количества базовых фактов, вырабатываемых в процессе вывода. А если бы вместо этого применялся прямой логический вывод, то можно было бы ограничиться выработкой, самое большее, n² фактов path (X, Y), связывающих п узлов. При этом для решения задачи, приведенной на рисунке б), потребовалось бы только 62 этапа логического вывода.

Иллюстрация недостатков языка Prolog: поиск пути от А до Сможет привести систему Prolog к созданию бесконечного цикла (а); граф, в котором каждый узел связан с двумя случайно выбираемыми преемниками на следующем уровне; для поиска пути от A₁ до J₄ требуется 877этапов логического вывода (б)

Иллюстрация того, что работа программы Prolog зависит от расположения взаимосвязанных выражений: успешное доказательство того, что путь от А до С существует (а); бесконечное дерево доказательства, формируемое из-за того, что выражения находятся в "неправильном " порядке (б)

Применение прямого логического вывода при решении задач поиска в графе представляет собой пример динамического программирования, в котором решения подзадач формируются инкрементно из решений меньших подзадач и кэшируются для предотвращения повторного вычисления. Аналогичный эффект в системе обратного логического вывода может быть достигнут с помощью запоминания (memoization), т.е. кэширования решений, найденных для подцелей, по мере их обнаружения, а затем повторного применения этих решений после очередного появления той же подцели, вместо повторения предыдущих вычислений. Этот подход применяется в системах табулированного логического программирования (tabled logic programming), в которых для реализации метода запоминания используются эффективные механизмы сохранения и выборки. В табулированном логическом программировании объединяется целенаправленность обратного логического вывода с эффективностью динамического программирования, присущей прямому логическому выводу. Кроме того, эти системы являются полными применительно к программам в формате Datalog, а это означает, что программисту приходится меньше беспокоиться о бесконечных циклах.