On Datalog vs. polynomial time (extended abstract)
Foto Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis · 1991
We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a “Pumping Lemma” for Datalog queries.