Collapse results for query languages in database theory

S. M. Dudakov ; M. A. Taitslin

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 61 (2006) no. 2, pp. 195-253

Résumé

This is a survey of collapse results obtained mainly by members of the Tver State University seminar on the theoretical foundations of computer science. Attention is focused on the relative properties of isolation and pseudo-finite homogeneity and universes without the independence property. The Baldwin–Benedikt reducibility theorem is proved for these universes. The Dudakov boundedness theorem is proved for reducible theories. The relative isolation theorem is proved for reducible and bounded theories, and as a consequence the collapse theorem is obtained for reducible theories. It is noted that reducibility is equivalent to the relative property of isolation. On the other hand, results of Dudakov are presented showing that the effectively reducible theories having an effective almost indiscernible sequence admit an effective collapse of locally generic queries using not only ordering and titles of stored tables but also relations and operations in the universe, into queries not using relations and operations in the universe. Also presented is Dudakov's example of an enrichment of the Presburger arithmetic for which the collapse theorem fails but the elementary theory of the enrichment is decidable. This answers some open questions in the negative.