Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Berkholz, Christoph, Vinall-Smeeth, Harry
Format:	Preprint
Published:	2025
Subjects:	Databases Data Structures and Algorithms Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Direct Access for Answers to Conjunctive Queries with Aggregation
by: Eldar, Idan, et al.
Published: (2023)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
by: Berkholz, Christoph, et al.
Published: (2024)

Ranked Enumeration for MSO on Trees via Knowledge Compilation
by: Amarilli, Antoine, et al.
Published: (2023)

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
by: Vinall-Smeeth, Harry
Published: (2023)

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
by: Carmeli, Nofar, et al.
Published: (2025)

MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
by: Kleest-Meißner, Sarah, et al.
Published: (2022)

Structured d-DNNF Is Not Closed Under Negation
by: Vinall-Smeeth, Harry
Published: (2024)

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
by: Muñoz, Martín
Published: (2026)

Correlation Sketches for Approximate Join-Correlation Queries
by: Santos, Aécio, et al.
Published: (2021)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Subgraph Isomorphism: Prolog vs. Conventional
by: Yin, Claire Y., et al.
Published: (2025)

Derivation and Verification of Array Sorting by Merging, and its Certification in Dafny
by: Carbonell, Juan Pablo, et al.
Published: (2025)

Algorithms and Complexity of Difference Logic
by: Dabrowski, Konrad K., et al.
Published: (2024)

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
by: Barto, Libor, et al.
Published: (2024)

Efficient Coalgebraic Partition Refinement
by: Dorsch, Ulrich, et al.
Published: (2017)

Model checking with temporal graphs and their derivative
by: Bui-Xuan, Binh-Minh, et al.
Published: (2026)

Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
by: Boreale, Michele, et al.
Published: (2019)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Exact Exploration
by: Blass, Andreas, et al.
Published: (2024)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Algorithms for Optimizing Acyclic Queries
by: Luo, Zheng, et al.
Published: (2025)

Approximating Queries on Probabilistic Graphs
by: Amarilli, Antoine, et al.
Published: (2023)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

Range (Rényi) Entropy Queries and Partitioning
by: Esmailpour, Aryan, et al.
Published: (2023)

Enumeration Algorithms for Conjunctive Queries with Projection
by: Deep, Shaleen, et al.
Published: (2021)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Polynomial Logical Zonotope: A Set Representation for Reachability Analysis of Logical Systems
by: Alanwar, Amr, et al.
Published: (2023)

Computing Data Distribution from Query Selectivities
by: Agarwal, Pankaj K., et al.
Published: (2024)

Querying in Constant Expected Time with Learned Indexes
by: Croquevielle, Luis, et al.
Published: (2024)

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
by: Arenas, Marcelo, et al.
Published: (2024)

Evaluating Regular Path Queries on Compressed Adjacency Matrices
by: Arroyuelo, Diego, et al.
Published: (2023)

Grafite: Taming Adversarial Queries with Optimal Range Filters
by: Costa, Marco, et al.
Published: (2023)

Socio-Spatial Group Queries for Impromptu Activity Planning
by: Shen, Chih-Ya, et al.
Published: (2015)