Datalog (i.e., function-free logic) programs with monotonicity constraints
on extensional predicates are considered. A monotonicity constraint states
that one argument of a predicate or a constant is always less than another
argument or a constant, according to some strict partial order. Relations o
f an extensional database are required to satisfy the monotonicity constrai
nts imposed on their predicates. More specifically, a strict partial order
is defined on the domain (i.e., set of constants) of the database, and ever
y tuple of each relation satisfies the monotonicity constraints imposed on
its predicate. This paper focuses on the problem of entailment of monotonic
ity constraints in the intensional database from monotonicity constraints i
n the extensional database. The entailment problem is proven to be decidabl
e, based on a suggested algorithm for computing sound and complete disjunct
ions of monotonicity and equality constraints that hold in the intentional
database. It is also shown that the entailment of monotonicity constraints
in programs is a complete problem for exponential time. For linear programs
, this problem is complete for polynomial space.