  We establish connections between the size of circuits and formulas computing
monotone Boolean functions and the size of first-order and nonrecursive Datalog
rewritings for conjunctive queries over OWL 2 QL ontologies. We use known lower
bounds and separation results from circuit complexity to prove similar results
for the size of rewritings that do not use non-signature constants. For
example, we show that, in the worst case, positive existential and nonrecursive
Datalog rewritings are exponentially longer than the original queries;
nonrecursive Datalog rewritings are in general exponentially more succinct than
positive existential rewritings; while first-order rewritings can be
superpolynomially more succinct than positive existential rewritings.
