Article

Free access

Safe constraint queries

Authors:

Michael Benedikt,

Leonid LibkinAuthors Info & Claims

PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 99 - 108

https://doi.org/10.1145/275487.275499

Published: 01 May 1998 Publication History

PDF eReader

References

[1]

S, Abiteboul, R. Hull and V. Vianu. Foundations of Databases, Addison-Wesley, 1995.

Digital Library

Google Scholar

[2]

A,K. Ailamazyan, M.M. Gilula, A.P. Stolboushkin and G,F, Shvarts. Reduction of a relational modal with infinite domains to the finite-domain ease. Doklady Akademii Nauk SSSR, 286 (1) (1986), 308-311. Translation in Soviet Physics - Doklady, 31 (1986), 11-13.

Google Scholar

[3]

A, Avron and J. Hirshfeld. On first order database query languages. In LIGSJ91, pages 226-231.

Google Scholar

[4]

M, Benedikt, G. Dong, L. Libkin and L. Wont. Relational expressive power of constraint query languages. J, A GM, 45 (1998). Extended abstract in PODS'96.

Digital Library

Google Scholar

[5]

M. Benedikt and L. Libkin. Languages for rdational databases over interpreted structures. In PODS'97, pages 87-98.

Digital Library

Google Scholar

[6]

M, Benedikt and L. Libkin. Safe constraint queries. Technical Memo, Bell Labs, 1997.

Google Scholar

[7]

C,C, Chang and H.J. Keisler. Model Theory. North Holland, 1990.

Google Scholar

[8]

M, Davis. On the number of solutions of Diophantine equations, Proc. AMS 35 (1972), 552-554.

Crossref

Google Scholar

[9]

F, Dumortier, M. Gyssens, L. Vandeurzen, and D. Van Gucht, On the decidability of semi-linearity of nemi-algebraie sets, and its implications for spatial databases. In PODS'97, pages 68-77.

Digital Library

Google Scholar

[10]

M, Escobar.Molano, R. Hull and D. Jaeobs. Safety and translation of calculus queries with scalar functions. In PODS'93, pages 253-264.

Digital Library

Google Scholar

[11]

S, Grumbach and J. Su. Finitely representable databases, JGSS 55 (1997), 273-298.

Digital Library

Google Scholar

[12]

S, Grumbaeh, J. Su, and C. Tollu. Linear constraint databases. In LCC'9}~, pages 426-446.

Digital Library

Google Scholar

[13]

R, Hull and J. Su. Domain independence and the rdational calculus. Acta Informatica 31:513-524, 1994.

Digital Library

Google Scholar

[14]

O,H, Ibarra and J, Su. On the containment and equivalence of database queries with linear constraints. In PODSJ97, pages 32-43.

Digital Library

Google Scholar

[15]

P, Kanellakis, G. Kuper, and P. Revesz. Constraint query languages. JCSS, 51 (1995), 26-52. Extended abstract in PODS'90, pages 299-313.

Digital Library

Google Scholar

[16]

M, Kifer, On safety, domain independence, and capturability of database queries. In Proc. Data and Knowledge Base, Jerusalem, 1988.

Google Scholar

[17]

M. Kifer, R. Ramakrishnan and A. Silberschatz. An axiomatic approach to deciding query safety in deductive databases. In PODS'88, pages 52-60.

Digital Library

Google Scholar

[18]

W. Neff Beitr~ge zur Theorie der Polyeder. Herbert Lung, Bern, 1978.

Google Scholar

[19]

:I. O'Rourke. Computational Geometry in G. Cambridge Univ. Press, 1994.

Digital Library

Google Scholar

[20]

J. Paredaens, J. Van den Bussche, and D. Van Gucht. Towards a theory of spatial database queries. In PODS'94, pages 279-288.

Digital Library

Google Scholar

[21]

J. Paredaens, J. Van den Bussche, and D. Van Gucht. First-order queries on finite structures over the reals. In {,ICS'95, pages 79-87.

Digital Library

Google Scholar

[22]

:I. Paredaens, B. Kuijpers, G. Kuper and L. Vandeurzen. Euclid, Tarski and Engeler encompassed. In DBPI,'97, Springer LNCS, to appear.

Google Scholar

[23]

R. Ramakrishnan, F. Bancilhon and A. Silberschatz. Safety of recursive Horn clauses with infinite relations. In PODS'87, pages 328-339.

Digital Library

Google Scholar

[24]

P. Revesz. Safe query languages for constraint databases. ACM TODS, to appear.

Digital Library

Google Scholar

[25]

R.T. Rockafellar. Convex Analysis. Princeton Univ. Press, 1970.

Crossref

Google Scholar

[26]

J. Ruppert and R. Seidel. On the difficulty of triangulating three-dimensional nonconvex polyhedra. Discrete and Computational Geometry 7 (1992), 227-254.

Digital Library

Google Scholar

[27]

Y. Sagiv and M. Yannakalds. Equivalence among relational expressions with the union and difference operators. J. A CM 27 (1980), 633-655.

Digital Library

Google Scholar

[28]

A. Stolboushkin and M. Tsaitlin. Finite queries do not have effective syntax, in PODS'95, pages 277-285,

Digital Library

Google Scholar

[29]

A. Stolboushkin and M.Tsaitlin. Linear vs. order constraint queries over rational databases. In PODS'96, pages 17-27.

Digital Library

Google Scholar

[30]

A. Stolboushkin and M. Tsaitlin. Safe stratified datalog with integer order does not have syntax. A CM TODS, to appear.

Digital Library

Google Scholar

[31]

L. van den Dries. O-minimal structures. In Logic: From Foundations to Applications, W. Hodges, et al, eds, Clarendon Press, 1996.

Digital Library

Google Scholar

[32]

L. Vandeurzen, M. Gyssens and D. Van Gueht. On query languages for linear queries definable with polynomial constraints. In CP'96, pages 468-481.

Google Scholar

[33]

L. Vandeurzen, M. Gyssens and D. Van Gucht. An expressive language for linear spatial database queries. This volume.

Digital Library

Google Scholar

[34]

M. Vardi. The decision problem for database dependencies. Inf. Proc. Let., 12 (1981), 251-254.

Crossref

Google Scholar

[35]

A.J. Wiltde. Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Amer. Math. Soc. 9 (1996), 1051-1094.

Crossref

Google Scholar

Cited By

View all

Nieva SSánchez-Hernández JSáenz-Pérez F(2008)Formalizing a Constraint Deductive Database Language Based on Hereditary Harrop Formulas with NegationFunctional and Logic Programming10.1007/978-3-540-78969-7_21(289-304)Online publication date: 2008
https://doi.org/10.1007/978-3-540-78969-7_21
Vandeurzen LGyssens MVan Gucht D(2001)On the expressiveness of linear-constraint query languages for spatial databasesTheoretical Computer Science10.1016/S0304-3975(99)00316-3254:1-2(423-463)Online publication date: 6-Mar-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2899%2900316-3
Grahne GWaller E(2001)How to Make SQL Stand for String Query LanguageResearch Issues in Structured and Semistructured Database Programming10.1007/3-540-44543-9_5(61-79)Online publication date: 13-Apr-2001
https://doi.org/10.1007/3-540-44543-9_5
Show More Cited By

Index Terms

Safe constraint queries
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
    2. Query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Safe Constraint Queries

We extend some of the classical characterization theorems of relational database theory---particularly those related to query safety---to the context where database elements come with fixed interpreted structure and where formulae over elements of that ...
Safe Datalog Queries with Linear Constraints
CP '98: Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming

In this paper we consider Datalog queries with linear constraints. We identify several syntactical subcases of Datalog queries with linear constraints, called safe queries, and show that the least model of safe Datalog queries with linear constraints ...
Containment of Conjunctive Queries with Safe Negation
ICDT '03: Proceedings of the 9th International Conference on Database Theory

We consider the problem of query containment for conjunctive queries with safe negated subgoals ( CQ s). We propose a new method for the containment test of CQ s. Comparing to the previous known approach, which always requires an exponential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

May 1998

286 pages

ISBN:0897919963

DOI:10.1145/275487

Chairmen:
Alberto Mendelson
Univ. of Toronto
,
Jan Paredaens
Univ. of Antwerp

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS98

Sponsor:

SIGMOD/PODS98: Special Interest Group on Management of Data

June 1 - 4, 1998

Washington, Seattle, USA

Acceptance Rates

PODS '98 Paper Acceptance Rate 28 of 119 submissions, 24%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nieva SSánchez-Hernández JSáenz-Pérez F(2008)Formalizing a Constraint Deductive Database Language Based on Hereditary Harrop Formulas with NegationFunctional and Logic Programming10.1007/978-3-540-78969-7_21(289-304)Online publication date: 2008
https://doi.org/10.1007/978-3-540-78969-7_21
Vandeurzen LGyssens MVan Gucht D(2001)On the expressiveness of linear-constraint query languages for spatial databasesTheoretical Computer Science10.1016/S0304-3975(99)00316-3254:1-2(423-463)Online publication date: 6-Mar-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2899%2900316-3
Grahne GWaller E(2001)How to Make SQL Stand for String Query LanguageResearch Issues in Structured and Semistructured Database Programming10.1007/3-540-44543-9_5(61-79)Online publication date: 13-Apr-2001
https://doi.org/10.1007/3-540-44543-9_5
Kuper GSu J(2001)A Representation Independent Language for Planar Spatial Databases with Euclidean DistanceResearch Issues in Structured and Semistructured Database Programming10.1007/3-540-44543-9_15(239-251)Online publication date: 13-Apr-2001
https://doi.org/10.1007/3-540-44543-9_15
Grohe MSegoufin L(2000)On first-order topological queriesProceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.99CB36332)10.1109/LICS.2000.855783(349-360)Online publication date: 2000
https://doi.org/10.1109/LICS.2000.855783
Gyssens MVandeurzen LVan Gucht D(2000)Linear-Constraint DatabasesConstraint Databases10.1007/978-3-662-04031-7_9(199-229)Online publication date: 2000
https://doi.org/10.1007/978-3-662-04031-7_9
Benedikt MLibkin L(2000)Query Safety with ConstraintsConstraint Databases10.1007/978-3-662-04031-7_5(109-129)Online publication date: 2000
https://doi.org/10.1007/978-3-662-04031-7_5
Benedikt MLibkin L(2000)Expressive Power: The Finite CaseConstraint Databases10.1007/978-3-662-04031-7_3(55-87)Online publication date: 2000
https://doi.org/10.1007/978-3-662-04031-7_3
Liu HYu J(1999)Safe Database Queries with External FunctionsProceedings of the 1999 International Symposium on Database Engineering & Applications10.5555/850953.853893Online publication date: 2-Aug-1999
https://dl.acm.org/doi/10.5555/850953.853893
Hong-Cheu Liu Yu J(1999)Safe database queries with external functionsProceedings. IDEAS'99. International Database Engineering and Applications Symposium (Cat. No.PR00265)10.1109/IDEAS.1999.787276(260-269)Online publication date: 1999
https://doi.org/10.1109/IDEAS.1999.787276
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Safe Constraint Queries

Safe Datalog Queries with Linear Constraints

Containment of Conjunctive Queries with Safe Negation