О безопасности одно- и многоместных IFP-операторов


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

Полный текст:


Аннотация

В работе изучается безопасность унарных операторов инфляционной неподвижной точки (IFP-операторов), то есть возможность их вычисления за конечное время. Такие операторы в точности соответствуют рекурсивным SQL-запросам, поэтому изучаемый вопрос имеет непосредственное отношение к базам данных. Исследуемая проблема возникает из-за того, что при одновременном применении в SQL запросе рекурсии и отношений универсума, например, сложения, может оказаться так, что процедура вычисления результата запроса зациклится. Более того, такая комбинация позволяет моделировать работу универсального вычислительного устройства, например, машины Тьюринга, поэтому вопрос о возможности вычисления SQL запроса за конечное время оказывается алгоритмически неразрешимым. В предыдущих работах были введены и изучены некоторые свойства универсумов, которые позволяют гарантировать возможность вычисления любых запросов за конечное время. Здесь мы изучаем вопрос о том, насколько существенна местность IFP-операторов в контексте их безопасности. Основным результатом настоящей работы является демонстрация того, что если ограничиться только унарными IFP-операторами, то не имеют места результаты, справедливые для IFP-операторов в общем случае без ограничения местности. Построен пример универсума, в котором все унарные IFP-операторы, не вложенные один в другой, безопасны. Вместе с тем в этом универсуме существуют небезопасные бинарные IFPоператоры, таким образом, при изменении местности безопасность может утрачиваться. Кроме того, существуют и небезопасные вложенные один в другой унарные операторы. Это контрастирует с общим случаем, в котором такое невозможно. Также существуют элементарно эквивалентные универсумы, в которых те же самые унарные IFP-операторы безопасными не являются. Такое поведение тоже отличается от поведения IFP-операторов произвольной местности.

Об авторе

Сергей Михайлович Дудаков
Тверской государственный университет.
Россия

 доктор физ.-мат. наук, доцент.

ул. Желябова, 33, г. Тверь, 170100.



Список литературы

1. Codd E. F., "Relational completeness of data base sublanguages", Database Systems, ed. Rustin R., Prentice-Hall, 1972, 33-64.

2. Дудаков С. М., “О безопасности рекурсивных запросов”, Вестник ТвГУ. Серия: Прикладная математика, 2012, № 4, 71–80.

3. Дудаков С. М., “О безопасности IFP-операторов и рекурсивных запросов”, Вестник ТвГУ. Серия: Прикладная математика, 2013, № 2, 5–13.

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.


Дополнительные файлы

Для цитирования: Дудаков С.М. О безопасности одно- и многоместных IFP-операторов. Моделирование и анализ информационных систем. 2018;25(5):525-533. https://doi.org/10.18255/1818-1015-2018-5-525-533

For citation: 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

Просмотров: 99

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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