On the Containment and Equivalence of Database Queries with Linear Constraints.

Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43

@inproceedings{DBLP:conf/pods/IbarraS97,
  author    = {Oscar H. Ibarra and
               Jianwen Su},
  editor    = {Alberto O. Mendelzon and
               Z. Meral {\"O}zsoyoglu},
  title     = {On the Containment and Equivalence of Database Queries with Linear
               Constraints},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona,
               USA},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {32-43},
  ee        = {http://doi.acm.org/10.1145/263661.263666, db/conf/pods/IbarraS97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We 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 decidable in double exponential time with an exponential time lower bound for conjunctive queries with linear contraints over Z and N, decidable in double exponential time for constant-free conjunctive queries with linear constraints over Q and R. For the general class 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 N, the containment and equivalence problems are decidable over "bounded-degree databases".

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Alberto O. Mendelzon, Z. Meral Özsoyoglu (Eds.): Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona, USA. ACM Press 1997, ISBN 0-89791-910-6
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1659 KB]

References

[AHV95]: Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[ASU79a]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979)
[ASU79b]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[BB74]: Brenda S. Baker, Ronald V. Book: Reversal-Bounded Multipushdown Machines. J. Comput. Syst. Sci. 8(3): 315-332(1974)
[BDLW96]: Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
[BL96]: Michael Benedikt, Leonid Libkin: On the Structure of Queries in Constraint Query Languages. LICS 1996: 25-34
[Che76]: Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976)
[CK73]: ...
[CM77]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[Cod70]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)
[CV93]: Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70
[DS96]: Guozhu Dong, Jianwen Su: Conjunctive Query Containment with Respect to Views and Constraints. Inf. Process. Lett. 57(2): 95-102(1996)
[End72]: ...
[Fag93]: Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993)
[FR74]: ...
[FR75]: Jeanne Ferrante, Charles Rackoff: A Decision Procedure for the First Order Theory of Real Addition with Order. SIAM J. Comput. 4(1): 69-76(1975)
[F�r]: Martin Fürer: The Complexity of Presburger Arithmetic with Bounded Quantifier Alternation Depth. Theor. Comput. Sci. 18: 105-111(1982)
[Gai81]: ...
[GI81]: Eitan M. Gurari, Oscar H. Ibarra: The Complexity of Decision Problems for Finite-Turn Multicounter Machines. J. Comput. Syst. Sci. 22(2): 220-229(1981)
[GI82]: Eitan M. Gurari, Oscar H. Ibarra: Two-Way Counter Machines and Diophantine Equations. J. ACM 29(3): 863-873(1982)
[GS94]: Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300
[GS95]: Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
[GS96]: Stéphane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. Theor. Comput. Sci. 173(1): 151-181(1997)
[Iba78]: Oscar H. Ibarra: Reversal-Bounded Multicounter Machines and Their Decision Problems. J. ACM 25(1): 116-133(1978)
[IJTW95]: Oscar H. Ibarra, Tao Jiang, Nicholas Q. Trân, Hui Wang: New Decidability Results Concerning Two-Way Counter Machines. SIAM J. Comput. 24(1): 123-137(1995)
[KG94]: ...
[KKR95]: Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995)
[Klu88]: Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988)
[Kup93]: Gabriel M. Kuper: Aggregation in Constraint Databases. PPCP 1993: 166-173
[LRU96]: Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237
[LW94]: Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237
[Min61]: ...
[PVV95]: Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87
[Ren92]: James Renegar: On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals. J. Symb. Comput. 13(3): 255-300(1992)
[Rev93]: Peter Z. Revesz: A Closed-Form Evaluation for Datalog Queries with Integer (Gap)-Order Constraints. Theor. Comput. Sci. 116(1&2): 117-149(1993)
[RL78]: C. R. Reddy, Donald W. Loveland: Presburger Arithmetic with Bounded Quantifier Alternation. STOC 1978: 320-325
[ST96]: Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27
[Tar51]: ...
[Tra50]: ...
[Ull88]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[vdM92]: Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345
[VP75]: Leslie G. Valiant, Mike Paterson: Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350(1975)

Last update Thu May 24 04:40:32 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page