Extended order-generic queries (Q1302301)

The authors consider (finite) relational databases over an ordered domain \(U\) with some additional relations. They study first-order queries that are invariant under order-preserving partial functions, so-called locally generic queries. They introduce various model-theoretic conditions on the first-order theory \(\text{Th}(U)\) of \(U\) that ensure that every locally generic query is equivalent to a pure order query in models of \(\text{Th}(U)\). The homogeneity property and the stronger property of quasi-o-minimality are among these conditions; they have turned out to be interesting notions from the model-theoretic point of view. The authors show how the results can be generalized to finitely presented databases.