ON DATABASE QUERIES OVER A WEAKLY O-MINIMAL DOMAIN WITH A SMALL COUNTABLE SPECTRUM

In the relational database model introduced by E.F. Codd, the database state is understood as a finite set of relationships between elements. The names of the relationships and their arnts (locations) are fixed and called the database schema. The individual information stored in the relationships of this schema is called the state of the database. Although relational databases were devised for finite sets of data, it is often convenient to assume that there is an infinite domain. We consider relational databases organized over an ordered domain with some additional relations – a typical example is the set of rational numbers together with the relation of linear order and binary operation of addition. If the first-order predicate logic language is used as the query language, then queries can use both database relationships and domain relationships, with variables changing throughout the domain. In the focus of our study are the first-order (FO) queries that are invariant under order-preserving permutations – such queries are called order-generic. It was discovered that for some domains order-generic FO queries fail to express more than pure order queries. Here we prove the collapse result theorem over a weakly o-minimal domain having convexity rank 1 and a small countable spectrum.

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.