A set of (disjunctive datalog) rules of the form A1 ? … ? Ak ? B1, ..., Bm, not Bm+1, …, not Bn, k+n>0, where A1, …, Ak, B1, …, Bn are atoms of the form p(t1, ..., th), p is a predicate symbol of arity h, and the terms t1,..., th are constants or variables. A not-free (?-free) program is called positive (or normal). Predicate symbols are partitioned into two distinct sets: base predicates (also called EDB predicates) and derived predicates (also called IDB predicates). Base predicates correspond to database relations defined over a given domain and they do not appear in the head of any rule; derived predicates are defined by means of rules.
Published in Chapter:
On the Implementation of a Logic Language for NP Search and Optimization Problems
Sergio Greco (University of Calabria, Italy), Cristian Molinaro (University of Calabria, Italy), Irina Trubitsyna (University of Calabria, Italy), and Ester Zumpano (University of Calabria, Italy)
Copyright: © 2009
|Pages: 7
DOI: 10.4018/978-1-60566-242-8.ch084
Abstract
It is well known that NP search and optimization problems can be formulated as DATALOG¬ (datalog with unstratified negation; Abiteboul, Hull, & Vianu, 1994) queries under nondeterministic stable-model semantics so that each stable model corresponds to a possible solution (Gelfond & Lifschitz, 1988; Greco & Saccà, 1997; Kolaitis & Thakur, 1994). Although the use of (declarative) logic languages facilitates the process of writing complex applications, the use of unstratified negation allows programs to be written that in some cases are neither intuitive nor efficiently valuable. This article presents the logic language NP Datalog, a restricted version of DATALOG¬ that admits only controlled forms of negation, such as stratified negation, exclusive disjunction, and constraints. NP Datalog has the same expressive power as DATALOG¬, enables a simpler and intuitive formulation for search and optimization problems, and can be easily translated into other formalisms. The example below shows how the vertex cover problem can be expressed in NP Datalog.