Rewriting queries using views over monadic database schemas

Abstract

In research in databases and AI, the problem of rewriting queries using views has received a lot of interest recently; we refer to the nice survey by Levy for background. In this short note, we offer two remarks on the computational complexity of this problem. First, we offer a most simple proof that the problem is NP-complete. We should specify immediately that we work with the contained rewriting variant of the notion of rewriting queries using views. For the equivalent rewriting variant, an NP-completeness proof was already published by Levy et al. Second, we restrict attention to database schemas with unary relations only. Such “monadic” database schemas have classically provided a special case where difficult problems become easy. For example, satisfiability of relational calculus sentences in general is undecidable, but is decidable if the database schema is monadic. We show that, over monadic database schemas, the problem of rewriting queries using views is efficiently solvable.