Title :
Dynamic programming in Datalog with aggregates
Author_Institution :
Dipt. di Elettronica Inf. e Sistemistica, Calabria Univ., Italy
Abstract :
Dynamic programming is a general technique for solving optimization problems. It is based on the division of problems into simpler subproblems that can be computed separately. In this paper, we show that Datalog with aggregates and other nonmonotonic constructs can express classical dynamic programming optimization problems in a natural fashion, and then we discuss the important classes of queries and applications that benefit from these techniques
Keywords :
DATALOG; database theory; deductive databases; dynamic programming; mathematics computing; nonmonotonic reasoning; query processing; Datalog; aggregates; deductive databases; dynamic programming; nonmonotonic reasoning; optimization problems; problem decomposition; queries; separately computable subproblems; Aggregates; Computer Society; Constraint optimization; Deductive databases; Dynamic programming; Linear programming; Tree graphs;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
