Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Free, publicly-accessible full text available May 30, 2027
-
PANDA is a powerful generic algorithm for answering conjunctive queries and disjunctive datalog rules given input degree constraints. In the special case of Boolean queries with only cardinality constraints, PANDA runs in O~ (Nsubw)-time, whereNis the input size, and subw is the submodular width of the query, a notion introduced by Daniel Marx (JACM 2013) in the context of constraint satisfaction problems. When specialized to certain classes of sub-graph pattern finding problems, the O~ (Nsubw) runtime matches the optimal runtime possible, modulo some conjectures in fine-grained complexity (Bringmann and Gorbachev (STOC 25)). The PANDA framework is much more general, as it handles arbitrary input degree constraints, which capture common statistics and integrity constraints used in relational database management systems, it works for queries with free variables, and for both conjunctive queries and disjunctive datalog rules. The key weakness of PANDA is the large polylog(N)-factor hidden in the O~ (·) notation, making it completely impractical, and falling short of what is achievable with specialized algorithms. This paper resolves this weakness with two novel ideas. First, we prove a new probabilistic inequality that upper-bounds the output size of disjunctive datalog rules under arbitrary degree constraints. Second, the proof of this inequality directly leads to a new algorithm named PANDAExpress that is bothsimplerandfasterthan PANDA. A novel feature of PANDAExpress is a new partitioning scheme that uses arbitrary hyperplane cuts instead of axisparallel hyperplanes used in PANDA. These hyperplanes are dynamically constructed based on data-skewness statistics carefully tracked throughout the algorithm's execution. As a result, PANDAExpress removes the polylog(N)-factor from the runtime of PANDA, matching the runtimes of intricate specialized algorithms, while retaining all its generality and power. As a bonus, we also show how PANDAExpress can handle ℓp-norm constraints, which generalize degree constraints.more » « lessFree, publicly-accessible full text available May 12, 2027
-
Recent work has demonstrated the catastrophic effects of poor cardinality estimates on query processing time. In particular, underestimating query cardinality can result in overly optimistic query plans which take orders of magnitude longer to complete than one generated with the true cardinality. Cardinality bounding avoids this pitfall by computing an upper bound on the query’s output size using statistics about the database such as table sizes and degrees, i.e., value frequencies. In this article, we extend this line of work by proving a novel bound called the Degree Sequence Bound, which takes into account the full degree sequences and the max tuple multiplicity. This work focuses on the important class of Berge-Acyclic queries for which the Degree Sequence Bound is tight and provably improves on prior work. We further describe how to practically compute this bound using a functional approximation of the true degree sequences and prove that even this functional form improves upon previous bounds. Lastly, we outline the challenges of implementing this in a real system and some techniques for overcoming these challenges.more » « lessFree, publicly-accessible full text available March 31, 2027
-
We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and a well-known parameter of the query that is called the ''free-connex fractional hypertree width''. Our algorithm improves upon the complexity of the recently introduced output-sensitive algorithm for acyclic CRPQs. More notably, the complexity of our algorithm for a given acyclic CRPQ Q matches the best known output-sensitive complexity for the ''corresponding'' conjunctive query (CQ), that is the CQ that has the same structure as the CRPQ Q except that each RPQ is replaced with a binary atom (or a join of two binary atoms). This implies that it is not possible to improve upon our complexity for acyclic CRPQs without improving the state-of-the-art on output-sensitive evaluation for acyclic CQs. Our result is surprising because RPQs, and by extension CRPQs, are equivalent to recursive Datalog programs, which are generally poorly understood from a complexity standpoint. Yet, our result implies that the recursion aspect of acyclic CRPQs does not add any extra complexity on top of the corresponding (non-recursive) CQs, at least as far as output-sensitive analysis is concerned.more » « lessFree, publicly-accessible full text available May 12, 2027
-
ten Cate, Balder; Funk, Maurice (Ed.)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.more » « lessFree, publicly-accessible full text available January 1, 2027
-
Free, publicly-accessible full text available January 1, 2027
-
ten Cate, Balder; Funk, Maurice (Ed.)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.more » « lessFree, publicly-accessible full text available January 1, 2027
-
This paper introducesCorrBound, a cardinality estimator that exploits the correlations between the join columns across and within relations. The state-of-the-art estimators do not observe such correlations and can therefore yield poor estimates. By explicitly accounting for correlations,CorrBoundcan significantly improve the accuracy of cardinality estimation. CorrBoundsupports multi-join queries (acyclic or cyclic) with conjunctions of equality and range predicates and group-by clauses. Its estimate is the optimal solution of a linear program whose constraints encode data statistics and Shannon inequalities. It uses a new information inequality that captures the intra- and inter-relation correlations of join columns and uses the generalized inner product of degree vectors of join columns. This inequality also captures the ℓp-norm inequality used by the state-of-the-art estimator LpBound. The inequality comes with a high-dimensionality challenge: managing the cardinality tensor defined by the generalized inner products of many large degree vectors. To keep the estimation time feasible,CorrBounduses two compression techniques that retain the accuracy of the inner products: sketches of degree vectors and low-rank decomposition of the cardinality tensor. We experimentally evaluateCorrBoundagainst traditional, pessimistic, and machine learning-based estimators on the JOBlight and STATS, and subgraph matching benchmarks. Our main finding is thatCorrBoundcan be more accurate than the state of the art while maintaining a low estimation time.more » « lessFree, publicly-accessible full text available April 2, 2027
-
To achieve true scalability on massive datasets, a modern query engine needs to be able to take advantage of large, shared-memory, multicore systems.Binary joinsare conceptually easy to parallelize on a multicore system; however, several applications require a different approach to query evaluation, using a Worst-Case Optimal Join (WCOJ) algorithm. WCOJ is known to outperform traditional query plans for cyclic queries. However, there is no obvious adaptation of WCOJ to parallel architectures. The few existing systems that parallelizeWCOJ do this by partitioning only the top variable of theWCOJ algorithm. This leads to work skew (since some relations end up being read entirely by every thread), possible contention between threads (when the hierarchical trie index is built lazily, which is the case on most recent WCOJ systems), and exacerbates the redundant computations already existing in WCOJ.more » « less
-
While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ignored. This is a particular challenge in settings with strict pre-defined space constraints. In this paper, we examine the combined space-time complexity of conjunctive queries (CQs) and, more generally, of sum-product queries (SPQs). We propose several classes of space-efficient algorithms for evaluating SPQs, and we show that the optimal time complexity is almost always achievable with asymptotically lower space complexity than traditional approaches.more » « lessFree, publicly-accessible full text available November 10, 2026
An official website of the United States government
