Трансляционные результаты для языков запросов в теории баз данных

В этом обзоре мы излагаем трансляционные результаты, полученные, главным образом, участниками тверского семинара “Теоретические основы информатики”. В центре нашего внимания так называемые относительные свойства изолированности и псевдоконечной однородности и универсумы без независимой формулы. Для последних мы доказываем теорему Болдвина–Бенедикта о сводимости. Для сводимых теорий мы доказываем теорему Дудакова об ограниченности. Для сводимых и ограниченных теорий мы доказываем теорему об относительной изолированности и, как следствие, получаем для сводимых теорий трансляционную теорему. Мы также замечаем, что сводимость равносильна относительной изолированности. С другой стороны, мы приводим теоремы Дудакова, которые показывают, что для эффективно сводимых теорий, в которых существует эффективная почти неразличимая последовательность, возможна эффективная трансляция локально генерических запросов, использующих, кроме упорядочения и имен хранящихся таблиц, также и отношения и операции универсума, в запросы, которые эти отношения и операции универсума уже не используют. Мы приводим также пример Дудакова такого обогащения арифметики Пресбургера, для которого трансляционная теорема не имеет места, но элементарная теория которого разрешима. Это дает отрицательный ответ на некоторые открытые вопросы.
Библиография: 23 названия.