|
Эта публикация цитируется в 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{https://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{https://elibrary.ru/item.asp?id=14320563}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33748288057}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/umn1713https://doi.org/10.4213/rm1713 http://mi.mathnet.ru/rus/umn/v61/i2/p3
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
С. М. Дудаков, “Псевдоконечная однородность, изолированность и сводимость”, Матем. заметки, 81:4 (2007), 515–527
; S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466 -
С. М. Дудаков, “Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы”, Изв. РАН. Сер. матем., 75:5 (2011), 47–64
; S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932 -
М. А. Тайцлин, “Сравнение выразительной силы некоторых языков запросов для баз данных”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 297–313
; M. A. Taitslin, “Comparison of expressive power of some query languages for databases”, Proc. Steklov Inst. Math., 274 (2011), 273–288 -
С. М. Дудаков, “О границах трансфинитного построения инфляционной неподвижной точки”, Вестник ТвГУ. Серия: Прикладная математика, 2018, № 3, 72–80
|
Просмотров: |
Эта страница: | 513 | Полный текст: | 208 | Литература: | 32 | Первая стр.: | 2 |
|