A Technique for Proving Decidability of Containment and Equivalence of Linear Constraint Queries

AbstractWe develop a new technique based on counter machines to study the containment and equivalence of queries with linear constraints over integers Z, natural numbers N, rational numbers Q, and real numbers R. We show that the problems are dedicable in exponential space with an exponential time lower bound for conjunctive queries with linear constraints. For a subclass, called SQL-like conjunctive queries, the problems are shown to have a polynomial space upper bound. We also use the counter machine technique to show that for a syntactically restricted subclass of first-order queries with linear constraints over Z and N, the containment and equivalence problems are undecidable for finite databases but decidable for a subclass of finite databases