On the containment and equivalence of database queries with linear constraints (extended abstract)
Óscar H. Ibarra, Jianwen Su · 1997
We develop a new technique based on counter machines to study the containment and equivalence of queries with linear constraints overintegers Z, natural numbers M, rational numbers Q and real numbers RWe show that the problems are decidable in double exponential time with an exponential time lower bound for conjunctive queries with linear constraints over Z and lV, decidable in double exponential time for constant-free conjunctive queries with linear constraints over Q and R. For the general classes of conjunctive queries with linear constraints over Q and R, the problems are decidable in double exponential space using reductions to the first-order theory of reals with addition.We also use the counter machine technique to show that for "connected" first-order queries with linear constraints over Z and lV, the containment and equivalence problems are decidable over "bounded-degree databases".