DATALOG with nested rules

This paper presents an extension of disjunctive dat slog (Datalog(V)) by nested rules. Nested rules are (disjunctive) rules where elements of the head may be also rules. Nested rules increase the knowledge representation power of Datalog(V) both from a theoretical and from a practical viewpoint. A number of examples show that nested rules allow to naturally model several real world situations that cannot be represented in Datalog(V). An in depth analysis of complexity and expressive power of the language shows that nested rules do increase the expressiveness of Datalog(V) without implying any increase in its computational complexity.