It is a well-known result that Datalog, with the added assumption that the input databases are ordered, can express exactly those queries that belong in class PTIME. Recently, this result was extended for higher-order Datalog that does not contain negation. It ap- pears that an increase in the order allowed in the programs results in a direct increase in expressiveness. This thesis studies the expressiveness of higher-order Datalog when we introduce negation. More specifically, we present a study of the expressiveness of different higher-order Datalog language fragments where each time a subset of fea- tures is allowed from negation, partially-applied expressions as predicate arguments, and higher-order existential variables. For each such choice of features, we investi- gate the resulting expressiveness as we increase the order for the types we allow in our programs.
It follows that the original expressiveness result is not changed when we just intro- duce negation. However, in the case that we restrict partial application from our syntax, there is a big difference. Partially-applied expressions can alone give the maximum ex- pressiveness achieved by higher-order Datalog while in their absence only negation paired with higher-order existential variables can achieve the same result. Finally, all other choices of features result in a collapse in PTIME for the problems the language fragments can express regardless of the order we allow in our programs.