On safety of unary and non-unary IFP-operators

S. M. Dudakov

Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 5, pp. 525-533

Résumé

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.

Détail

Keywords: inflationary fixed point, arity, safety.