Я все еще думаю о том, как перевести рекурсивность программы Datalog в SQL, например
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
где A/1 — предикат EDB. Это, есть взаимозависимость между P и Q. Для более длинных запросов, как решить эту проблему?
Более того, есть ли какая-нибудь система, полностью реализующая перевод? Если есть, могу ли я узнать, какую систему или какой документ я могу сослаться?
Если вы примете подход «занесения в таблицу» предыдущих выводов и рассуждений по ним в прямой цепочке для вывода новых выводов, рекурсивная «глубина» не потребуется.
Имейте в виду, что Datalog требует некоторых ограничений на правила и переменные, которые гарантируют конечное завершение и, следовательно, конечное число выводов. Например, переменные должны иметь конечный диапазон возможных значений.
Предположим, ваш пример относится к константам, а не к переменным:
P(x,y) <- Q(x,y).
Q(x,y) <- P(x,z), A(y).
Одна проблема заключается в том, что вы хотите, чтобы A/1 была реализована как расширенная хранимая процедура или внешний код. Для этого я бы предложил свести в таблицу все результаты вызова A по всем возможным аргументам (конечное количество). В конце концов, это одни из выводов (доказуемых утверждений) вашей системы.
Как только это будет сделано, вывод прямой цепочки будет выполняться итеративно, а не рекурсивно. На каждом шаге рассматривайте каждое правило, применяя его с посылками (правыми частями), являющимися ранее полученными (табличными) выводами, если оно приводит к новому заключению. Если ни одно правило не приводит к новому заключению на текущем шаге, остановитесь. Процедура доказательства завершена.
В вашем примере доказательства останавливаются после того, как будут приведены все A факта, потому что нет достаточных выводов, чтобы применить какое-либо правило для получения новых выводов.
A/1, реализованные как внешний код, они будут обрабатываться как простые факты, т. е. сохранять любые успешные результаты их вызова для всех возможных входных данных (помните, что в Datalog диапазон любой переменной конечен). Таким образом, эту морщинку можно свести к стандартным фактам и правилам Datalog.
- person hardmath; 11.07.2011
Возможный подход заключается в использовании рекурсивных CTE в SQL, которые обеспечивают возможности транзитивного замыкания. Реляционная алгебра + транзитивное замыкание = Datalog.
