First-Order Queries on Finite Structures Over the Reals

DOI10.1137/S009753979629766MaRDI QIDQ4210130zbMATH OpenOpenAlexFDO

Authors Jan Paredaens, Jan Van den Bussche, D. Van Gucht

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979629766

zbMATH Keywords

constraint programmingrelational databasesfirst-order logiclinear arithmetic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Database theory (68P15) Basic properties of first-order languages and structures (03C07) Quantifier elimination, model completeness, and related topics (03C10)

Recommendations

• First-order queries on classes of structures with bounded expansion
• First-order queries on databases embedded in an infinite structure
• On first-order topological queries
• First-order definability on finite structures
• First-order definable counting-only queries
• First-order definable counting-only queries
• Complexity of the first-order theory of almost all finite structures
• First-order queries on finite abelian groups
• Logical quantizations of first-order structures
• Finite quantifier hierarchies in relational algebras

Cited in

(20)

• First-order queries on structures of bounded degree are computable with constant delay
• Aggregate operators in constraint query languages
• Linear constraint query languages expressive power and complexity
• scientific article; zbMATH DE number 1418323 (Why is no real title available?)
• Ehrenfeucht-Fraïssé goes automatic for real addition
• Finitely representable databases
• Queries with arithmetical constraints
• A collapse result for constraint queries over structures of small degree
• Expressing the box cone radius in the relational calculus with real polynomial constraints
• A representation independent language for planar spatial databases with Euclidean distance
• First-Order Queries over One Unary Function
• Stability theory, permutations of indiscernibles, and embedded finite models
• Reachability and connectivity queries in constraint databases
• On first-order topological queries
• First-order definable counting-only queries
• A technique for proving decidability of containment and equivalence of linear constraint queries
• First-order queries on databases embedded in an infinite structure
• scientific article; zbMATH DE number 1848311 (Why is no real title available?)
• The past and future of embedded finite model theory
• On the expressiveness of linear-constraint query languages for spatial databases

This page was built for publication: First-Order Queries on Finite Structures Over the Reals

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