DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2026.8

Neither Cover nor Pack: Distributed Worst-Case Optimality of Degree-2 Joins

Authors: Heba Aamer, Xiao Hu, and Bas Ketsman

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

We study the worst-case communication complexity of the join query evaluation problem over large-scale data in distributed shared-nothing systems under the MPC model. We focus on multi-round MPC algorithms that run in constant number of rounds. The problem is well-understood for a few classes of queries, mainly the class of acyclic queries and the class of graph-like queries. For queries not belonging to either class, the complexity picture is much less clear. We study the class of degree-two queries and fragments thereof. In this paper, we tighten the gap between the upper and lower bounds for the studied classes and establish worst-case optimality for some fragments of the considered classes. We also debunk a well-believed conjecture about which query-related quantity, in the worst-case, optimally captures the communication complexity of the studied problem.

Cite as

Heba Aamer, Xiao Hu, and Bas Ketsman. Neither Cover nor Pack: Distributed Worst-Case Optimality of Degree-2 Joins. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aamer_et_al:LIPIcs.ICDT.2026.8,
  author =	{Aamer, Heba and Hu, Xiao and Ketsman, Bas},
  title =	{{Neither Cover nor Pack: Distributed Worst-Case Optimality of Degree-2 Joins}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.8},
  URN =		{urn:nbn:de:0030-drops-256226},
  doi =		{10.4230/LIPIcs.ICDT.2026.8},
  annote =	{Keywords: degree-two joins, worst-case optimality, distributed algorithms}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.10

Bounding the Makespan of Transaction Schedules

Authors: Tim Baccaert, Brecht Vandevoort, and Bas Ketsman

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

The performance of transactional database systems is typically evaluated by measuring the amount of transactions they can commit to the database per second. However, fairly measuring this for the same workload on different systems is not trivial. It is therefore relevant to formalize schedule efficiency, investigate the space of all possible efficient schedules, and identify whether there is any room for improvement. Prior transaction theory largely centers on decision problems relating to safety, such as the serializability, robustness, and allocation problems. Most pertinently, these problems take already scheduled transactions as input, and do not directly consider the efficiency of those schedules. In this work, we define schedules as assignments of operations on objects to discrete points in time. This allows us to quantify efficiency as the elapsed duration between the schedule’s beginning and end, more commonly known as the makespan in the scheduling literature. We establish that, given some set of transactions and a desired makespan, it is NP-complete to decide if there exists a conflict serializable schedule which is bounded by that makespan. We additionally provide an instance optimal algorithm for scheduling transaction sets with a single contention point, that is, exactly one object may appear in conflicting operations. Lastly, we give worst-case optimal bounds on the makespan, meaning that schedules can never exceed this bound, and for the worst transaction sets, the bound is optimal.

Cite as

Tim Baccaert, Brecht Vandevoort, and Bas Ketsman. Bounding the Makespan of Transaction Schedules. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baccaert_et_al:LIPIcs.ICDT.2026.10,
  author =	{Baccaert, Tim and Vandevoort, Brecht and Ketsman, Bas},
  title =	{{Bounding the Makespan of Transaction Schedules}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.10},
  URN =		{urn:nbn:de:0030-drops-256242},
  doi =		{10.4230/LIPIcs.ICDT.2026.10},
  annote =	{Keywords: Transactions, Scheduling, Discrete Optimization, Complexity}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.23

Conjunctive Query Containment with Safe Negation and TGD One-Boundedness

Authors: Xavier Oriol

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

Query containment is a fundamental database problem which has been extensively studied for conjunctive queries (CQs). The most famous result is arguably the Homomorphism Theorem: a CQ q₁ is contained in a CQ q₂ iff there is a homomorphism from q₂ to q₁. However, when extending conjunctive queries with safe base negation (CQ^¬), this test becomes incomplete, hence, requiring significantly more expensive procedures due to its inherently harder complexity (Π₂^P-hard). In this paper, we define and study the classes CQ^{1¬}_{HT} and CQ^{¬}_{HT}: the classes of conjunctive queries extended with one or several safe negated atoms that satisfy the Homomorphism Theorem, and hence, whose containment check is in NP. To characterise them, we define what we call the dependency-version of a query, which is a dependency that, intuitively, models the databases in which the query is false. It turns out that, when the query q contains one (several) negated atom(s), the query satisfies the Homomorphism Theorem iff its tgd(ded)-version is uniformly one-bounded. We also show that CQ^¬_{HT} membership is EXPTIME-hard, but its complexity reduces to Π₂^P in the CQ^{1¬}_{HT} case, and to NP when bounding the number of positive atoms that can unify with the negated one.

Cite as

Xavier Oriol. Conjunctive Query Containment with Safe Negation and TGD One-Boundedness. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{oriol:LIPIcs.ICDT.2026.23,
  author =	{Oriol, Xavier},
  title =	{{Conjunctive Query Containment with Safe Negation and TGD One-Boundedness}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.23},
  URN =		{urn:nbn:de:0030-drops-256373},
  doi =		{10.4230/LIPIcs.ICDT.2026.23},
  annote =	{Keywords: conjunctive queries, query containment, safe negation, tgd, one-boundedness}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.6

PAC: Computing Join Queries with Semi-Covers

Authors: Heba Aamer and Bas Ketsman

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

An increased and growing interest in large-scale data processing has triggered a demand for specialized algorithms that thrive in massively parallel shared-nothing systems. To answer the question of how to efficiently compute join queries in this setting, a rich line of research has emerged specifically for the Massively Parallel Communication (MPC) model. In the MPC model, algorithms are executed in rounds, with each round consisting of a synchronized communication phase and a separate local computation phase. The main cost measure is the load of the algorithm, defined as the maximum number of messages received by any server in any round. We study worst-case optimal algorithms for the join query evaluation problem in the constant-round MPC model. In the single-round variant of MPC, the worst-case optimal load for this problem is well understood and algorithms exist that guarantee this load for any join query. In the constant-round variant of MPC, queries can often be computed with a lower load compared to the single-round variant, but the worst-case optimal load is only known for specific classes of join queries, including graph-like and acyclic join queries, and the associated algorithms use very different techniques. In this paper, we propose a new constant-round MPC algorithm for computing join queries. Our algorithm is correct for every join query and its load matches (up to a polylog factor) the worst-case optimal load for at least all join queries that are acyclic or graph-like.

Cite as

Heba Aamer and Bas Ketsman. PAC: Computing Join Queries with Semi-Covers. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aamer_et_al:LIPIcs.ICDT.2025.6,
  author =	{Aamer, Heba and Ketsman, Bas},
  title =	{{PAC: Computing Join Queries with Semi-Covers}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.6},
  URN =		{urn:nbn:de:0030-drops-229474},
  doi =		{10.4230/LIPIcs.ICDT.2025.6},
  annote =	{Keywords: Worst-case optimal load, MPC model, join queries}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.32

The Free Termination Property of Queries over Time

Authors: Conor Power, Paraschos Koutris, and Joseph M. Hellerstein

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

Building on prior work on distributed databases and the CALM Theorem, we define and study the question of free termination: in the absence of distributed coordination, what query properties allow nodes in a distributed (database) system to unilaterally terminate execution even though they may receive additional data or messages in the future? This completeness question is complementary to the soundness questions studied in the CALM literature. We also develop a new model based on semiautomata that allows us to bridge from the relational transducer model of the CALM papers to algebraic models that are popular among software engineers (e.g. CRDTs) and of increasing interest to database theory for datalog extensions and incremental view maintenance.

Cite as

Conor Power, Paraschos Koutris, and Joseph M. Hellerstein. The Free Termination Property of Queries over Time. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{power_et_al:LIPIcs.ICDT.2025.32,
  author =	{Power, Conor and Koutris, Paraschos and Hellerstein, Joseph M.},
  title =	{{The Free Termination Property of Queries over Time}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.32},
  URN =		{urn:nbn:de:0030-drops-229736},
  doi =		{10.4230/LIPIcs.ICDT.2025.32},
  annote =	{Keywords: distributed systems, algebraic data models, coordination-free systems}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.27

Parallel Query Processing with Heterogeneous Machines

Authors: Simon Frisk and Paraschos Koutris

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

We study the problem of computing a full Conjunctive Query in parallel using p heterogeneous machines. Our computational model is similar to the MPC model, but each machine has its own cost function mapping from the number of bits it receives to a cost. An optimal algorithm should minimize the maximum cost across all machines. We consider algorithms over a single communication round and give a lower bound and matching upper bound for databases where each relation has the same cardinality. We do this for both linear cost functions like in previous work, but also for more general cost functions. For databases with relations of different cardinalities, we also find a lower bound, and give matching upper bounds for specific queries like the cartesian product, the join, the star query, and the triangle query. Our approach is inspired by the HyperCube algorithm, but there are additional challenges involved when machines have heterogeneous cost functions.

Cite as

Simon Frisk and Paraschos Koutris. Parallel Query Processing with Heterogeneous Machines. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{frisk_et_al:LIPIcs.ICDT.2025.27,
  author =	{Frisk, Simon and Koutris, Paraschos},
  title =	{{Parallel Query Processing with Heterogeneous Machines}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.27},
  URN =		{urn:nbn:de:0030-drops-229683},
  doi =		{10.4230/LIPIcs.ICDT.2025.27},
  annote =	{Keywords: Joins, Massively Parallel Computation, Heterogeneous}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.25

Optimal Oblivious Algorithms for Multi-Way Joins

Authors: Xiao Hu and Zhiang Wu

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

In cloud databases, cloud computation over sensitive data uploaded by clients inevitably causes concern about data security and privacy. Even if cryptographic primitives and trusted computing environments are integrated into query processing to safeguard the actual contents of the data, access patterns of algorithms can still leak private information about data. Oblivious RAM (ORAM) and circuits are two generic approaches to address this issue, ensuring that access patterns of algorithms remain oblivious to the data. However, deploying these methods on insecure algorithms, particularly for multi-way join processing, is computationally expensive and inherently challenging. In this paper, we propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor. Furthermore, it is cache-agnostic, with cache complexity matching the insecure lower bound, also up to a logarithmic factor. This clean and straightforward approach has the potential to be extended to other security settings and implemented in practical database systems.

Cite as

Xiao Hu and Zhiang Wu. Optimal Oblivious Algorithms for Multi-Way Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2025.25,
  author =	{Hu, Xiao and Wu, Zhiang},
  title =	{{Optimal Oblivious Algorithms for Multi-Way Joins}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.25},
  URN =		{urn:nbn:de:0030-drops-229662},
  doi =		{10.4230/LIPIcs.ICDT.2025.25},
  annote =	{Keywords: oblivious algorithms, multi-way joins, worst-case optimality}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2022.16

Robustness Against Read Committed for Transaction Templates with Functional Constraints

Authors: Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract

The popular isolation level Multiversion Read Committed (RC) trades some of the strong guarantees of serializability for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining serializability at the lower cost of RC. Such workloads are said to be robust against RC. Previous work has yielded a tractable procedure for deciding robustness against RC for workloads generated by transaction programs modeled as transaction templates. An important insight of that work is that, by more accurately modeling transaction programs, we are able to recognize larger sets of workloads as robust. In this work, we increase the modeling power of transaction templates by extending them with functional constraints, which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust that otherwise would not be. Even though we establish that the robustness problem becomes undecidable in its most general form, we show that various restrictions on functional constraints lead to decidable and even tractable fragments that can be used to model and test for robustness against RC for realistic scenarios.

Cite as

Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness Against Read Committed for Transaction Templates with Functional Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vandevoort_et_al:LIPIcs.ICDT.2022.16,
  author =	{Vandevoort, Brecht and Ketsman, Bas and Koch, Christoph and Neven, Frank},
  title =	{{Robustness Against Read Committed for Transaction Templates with Functional Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{16:1--16:17},
  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/entities/document/10.4230/LIPIcs.ICDT.2022.16},
  URN =		{urn:nbn:de:0030-drops-158905},
  doi =		{10.4230/LIPIcs.ICDT.2022.16},
  annote =	{Keywords: concurrency control, robustness, complexity}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2020.13

Distribution Constraints: The Chase for Distributed Data

Authors: Gaetano Geck, Frank Neven, and Thomas Schwentick

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract

This paper introduces a declarative framework to specify and reason about distributions of data over computing nodes in a distributed setting. More specifically, it proposes distribution constraints which are tuple and equality generating dependencies (tgds and egds) extended with node variables ranging over computing nodes. In particular, they can express co-partitioning constraints and constraints about range-based data distributions by using comparison atoms. The main technical contribution is the study of the implication problem of distribution constraints. While implication is undecidable in general, relevant fragments of so-called data-full constraints are exhibited for which the corresponding implication problems are complete for EXPTIME, PSPACE and NP. These results yield bounds on deciding parallel-correctness for conjunctive queries in the presence of distribution constraints.

Cite as

Gaetano Geck, Frank Neven, and Thomas Schwentick. Distribution Constraints: The Chase for Distributed Data. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{geck_et_al:LIPIcs.ICDT.2020.13,
  author =	{Geck, Gaetano and Neven, Frank and Schwentick, Thomas},
  title =	{{Distribution Constraints: The Chase for Distributed Data}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.13},
  URN =		{urn:nbn:de:0030-drops-119378},
  doi =		{10.4230/LIPIcs.ICDT.2020.13},
  annote =	{Keywords: tuple-generating dependencies, chase, conjunctive queries, distributed evaluation}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2020.19

Datalog with Negation and Monotonicity

Authors: Bas Ketsman and Christoph Koch

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract

Positive Datalog has several nice properties that are lost when the language is extended with negation. One example is that fixpoints of positive Datalog programs are robust w.r.t. the order in which facts are inserted, which facilitates efficient evaluation of such programs in distributed environments. A natural question to ask, given a (stratified) Datalog program with negation, is whether an equivalent positive Datalog program exists. In this context, it is known that positive Datalog can express only a strict subset of the monotone queries, yet the exact relationship between the positive and monotone fragments of semi-positive and stratified Datalog was previously left open. In this paper, we complete the picture by showing that monotone queries expressible in semi-positive Datalog exist which are not expressible in positive Datalog. To provide additional insight into this gap, we also characterize a large class of semi-positive Datalog programs for which the dichotomy `monotone if and only if rewritable to positive Datalog' holds. Finally, we give best-effort techniques to reduce the amount of negation that is exhibited by a program, even if the program is not monotone.

Cite as

Bas Ketsman and Christoph Koch. Datalog with Negation and Monotonicity. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2020.19,
  author =	{Ketsman, Bas and Koch, Christoph},
  title =	{{Datalog with Negation and Monotonicity}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.19},
  URN =		{urn:nbn:de:0030-drops-119432},
  doi =		{10.4230/LIPIcs.ICDT.2020.19},
  annote =	{Keywords: Datalog, Monotonicity}
}

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}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2018.18

Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics

Authors: Bas Ketsman, Frank Neven, and Brecht Vandevoort

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

Abstract

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query. This property is referred to as parallel-correctness. Another key problem is to detect whether the data reshuffle step can be avoided when evaluating subsequent queries. The latter problem is referred to as transfer of parallel-correctness. This paper extends the study of parallel-correctness and transfer of parallel-correctness of conjunctive queries to incorporate bag semantics. We provide semantical characterizations for both problems, obtain complexity bounds and discuss the relationship with their set semantics counterparts. Finally, we revisit both problems under a modified distribution model that takes advantage of a linear order on compute nodes and obtain tight complexity bounds.

Cite as

Bas Ketsman, Frank Neven, and Brecht Vandevoort. Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2018.18,
  author =	{Ketsman, Bas and Neven, Frank and Vandevoort, Brecht},
  title =	{{Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{18:1--18:16},
  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.18},
  URN =		{urn:nbn:de:0030-drops-86040},
  doi =		{10.4230/LIPIcs.ICDT.2018.18},
  annote =	{Keywords: Conjunctive queries, distributed evaluation, bag semantics}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2016.9

Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation

Authors: Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This paper extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with and without negation. As a by-product it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.

Cite as

Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{geck_et_al:LIPIcs.ICDT.2016.9,
  author =	{Geck, Gaetano and Ketsman, Bas and Neven, Frank and Schwentick, Thomas},
  title =	{{Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.9},
  URN =		{urn:nbn:de:0030-drops-57787},
  doi =		{10.4230/LIPIcs.ICDT.2016.9},
  annote =	{Keywords: Conjunctive queries, distributed evaluation}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2015.291

Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data

Authors: Bas Ketsman and Frank Neven

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract

In a distributed context where data is dispersed over many computing nodes, monotone queries can be evaluated in an eventually consistent and coordination-free manner through a simple but naive broadcasting strategy which makes all data available on every computing node. In this paper, we investigate more economical broadcasting strategies for full conjunctive queries without self-joins that only transmit a part of the local data necessary to evaluate the query at hand. We consider oblivious broadcasting strategies which determine which local facts to broadcast independent of the data at other computing nodes. We introduce the notion of broadcast dependency set (BDS) as a sound and complete formalism to represent locally optimal oblivious broadcasting functions. We provide algorithms to construct a BDS for a given conjunctive query and study the complexity of various decision problems related to these algorithms.

Cite as

Bas Ketsman and Frank Neven. Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 291-307, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2015.291,
  author =	{Ketsman, Bas and Neven, Frank},
  title =	{{Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{291--307},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.291},
  URN =		{urn:nbn:de:0030-drops-49913},
  doi =		{10.4230/LIPIcs.ICDT.2015.291},
  annote =	{Keywords: Coordination-free evaluation, conjunctive queries, broadcasting}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2015.308

Datalog Queries Distributing over Components

Authors: Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract

We investigate the class D of queries that distribute over components. These are the queries that can be evaluated by taking the union of the query results over the connected components of the database instance. We show that it is undecidable whether a (positive) Datalog program distributes over components. Additionally, we show that connected Datalog with Negation (the fragment of Datalog with Negation where all rules are connected) provides an effective syntax for Datalog with Negation programs that distribute over components under the stratified as well as under the well-founded semantics. As a corollary, we obtain a simple proof for one of the main results in previous work [Zinn, Green, and Ludäscher, ICDT2012], namely, that the classic win-move query is in F_2 (a particular class of coordination-free queries).

Cite as

Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn. Datalog Queries Distributing over Components. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 308-323, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{ameloot_et_al:LIPIcs.ICDT.2015.308,
  author =	{Ameloot, Tom J. and Ketsman, Bas and Neven, Frank and Zinn, Daniel},
  title =	{{Datalog Queries Distributing over Components}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{308--323},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.308},
  URN =		{urn:nbn:de:0030-drops-49920},
  doi =		{10.4230/LIPIcs.ICDT.2015.308},
  annote =	{Keywords: Datalog, stratified semantics, well-founded semantics, coordination-free evaluation, distributed databases}
}

15 Search Results for "Ketsman, Bas"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message