DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2018.17

Distribution Policies for Datalog

Authors: Bas Ketsman, Aws Albarghouthi, and Paraschos Koutris

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

Abstract

Modern data management systems extensively use parallelism to speed up query processing over massive volumes of data. This trend has inspired a rich line of research on how to formally reason about the parallel complexity of join computation. In this paper, we go beyond joins and study the parallel evaluation of recursive queries. We introduce a novel framework to reason about multi-round evaluation of Datalog programs, which combines implicit predicate restriction with distribution policies to allow expressing a combination of data-parallel and query-parallel evaluation strategies. Using our framework, we reason about key properties of distributed Datalog evaluation, including parallel-correctness of the evaluation strategy, disjointness of the computation effort, and bounds on the number of communication rounds.

Cite as

Bas Ketsman, Aws Albarghouthi, and Paraschos Koutris. Distribution Policies for Datalog. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2018.17,
  author =	{Ketsman, Bas and Albarghouthi, Aws and Koutris, Paraschos},
  title =	{{Distribution Policies for Datalog}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{17:1--17:22},
  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.17},
  URN =		{urn:nbn:de:0030-drops-86034},
  doi =		{10.4230/LIPIcs.ICDT.2018.17},
  annote =	{Keywords: Datalog queries, Distributed evaluation, Distribution policies}
}

Search Results

Documents authored by Albarghouthi, Aws

Distribution Policies for Datalog

Abstract

Cite as

Thanks for your feedback!

Could not send message