Monotone Rewritability and the Analysis of Queries, Views, and Rules

We study the interaction of views, queries, and background

knowledge in the form of existential rules. The motivating

questions concern monotonic determinacy of a query using

views w.r.t. rules, which refers to the ability to recover the

query answer from the views via a monotone function. We

study the decidability of monotonic determinacy, and compare

with variations that require the “recovery function” to

be in a well-known monotone query language, such as conjunctive queries or Datalog. Surprisingly, we find that even

in the presence of basic existential rules, the borderline between well-behaved and badly-behaved answerability differs

radically from the unconstrained case. In order to understand

this boundary, we require new results concerning entailment

problems involving views and rules.