G. Gottlob, C. Papadimitriou: "On the Complexity of single-rule datalog Queries"; Information and Computation, 183 (2003), 1; 104 - 122.
http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04968353