A classical problem of relational queries is preserving closure under a chosen encoding of databases: in the standard relational setting this requirement boils down to preserving finiteness of answers to queries over finite relations. However, when a more sophisticated encoding iss used (e.g., a constraint-based encoding), the safety and closure questions re-emerge: for a given encoding of data (based on a class of constraints) and a query language (based on potentially different class of constraints) we want to find answers to the following questions:
Datalog is a query language of function-free horn clauses that allows formulation of advanced queries which cannot be asked in standard SQL. An inherent feature of Datalog is that, despite of the recursive nature of the queries (and unlike Prolog, its bigger brother), it guarantees termination for all queries. To extend the application range of Datalog, several constraint extensions of the language have been proposed in the literature, all of them guaranteeing termination. However, the termination arguments are complicated. [Toman97a] has proposed a sufficient condition on the constraint theory (constraint compactness) that guarantees termination. However, the conjecture about the necessity of this condition is still open. In this project we study necessary conditions a constraint theory has to satisfy for all Datalog queries to terminate. We may also study classes queries between first-order (trivial) and full Datalog (possibly with well-founded negation) and their termination properties.