Datalog queries of set constraint databases

Extension of the relational database model to represent complex data has been a focus of much research in recent years. At the same time, an alternative extension of the relational database model has proposed using constraint databases that finitely describe infinite relations. This paper attempts to combine these two divergent approaches. In particular a query language called Datalog with set order constraints, or Datalog(subset of P(Z)), is proposed. This language can express many natural problems with sets, including reasoning about inheritance hierarchies. Datalog(subset of P(Z)) queries over set constraint databases are shown to be evaluable bottom-up in closed form and to have DEXPTIME-complete data complexity.