Michael Benedikt, Leonid Libkin  @ NUS Home/Search
Context Related
| belllabs.com/~benedikt...sqcfin.cop.ps belllabs.com/user/bene...sqcfin.cop.ps Cached: PS.gz PS PDF Image Update Help From: belllabs.com/~benedikt/ (more) From: belllabs.com/user/benedikt/ (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We study the structure of first-order and secondorder 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.... (Update)
Context of citations to this paper: More
.... theorem of algebra) More recently, it was shown that the exponential field hR; Delta; e x i is o minimal [34] Theorem 2 ([8, 9]) Let M be an o minimal structure admitting quantifier elimination. Then M admits the natural active collapse: FO(M;SC) FO act (M;SC) 2...
...to get expressivity and complexity bounds for nonboolean queries. Section 7 contains concluding remarks. All proofs can be found in [5]. 2. Notations Assume that the domain is an infinite set U. A schema is a nonempty collection SC = hR 1 ; R k i of relation names,...
Cited by: More
Relational Expressive Power of Constraint Query Languages - Benedikt, Dong, Libkin, Wong (1995) (Correct)
Querying Aggregate Data - Grumbach, Rafanelli, Tininini (1999) (Correct)
Safe Constraint Queries - Benedikt, Libkin (1998) (Correct)
Active bibliography (related documents): More All
1.4: On the Structure of Queries in Constraint Query Languages - Benedikt, Libkin (1996) (Correct)
0.4: Relational Queries over Interpreted Structures - Benedikt, Libkin (Correct)
0.3: Embedded Finite Models, Stability, and the Impact of Order - Baldwin, Benedikt (1998) (Correct)
Similar documents based on text: More All
0.5: Languages for Relational Databases over Interpreted Structures - Benedikt, Libkin (1997) (Correct)
0.4: Reachability and Connectivity Queries in Constraint.. - Benedikt, Grohe.. (1999) (Correct)
0.4: Verifiable Properties of Database Transactions - Benedikt, Griffin, al. (1998) (Correct)
Related documents from co-citation: More All
20: Relational expressive power of constraint query languages - Benedikt, Dong et al. - 1995
16: First-order queries on finite structures over the reals - Paredaens, Van den Bussche et al. - 1995
15: Foundations of databases (context) - Abiteboul, Hull et al. - 1995
BibTeX entry: (Update)
M. Benedikt and L. Libkin. On the structure of queries in constraint query languages. In Proceedings of IEEE Symposium on Logic in Computer Science, 1996, to appear. http://citeseer.comp.nus.edu.sg/65568.html More
@misc{ benedikt96structure,
author = "M. Benedikt and L. Libkin",
title = "the structure of queries in constraint query languages",
text = "M. Benedikt and L. Libkin. On the structure of queries in constraint query
languages. In Proceedings of IEEE Symposium on Logic in Computer Science,
1996, to appear.",
year = "1996",
url = "citeseer.comp.nus.edu.sg/65568.html" }
Citations (may not include all citations):775 Foundations of Databases (context) - Abiteboul, Hull et al. - 1995
315 Constraint query languages - Kanellakis, Kuper et al. - 1995
227 North Holland (context) - Chang, Keisler - 1990
189 Computable queries for relational databases - Chandra, Harel - 1980
163 Universality of data retrieval languages (context) - Aho, Ullman
141 The Complexity of Finite Functions (context) - Boppana, Sipser - 1990
116 On uniformity within NC - Barrington, Immerman et al. - 1990
116 On local and non-local properties (context) - Gaifman - 1982
87 Towards a theory of spatial database queries (context) - Paredaens, Van den Bussche et al.
83 Relational expressive power of constraint query languages - Benedikt, Dong et al. - 1995
72 Finitely representable databases - Grumbach, Su
57 The complexity of elementary algebra and geometry (context) - Ben-Or, Kozen et al. - 1986
48 Linear Orderings (context) - Rosenstein - 1982
46 Rothschild and J (context) - Graham - 1990
44 First-order queries on finite structures over the reals - Paredaens, Van den Bussche et al.
41 Topological queries in spatial databases - Papadimitriou, Suciu et al.
40 Definable sets in ordered structures (context) - Pillay, Steinhorn - 1984
31 Linear constraint databases (context) - Grumbach, Su et al. - 1994
27 The elementary theory of restricted analytic fields with exp.. (context) - Van den Dries, Macintyre et al. - 1994
23 Domain independence and the relational calculus - Hull, Su - 1994
16 Constraint programming and database languages: A tutorial (context) - Kanellakis
16 Firstorder queries on databases embedded in an infinite stru.. - Otto, Van den Bussche - 1995
14 First-order definability over constraint databases (context) - Grumbach, Su - 1995
10 Descriptive complexity: A logician 's approach to computatio.. - Immerman - 1995
10 Parallel computation and threshold functions (context) - Parberry, Schnitger - 1988
9 The isomorphism property in nonstandard analysis and its use.. (context) - Henson - 1974
6 Combinatorial Set Theory: Partition Relations for Cardinals (context) - Erdos, Hajnal et al. - 1984
2 Languages for collection types: A tutorial (context) - Tannen
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.bell-labs.com/~benedikt/):
Exact and Approximate Aggregation in Constraint Query Languages - Benedikt, Libkin (1998) (Correct)
A Decidable Logic for Describing Linked Data Structures - Benedikt, Reps, Sagiv (1999) (Correct)
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.