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

Authors
Citation
Oh. Ibarra et Jw. Su, A technique for proving decidability of containment and equivalence of linear constraint queries, J COMPUT SY, 59(1), 1999, pp. 1-28
Citations number
50
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
00220000 → ACNP
Volume
59
Issue
1
Year of publication
1999
Pages
1 - 28
Database
ISI
SICI code
0022-0000(199908)59:1<1:ATFPDO>2.0.ZU;2-4
Abstract
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.