Cover Image

The Space-Time Complexity of Sum-Product Queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Deeds, Kyle, Merkl, Timo Camillo, Pichler, Reinhard, Suciu, Dan
Format:	Preprint
Published:	2025
Subjects:	Databases
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
by: Deeds, Kyle, et al.
Published: (2025)

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Query Answering under Volume-Based Diversity Functions
by: Arenas, Marcelo, et al.
Published: (2025)

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

Galley: Modern Query Optimization for Sparse Tensor Programs
by: Deeds, Kyle, et al.
Published: (2024)

Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation
by: Deeds, Kyle, et al.
Published: (2024)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Pessimistic Cardinality Estimation
by: Khamis, Mahmoud Abo, et al.
Published: (2024)

Convergence of Datalog over (Pre-) Semirings
by: Khamis, Mahmoud Abo, et al.
Published: (2021)

Output-Sensitive Evaluation of Regular Path Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2024)

Avoiding Materialisation for Guarded Aggregate Queries
by: Lanzinger, Matthias, et al.
Published: (2024)

Insert-Only versus Insert-Delete in Dynamic Query Evaluation
by: Khamis, Mahmoud Abo, et al.
Published: (2023)

Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

From FPT Decision to FPT Enumeration
by: Creignou, Nadia, et al.
Published: (2025)

PANDA: Query Evaluation in Submodular Width
by: Khamis, Mahmoud Abo, et al.
Published: (2024)

Applications of Information Inequalities to Database Theory Problems
by: Suciu, Dan
Published: (2023)

Query Optimization and Evaluation via Information Theory: A Tutorial
by: Khamis, Mahmoud Abo, et al.
Published: (2026)

HoneyComb: A Parallel Worst-Case Optimal Join on Multicores
by: Wu, Jiacheng, et al.
Published: (2025)

Thucy: An LLM-based Multi-Agent System for Claim Verification across Relational Databases
by: Theologitis, Michael, et al.
Published: (2025)

Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue
by: Böhm, Daniela, et al.
Published: (2025)

JOB-Complex: A Challenging Benchmark for Traditional & Learned Query Optimization
by: Wehrstein, Johannes, et al.
Published: (2025)

Space-Time Tradeoffs for Spatial Conjunctive Queries
by: Esmailpour, Aryan, et al.
Published: (2025)

LpBound: Pessimistic Cardinality Estimation using $\ell_p$-Norms of Degree Sequences
by: Zhang, Haozhe, et al.
Published: (2025)

Semantic foundations of equality saturation
by: Suciu, Dan, et al.
Published: (2025)

Join Size Bounds using Lp-Norms on Degree Sequences
by: Khamis, Mahmoud Abo, et al.
Published: (2023)

Soft and Constrained Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2024)

Size Bound-Adorned Datalog
by: Fattebert, Christian, et al.
Published: (2026)

Fast Matrix Multiplication meets the Submodular Width
by: Abo-Khamis, Mahmoud, et al.
Published: (2024)

PANDAExpress: a Simpler and Faster PANDA Algorithm
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Complexity of Evaluating GQL Queries
by: Figueira, Diego, et al.
Published: (2024)

CHORUS: Foundation Models for Unified Data Discovery and Exploration
by: Kayali, Moe, et al.
Published: (2023)

Data Generation for Testing Complex Queries
by: Somwase, Sunanda, et al.
Published: (2024)

Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms
by: Abramovich, Omer, et al.
Published: (2025)

A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join
by: Padmanabha, Anantha, et al.
Published: (2023)

Sketched Sum-Product Networks for Joins
by: Tsan, Brian, et al.
Published: (2025)

QirK: Question Answering via Intermediate Representation on Knowledge Graphs
by: Scheerer, Jan Luca, et al.
Published: (2024)

A Unified Model for Cardinality Estimation by Learning from Data and Queries via Sum-Product Networks
by: Liu, Jiawei, et al.
Published: (2025)

A Graph-native Optimization Framework for Complex Graph Queries
by: Lyu, Bingqing, et al.
Published: (2025)