Circumscribing datalog: Expressive power and complexity

AbstractIn this paper we study a generalization of datalog, the language of function-free definite clauses. It is known that standard datalog semantics (i.e., least Herbrand model semantics) can be obtained by regarding programs as theories to be circumscribed with all predicates to be minimized. The extension proposed here, called datalogcirc, consists in considering the general form of circumscription, where some predicates are minimized, some predicates are fixed, and some vary. We study the complexity and the expressive power of the language thus obtained. We show that this language (and, actually, its non-recursive fragment) is capable of expressing all the queries in DB-co-NP and, as such, is much more powerful than standard datalog, whose expressive power is limited to a strict subset of PTIME queries. Both data and combined complexities of answering datalogcirc queries are studied. Data complexity is proved to be co-NP-complete. Combined complexity is shown to be in general hard for co-NE and complete for co-NE in the case of Herbrand bases containing k distinct constant symbols, where k is bounded