Abstract:One fundamental question in database theory is the following: Given a Boolean Conjunctive Query (BCQ) Q, what is the best complexity for computing the answer to Q in terms of the input database size N? When restricted to the class of combinatorial algorithms, it is known that the best known complexity for any query Q is captured by the submodular width of Q. However, beyond combinatorial algorithms, certain queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queries Q.
In this work, we introduce a general framework that captures the best complexity for answering any BCQ Q using matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the notion of submodular width to a new stronger notion called the omega-submodular width that naturally incorporates the power of fast matrix multiplication. We describe a matching algorithm that computes the answer to any query Q in time corresponding to the omega-submodular width of Q. We show that our framework recovers the best known complexities for Boolean queries that have been studied in the literature, to the best of our knowledge, and also discovers new algorithms for some classes of queries that improve upon the best known complexities.
From: Mahmoud Abo Khamis [view email]
[v1]
Mon, 9 Dec 2024 03:57:03 UTC (228 KB)
[v2]
Tue, 10 Dec 2024 03:36:20 UTC (228 KB)
[v3]
Sat, 11 Jan 2025 16:16:04 UTC (228 KB)
[v4]
Tue, 25 Mar 2025 22:46:38 UTC (645 KB)
[v5]
Fri, 3 Jul 2026 02:55:25 UTC (267 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。