Datalog is a syntactic subset of Prolog, and Datalog queries can be evaluated in polynomial time. This does not fully answer your question, but I hope it is useful for you as a starting point.