On Order-Generic Queries
Oleg Belegradek, Alexei P. Stolboushkin, Michael A. Taitslin · 1996
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 ternary relation + 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. In fact, we consider two formalizations of this notion: "generic", and "locally generic", queries. For several domains order-generic queries fail to express more than pure order queries, for example, every order-generic query over rational numbers with + can be rewritten without +. Our goal is to find general conditions on the domain that allow for such a simplification of order-generic queries. An important difference of this paper from a recent series of related papers (see, for example, [14, 2]) is that we generalize all notions to the case of finitely representable database states---as opposed to finite states---and develop a ...