Finitely representable databases

DOI10.1006/jcss.1997.1524zbMath0887.68023OpenAlexW2037381552MaRDI QIDQ1376408

Stéphane Grumbach, Jianwen Su

Publication date: 17 December 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00120273/file/97jcss-grumbach-su.pdf

zbMATH Keywords

relational databasesfinitely representable databases

Mathematics Subject Classification ID

Database theory (68P15)

Related Items

A representation independent language for planar spatial databases with Euclidean distance ⋮ Metafinite model theory ⋮ Queries with arithmetical constraints ⋮ Linear constraint query languages expressive power and complexity ⋮ Topological elementary equivalence of regular semi‐algebraic sets in three‐dimensional space ⋮ Metafinite model theory ⋮ Aggregate operators in constraint query languages ⋮ Uniform generation in spatial constraint databases and applications ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Constraint-generating dependencies ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries ⋮ Extended order-generic queries ⋮ Querying spatial databases via topological invariants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic and calculus query languages for recursively typed complex objects
• Finite-model theory -- A personal perspective
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The complexity of elementary algebra and geometry
• Computable queries for relational data bases
• Datalog extensions for database queries and updates
• On the expressive power of database queries with intermediate types
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Domain independence and the relational calculus
• The elementary theory of restricted analytic fields with exponentiation
• Metafinite model theory
• Model theory
• Structure and complexity of relational queries
• Completeness results for recursive data bases
• Indexing for data models with constraints and classes
• An application of games to the completeness problem for formalized theories
• Parity, circuits, and the polynomial-time hierarchy
• Relative Information Capacity of Simple Relational Database Schemata
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Sentences true in all constructive models
• Probabilities on finite models
• First-Order Queries on Finite Structures Over the Reals
• A relational model of data for large shared data banks