Preview

Modeling and Analysis of Information Systems

Advanced search

On Safety of Unary and Non-unary IFP-operators

https://doi.org/10.18255/1818-1015-2018-5-525-533

Abstract

In this paper, we investigate the safety of unary inflationary fixed point operators (IFPoperators). 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 IFPoperators become unsafe. For general IFP-operators it is also impossible.

About the Author

Sergey Dudakov
Tver State University.
Russian Federation

Dr. of Science.

33 Zhelyabova str., Tver 170100.



References

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, № 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, № 2, 5-13, (in Russian).

4. Dudakov S. M., "On inflationary fix-point operators safety", Lobachevskii J. Math., 36:4 (2015), 328-331.

5. Gurevich Y., Shelah S., "Fixed-point extensions of first-order logic", Annals of Pure and Applied Logic, 32 (1986), 265-280.

6. Kanellakis P., Kuper G., Revesz P., "Constraint query languages", J. of Computer and System Sciences, 51:1 (1995), 26-52.

7. Marker D., Model theory: an introduction, Springer-Verlag, New York, 2002.


Review

For citations:


Dudakov S. On Safety of Unary and Non-unary IFP-operators. Modeling and Analysis of Information Systems. 2018;25(5):525-533. (In Russ.) https://doi.org/10.18255/1818-1015-2018-5-525-533

Views: 770


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)