6533b850fe1ef96bd12a81df
RESEARCH PRODUCT
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases
Clemens LautemannNicole Schweikardtsubject
Infinite numberDatabaseLogic in computer scienceRelational databaseCollapse (topology)Database theorycomputer.software_genreMathematical proofFirst ordercomputerComputer Science::DatabasesMathematicsFirst-order logicdescription
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.
year | journal | country | edition | language |
---|---|---|---|---|
2001-01-01 |