Geodesic
On safety of unary and non-unary IFP-operators
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 5, pp. 525-533.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we investigate the safety of unary inflationary fixed point operators (IFP-operators). The safety is a computability in finitely many steps. IFP-operators exactly correspond to recursive SQL-queries hence this problem has a value for database theory. The problem appears from the fact that if recursive queries contain universe functions and relations, then its execution can fall into an infinite loop. Moreover, universal computational devices (Turing machines et al.) can be modelled by such queries. Hence the problem of the finite computability for such queries is undecidable. In our previous works we established some properties of a universe which imply the finite computability of all IFP-operators in the universe. Here, we investigate a connection between an arity of IFP-operators and their safety. We prove that some results for general IFP-operators don't hold for unary ones. We construct a universe where all unary unnesed IFP-operators are safe. But in this universe there exist unsafe nested unary IFP-operators and unsafe unnested binary IFP-operators. This differs from general IFP-operators because in general case the safety of all unnesed IFP-operators implies the safety of all IFP-operators. Also there exist elementary equivalent universes where some unary unnesed IFP-operators become unsafe. For general IFP-operators it is also impossible.
Keywords: inflationary fixed point, arity, safety. 
@article{MAIS_2018_25_5_a5,
     author = {S. M. Dudakov},
     title = {On safety of unary and non-unary {IFP-operators}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {525--533},
     publisher = {mathdoc},
     volume = {25},
     number = {5},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_5_a5/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On safety of unary and non-unary IFP-operators
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 525
EP  - 533
VL  - 25
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_5_a5/
LA  - ru
ID  - MAIS_2018_25_5_a5
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On safety of unary and non-unary IFP-operators
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 525-533
%V 25
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_5_a5/
%G ru
%F MAIS_2018_25_5_a5
S. M. Dudakov. On safety of unary and non-unary IFP-operators. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 5, pp. 525-533. http://geodesic.mathdoc.fr/item/MAIS_2018_25_5_a5/

[1] Codd E. F., “Relational completeness of data base sublanguages”, Database Systems, ed. Rustin R., Prentice-Hall, 1972, 33–64

[2] Dudakov S. M., “On safety of recursive queries”, Vestnik TvGU. Ser.: Prikl. Matem. [Herald of Tver State University. Ser.: Appl. Math.], 2012, no. 4, 71–80 (in Russian)

[3] Dudakov S. M., “On safety of IFP-operators and recursive queries”, Vestnik TvGU. Ser.: Prikl. Matem. [Herald of Tver State University. Ser.: Appl. Math.], 2013, no. 2, 5–13 (in Russian)

[4] Dudakov S. M., “On inflationary fix-point operators safety”, Lobachevskii J. Math., 36:4 (2015), 328–331 | DOI | MR | Zbl

[5] Gurevich Y., Shelah S., “Fixed-point extensions of first-order logic”, Annals of Pure and Applied Logic, 32 (1986), 265–280 | DOI | MR | Zbl

[6] Kanellakis P., Kuper G., Revesz P., “Constraint query languages”, J. of Computer and System Sciences, 51:1 (1995), 26–52 | DOI | MR

[7] Marker D., Model theory: an introduction, Springer-Verlag, New York, 2002 | MR | Zbl