A technique for proving decidability of containment and equivalence of linear constraint queries

We develop a new technique based on counter machines to study the containme nt and equivalence: of queries with linear constraints over integers Z, nat ural numbers N, rational numbers Q, and real numbers R. We show that the pr oblems are dedicable in exponential space with an exponential time lower bo und for conjunctive queries with linear constraints. For a subclass, called SQL-like conjunctive queries, the problems are shown to have a poly nomial 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 unde cidable for finite databases but decidable for a subclass of finite databas es. (C) 1999 Academic Press.