О ЗАПРОСАХ БАЗ ДАННЫХ НАД СЛАБО О-МИНИМАЛЬНОЙ ОБЛАСТЬЮ С МАЛЫМ СЧЕТНЫМ СПЕКТРОМ

В реляционной модели баз данных, введенной Э.Ф. Коддом, состояние базы данных понимается как конечная совокупность отношений между элементами. Имена отношений и их арности (местности) фиксируются и называются схемой базы данных. Отдельная информация, хранимая в отношениях данной схемы, называется состоянием базы данных. Хотя реляционные базы данных были придуманы для конечных совокупностей данных, часто удобно предполагать, что существует бесконечная область определения. Мы исследуем реляционные базы данных над упорядоченной областью определения с некоторыми дополнительными отношениями – типичным примером является множество рациональных чисел с отношением линейного порядка и бинарной операцией сложения. Если в качестве языка запросов используется язык логики предикатов первого порядка, то запросы могут использовать как отношения базы данных, так и отношения области определения, при этом переменные изменяются на всей области определения. В фокусе наших исследований запросы первого порядка (FO), инвариантные относительно перестановок, сохраняющих порядок, такие запросы называются порядково-генерическими. Установлено, что для некоторых областей порядково-генерические запросы первого порядка сводятся к запросам чистого порядка. Здесь мы доказываем теорему сводимости над слабо о-минимальной областью определения, имеющей ранг выпуклости 1 и малый счетный спектр.

1. Codd E.F. A relational model for large shared data banks // Communications ACM, 1970, vol. 13, no. 6, pp. 377–387.

2. Codd E.F. Relational completeness of database sublanguages // Database systems, Prentice- Hall, 1972, pp. 33–64.

3. Benedikt M., Dong G., Libkin L., Wong L. Relational expressive power of constraint query languages // Journal of ACM, 1998, vol. 45, no. 1, pp. 1–34.

4. Belegradek O.V., Stolboushkin A.P. and Taitslin M.A. Extended order-generic queries // Annals of Pure and Applied Logic, 1999, vol. 97, pp. 85–125.

5. Taitslin M.A. A general condition for collapse results // Annals of Pure and Applied Logic, 2002, vol. 113, no. 1–3, pp. 323–330.

6. Dudakov S.M., Tajclin M.A. Transljacionnye rezul'taty dlja jazykov zaprosov v teorii baz dannyh // Uspehi matematicheskih nauk, 2006, vol. 61, no. 2, pp. 3–66.

7. Kulpeshov B.Sh. On Problem of Expressiveness of Database Queries // International Journal of Mathematics, Computer Sciences and Information Technology, 2010, vol. 3, no. 2, pp. 123–128.

8. Kulpeshov B.Sh. To Reducibility of Database Queries over an Ordered Domain // Computer Modelling and New Technologies, 2012, vol. 16, no. 2, pp. 34–39.

9. Kulpeshov B.Sh. On Reducibility of database queries over a circularly minimal domain // Advances in Computational Sciences and Technology, 2013, vol. 6, no. 1, pp. 25–33.

10. Baizhanov B.S., Kulpeshov B.Sh. On the Isolation Property over a Database Domain // Journal of Mathematics and System Science, 2013, vol. 3, no. 2, pp. 96–100.

11. Macpherson H.D., Marker D., Steinhorn Ch. Weakly o-minimal structures and real closed fields // Transactions of the American Mathematical Society, 2000, vol. 352, pp. 5435–5483.

12. Kulpeshov B.Sh. Weakly o-minimal structures and some of their properties // The Journal of Symbolic Logic, 1998, vol. 63, pp. 1511–1528.

13. Baizhanov B.S. Expansion of a model of a weakly o-minimal theory by a family of unary predicates // The Journal of Symbolic Logic, 2001, vol. 66, pp. 1382–1414.

14. Ikeda K., Pillay A., Tsuboi A. On theories having three countable models // Mathematical Logic Quarterly, 1998, vol. 44, no. 2, pp. 161–166.

15. Sudoplatov S.V. Classification of countable models of complete theories. Part 1. Novosibirsk: Novosibirsk State Technical University Publishing House, 2018, 326 p. ISBN 978-5-7782-3527-4.

16. Peretyat’kin M.G. A theory with three countable models // Algebra and Logic, 1980, vol. 19, no. 2, pp. 139–147.

17. Kulpeshov B.Sh., Sudoplatov S.V. Linearly ordered theories which are nearly countably categorical // Mathematical Notes, 2017, vol. 101, no. 3, pp. 475–483.

18. Altayeva A.B., Kulpeshov B.Sh. Binarity of almost-categorical quite o-minimal theories // Siberian Mathematical Journal, 2020, vol. 61,no. 3, pp. 379–390.

19. Kulpeshov B.Sh., Mustafin T.S. Almost-categorical weakly o-minimal theories of convexity rank 1 // Siberian Mathematical Journal, 2021, vol. 62, no. 1, pp. 52–65.