RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


УМН, 2006, том 61, выпуск 2(368), страницы 3–66 (Mi umn1713)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

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

С. М. Дудаков, М. А. Тайцлин

Тверской государственный университет

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

DOI: https://doi.org/10.4213/rm1713

Полный текст: PDF файл (911 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Mathematical Surveys, 2006, 61:2, 195–253

Реферативные базы данных:

УДК: 510.67
MSC: 68P15, 03B70
Поступила в редакцию: 03.06.2004

Образец цитирования: С. М. Дудаков, М. А. Тайцлин, “Трансляционные результаты для языков запросов в теории баз данных”, УМН, 61:2(368) (2006), 3–66; Russian Math. Surveys, 61:2 (2006), 195–253

Цитирование в формате AMSBIB
\RBibitem{DudTai06}
\by С.~М.~Дудаков, М.~А.~Тайцлин
\paper Трансляционные результаты для языков запросов в~теории баз данных
\jour УМН
\yr 2006
\vol 61
\issue 2(368)
\pages 3--66
\mathnet{http://mi.mathnet.ru/umn1713}
\crossref{https://doi.org/10.4213/rm1713}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2261542}
\zmath{https://zbmath.org/?q=an:1119.68063}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2006RuMaS..61..195D}
\elib{http://elibrary.ru/item.asp?id=25787278}
\transl
\jour Russian Math. Surveys
\yr 2006
\vol 61
\issue 2
\pages 195--253
\crossref{https://doi.org/10.1070/RM2006v061n02ABEH004311}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000240101600001}
\elib{http://elibrary.ru/item.asp?id=14320563}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33748288057}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn1713
  • https://doi.org/10.4213/rm1713
  • http://mi.mathnet.ru/rus/umn/v61/i2/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. С. М. Дудаков, “Псевдоконечная однородность, изолированность и сводимость”, Матем. заметки, 81:4 (2007), 515–527  mathnet  crossref  mathscinet  zmath  elib; S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466  crossref  isi  elib
    2. С. М. Дудаков, “Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы”, Изв. РАН. Сер. матем., 75:5 (2011), 47–64  mathnet  crossref  mathscinet  zmath  adsnasa  elib; S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932  crossref  isi  elib
    3. М. А. Тайцлин, “Сравнение выразительной силы некоторых языков запросов для баз данных”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 297–313  mathnet  mathscinet  elib; M. A. Taitslin, “Comparison of expressive power of some query languages for databases”, Proc. Steklov Inst. Math., 274 (2011), 273–288  crossref  isi  elib
    4. С. М. Дудаков, “О границах трансфинитного построения инфляционной неподвижной точки”, Вестник ТвГУ. Серия: Прикладная математика, 2018, № 3, 72–80  mathnet  crossref  elib
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:496
    Полный текст:192
    Литература:32
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020