Where decidability returns

Undecidability is a statement about the full language. Restrict the shape and the questions become decidable again. A few cases:

  • Monadic intensionals: every rule-defined predicate is unary. Containment is decidable; this is monadic Datalog.
  • Monadic extensionals: the input predicates are all unary.
  • No recursion: a non-recursive program is a union of conjunctive queries, where containment is decidable.
Expressive power and decidable reasoning pull against each other. A restricted fragment regains whichever property matters more for the task at hand.