Safe Constraint Queries
Summary: Syntactic characterization of safe queries in relational calculus extended with interpreted functions (e.g., real +, ×, exponentiation), giving an interpreted analogue of range-restriction and an effective syntax for real-arithmetic/polynomial queries. Shows decidability of safety for Boolean combinations of CQs over broad interpreted structures, proves a polynomial output-growth dichotomy, and applies results to finitely representable and geometric (convex/polyhedral/semi-linear) databases. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Michael Benedikt (AT&T)
- 2. Leonid Libkin (AT&T)
BibTeX Citation
@inproceedings{benedikt_pods98,
address = {New York, NY, USA},
series = {{PODS} '98},
title = {{Safe Constraint Queries}},
url = {https://dl.acm.org/doi/10.1145/275487.275499},
doi = {10.1145/275487.275499},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Benedikt, Michael and Libkin, Leonid},
year = {1998}
}Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,203 | An Expressive Language for Linear Spatial Database Queries (extended abstract) | 1998 | PODS | 6.8354052e-05 |
| 4,543 | Exact and Approximate Aggregation in Constraint Query Languages | 1999 | PODS | 6.6388258e-05 |
| 6,184 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS | 5.9488379e-05 |
| 12,626 | Index-Based Multidimensional Array Queries: Safety and Equivalence | 2007 | PODS | 5.093636e-05 |
| 12,857 | String Operations in Query Languages | 2001 | PODS | 5.093636e-05 |
| 12,876 | Linear approximation of planar spatial databases using transitive-closure logic | 2000 | PODS | 5.093636e-05 |
| 12,879 | Uniform Generation in Spatial Constraint Databases and Applications | 2000 | PODS | 5.093636e-05 |
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.
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,002 | An Effective Syntax for Bounded Relational Queries | 2016 | SIGMOD |
| 2 | 3,730 | Safety and Correct Translation of Relational Calculus Formulas | 1987 | PODS |
| 3 | 6,077 | Safety of Datalog Queries over Infinite Databases | 1989 | PODS |
| 4 | 382 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS |
| 5 | 4,336 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS |
| 6 | 1,498 | Safety of Recursive Horn Clauses With Infinite Relations | 1987 | PODS |
| 7 | 6,286 | Finite Queries do not Have Effective Syntax | 1995 | PODS |
| 8 | 1,630 | On the Decidability of Query Containment under Constraints | 1998 | PODS |
| 9 | 3,025 | An Axiomatic Approach to Deciding Query Safety in Deductive Databases | 1988 | PODS |
| 10 | 1,890 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS |