Adding disjunction to datalog (extended abstract)
Thomas Eiter, Georg Gottlob, Heikki Mannila · 1994
We study the expressive power and complexity of disjunctive datalog, i.e., datalog with disjunctive rule heads, under three different semantics: the minimal model semantics, the perfect models semantics, and the stable model semantics. We show that the brave variants of these semantics express the same set of queries. In fact, they precisely capture the complexity of class ΣP/2. The combined complexity of disjunctive datalog is shown to be NEXPTIMENP-complete.