DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2018.9

Expressivity and Complexity of MongoDB Queries

Authors: Elena Botoeva, Diego Calvanese, Benjamin Cogrel, and Guohui Xiao

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)

Abstract

In this paper, we consider MongoDB, a widely adopted but not formally understood database system managing JSON documents and equipped with a powerful query mechanism, called the aggregation framework. We provide a clean formal abstraction of this query language, which we call MQuery. We study the expressivity of MQuery, showing the equivalence of its well-typed fragment with nested relational algebra. We further investigate the computational complexity of significant fragments of it, obtaining several (tight) bounds in combined complexity, which range from LogSpace to alternating exponential-time with a polynomial number of alternations.

Cite as

Elena Botoeva, Diego Calvanese, Benjamin Cogrel, and Guohui Xiao. Expressivity and Complexity of MongoDB Queries. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{botoeva_et_al:LIPIcs.ICDT.2018.9,
  author =	{Botoeva, Elena and Calvanese, Diego and Cogrel, Benjamin and Xiao, Guohui},
  title =	{{Expressivity and Complexity of MongoDB Queries}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.9},
  URN =		{urn:nbn:de:0030-drops-86074},
  doi =		{10.4230/LIPIcs.ICDT.2018.9},
  annote =	{Keywords: MongoDB, NoSQL, aggregation framework, expressivity}
}

Search Results

Documents authored by Cogrel, Benjamin

Expressivity and Complexity of MongoDB Queries

Abstract

Cite as

Thanks for your feedback!

Could not send message