On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)
Summary: Introduces counter‑machine techniques to decide containment/equivalence of queries with linear arithmetic constraints over Z, N, Q, R. Shows 2-EXPTIME decidability (EXPTIME lower bound) for CQs over Z/N, 2-EXPTIME for constant‑free CQs over Q/R, 2-EXPSPACE for general Q/R via FO‑reals, and decidability for connected FO queries on bounded‑degree databases. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Oscar H. Ibarra (University of California Santa Barbara)
- 2. Jianwen Su (University of California Santa Barbara)
BibTeX Citation
@inproceedings{ibarra_pods97,
address = {New York, NY, USA},
series = {{PODS} '97},
title = {{On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)}},
url = {https://dl.acm.org/doi/10.1145/263661.263666},
doi = {10.1145/263661.263666},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Ibarra, Oscar H. and Su, Jianwen},
year = {1997}
}
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,305 | Querying Aggregate Data | 1999 | PODS | 8.7766218e-05 |
| 4,226 | Safe Constraint Queries | 1998 | PODS | 6.8211482e-05 |
| 12,626 | Index-Based Multidimensional Array Queries: Safety and Equivalence | 2007 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 97 | Efficient Optimization of a Class of Relational Expressions | 1978 | SIGMOD | 0.00034574497 |
| 309 | Optimization of Real Conjunctive Queries | 1993 | PODS | 0.00021768596 |
| 633 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00015560958 |
| 889 | Constraint Programming and Database Languages: A Tutorial | 1995 | PODS | 0.00013398105 |
| 1,031 | Answering Queries Using Limited External Query Processors | 1996 | PODS | 0.0001253927 |
| 1,890 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS | 9.5330753e-05 |
| 2,241 | Finitely Representable Databases | 1994 | PODS | 8.8845324e-05 |
| 4,013 | Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract) | 1996 | PODS | 6.9565842e-05 |
| 5,523 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS | 6.1870017e-05 |
| 7,849 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS | 5.5324391e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,457 | Bag Query Containment and Information Theory | 2020 | PODS |
| 2 | 4,013 | Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract) | 1996 | PODS |
| 3 | 3,801 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS |
| 4 | 134 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS |
| 5 | 12,875 | Fixed-Point Query Languages for Linear Constraint Databases | 2000 | PODS |
| 6 | 5,523 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS |
| 7 | 1,269 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS |
| 8 | 382 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS |
| 9 | 7,886 | Polynomial-time program transformations in deductive databases | 1990 | PODS |
| 10 | 1,630 | On the Decidability of Query Containment under Constraints | 1998 | PODS |