6533b850fe1ef96bd12a81df

RESEARCH PRODUCT

An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases

Clemens LautemannNicole Schweikardt

subject

Infinite numberDatabaseLogic in computer scienceRelational databaseCollapse (topology)Database theorycomputer.software_genreMathematical proofFirst ordercomputerComputer Science::DatabasesMathematicsFirst-order logic

description

We present a new proof technique for collapse results for first-order queries on databases which are embedded in N or R>o. Our proofs are by means of an explicitly constructed winning strategy for Duplicator in an Ehrenfeucht-FraissE game, and can deal with certain infinite databases where previous, highly involved methods fail. Our main result is that first-order logic has the natural-generic collapse over {N,≤ ,+} for arbitrary (i.e., possibly infinite) databases. Furthermore, a first application of this result shows the natural-generic collapse of first-order logic over {R>o,≤,+} for a certain kind of databases over R>o which consist of a possibly infinite number of regions.

https://doi.org/10.1007/3-540-44693-1_40