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

• Напомним, что большинство правил в базах знаний, применяемых на практике, являются небольшими и простыми (подобно правилам, используемым в примере доказательства преступления), а не большими и сложными (как в формулировке задачи CSP, приведенной на рис. 9.3). В мире пользователей баз данных принято считать, что размеры правил и арности предикатов не превышают некоторого постоянного значения, и принимать во внимание только сложность данных, т.е. сложность логического вывода как функции от количества базовых фактов в базе данных. Можно легко показать, что обусловленная данными сложность в прямом логическом выводе определяется полиномиальной зависимостью.

Рис. 9.3. Иллюстрация связи между процессами согласования с шаблоном и удовлетворения ограничений: граф ограничений для раскрашивания карты Австралии (см. рис. 5.1) (а); задача CSP раскрашивания карты, представленная в виде единственного определенного выражения (б). Обратите внимание на то, что области определения переменных заданы неявно с помощью констант, приведенных в базовых фактах для предиката Di f f

•    Могут рассматриваться подклассы правил, для которых согласование является наиболее эффективным. По сути, каждое выражение на языке Datalog может рассматриваться как определяющее некоторую задачу CSP, поэтому согласование будет осуществимым только тогда, когда соответствующая задача CSP является разрешимой. Некоторые разрешимые семейства задач CSP описаны в главе 5. Например, если граф ограничений (граф, узлами которого являются переменные, а дугами — ограничения) образует дерево, то задача CSP может быть решена за линейное время. Точно такой же результат остается в силе для согласования с правилами. Например, если из карты, приведенной на рис. 9.3, будет удален узел SA, относящийся к Южной Австралии, то результирующее выражение примет следующий вид: что соответствует сокращенной задаче CSP, показанной на рис. 5.7. Для решения задачи согласования с правилами могут непосредственно применяться алгоритмы решения задач CSP с древовидной структурой.