An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

DOI10.1016/J.IC.2006.10.002zbMATH Open1110.68035arXivcs/0212049OpenAlexW1979165044MaRDI QIDQ870360FDOQ870360

Nicole Schweikardt

Publication date: 12 March 2007

Published in: Information and Computation (Search for Journal in Brave)

Abstract: We present a new Ehrenfeucht-Fraisse game approach to collapse results in database theory and we show that, in principle, this approach suffices to prove every natural generic collapse result. Following this approach we can deal with certain infinite databases where previous, highly involved methods fail. We prove the natural generic collapse for Z-embeddable databases over any linearly ordered context structure with arbitrary monadic predicates, and for N-embeddable databases over the context structure (R,<,+,Mon_Q,Groups). Here, N, Z, R, denote the sets of natural numbers, integers, and real numbers, respectively. Groups is the collection of all subgroups of (R,+) that contain Z, and Mon_Q is the collection of all subsets of a particular infinite subset Q of N. Restricting the complexity of the formulas that may be used to formulate queries to Boolean combinations of purely existential first-order formulas, we even obtain the collapse for N-embeddable databases over any linearly ordered context structure with arbitrary predicates. Finally, we develop the notion of N-representable databases, which is a natural generalization of the classical notion of finitely representable databases. We show that natural generic collapse results for N-embeddable databases can be lifted to the larger class of N-representable databases. To obtain, in particular, the collapse result for (N,<,+,Mon_Q), we explicitly construct a winning strategy for the duplicator in the presence of the built-in addition relation +. This, as a side product, also leads to an Ehrenfeucht-Fraisse game proof of the theorem of Ginsburg and Spanier, stating that the spectra of FO(<,+)-sentences are semi-linear.

Full work available at URL: https://arxiv.org/abs/cs/0212049

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

• Stability theory, permutations of indiscernibles, and embedded finite models
• Elements of finite model theory.
• An application of games to the completeness problem for formalized theories
• Finite model theory and its applications.
• Relational queries over interpreted structures
• Extended order-generic queries
• Arithmetic, first-order logic, and counting quantifiers
• Relational expressive power of constraint query languages
• A collapse result for constraint queries over structures of small degree
• First-order queries on databases embedded in an infinite structure
• Querying spatial databases via topological invariants
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• On sets of relations definable by addition
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• On complexity of Ehrenfeucht-Fraïssé games

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On complexity of Ehrenfeucht-Fraïssé games 👍 👎
• On the Ehrenfeucht-Fraïssé game in theoretical computer science 👍 👎
• A collapse result for constraint queries over structures of small degree 👍 👎
• Games and total Datalog\(^{\lnot}\) queries 👍 👎
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures 👍 👎
• On Complexity of Ehrenfeucht-Fraïssé Games 👍 👎
• Ehrenfeucht-Fraïssé games in finite set theory 👍 👎

This page was built for publication: An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

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