Как я могу рассчитать идеальную точку фиксации стратифицированной программы Datalog?
Каков порядок оценки для инструкций в программе Datalog? Всегда ли идеальная точка фиксации является минимальной?
2 ответа
Если ваша программа стратифицирована, то вы следуете стратам в своих расчетах: начните с "основных фактов" (EDB), а затем переходите к IDB, которые зависят только от EDB, к IDB, которые зависят только от IDB, которые зависят только от EDB и т. Д. Fixpoint гарантированно будет уникальным.
Да, идеальная модель определенной программы Datalog совпадает с ее наименьшей моделью Хербранда (это предложение можно найти, например, в [1]).
Теперь стратифицированная программа Datalog - это программа в Datalog с отрицанием, которое можно расслоить. Программа не является определенной, но она поддается расслоению, и поэтому она может быть оценена стратом по страте (как Александр описывает в своем ответе). Нетрудно увидеть, что вы снова достигли минимальной точки фиксации. Раньше был хороший учебник по базе данных и дедуктивным базам данных проф. Андрей Воронков.
Порядок оценки определенной программы Datalog не имеет значения. В случае Datalog с отрицанием вы должны быть более осторожными.
[1] Ллойд - Основы логического программирования