Botoeva, Elena ;
Calvanese, Diego ;
Cogrel, Benjamin ;
Xiao, Guohui
Expressivity and Complexity of MongoDB Queries
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.
BibTeX - Entry
@InProceedings{botoeva_et_al:LIPIcs:2018:8607,
author = {Elena Botoeva and Diego Calvanese and Benjamin Cogrel and Guohui Xiao},
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 = {Benny Kimelfeld and Yael Amsterdamer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8607},
URN = {urn:nbn:de:0030-drops-86074},
doi = {10.4230/LIPIcs.ICDT.2018.9},
annote = {Keywords: MongoDB, NoSQL, aggregation framework, expressivity}
}
|
Keywords: |
|
MongoDB, NoSQL, aggregation framework, expressivity |
|
Seminar: |
|
21st International Conference on Database Theory (ICDT 2018)
|
|
Issue date: |
|
2018 |
|
Date of publication: |
|
2018 |
2018
