Dynamic programming in Datalog with aggregates

Dynamic programming is a general technique for solving optimization problem s. It is based on the division of problems into simpler subproblems that ca n be computed separately. In this paper, we show that Datalog with aggregat es and other nonmonotonic constructs can express classical dynamic programm ing optimization problems in a natural fashion, and then we discuss the imp ortant classes of queries and applications that benefit from these techniqu es.