An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory

Details An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory

2002-12-20

arxiv.org/abs/cs/0212049v1

Computer Science

Logic in Computer Science

70 pages, 9 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-724592