License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2022.3
URN: urn:nbn:de:0030-drops-158771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15877/
Go to the corresponding LIPIcs Volume Portal

Carmeli, Nofar

Answering Unions of Conjunctive Queries with Ideal Time Guarantees (Invited Talk)

pdf-format:
LIPIcs-ICDT-2022-3.pdf (0.3 MB)

Abstract

The holy grail we strive for is, given a query, to identify an algorithm that answers it over general databases with optimal time guarantees for the specific query. In this tutorial, we focus on what can be seen as ideal time guarantees: linear preprocessing (needed to read the input) and constant time per answer (needed to print the output). We seek to understand which queries can be solved with these (or almost these) time guarantees and how.
We start with the basic building blocks of database queries: joins, and slowly increase the expressivity by introducing projections and unions until we cover positive relational algebra. We first consider the task of enumerating all query answers and then discuss related, more demanding, tasks such as ordered enumeration and direct access to query answers. We investigate the challenges in answering such queries and provide algorithms and conditional lower bounds

BibTeX - Entry

@InProceedings{carmeli:LIPIcs.ICDT.2022.3,
  author =	{Carmeli, Nofar},
  title =	{{Answering Unions of Conjunctive Queries with Ideal Time Guarantees}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15877},
  URN =		{urn:nbn:de:0030-drops-158771},
  doi =		{10.4230/LIPIcs.ICDT.2022.3},
  annote =	{Keywords: query evaluation, enumeration, fine-grained complexity, constant delay, union of conjunctive queries}
}

Keywords: query evaluation, enumeration, fine-grained complexity, constant delay, union of conjunctive queries
Collection: 25th International Conference on Database Theory (ICDT 2022)
Issue Date: 2022
Date of publication: 19.03.2022
Supplementary Material: Audiovisual (Video of the Presentation): https://doi.org/10.5446/58129

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI