Extended order-generic queries

Annals of Pure and Applied Logic 97 (1-3):85-125 (1999)

We consider relational databases organized over an ordered domain with some additional relations — a typical example is the ordered domain of rational numbers together with the operation of addition. In the focus of our study are the first-order queries that are invariant under order-preserving “permutations” — such queries are called order-generic. It has recently been discovered that for some domains order-generic FO queries fail to express more than pure order queries. For example, every order-generic FO query over rational numbers with + can be rewritten without +. For some other domains, however, this is not the case.We provide very general conditions on the FO theory of the domain that ensure the collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all the o-minimal domains, but also the ordered group of integer numbers and the ordered semigroup of natural numbers, and some other domains.An important difference of this paper from the recent series of related papers is that we generalize all the notions to the case of finitely representable database states — as opposed to finite states — and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finitely representable states. We show, however, that these results cannot be transfered to arbitrary infinite states
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(98)00025-6
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,683
Through your library

References found in this work BETA

Definability and Decision Problems in Arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.
Ultrahomogeneous Structures.Bruce I. Rose & Robert E. Woodrow - 1981 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 27 (2-6):23-30.
Ultrahomogeneous Structures.Bruce I. Rose & Robert E. Woodrow - 1981 - Mathematical Logic Quarterly 27 (2‐6):23-30.

Add more references

Citations of this work BETA

Coset-Minimal Groups.Oleg Belegradek, Viktor Verbovskiy & Frank O. Wagner - 2003 - Annals of Pure and Applied Logic 121 (2-3):113-143.
Finite and Infinite Model Theory-A Historical Perspective.John Baldwin - 2000 - Logic Journal of the IGPL 8 (5):605-628.
A General Condition for Collapse Results.Michael A. Taitslin - 2001 - Annals of Pure and Applied Logic 113 (1-3):323-330.
In Memoriam: Mikhail A. Taitslin 1936–2013.Oleg Belegradek & Boris Zilber - 2014 - Bulletin of Symbolic Logic 20 (1):99-102.

Add more citations

Similar books and articles

On Notions of Genericity and Mutual Genericity.J. K. Truss - 2007 - Journal of Symbolic Logic 72 (3):755 - 766.
The Distribution of the Generic Recursively Enumerable Degrees.Ding Decheng - 1992 - Archive for Mathematical Logic 32 (2):113-135.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Complexity of the -Query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
Recursive in a Generic Real.Juichi Shinoda & Theodore A. Slaman - 2000 - Journal of Symbolic Logic 65 (1):164-172.
The Degrees Below a 1-Generic Degree $.Christine Ann Haught - 1986 - Journal of Symbolic Logic 51 (3):770 - 777.
Generic Complexity of Undecidable Problems.Alexei G. Myasnikov & Alexander N. Rybalov - 2008 - Journal of Symbolic Logic 73 (2):656 - 673.


Added to PP index

Total views
12 ( #621,313 of 2,242,821 )

Recent downloads (6 months)
2 ( #814,790 of 2,242,821 )

How can I increase my downloads?


My notes

Sign in to use this feature