Extended order-generic queries

DOI10.1016/S0168-0072(98)00025-6MaRDI QIDQ1302301zbMATH OpenOpenAlexFDO

Authors Oleg Belegradek, Alexei P. Stolboushkin, Michael A. Taitslin

Publication date 13 March 2001

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0168-0072(98)00025-6

zbMATH Keywords

embedded finite modelsfinitely presented databasesfirst-order querieslocally generic queriesquasi-o-minimalityrelational databases

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Models with special properties (saturated, rigid, etc.) (03C50) Database theory (68P15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1114329
• First-order queries on databases embedded in an infinite structure
• scientific article; zbMATH DE number 1848311
• scientific article; zbMATH DE number 1302667

Cites work

• Classification theory and the number of non-isomorphic models.
• Computable queries for relational data bases
• Definability and decision problems in arithmetic
• Definable Sets in Ordered Structures. I
• Definable Sets in Ordered Structures. II
• Definable Sets in Ordered Structures. III
• Finitely representable databases
• First-order queries on databases embedded in an infinite structure
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 1114329 (Why is no real title available?)
• scientific article; zbMATH DE number 1479611 (Why is no real title available?)
• scientific article; zbMATH DE number 3382339 (Why is no real title available?)
• Model theory.
• The comparison of the expressive power of first-order dynamic logics
• Ultrahomogeneous Structures

Cited in

(16)

• Metafinite model theory
• Coset-minimal groups
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Invariance to ordinal transformations in rank-aware databases
• Pseudofinite homogeneity, isolation, and reducibility
• In memoriam: Mikhail A. Taitslin, 1936--2013
• Query Order
• scientific article; zbMATH DE number 1114329 (Why is no real title available?)
• Stability theory, permutations of indiscernibles, and embedded finite models
• scientific article; zbMATH DE number 975710 (Why is no real title available?)
• Sufficient conditions for effective translation of locally generic queries
• A general condition for collapse results
• The past and future of embedded finite model theory
• On o-Stable Expansions of $$\boldsymbol{(\mathbb{Z},<,+)}$$
• Aggregate operators in constraint query languages
• An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

This page was built for publication: Extended order-generic queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1302301)