Russian Mathematical Surveys
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Russian Mathematical Surveys, 2006, Volume 61, Issue 2, Pages 195–253
DOI: https://doi.org/10.1070/RM2006v061n02ABEH004311
(Mi rm1713)
 

This article is cited in 13 scientific papers (total in 13 papers)

Collapse results for query languages in database theory

S. M. Dudakov, M. A. Taitslin

Tver State University
References:
Abstract: This is a survey of collapse results obtained mainly by members of the Tver State University seminar on the theoretical foundations of computer science. Attention is focused on the relative properties of isolation and pseudo-finite homogeneity and universes without the independence property. The Baldwin–Benedikt reducibility theorem is proved for these universes. The Dudakov boundedness theorem is proved for reducible theories. The relative isolation theorem is proved for reducible and bounded theories, and as a consequence the collapse theorem is obtained for reducible theories. It is noted that reducibility is equivalent to the relative property of isolation. On the other hand, results of Dudakov are presented showing that the effectively reducible theories having an effective almost indiscernible sequence admit an effective collapse of locally generic queries using not only ordering and titles of stored tables but also relations and operations in the universe, into queries not using relations and operations in the universe. Also presented is Dudakov's example of an enrichment of the Presburger arithmetic for which the collapse theorem fails but the elementary theory of the enrichment is decidable. This answers some open questions in the negative.
Received: 03.06.2004
Russian version:
Uspekhi Matematicheskikh Nauk, 2006, Volume 61, Issue 2(368), Pages 3–66
DOI: https://doi.org/10.4213/rm1713
Bibliographic databases:
Document Type: Article
UDC: 510.67
MSC: 68P15, 03B70
Language: English
Original paper language: Russian
Citation: S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Uspekhi Mat. Nauk, 61:2(368) (2006), 3–66; Russian Math. Surveys, 61:2 (2006), 195–253
Citation in format AMSBIB
\Bibitem{DudTai06}
\by S.~M.~Dudakov, M.~A.~Taitslin
\paper Collapse results for query languages in database theory
\jour Uspekhi Mat. Nauk
\yr 2006
\vol 61
\issue 2(368)
\pages 3--66
\mathnet{http://mi.mathnet.ru/rm1713}
\crossref{https://doi.org/10.4213/rm1713}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2261542}
\zmath{https://zbmath.org/?q=an:1119.68063}
\adsnasa{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&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}
Linking options:
  • https://www.mathnet.ru/eng/rm1713
  • https://doi.org/10.1070/RM2006v061n02ABEH004311
  • https://www.mathnet.ru/eng/rm/v61/i2/p3
  • This publication is cited in the following 13 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Statistics & downloads:
    Abstract page:696
    Russian version PDF:307
    English version PDF:22
    References:44
    First page:2
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024