  We consider the setting of ontological database access, where an Abox is
given in form of a relational database D and where a Boolean conjunctive query
q has to be evaluated against D modulo a Tbox T formulated in DL-Lite or Linear
Datalog+/-. It is well-known that (T,q) can be rewritten into an equivalent
nonrecursive Datalog program P that can be directly evaluated over D. However,
for Linear Datalog? or for DL-Lite versions that allow for role inclusion, the
rewriting methods described so far result in a nonrecursive Datalog program P
of size exponential in the joint size of T and q. This gives rise to the
interesting question of whether such a rewriting necessarily needs to be of
exponential size. In this paper we show that it is actually possible to
translate (T,q) into a polynomially sized equivalent nonrecursive Datalog
program P.
