More Web Proxy on the site http://driver.im/

Article

On the Structure of Queries in Constraint Query Languages

Authors:

Michael Benedikt,

Leonid LibkinAuthors Info & Claims

LICS '96: Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science

Page 25

Published: 27 July 1996 Publication History

Abstract

We study the structure of first-order and second-order queries over constraint databases. Constraint databases are formally modeled as finite relational structures embedded in some fixed infinite structure. We concentrate on problems of elimination of constraints, reducing quantification range to the active domain of the database and obtaining new complexity bounds. We show that for a large class of signatures, including real arithmetic constraints, unbounded quantification can be eliminated. That is, one can transform a sentence containing unrestricted quantification over the infinite universe to get an equivalent sentence in which quantifiers range over the finite relational structure. We use this result to get a new complexity upper bound on the evaluation of real arithmetic constraints. We also expand upon techniques in [21] and [4] for getting upper bounds on the expressiveness of constraint query languages, and apply it to a number of first-order and second-order query languages.

References

[1]

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

[2]

A. V. Aho and J. D. Ullman. Universality of data retrieval languages. In POPL'79, pages 110-120.

Digital Library

[3]

D.A. Barrington, N. Immerman, H. Straubing. On uniformity within NC¹ ¿ JCSS, 41:274-306, 1990.

[4]

M. Benedikt, G. Dong, L. Libkin and L. Wong. Relational expressive power of constraint query languages. In PODS'96, pages 5-16.

Digital Library

[5]

M. Benedikt and L. Libkin. On the structure of queries in constraint query languages. Bell Labs Technical Memo, 1995.

[6]

M. Ben-Or, D. Kozen, J. Reif. The complexity of elementary algebra and geometry. JCSS, 32:251-264, 1986.

[7]

R.B. Boppana and M. Sipser. The Complexity of Finite Functions. In Handbook of Theoretical Computer Science, Vol. A, chapter 14, (J. van Leeuwen editor), North-Holland, 1990.

[8]

A. Chandra and D. Harel. Computable queries for relational databases. JCSS, 21(2):156-178, 1980.

[9]

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

[10]

P. Erdös, A. Hajnal, A. Máté and R. Rado. Combinatorial Set Theory: Partition Relations for Cardinals. North Holland, 1984.

[11]

H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium '81, pages 105-135, North Holland, 1982.

[12]

R.L. Graham, B.L. Rothschild and J.H. Spencer. Ramsey Theory. John Wiley & Sons, 1990.

[13]

S. Grumbach and J. Su. Finitely representable databases, In PODS'94, pages 289-300.

Digital Library

[14]

S. Grumbach and J. Su. First-order definability over constraint databases. Proc. Conf. on Constr. Progr., 1995.

[15]

S. Grumbach, J. Su, and C. Tollu. Linear constraint databases. In Proceedings of Logic and Comput. Complexity, 1994, pages 426-446.

[16]

C.W. Henson. The isomorphism property in nonstandard analysis and its use in the theory of Banach spaces. Journal of Symbolic Logic 39 (1974), 717-731.

[17]

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

[18]

N. Immerman. Descriptive complexity: A logician's approach to computation. Notices of the AMS 42 (1995), 1127-1133.

[19]

P. Kanellakis. Constraint programming and database languages: A tutorial. In PODS'95, pages 46-53.

Digital Library

[20]

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

[21]

M. Otto and J. Van den Bussche. First-order queries on databases embedded in an infinite structure. Technical Report, University of Antwerp, October 1995.

[22]

C. Papadimitriou, D. Suciu and V. Vianu. Topological queries in spatial databases. In PODS'96, pages 81-92.

Digital Library

[23]

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

[24]

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

Digital Library

[25]

A. Pillay, C. Steinhorn. Definable sets in ordered structures. Bulletin of the AMS 11 (1984), 159-162.

[26]

J. G. Rosenstein. Linear Orderings. Academic Press, New York, 1982.

[27]

V. Tannen. Languages for collection types: A tutorial. in PODS'94, pages 150-154.

Digital Library

[28]

L. Van den Dries, A. Macintyre and D. Marker. The elementary theory of restricted analytic fields with exponentiation. Annals of Mathematics 85 (1994), 19-56.

Cited By

Dantsin EEiter TGottlob GVoronkov A(2001)Complexity and expressive power of logic programmingACM Computing Surveys10.1145/502807.50281033:3(374-425)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1145/502807.502810
Grumbach SRafanelli MTininini LVianu VPapadimitriou C(1999)Querying aggregate dataProceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/303976.303994(174-184)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/303976.303994
Benedikt MLibkin LMendelzon AÖzsoyoglu Z(1997)Languages for relational databases over interpreted structuresProceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/263661.263672(87-98)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/263661.263672
Show More Cited By

On the Structure of Queries in Constraint Query Languages
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Constraint query languages
Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls
ICDT '01: Proceedings of the 8th International Conference on Database Theory

We define various extensions of first-order logic on linear as well as polynomial constraint databases. First, we extend first-order logic by a convex closure operator and show this logic, FO(conv), to be closed and to have Ptime data-complexity. We ...
Constraint Query Languages

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

LICS '96: Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science

July 1996

ISBN:0818674636

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 27 July 1996

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dantsin EEiter TGottlob GVoronkov A(2001)Complexity and expressive power of logic programmingACM Computing Surveys10.1145/502807.50281033:3(374-425)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1145/502807.502810
Grumbach SRafanelli MTininini LVianu VPapadimitriou C(1999)Querying aggregate dataProceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/303976.303994(174-184)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/303976.303994
Benedikt MLibkin LMendelzon AÖzsoyoglu Z(1997)Languages for relational databases over interpreted structuresProceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/263661.263672(87-98)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/263661.263672
Ibarra OSu JMendelzon AÖzsoyoglu Z(1997)On the containment and equivalence of database queries with linear constraints (extended abstract)Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/263661.263666(32-43)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/263661.263666
Basu SChar BWang P(1997)Uniform quantifier elimination and constraint query processingProceedings of the 1997 international symposium on Symbolic and algebraic computation10.1145/258726.258739(21-27)Online publication date: 1-Jul-1997
https://dl.acm.org/doi/10.1145/258726.258739
Stolboushkin ATaitslin MHull R(1996)Linear vs. order constraint queries over rational databases (extended abstract)Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/237661.237669(17-27)Online publication date: 3-Jun-1996
https://dl.acm.org/doi/10.1145/237661.237669
Benedikt MDong GLibkin LWong LHull R(1996)Relational expressive power of constraint query languagesProceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/237661.237667(5-16)Online publication date: 3-Jun-1996
https://dl.acm.org/doi/10.1145/237661.237667

View Options

View options

Media

Figures

Other

Tables

View Table of Contents