Download now Free registration required
The authors present a new Ehrenfeucht-Fraisse game approach to collapse results in database theory. They show that, in principle, every natural generic collapse result may be proved via a translation of winning strategies for the duplicator in an Ehrenfeucht-Fraisse game. Following this approach, they can deal with certain infinite databases where previous, highly involved methods fail. Restricting the complexity of the formulas that may be used to formulate queries to Boolean combinations of purely existential first-order formulas, they even obtain the collapse for Nembeddable databases over any linearly ordered context structure with arbitrary predicates.
- Format: PDF
- Size: 738.01 KB