DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.12

Dynamic and Streaming Algorithms for Union Volume Estimation

Authors: Sujoy Bhore, Karl Bringmann, Timothy M. Chan, and Yanheng Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The union volume estimation problem asks to (1±ε)-approximate the volume of the union of n given objects X₁,…,X_n ⊂ ℝ^d. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time O(n/ε²) in an oracle model where each object X_i can be accessed via three types of queries: obtain the volume of X_i, sample a random point from X_i, and test whether X_i contains a given point x. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: 1) an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); 2) an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; 3) an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space.

Cite as

Sujoy Bhore, Karl Bringmann, Timothy M. Chan, and Yanheng Wang. Dynamic and Streaming Algorithms for Union Volume Estimation. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.12,
  author =	{Bhore, Sujoy and Bringmann, Karl and Chan, Timothy M. and Wang, Yanheng},
  title =	{{Dynamic and Streaming Algorithms for Union Volume Estimation}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.12},
  URN =		{urn:nbn:de:0030-drops-258180},
  doi =		{10.4230/LIPIcs.SoCG.2026.12},
  annote =	{Keywords: union volume estimation, dynamic algorithms, streaming algorithms}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.ICDT.2026.1

Query Decompositions and All That (Invited Talk)

Authors: Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler, and Dan Suciu

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

Abstract

The close relationship between Conjunctive Queries (CQs) and Constraint Satisfaction Problems (CSPs) has long been known. Nevertheless, apart from decomposition methods, research on efficient query evaluation or constraint solving algorithms has developed rather independently. In this article, we illustrate how search algorithms originating from the CSP community can be fruitfully applied to query evaluation - either by further developing the original search algorithms or by combining them with query decomposition methods. It turns out that the resulting approaches may indeed lead to lower time and/or space complexity than previous query evaluation methods.

Cite as

Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler, and Dan Suciu. Query Decompositions and All That (Invited Talk). In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deeds_et_al:LIPIcs.ICDT.2026.1,
  author =	{Deeds, Kyle and Merkl, Timo Camillo and Pichler, Reinhard and Suciu, Dan},
  title =	{{Query Decompositions and All That}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{1:1--1: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.1},
  URN =		{urn:nbn:de:0030-drops-256158},
  doi =		{10.4230/LIPIcs.ICDT.2026.1},
  annote =	{Keywords: Query evaluation, Query decompositions, Complexity}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.ICDT.2026.3

Building Relational Circuits (Invited Talk)

Authors: Florent Capelli

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

Abstract

We review two algorithms which allow to build a factorized representation of the answers set of join queries. In a nutshell, the representation builds a circuit representing the answers set of a join query by starting from atomic relations and iteratively combine them by either constructing the Cartesian product or the disjoint union of previously computed relations. The first one can be seen as the trace of the celebrated Yannakakis algorithm, building the answer set from the inputs to the output of the circuit while the second adopts a top-down approach which can be seen as a generalization of the exhaustive DPLL algorithm, originally designed to solve the #SAT problem.

Cite as

Florent Capelli. Building Relational Circuits (Invited Talk). In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{capelli:LIPIcs.ICDT.2026.3,
  author =	{Capelli, Florent},
  title =	{{Building Relational Circuits}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-256172},
  doi =		{10.4230/LIPIcs.ICDT.2026.3},
  annote =	{Keywords: Conjunctive queries, factorized databases, knowledge compilation}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.5

Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP

Authors: Philipp Hanisch and Markus Krötzsch

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

Abstract

Static filtering is a data-independent optimisation method for Datalog, which generalises algebraic query rewriting techniques from relational databases. In spite of its early discovery by Kifer and Lozinskii in 1986, the method has been overlooked in recent research and system development, and special cases are being rediscovered independently. We therefore recall the original approach, using updated terminology and more general filter predicates that capture features of modern systems, and we show how to extend its applicability to answer set programming (ASP). The outcome is strictly more general but also more complex than the classical approach: double exponential in general and single exponential even for predicates of bounded arity. As a solution, we propose tractable approximations of the algorithm that can still yield much improved logic programs in typical cases, e.g., it can improve the performance of rule systems over real-world data in the order of magnitude.

Cite as

Philipp Hanisch and Markus Krötzsch. Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hanisch_et_al:LIPIcs.ICDT.2026.5,
  author =	{Hanisch, Philipp and Kr\"{o}tzsch, Markus},
  title =	{{Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{5:1--5:19},
  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.5},
  URN =		{urn:nbn:de:0030-drops-256197},
  doi =		{10.4230/LIPIcs.ICDT.2026.5},
  annote =	{Keywords: Rule rewriting, static optimisation, static filtering, Datalog, Answer Set Programming}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.7

The Importance of Parameters in Ranking Functions

Authors: Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld

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

Abstract

How important is the weight of a given column in determining the ranking of tuples in a table? To address such an explanation question about a ranking function, we investigate the computation of SHAP scores for column weights, adopting a recent framework by Grohe et al. [ICDT'24]. The exact definition of this score depends on three key components: (1) the ranking function in use, (2) an effect function that quantifies the impact of using alternative weights on the ranking, and (3) an underlying weight distribution. We analyze the computational complexity of different instantiations of this framework for a range of fundamental ranking and effect functions, focusing on probabilistically independent finite distributions for individual columns. For the ranking functions, we examine lexicographic orders and score-based orders defined by the summation, minimum, and maximum functions. For the effect functions, we consider global, top-k, and local perspectives: global measures quantify the divergence between the perturbed and original rankings, top-k measures inspect the change in the set of top-k answers, and local measures capture the impact on an individual tuple of interest. Although all cases admit an additive fully polynomial-time randomized approximation scheme (FPRAS), we establish the complexity of exact computation, identifying which cases are solvable in polynomial time and which are #P-hard. We further show that all complexity results, lower bounds and upper bounds, extend to a related task of computing the Shapley value of whole columns (regardless of their weight).

Cite as

Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld. The Importance of Parameters in Ranking Functions. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{standke_et_al:LIPIcs.ICDT.2026.7,
  author =	{Standke, Christoph and Tziavelis, Nikolaos and Gatterbauer, Wolfgang and Kimelfeld, Benny},
  title =	{{The Importance of Parameters in Ranking Functions}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-256217},
  doi =		{10.4230/LIPIcs.ICDT.2026.7},
  annote =	{Keywords: Ranking, Explanation, Shapley value, SHAP scores}
}

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.9

Acyclic Join Sampling Under Selections: Dichotomy, Union Sampling, and Enumeration

Authors: Jinchao Huang, Yufei Tao, and Sibo Wang

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

Abstract

Previous research on join sampling has focused on joins without selection conditions, even though such conditions are prevalent in everyday queries in database systems. Motivated by this, we undertake a systematic investigation on the complexity of sampling from the result of an acyclic join under equality conditions given only at runtime. When conditions are conjunctive, the goal is to understand when it is possible to precompute a feasible structure that uses Õ(IN) space and supports sampling in Õ(1) time, where IN is the input size. We present a dichotomy to characterize (subject to a widely-accepted conjecture) the existence of such structures based on the conditions supplied and, in every feasible scenario, give an optimal structure of O(IN) space and O(1) sample time. We then extend our investigation to conditions expressed in disjunctive normal form, where the core challenge reduces to the fundamental set union sampling problem. We overcome the challenge with an optimal algorithm and utilize it to develop optimal sampling structures. Our findings also lead to new results on the closely-related random enumeration problem.

Cite as

Jinchao Huang, Yufei Tao, and Sibo Wang. Acyclic Join Sampling Under Selections: Dichotomy, Union Sampling, and Enumeration. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICDT.2026.9,
  author =	{Huang, Jinchao and Tao, Yufei and Wang, Sibo},
  title =	{{Acyclic Join Sampling Under Selections: Dichotomy, Union Sampling, and Enumeration}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-256231},
  doi =		{10.4230/LIPIcs.ICDT.2026.9},
  annote =	{Keywords: Conjunctive Queries, Acyclic Joins, Sampling, Lower Bounds}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.11

Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy

Authors: Christoph Berkholz and Harry Vinall-Smeeth

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

Abstract

A common theme in factorised databases and knowledge compilation is the representation of solution sets in a useful yet succinct data structure. In this paper, we study the representation of the result of join queries (or, equivalently, the set of homomorphisms between two relational structures). We focus on the very general format of {∪,×}-circuits - also known as d-representations or DNNF circuits - and aim to find the limits of this approach. In prior work, it has been shown that there always exists a {∪,×}-circuit of size N^O(subw) representing the query result, where N is the size of the database and subw the submodular width of the query. If the arity of all relations is bounded by a constant, then subw is linear in the treewidth tw of the query. In this setting, the authors of this paper proved a lower bound of N^Ω(tw^ε) on the circuit size (ICALP 2023), where ε > 0 depends on the excluded grid theorem. Our first main contribution is to improve this lower bound to N^Ω(tw), which is tight up to a constant factor in the exponent. Our second contribution is a N^Ω(subw^{1/4}) lower bound on the circuit size for join queries over relations of unbounded arity. Both lower bounds are unconditional lower bounds on the circuit size for well-chosen database instances. Their proofs use a combination of structural (hyper)graph theory with communication complexity in a simple yet novel way. While the second lower bound is asymptotically equivalent to Marx’s conditional bound on the decision complexity (JACM 2013), our N^Θ(tw) bound in the bounded arity setting is tight, while the best conditional bound on the decision complexity is N^Ω(tw/log tw). Note that removing this logarithmic factor in the decision setting is a major open problem.

Cite as

Christoph Berkholz and Harry Vinall-Smeeth. Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.ICDT.2026.11,
  author =	{Berkholz, Christoph and Vinall-Smeeth, Harry},
  title =	{{Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-256255},
  doi =		{10.4230/LIPIcs.ICDT.2026.11},
  annote =	{Keywords: join queries, homomorphisms, factorised databases, succinct representation, knowledge compilation, lower bounds}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.12

The Complexity of Finding Missing Answer Repairs

Authors: Jesse Comer and Val Tannen

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

Abstract

We investigate the problem of identifying database repairs for missing tuples in query answers. We show that when the query is part of the input - the combined complexity setting - determining whether or not a repair exists is polynomial-time equivalent to the satisfiability problem for classes of queries admitting a weak form of projection and selection. We then identify the sub-classes of unions of conjunctive queries with negated atoms, defined by the relational algebra operations permitted to appear in the query, for which the minimal repair problem can be solved in polynomial time. In contrast, we show that the problem is NP-hard, as well as set cover-hard to approximate via strict reductions, whenever both projection and join are permitted in the input query. Additionally, we show that finding the size of a minimal repair for unions of conjunctive queries (with negated atoms permitted) is OptP[log(n)]-complete, while computing a minimal repair is possible with O(n²) queries to an NP oracle. With recursion permitted, the combined complexity of all of these variants increases significantly, with an EXP lower bound. However, from the data complexity perspective, we show that minimal repairs can be identified in polynomial time for all queries expressible as semi-positive datalog programs.

Cite as

Jesse Comer and Val Tannen. The Complexity of Finding Missing Answer Repairs. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{comer_et_al:LIPIcs.ICDT.2026.12,
  author =	{Comer, Jesse and Tannen, Val},
  title =	{{The Complexity of Finding Missing Answer Repairs}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-256265},
  doi =		{10.4230/LIPIcs.ICDT.2026.12},
  annote =	{Keywords: Missing answers, database repairs, datalog, computational complexity}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.13

Complexity of Evaluating GQL Queries

Authors: Diego Figueira, Anthony W. Lin, and Liat Peterfreund

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

Abstract

GQL has recently emerged as the standard query language over graph databases, particularly, property graphs. Indeed, this is analogous to the role of SQL for relational databases. Unlike SQL, however, fundamental problems regarding GQL are still unsolved, most notably the complexity of query evaluation. In this paper we provide a complete solution to this problem for the core fragment of GQL and for its extension with path restrictors. In particular, we show that the data complexity of these fragments is P^NP[log]-complete in general, and drops to NL-complete when restrictors are disallowed. Using techniques from embedded finite model theory, we show that this is true, even when the queries use data from infinite concrete domains such as real numbers with arithmetic. In proving these results, we establish and exploit tight connections between GQL and query languages over relational databases, especially extensions of relational calculus with transitive closure operators and fragments of second-order logic.

Cite as

Diego Figueira, Anthony W. Lin, and Liat Peterfreund. Complexity of Evaluating GQL Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2026.13,
  author =	{Figueira, Diego and Lin, Anthony W. and Peterfreund, Liat},
  title =	{{Complexity of Evaluating GQL Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{13:1--13:18},
  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.13},
  URN =		{urn:nbn:de:0030-drops-256278},
  doi =		{10.4230/LIPIcs.ICDT.2026.13},
  annote =	{Keywords: Graph query languages, GQL, complexity, database theory}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.14

Lower Bounds for the Algorithmic Complexity of Learned Indexes

Authors: Luis Alberto Croquevielle, Roman Sokolovskii, and Thomas Heinis

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

Abstract

Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in practice, their theoretical limitations are not fully understood. We present a framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation. Our formulation captures a broad family of one-dimensional learned indexes, including most existing designs, as piecewise model-based predictors. We solve the problem of lower bounding query time in two steps: first, we use probabilistic tools to control the effect of sampling when the database attribute is drawn from a probability distribution. Then, we analyze the approximation-theoretic problem of how to optimally represent a cumulative distribution function with approximators from a given model class. Within this framework, we derive lower bounds under a range of modeling and distributional assumptions, paying particular attention to the case of piecewise linear and piecewise constant model classes, which are common in practical implementations. Our analysis shows how tools from approximation theory, such as quantization and Kolmogorov widths, can be leveraged to formalize the space-time trade-offs inherent to learned index structures. The resulting bounds illuminate core limitations of these methods.

Cite as

Luis Alberto Croquevielle, Roman Sokolovskii, and Thomas Heinis. Lower Bounds for the Algorithmic Complexity of Learned Indexes. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{croquevielle_et_al:LIPIcs.ICDT.2026.14,
  author =	{Croquevielle, Luis Alberto and Sokolovskii, Roman and Heinis, Thomas},
  title =	{{Lower Bounds for the Algorithmic Complexity of Learned Indexes}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{14:1--14:21},
  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.14},
  URN =		{urn:nbn:de:0030-drops-256285},
  doi =		{10.4230/LIPIcs.ICDT.2026.14},
  annote =	{Keywords: Learned Indexes, Stochastic Processes, Approximation Theory}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.16

Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions

Authors: Albert Atserias and Phokion G. Kolaitis

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

Abstract

During the early days of relational database theory it was realized that "acyclic" database schemas possess a number of desirable properties. In fact, three different notions of "acyclicity" were identified and investigated during the 1980s, namely, α-acyclicity, β-acyclicity, and γ-acyclicity. Much more recently, the study of α-acyclicity was extended to annotated relations, where the annotations are values from some positive commutative monoid. The recent results about α-acyclic schemas and annotated relations give rise to results about β-acyclic schemas and annotated relations, since a schema is β-acyclic if and only if every sub-schema of it is α-acyclic. Here, we study γ-acyclic schemas and annotated relations. Our main finding is that the characterization of γ-acyclic schemas in terms of monotone sequential join expression extends to annotated relations, provided the annotations come from a positive commutative monoid that has the inner consistency property. Furthermore, the results reported here shed light on the role of the join of two standard relations. Specifically, our results reveal that the only relevant property of the join of two standard relations is that it is a witness to the consistency of the two relations, provided that these two relations are consistent. For the more abstract setting of annotated relations, this property of the standard join is captured by the notion of a consistency witness function, a notion which we systematically utilize in this work.

Cite as

Albert Atserias and Phokion G. Kolaitis. Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.ICDT.2026.16,
  author =	{Atserias, Albert and Kolaitis, Phokion G.},
  title =	{{Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-256304},
  doi =		{10.4230/LIPIcs.ICDT.2026.16},
  annote =	{Keywords: annotated relations, gamma-acyclicity, consistency witness functions}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.17

Algorithms for Optimizing Acyclic Queries

Authors: Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang

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

Abstract

Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis' algorithm. These algorithms rely on join trees, which differ from the operator trees for binary joins and require new optimization techniques. We propose three approaches to constructing join trees for acyclic queries. First, we give an algorithm to enumerate all join trees of an α-acyclic query by edits in linear time with amortized constant delay, which forms the basis of a cost-based optimizer for acyclic joins. Second, we show the Maximum Cardinality Search algorithm by Tarjan and Yannakakis constructs the unique shallowest join tree for any Berge-acyclic query, thus enabling parallel execution of large join queries. Finally, we prove that a simple algorithm by Hu et al. converts any connected left-deep linear plan of a γ-acyclic query into a join tree, allowing reuse of optimizers developed for binary joins.

Cite as

Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang. Algorithms for Optimizing Acyclic Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ICDT.2026.17,
  author =	{Luo, Zheng and Van den Broeck, Wim and Van den Broeck, Guy and Wang, Yisu Remy},
  title =	{{Algorithms for Optimizing Acyclic Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{17:1--17:18},
  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.17},
  URN =		{urn:nbn:de:0030-drops-256319},
  doi =		{10.4230/LIPIcs.ICDT.2026.17},
  annote =	{Keywords: Query Optimization, Join Trees, Enumeration}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2026.18

Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries

Authors: Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu, and Zilu Tian

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

Abstract

Conjunctive Regular Path Queries, or CRPQs for short, are an essential construct in graph query languages. In this paper, we propose the first output-sensitive algorithm for evaluating acyclic CRPQs. It is output-sensitive in the sense that its complexity is a function of the sizes of the input graph and of the query output and not of the output sizes of the regular expressions that appear in the query, as these latter sizes can be larger than the query output size. Our algorithm proceeds in two stages. In the first stage, it contracts the given query into a free-connex acyclic one such that the output of the original query can be obtained from the output of the contracted one. This contraction removes bound variables by composing regular expressions or by promoting bound variables to free ones. The minimum necessary number of promoted bound variables gives the contraction width, which is a novel parameter specific to CRPQs. In the second stage, our algorithm evaluates the free-connex acyclic CRPQ and projects away the columns of the promoted bound variables. It ensures output-sensitivity by computing the calibrated outputs of the regular expressions appearing in the free-connex acyclic CRPQ in time proportional to their sizes. Our algorithm has lower complexity than the state-of-the-art approaches for problem instances where the query output is asymptotically smaller than the output sizes of the regular expressions that appear in the query.

Cite as

Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu, and Zilu Tian. Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abokhamis_et_al:LIPIcs.ICDT.2026.18,
  author =	{Abo Khamis, Mahmoud and Hurjui, Alexandru-Mihai and Kara, Ahmet and Olteanu, Dan and Suciu, Dan and Tian, Zilu},
  title =	{{Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{18:1--18: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.18},
  URN =		{urn:nbn:de:0030-drops-256321},
  doi =		{10.4230/LIPIcs.ICDT.2026.18},
  annote =	{Keywords: graph databases, regular path queries, output-sensitive algorithms}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.STACS.2026.1

Query Languages for Machine-Learning Models (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

In my invited talk and this accompanying paper, I discuss two logics for weighted finite structures: first-order logic with summation (FO(SUM)) and its recursive extension IFP(SUM). These logics originate from foundational work by Grädel, Gurevich, and Meer in the 1990s. In recent joint work with Standke, Steegmans, and Van den Bussche, we have investigated these logics as query languages for machine learning models, specifically neural networks, which are naturally represented as weighted graphs. I present illustrative examples of queries to neural networks that can be expressed in these logics and discuss fundamental results on their expressiveness and computational complexity.

Cite as

Martin Grohe. Query Languages for Machine-Learning Models (Invited Talk). In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.STACS.2026.1,
  author =	{Grohe, Martin},
  title =	{{Query Languages for Machine-Learning Models}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.1},
  URN =		{urn:nbn:de:0030-drops-254904},
  doi =		{10.4230/LIPIcs.STACS.2026.1},
  annote =	{Keywords: Expressive power of query languages, fixed-point logics, weighted structures, neural networks, explainable AI}
}

72 Search Results for "Suciu, Dan"

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