On Safety of Unary and Non-unary IFP-operators
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 t...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
Yaroslavl State University
2018-10-01
|
Series: | Моделирование и анализ информационных систем |
Subjects: | |
Online Access: | https://www.mais-journal.ru/jour/article/view/747 |
_version_ | 1797878033195991040 |
---|---|
author | Sergey Dudakov |
author_facet | Sergey Dudakov |
author_sort | Sergey Dudakov |
collection | DOAJ |
description | 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. |
first_indexed | 2024-04-10T02:26:16Z |
format | Article |
id | doaj.art-a43e8d9992934c16969a555ec4ae046f |
institution | Directory Open Access Journal |
issn | 1818-1015 2313-5417 |
language | English |
last_indexed | 2024-04-10T02:26:16Z |
publishDate | 2018-10-01 |
publisher | Yaroslavl State University |
record_format | Article |
series | Моделирование и анализ информационных систем |
spelling | doaj.art-a43e8d9992934c16969a555ec4ae046f2023-03-13T08:07:29ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172018-10-0125552553310.18255/1818-1015-2018-5-525-533523On Safety of Unary and Non-unary IFP-operatorsSergey Dudakov0Тверской государственный университет.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.https://www.mais-journal.ru/jour/article/view/747инфляционная неподвижная точкаместностьбезопасность |
spellingShingle | Sergey Dudakov On Safety of Unary and Non-unary IFP-operators Моделирование и анализ информационных систем инфляционная неподвижная точка местность безопасность |
title | On Safety of Unary and Non-unary IFP-operators |
title_full | On Safety of Unary and Non-unary IFP-operators |
title_fullStr | On Safety of Unary and Non-unary IFP-operators |
title_full_unstemmed | On Safety of Unary and Non-unary IFP-operators |
title_short | On Safety of Unary and Non-unary IFP-operators |
title_sort | on safety of unary and non unary ifp operators |
topic | инфляционная неподвижная точка местность безопасность |
url | https://www.mais-journal.ru/jour/article/view/747 |
work_keys_str_mv | AT sergeydudakov onsafetyofunaryandnonunaryifpoperators |