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

@inproceedings{DBLP:conf/pods/IbarraS97,
  author    = {Oscar H. Ibarra and
               Jianwen Su},
  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},
  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

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.

• 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/...

• 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

Online Edition: ACM Digital Library

References

[AHV95]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[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) BibTeX

[ASU79b]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[BB74]

Brenda S. Baker, Ronald V. Book: Reversal-Bounded Multipushdown Machines. J. Comput. Syst. Sci. 8(3): 315-332(1974) BibTeX

[BDLW96]

Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16 BibTeX

[BL96]

Michael Benedikt, Leonid Libkin: On the Structure of Queries in Constraint Query Languages. LICS 1996: 25-34 BibTeX

[Che76]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[CK73]

...

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[Cod70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[CV93]

Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70 BibTeX

[DS96]

Guozhu Dong, Jianwen Su: Conjunctive Query Containment with Respect to Views and Constraints. Inf. Process. Lett. 57(2): 95-102(1996) BibTeX

[End72]

...

[Fag93]

Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993) BibTeX

[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) BibTeX

[F�r]

Martin Fürer: The Complexity of Presburger Arithmetic with Bounded Quantifier Alternation Depth. Theor. Comput. Sci. 18: 105-111(1982) BibTeX

[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) BibTeX

[GI82]

Eitan M. Gurari, Oscar H. Ibarra: Two-Way Counter Machines and Diophantine Equations. J. ACM 29(3): 863-873(1982) BibTeX

[GS94]

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX

[GS95]

Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77 BibTeX

[GS96]

Stéphane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. Theor. Comput. Sci. 173(1): 151-181(1997) BibTeX

[Iba78]

Oscar H. Ibarra: Reversal-Bounded Multicounter Machines and Their Decision Problems. J. ACM 25(1): 116-133(1978) BibTeX

[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) BibTeX

[KG94]

...

[KKR95]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[Klu88]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[Kup93]

Gabriel M. Kuper: Aggregation in Constraint Databases. PPCP 1993: 166-173 BibTeX

[LRU96]

Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX

[LW94]

Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX

[Min61]

...

[PVV95]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87 BibTeX

[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) BibTeX

[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) BibTeX

[RL78]

C. R. Reddy, Donald W. Loveland: Presburger Arithmetic with Bounded Quantifier Alternation. STOC 1978: 320-325 BibTeX

[ST96]

Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27 BibTeX

[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 BibTeX

[vdM92]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 BibTeX

[VP75]

Leslie G. Valiant, Mike Paterson: Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350(1975) BibTeX

Referenced by

1. Jan Van den Bussche: Constraint databases: A tutorial introduction. SIGMOD Record 29(3): 44-51(2000)
2. Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini: Querying Aggregate Data. PODS 1999: 174-184
3. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
4. Nieves R. Brisaboa, Héctor J. Hernández, José R. Paramá, Miguel R. Penabad: Containment of Conjunctive Queries with Built-in Predicates with Variables and Constants over any Ordered Domain. ADBIS 1998: 46-57