Implementation and Experimentation of the Logic Language NP Datalog

This paper presents a system prototype implementing NP Datalog, a Datalog-like language for expressing NP search and optimization problems. NP Datalog extends DATALOG-s (DATALOG with stratified negation) with intuitive and efficient constructs, i.e. constraints and a restricted form of (exclusive) disjunction used to define (nondeterministically) subsets (or partitions) of relations. The system translates NP Datalog queries into OPL programs, then solves them by using the ILOG Solver [16]. Thus, it combines an easy formulation of problems, expressed by means of a declarative logic language, and an efficient execution of the ILOG Solver. Several experiments show the effectiveness of this approach.