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.

Bibliographie

[1] E. F. Codd, “A relational model for large shared data banks”, Commun. ACM, 13:6 (1970), 377–387 | DOI | Zbl

[2] E. F. Codd, “Relational completeness of data base sublanguages”, Database systems, ed. R. Rustin, Prentice-Hall, Englewood Cliffs, NJ, 1972, 33–64

[3] O. V. Belegradek, A. P. Stolboushkin, M. A. Taitslin, “Extended order-generic queries”, Ann. Pure Appl. Logic, 97:1–3 (1999), 85–125 | DOI | MR | Zbl

[4] M. Benedikt, G. Dong, L. Libkin, L. Wong, “Relational expressive power of constraint query languages”, J. ACM, 45:1 (1998), 1–34 | DOI | MR | Zbl

[5] J. Baldwin, M. Benedikt, “Stability theory, permutations of indiscernibles, and embedded finite models”, Trans. Amer. Math. Soc., 352:11 (2000), 4937–4969 | DOI | MR | Zbl

[6] S. M. Dudakov, “Translyatsionnaya teorema v teoriyakh predikatnykh obogaschenii nachalnogo fragmenta nestandartnykh modelei arifmetiki Presburgera”, Slozhnye sistemy: obrabotka informatsii, modelirovanie i optimizatsiya, Tver. gos. un-t, Tver, 2002, 24–37

[7] S. M. Dudakov, “Translyatsionnyi rezultat dlya rasshirenii arifmetiki Presburgera odnomestnoi funktsiei, soglasovannoi so slozheniem”, Matem. zametki, 76:3 (2004), 362–371 | MR | Zbl

[8] S. M. Dudakov, “Translyatsionnaya teorema dlya teorii $I$-svodimykh algebraicheskikh sistem”, Izv. RAN. Ser. matem., 68:5 (2004), 67–90 | MR | Zbl

[9] I. V. Popov, “Eliminatsiya kvantorov v nekotorykh obogascheniyakh arifmetiki Presburgera”, Slozhnye sistemy: obrabotka informatsii, modelirovanie i optimizatsiya, Tver. gos. un-t, Tver, 2002, 38–47

[10] M. A. Taitslin, “Translyatsionnye rezultaty v teorii baz dannykh”, Slozhnye sistemy: obrabotka informatsii, modelirovanie i optimizatsiya, Tver. gos. un-t, Tver, 2002, 5–23

[11] M. A. Taitslin, “Ogranichennye psevdokonechnaya odnorodnost i izolirovannost”, Vestnik Tver. gos. un-ta, ser. «Prikladnaya matematika», vyp. 2, no. 2(2), Tver. gos. un-t, Tver, 2003, 5–15

[12] O. V. Belegradek, A. P. Stolboushkin, M. A. Taitslin, “Bazy dannykh nad fiksirovannym beskonechnym universumom”, Programmirovanie, 1998, no. 1, 6–17 | MR | Zbl

[13] S. M. Dudakov, “Razreshimaya teoriya bez translyatsionnoi teoremy”, Vestnik Tver. gos. un-ta, ser. «Prikladnaya matematika», vyp. 2, no. 6(12), Tver. gos. un-t, Tver, 2005, 23–26

[14] S. M. Dudakov, “Vyrazitelnaya sila yazykov zaprosov pervogo poryadka dlya baz dannykh na neuporyadochennom sluchainom grafe”, Vestnik NovgGU, 2005, no. 5, 45–50

[15] M. A. Taitslin, “A general condition for collapse results”, Ann. Pure Appl. Logic, 113:1–3 (2002), 323–330 | MR | Zbl

[16] A. Blumensath, E. Grädel, “Automatic structures”, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, CA, 2000, 51–62 | MR

[17] T. Iekh, Teoriya mnozhestv i metod forsinga, Mir, M., 1973 | MR | Zbl

[18] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1977 | MR

[19] S. Shelah, Classification theory and the number of nonisomorphic models, Stud. Logic Found. Math., 92, North-Holland, Amsterdam, 1990 | MR | Zbl

[20] S. Shelah, “Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory”, Ann. Math. Logic, 3:3 (1971), 271–362 | DOI | MR | Zbl

[21] M. Benedikt, L. Libkin, T. Schwentick, L. Segoufin, “A model-theoretic approach to regular string relations”, Proceedings of the 16th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 2001, 431–442

[22] M. O. Rabin, “Decidability of second-order theories and automata on infinite trees”, Trans. Amer. Math. Soc., 141:7 (1969), 1–35 | DOI | MR | Zbl

[23] M. O. Rabin, “Razreshimost teorii vtorogo poryadka i avtomaty nad beskonechnymi derevyami”, Kiberneticheskii sbornik, 8, Mir, M., 1971, 72–116 | MR | Zbl