PaperlayerView exact revision on arXiv

Source-linked AI summary

FAQ: Questions Asked Frequently

Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra

arXiv:1504.04044v7cs.DBcs.DScs.LO

TL;DR

The paper studies diverse problems sharing a common algebraic structure and presents InsideOut, a variable-elimination algorithm for FAQ. It addresses variable-ordering optimization and reports practical evidence that fractional hypertree-width theory predicts performance, with selected systems at least an order of magnitude faster than commercial alternatives.

  • Problem

    Fundamental problems from three diverse domains share a common algebraic structure, motivating a unified FAQ formulation.

  • Method

    InsideOut solves FAQ through variable elimination, while the technical analysis chooses an ordering σ minimizing faqw(σ) and defines expression-tree structure.

  • Results

    Fractional hypertree-width theory predicts practical performance well, with selected systems at least an order of magnitude faster than existing commercial systems.

  • Takeaways & Limitations

    The results support applying the FAQ framework and InsideOut across problems represented by a shared algebraic structure.

  • Takeaways & Limitations

    Some input representations can cause combinatorial explosion, producing up to Ω(m^2) clauses after one step.

Abstract

from arXiv · show

We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models and logic. This is our main conceptual contribution. We then present a simple algorithm called "InsideOut" to solve this general problem. InsideOut is a variation of the traditional dynamic programming approach for constraint programming based on variable elimination. Our variation adds a couple of simple twists to basic variable elimination in order to deal with the generality of FAQ, to take full advantage of Grohe and Marx's fractional edge cover framework, and of the analysis of recent worst-case optimal relational join algorithms. As is the case with constraint programming and graphical model inference, to make InsideOut run efficiently we need to solve an optimization problem to compute an appropriate 'variable ordering'. The main technical contribution of this work is a precise characterization of when a variable ordering is 'semantically equivalent' to the variable ordering given by the input FAQ expression. Then, we design an approximation algorithm to find an equivalent variable ordering that has the best 'fractional FAQ-width'. Our results imply a host of known and a few new results in graphical model inference, matrix operations, relational joins, and logic. We also briefly explain how recent algorithms on beyond worst-case analysis for joins and those for solving SAT and #SAT can be viewed as variable elimination to solve FAQ over compactly represented input functions.

1 INTRODUCTION

The paper unifies fundamental problems across several domains as Functional Aggregate Queries and develops InsideOut to solve them, while emphasizing representation and variable-ordering choices.

  • 1.1 Motivating examples: Matrix chain multiplication and marginal MAP inference are examples of computations represented as functions of variables and factors followed by aggregation.
  • 1.1 Motivating examples: Functional Aggregate Query (FAQ) expresses problems from constraint satisfaction, databases, matrix operations, probabilistic graphical models, logic, coding theory, and complexity theory.
  • 1.2 The FAQ problem: An FAQ instance combines variables, a multi-hypergraph of factor supports, free and bound variables, input functions, and aggregate operators over variable domains.
  • 1.3 Input and output representation: Input and output representations substantially affect FAQ tractability; listing representation is assumed initially, while the algorithms support a more general class.
  • 2.2 Algorithmic contribution: InsideOut solves FAQ through a variation of variable elimination, and its runtime depends on selecting an appropriate variable ordering.
  • 1.4 Paper organization: The paper connects InsideOut with algorithms for SAT and #SAT over compactly represented input functions and organizes later analysis around equivalent orderings and representation effects.

2 SUMMARY OF CONTRIBUTIONS

The paper generalizes SumProd into FAQ, a declarative framework spanning constraint satisfaction, databases, matrix operations, graphical models, and logic, and presents InsideOut to solve it. It characterizes semantically equivalent variable orderings and uses that characterization to approximate an ordering with favorable FAQ-width, yielding known and new results across these areas.

  • FAQ generalizes SumProd to capture problems including quantified conjunctive queries and sharp quantified conjunctive queries.
  • InsideOut solves FAQ by extending variable elimination with backtracking-based intermediate computation, indicator projections, and aggregate-product swaps.
  • InsideOut runs in ˜O(N^faqw(σ) + ∥φ∥) for a chosen variable ordering under listing representations, up to logarithmic data and polynomial query factors.
  • The paper characterizes semantically equivalent orderings through component-wise equivalence and shows membership in EVO(φ) is decidable in polynomial query complexity.
  • Linear extensions of a precedence poset suffice for optimization because every such extension is semantically equivalent and matches the FAQ-width of some ordering in EVO(φ).
  • Using an fhtw approximation black box, the paper constructs an ordering with faqw(σ) ≤ opt + g(opt), improving to faqw(σ) ≤ g(opt) for FAQ-SS.

3 RELATED WORK

The related work connects FAQ to established frameworks in graphical models, databases, CSPs, matrix operations, and logic. It positions InsideOut as a unifying framework that recovers, improves, or extends several prior results, including a new result for #QCQ.

  • Graphical models and matrix operations: FAQ-SS was explicitly defined as the MPF problem, with message passing shown to meet the treewidth bound and capture problems including matrix chain multiplication.
  • Factorized databases: Factorized databases and InsideOut have the same runtime complexity for the single-semiring FAQ-SS case, despite using top-down and bottom-up dynamic programming, respectively.
  • Framework comparison: The FAQ framework handles multiple aggregate types and contributes a characterization of EVO together with an approximation algorithm for faqw.
  • Logic and query evaluation: InsideOut’s runtime is unboundedly better than earlier results for CQ, #CQ, and QCQ, while its #QCQ result is new because no non-trivial efficient algorithms were previously known.

4 PRELIMINARIES

The preliminaries establish representations for factors and outputs, define hypergraph covers and decompositions, and connect variable orderings with induced width measures. These definitions support the later analysis of InsideOut through fractional hypertree-style parameters.

  • Factor representations: In the listing representation, each factor stores all nonzero tuples, and the paper assumes this representation for most input and output factors.
  • Factor representations: A factor’s size is the number of nonzero points in its domain, while N denotes the maximum size among all input factors.
  • Hypergraph measures: Integral and fractional edge covers assign weights to hyperedges covering a vertex set, with their optimal values defining corresponding cover numbers.
  • Tree decompositions and widths: Tree decompositions use bags satisfying hyperedge coverage and vertex-connectedness conditions; applying a width function to bags yields the corresponding hypergraph width.
  • Tree decompositions and widths: Treewidth, generalized hypertree width, and fractional hypertree width are respectively defined through s, ρ, and ρ* width functions.
  • Variable orderings: For a variable ordering, the elimination hypergraph sequence records the successive unions of edges incident to eliminated vertices.
  • Acyclicity: β-acyclicity is characterized by an ordering whose incident hyperedges form nested inclusion chains, and it can be verified in polynomial time.
  • Variable orderings: A hypergraph has g-width at most w exactly when some vertex ordering has induced g-width at most w; this yields equivalent ordering characterizations for the common width parameters.

5 THE InsideOut ALGORITHM

InsideOut solves FAQ queries by combining variable elimination with join-based computation, while preserving efficiency through carefully chosen variable orderings. The section develops OutsideIn for shared semiring aggregates, extends elimination to general FAQ operators, and analyzes the resulting runtimes and width properties.

  • 5.1.1 Backtracking search: OutsideIn evaluates FAQ-SS expressions by backtracking over tuples satisfying every factor and aggregating their factor products.It serves as the algorithmic building block for InsideOut and is essentially a join algorithm when factors use listing representations.
  • 5.3 Analysis: InsideOut runs in time ˜O(N^faqw(σ) + ∥φ∥) for a selected variable ordering σ, linking runtime to FAQ-width.The analysis also gives specialized bounds, including O(n·m·log N·AGM_H(V)) for FAQ-SS and an O(N) example under a suitable ordering.
  • 5.1.1 Backtracking search: Backtracking search uses little extra space but may recompute the same subproblem multiple times, motivating its dual dynamic-programming approach.The section frames variable elimination as the other side of the backtracking-search/dynamic-programming duality.
  • 5.1.2 Variable elimination: Variable elimination removes variables by materializing an intermediate factor over their neighboring variables and recursively solving the resulting FAQ-SS instance.The intermediate factor is formed using distributivity, then the eliminated variable and incident edges are replaced by a new hyperedge.
  • 5.2 The InsideOut Algorithm: For sparse factors, InsideOut avoids entries later annihilated by other factors by incorporating indicator projections during intermediate-factor computation.Only surviving entries are computed, while the real factored-out factors do not participate directly.
  • 5.2 The InsideOut Algorithm: Worst-case optimal multiway-join algorithms compute intermediate factors without performing semijoins individually.This implementation is especially relevant when input factors are represented by their nonzero entries.
  • 5.5 FAQ-width of a variable ordering: The paper characterizes semantically equivalent variable orderings using component-wise equivalence and shows that LinEx(P) captures the relevant orderings for FAQ-width.Every ordering in LinEx(P) is φ-equivalent; every EVO ordering is component-wise equivalent to one in LinEx(P), and equivalent orderings have matching FAQ-width under the stated result.

6 CHARACTERIZING EQUIVALENT VARIABLE ORDERINGS

This section characterizes semantically equivalent variable orderings for FAQ expressions using an expression tree and its precedence poset. It shows that equivalent orderings can be reduced to linear extensions of the poset without changing FAQ-width, enabling efficient search for good orderings.

  • Precedence poset: Component-wise equivalence preserves both FAQ-width and semantic equivalence, providing the key bridge between orderings and the precedence poset.The section uses component-wise equivalence to compare arbitrary variable orderings with structured orderings generated by the tree.
  • Expression tree construction: The expression tree is built by compartmentalizing variables according to hypergraph connected components, then compressing adjacent nodes with identical tags.The initial tagged sequence includes free variables and aggregate-tagged bound variables; compression merges a child into a parent when their tags match.
  • Soundness and completeness: Every linear extension of the precedence poset is φ-equivalent to the original FAQ ordering.This is the soundness direction of the characterization for the semiring-aggregate setting and its extension to idempotent product aggregates.
  • Soundness and completeness: Every φ-equivalent ordering is component-wise equivalent to some linear extension of the precedence poset.Thus, the poset’s linear extensions represent all semantically relevant orderings up to component-wise equivalence.
  • Width optimization: faqw(φ) = min {faqw(σ) | σ∈LinEx(P)}, so optimizing FAQ-width only requires considering linear extensions of the precedence poset.The result removes redundant orderings from the search space while preserving the optimal FAQ-width.
  • Structural properties: The precedence relation is a partial order, and structural properties constrain product-tagged nodes and non-closed semiring aggregates.In particular, product-tagged nodes have at most one child in the final tree, while certain non-closed semiring aggregates must precede product aggregates.

7 APPROXIMATING THE FAQ-WIDTH

The paper shows that FAQ-width generalizes fractional hypertree width and develops approximation algorithms for semantically equivalent variable orderings. These algorithms inherit guarantees from fractional hypertree-width approximations and yield tractability results when FAQ-width is bounded.

  • FAQ-width exactly generalizes fractional hypertree width, coinciding with it for SumProd queries and queries whose variables are all free.
  • Computing FAQ-width and finding an optimal FAQ-width tree decomposition are NP-hard.
  • A polynomial-time approximation algorithm uses any fractional hypertree-width approximation as a black box and the FAQ expression tree.
  • For semiring aggregates, the algorithm computes a φ-equivalent ordering σ in time |H| · t(|H|, faqw(φ)) satisfying faqw(σ) ≤ faqw(φ) + g(faqw(φ)).
  • For FAQ queries with an inner FAQ formula closed under idempotent elements, the analogous ordering satisfies faqw(σ) ≤ faqw(φ, D_I) + g(faqw(φ, D_I)).
  • When faqw(φ, D_I) is bounded by a constant, the resulting ordering can be computed in polynomial time, implying tractability for QCQ and #QCQ.

8 INPUT AND OUTPUT REPRESENTATION

The paper extends FAQ beyond listing representations through an oracle model, succinct factor encodings, and alternative output representations. It also applies InsideOut and OutsideIn ideas to SAT, #SAT, joins, and compact intermediate factors.

  • The framework handles more succinct input representations, including GDNFs and decision diagrams, while SAT and #SAT require specialized treatment.
  • FAQ algorithms can operate under conditional-query and product-marginalization assumptions for factor oracles.
  • Truth-table representations explicitly list zero-valued tuples, whereas listing representations retain tuples whose factor value is nonzero.
  • Nested elimination orders avoid clause or box-factor explosion, keeping intermediate box factors compact as products of a small number of box factors.
  • For β-acyclic CNF formulas, the paper recovers polynomial-time algorithms for both SAT and #SAT.
  • The framework supports alternative output representations, including constant-delay enumeration and near-constant value-query time after preprocessing in the stated setting.

9 CONCLUDING REMARKS

The concluding discussion emphasizes FAQ’s practical reach across database systems, machine learning, graph-pattern counting, and logic. It also identifies optimizer complexity and representation-specific bounds as important implementation considerations.

  • Implementations of join algorithms based on fractional hypertree width were at least an order of magnitude faster than existing commercial systems for selected queries.
  • InsideOut was implemented in the LogicBlox database system and used to train a large class of machine-learning models inside the database.
  • The implementation achieved orders-of-magnitude speedup over exporting data and running it through R or Python.
  • Treating immaterialized predicates as infinite-size inputs can make the AGM bound loose or infinite even when the query is small.
  • Because there are n! variable orderings and optimizer cost estimation is time-consuming, the paper recommends approximation algorithms or greedy heuristics for ordering.
  • FAQ reductions cover graphical-model inference, matrix multiplication, constraint satisfaction, quantified conjunctive queries, natural joins, coding theory, SAT, and related problems.

A.5 Applications of the FAQ problem

The appendix illustrates how FAQ represents counting and decision problems involving existential and universal quantification. These examples show both the breadth of the framework and why general quantified queries require more than FAQ-SS.

  • Quantifier-free #CQ reduces to FAQ-SS over the sum-product semiring, but straightforward mapping fails when existential quantifiers are present.
  • QCQ includes both existential and universal quantifiers and cannot be reduced to the basic FAQ-SS formulation.
  • #QCQ counts assignments or tuples satisfying quantified conjunctive formulas and is similarly reduced to FAQ with a constant function.
  • The paper gives alternative FAQ reductions for QCQ using aggregate operators corresponding to the formula’s quantifiers.
  • The QCQ reduction places product both over universally quantified variables and over the input factors.

B REDUCTIONS FROM NON-SEMIRING TO SEMIRING

The section shows how non-semiring aggregates can be handled by embedding them into an extended commutative semiring, then transferring inputs and results between domains. Examples include conditional averages, uniqueness quantification, and max with multiplication, while weaker conditions impose limitations.

  • General reduction: A two-way mapping between an original domain and an extended commutative semiring allows variable elimination to proceed as if the original operations formed a commutative semiring.Inputs are transformed into the extended domain, computations are performed there, and results are transferred back after products are computed.
  • Conditions: Zero preservation is desirable because InsideOut and OutsideIn can exploit zero entries to save computation.The required properties are ¯0 = ¯f(0) and 0 = f(¯0).
  • Examples: Conditional average is not associative, but it can be represented over the commutative semiring (R × N, ¯⊕, ¯⊗).The construction tracks both accumulated values and counts, then maps the pair back to an average.
  • Examples: For (R, max, ×), adding NaN supplies a max identity, but multiplication still fails to distribute over max.The example therefore satisfies only conditions 1 and 2, allowing some reduction steps but not the final one.

C TREE DECOMPOSITIONS AND VARIABLE ELIMINATION

This section develops the correspondence between tree decompositions and vertex orderings used to analyze acyclicity and elimination widths. It gives constructive transformations in both directions and establishes structural and algorithmic properties of the resulting orderings.

  • Reduced tree decompositions: A reduced tree decomposition of a connected hypergraph on n vertices has at most a linear number of nodes.The proof repeatedly removes a private vertex from a leaf bag and applies induction.
  • Tree decomposition from vertex ordering: A vertex ordering recursively induces a tree decomposition by adding a bag for each eliminated vertex and then removing redundant bags.The construction produces at most n bags before reduction and yields a non-redundant decomposition whose bags correspond to elimination stages.
  • Tree decomposition from vertex ordering: In a decomposition induced by an ordering, every bag is associated with an ordering position, and the resulting decomposition is non-redundant.The associated bag contains the relevant induced hyperedge for each position.
  • GYO elimination: GYO elimination removes subset bags and vertices appearing in only one bag; reversing the removed-vertex sequence gives an ordering with width no worse than the decomposition’s width.The root bag can be chosen arbitrarily, so its vertices are eliminated last and appear first in the resulting ordering.
  • Vertex ordering from tree decomposition: A tree decomposition induces a vertex ordering whose induced sets are contained in decomposition bags, and this ordering can be constructed in polynomial time.The construction removes leaf bags and appends their private vertices recursively.
  • Acyclicity and widths: The proofs connect ordering properties with hypergraph acyclicity: α-acyclicity corresponds to orderings whose induced sets fit within hyperedges, while β-acyclicity corresponds to orderings whose relevant edge collections form chains.The converse α-acyclicity proof reconstructs a tree decomposition, and the β-acyclicity proof derives a contradiction from a forbidden sequence.

E QUICK APPLICATIONS OF InsideOut

The applications show that InsideOut reproduces or approximates standard computations for matrix products and structured transforms. Appropriate variable orderings and fractional covers determine the resulting runtime bounds.

  • Matrix Chain Multiplication: Matrix Chain Multiplication reduces to choosing a variable ordering that minimizes the same multiplication-cost expression as the classical dynamic-programming problem.Thus, the best ordering can be found by dynamic programming.
  • Structured matrix-vector multiplication: InsideOut computes a DFT-based matrix-vector multiplication in O(n log^4 n), compared with FFT’s O(n log n) runtime.The bound is a log^3 n factor slower than FFT under the stated parameterization.
  • Structured matrix-vector multiplication: For the DFT-based FAQ formulation, precomputed factors and the chosen ordering yield an overall O(n log n) runtime.Each of m elimination steps costs O(p^m), giving O(m p^m) = O(n log n).
  • Structured matrix-vector multiplication: For a circulant matrix, InsideOut evaluates two forward DFTs, a component-wise product, and an inverse DFT, for an overall O(n log n) runtime.The variable ordering mirrors the sequence F · b, F · c, component-wise multiplication, and F^-1 · u.
  • Structured matrix products: For the Kronecker product D ⊗ E, the fractional-cover analysis gives an overall runtime bound of O(n^3).The bound follows from covering the intermediate sets and the free-variable set using the specified factors.
  • Structured matrix products: For the Khatri-Rao product, a direct edge-cover calculation is quadratic, but InsideOut achieves O(n^5/3) using additional structure and projected factors.The same runtime holds with the indicated truth-table representations and projections.

F.1 Qick applications of FAQ-SS without free variables (i.e. SumProd)

The section applies FAQ-SS without free variables to joins, counting, and probabilistic graphical models, while accounting for both computation and output reporting. It also describes width-based approximation and the resulting tractability guarantees.

  • Ordering approximation: Optimal fractional hypertree width is NP-hard to compute, while Marx’s approximation produces width O(fhtw^3(H)) and runs in time O(|H|^O(fhtw^3(H))).When fhtw(H) is bounded, the resulting algorithm is polynomial in the hypergraph size.
  • General FAQ-SS guarantees: When fractional hypertree width is bounded by a constant, FAQ-SS without free variables can be solved over an arbitrary semiring within the width-based input-size bound plus output-reporting time.The bound is expressed using N^fhtw(H) and ||φ|| in the listing representation.
  • Counting queries: Quantifier-free #CQ is solvable in time ˜O(N^O(fhtw^3(H))) when fhtw(H) is bounded by a constant.In particular, conjunctive queries with bounded fractional hypertree width are tractable.
  • Probabilistic graphical models: The partition function in probabilistic graphical models has the same ˜O(N^O(fhtw^3(H))) bound under constant fractional hypertree width.The passage also notes that sparse inputs can make this bound substantially smaller than a domain-size-based treewidth bound.
  • Natural joins: InsideOut computes natural joins in ˜O(N^fhtw(H) + ||φ||) time when using the set-semiring formulation and an appropriate ordering.The induced fractional edge-cover width of the ordering equals faqw(σ).
  • Natural joins: Trie-like indexes respecting the variable ordering perform marginalization implicitly by exposing the required projected tuples without brute-force set union.This representation supports the intermediate relational operations used by InsideOut.
  • Output reporting: Reporting all join tuples takes O(n||φ|| log N) time, so output size can dominate the width-based computation cost.Acyclicity or small fractional hypertree width does not by itself prevent very large outputs, such as star joins with up to N^n−1 tuples.

F.2.1 The precedence poset.

The precedence poset characterizes variable-ordering constraints, and its linear extensions are sufficient to search for an equivalent ordering minimizing FAQ-width. The section also shows that FAQ-width can differ sharply from fractional hypertree width when only some variables are free.

  • The precedence poset orders variables so that every variable in L precedes variables outside L within each connected component.
  • LinEx(P), the set of linear extensions of the precedence poset, is sound and complete for finding an equivalent ordering minimizing FAQ-width.Every φ-equivalent ordering has an ordering in LinEx(φ) with the same FAQ-width.
  • When ∅⊂L⊂[n], FAQ-width can be arbitrarily larger than fractional hypertree width.In a star graph, fhtw(H)=1, while prefixing all but the center forces the center to be last in every equivalent ordering.
  • Theorem F.13 bounds FAQ-width by (1 + L-ss(H)) · fhtw(H).The proof constructs a tree decomposition and an equivalent ordering consistent with the L-prefix constraint.
  • FAQ-width is bounded exactly when both L-star size and the fractional hypertree width of the relevant hypergraph are bounded.

F.2.3 Approximating

The approximation framework reduces equivalent variable-ordering selection to fractional hypertree-width decompositions. It yields additive FAQ-width guarantees and tractability results for bounded-width FAQ and conjunctive-query classes.

  • The hypergraph H_L contains edges wholly inside L and one neighborhood edge U(C) for each connected component C of H−L.H_L is essentially the contraction of (H,L) described in earlier work.
  • Given a fractional hypertree-width approximation factor g, the algorithm computes an equivalent ordering σ with faqw(σ) ≤ faqw(φ) + g(faqw(φ)).Its running time is |H|·t(|H|,faqw(φ)) under the stated black-box assumptions.
  • The construction combines decompositions for H_L and each component of H−L, adds U(C) to component bags, and eliminates variables in L last.
  • For constant faqw(φ)≤c, a polynomial-time algorithm computes an equivalent ordering with faqw(σ)=O(faqw^3(φ)).
  • #CQ is tractable for query classes with bounded FAQ-width, and bounded FAQ-width is necessary under FPT ≠ W[1].
  • The factor-oracle representation supports queries respecting σ, with preprocessing and query answering described as near-linear and ˜O(1), respectively.Indicator projections require separate preprocessing.

G.3 Succinct Representation

This section develops succinct representations for FAQ input factors and explains how InsideOut can operate on encoded rather than unpacked functions. The framework covers decision diagrams, factorized representations, sparse tables, and structured matrix products.

  • The representations aim to reduce factor-storage size and enable efficient FAQ algorithms without unpacking succinct inputs.
  • Decision Diagram Representation: Decision diagrams generalize OBDDs and can be exponentially smaller than equivalent GDNF representations.
  • Factorized Databases: Factorized representations recursively combine factors through unions and Cartesian products, with repeated subexpressions optionally shared in DAGs.
  • Factorized Databases: For factorized inputs, prior work shows that the output can also be represented in the same format with tight output-size bounds.
  • Fast Matrix Vector Multiplication: Structured matrices can yield sub-quadratic matrix-vector multiplication by changing the factor representation and elimination order while retaining the same algorithm.
  • Fast Matrix Vector Multiplication: Circulant matrix-vector multiplication is expressed as C·b = F^-1·(F·c)·(F·b), connecting convolution and FAQ-SS representations.
Loading 1504.04044v7…