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 a shared algebraic structure across diverse problems and the tractability effects of input and output representations. It introduces InsideOut and characterizes semantically equivalent variable orderings, reporting a new non-trivial efficient result for #QCQ.

  • Problem

    The paper asks how diverse problems sharing an algebraic structure can be analyzed while accounting for representation-dependent tractability.

    Source: §1.1 · p. 1, §1.3 · p. 3

  • Method

    It introduces InsideOut, a variable-elimination algorithm, and defines semantically equivalent variable orderings for FAQ queries.

    Source: §2.2 · p. 4, §2.3 · p. 5

  • Results

    The paper reports a new result on #QCQ, for which no non-trivial efficient algorithms were previously known to the authors.

    Source: §3.4 · p. 10

  • Takeaways & Limitations

    FAQ provides a common framework for analyzing problems across constraint satisfaction, databases, matrix operations, graphical models, and logic.

    Source: §1.1 · p. 1

    The analysis assumes that most input and output factors use the listing representation.

    Source: §4.1 · p. 11

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 introduction shows that diverse problems share an algebraic structure captured by Functional Aggregate Queries (FAQ). It defines FAQ, explains representation choices, and previews the paper’s InsideOut-based analysis of variable orderings.

1.1 Motivating examples

  • Matrix multiplication, probabilistic inference, and quantified conjunctive queries exemplify problems unified by the Functional Aggregate Query framework.The framework also covers problems from CSP, databases, matrix operations, logic, coding theory, and complexity theory.Source: §1.1 · p. 2

1.2 The FAQ problem

  • FAQ computes an output function from input factors by aggregating over bound variables while retaining designated free variables.Each bound variable has an aggregate operator, with operators constrained by commutative-semiring conditions and at least one semiring aggregate required.Source: §1.2 · pp. 2–3

1.3 Input and output representation

  • Input and output representation materially affects FAQ tractability; the paper initially assumes sparse listing representations but supports a more general class.Listing representation stores all nonzero factor tuples and is common in CSP, databases, and sparse matrix computation.Source: §1.3 · p. 3

1.4 Paper organization

  • The paper develops InsideOut, characterizes semantically equivalent variable orderings, and searches for the best ordering before addressing representation effects and SAT/#SAT.The organization preview assigns these topics to Sections 5–8, including runtime analysis and efficient search for the fastest ordering.Source: §1.4 · pp. 3–4

2 SUMMARY OF CONTRIBUTIONS

The paper develops FAQ as a general declarative framework and InsideOut as a variable-elimination algorithm, with technical results on valid orderings, FAQ-width, and compact representations. It applies this framework across structured matrices, CSPs and logic, probabilistic graphical models, and matrix operations, summarizing corresponding runtimes.

2.1 Conceptual contribution

  • FAQ substantially generalizes SumProd and captures logical problems such as QCQ and #QCQ as a declarative query language over functions.The paper also relates output representation to factorized databases and shows that input representations can change tractability.Source: §2.1 · p. 4

2.2 Algorithmic contribution

  • InsideOut extends variable elimination with OutsideIn computation, indicator projections, and aggregate-product swaps, achieving time ˜O(N^faqw(σ) + ∥φ∥) for a chosen ordering σ.OutsideIn enables worst-case optimal joins within fractional edge-cover bounds, while indicator projections provide hypertree-width-style guarantees.Source: §2.2 · p. 4
  • With compactly represented factors, modified InsideOut recovers beyond-worst-case join results for Minesweeper and Tetris [2], plus tractability results for SAT and #SAT on β-acyclic formulas [74].These cases remain useful even when fractional hypertree-width bounds do not apply.Source: §2.2 · p. 4

2.3 Main technical contributions

  • The paper defines EVO(φ), characterizes its members through component-wise equivalence and linear extensions of a precedence poset, and provides polynomial-time membership testing.The precedence structure depends on both query scoping and hypergraph connectivity; FAQ-width is minimized over EVO(φ), reducing to fractional hypertree width for SumProd.Source: §2.3 · pp. 5–6
  • An approximation algorithm constructs an ordering with faqw(σ) ≤ opt + g(opt), improving to faqw(σ) ≤ g(opt) for FAQ-SS.Every linear extension of the precedence poset is semantically equivalent, and some such extension matches the FAQ-width of every equivalent ordering.Source: §2.3 · p. 6

2.3.2 The effect of input and output representation.

  • The framework handles representations beyond truth tables and listings, including GDNFs, decision diagrams, and algebraic decision diagrams.It views an input factor as potentially being the output of another FAQ instance.Source: §2.3.2 · pp. 6–7

2.3.2 The effect of input and output representation

  • InsideOut handles FAQ inputs and outputs represented as FAQ instances, quantifies improvements over naïve quadratic algorithms for structured matrices including DFT, and explains beyond-worst-case joins and acyclic SAT/#SAT as FAQ cases.For overly compact input factors, fewer FAQ queries remain tractable and fractional hypertree width no longer applies, although variable elimination remains useful with different subproblem algorithms.Source: §2.3.2 · p. 7

2.4 Highlights of our corollaries

  • Table 1 reports runtimes for selected FAQ corollaries assuming an optimal variable ordering, covering CSPs and logic, probabilistic graphical models, and matrix operations.InsideOut improves or extends results in CSPs and logic, improves PGM results using fractional hypertree width bounds, and gives no new matrix-operation results while explaining Matrix-Chain Multiplication and rewriting the DFT result.Source: §2.4 · p. 7, Table 1 · p. 8

3 RELATED WORK

The related work connects FAQ to semiring-based inference, factorized databases, hypergraph width parameters, and finite model theory. It emphasizes that InsideOut generalizes these lines of work and unifies prior tractability results while yielding new results for #QCQ.

3.1 Problems on one semiring

  • FAQ-SS is a semiring-only special case encompassing problems such as CSPs, while Aji and McEliece studied it as MPF using message passing meeting the treewidth bound.Their applications include Matrix Chain Multiplication, Matrix Vector Multiplication, FFT, and coding-theory decoding problems.Source: §3.1 · pp. 8–9

3.2 Factorized databases

  • Factorized databases and InsideOut have the same dynamic-programming runtime for the single-semiring case, differing mainly in top-down versus bottom-up evaluation.FAQ additionally supports multiple aggregate types and contributes the EVO characterization and an approximation algorithm for faqw.Source: §3.2 · p. 9

3.3 Width parameters

  • Database, CSP, and PGM research developed increasingly general width parameters, from acyclicity and treewidth to hypertree, generalized hypertree, and fractional hypertree width.Bounded width generally yields polynomial-time evaluation, while acyclic instances admit Yannakakis-style join evaluation and belief propagation.Source: §3.3 · pp. 9–10

3.4 Finite model theory

  • Finite-model-theory work characterizes tractable #CQ and QCQ cases through parameters such as quantified star size and elimination-ordering width, whereas InsideOut extends these results to #QCQ.For #ACQ, tractability holds in data and query complexity but not combined complexity, where the problem is #P-complete.Source: §3.4 · p. 10
  • InsideOut unifies prior results for CQ, #CQ, and QCQ, with unbounded runtime improvements over earlier results and the first known non-trivial efficient algorithms for #QCQ.The framework places these results under one variable-elimination umbrella.Source: §3.4 · p. 10

4 PRELIMINARIES

This section establishes the factor representations and size conventions, fractional-cover terminology, hypergraph width parameters, and ordering-based characterizations used throughout the paper. It also connects vertex orderings and elimination sequences to acyclicity and tree-decomposition widths.

4.1 Factors, their representations, and sizes

  • Input and output factors are usually stored in listing representation, containing exactly their nonzero tuples; N denotes the maximum input-factor size.Entries absent from a listing are 0-entries, and other representations are discussed later.Source: §4.1 · p. 11

4.2 AGM-bound and fractional cover numbers

  • Integral and fractional edge-cover numbers are defined by integer-program and linear-program relaxations, while the AGM-bound is the corresponding data-dependent quantity.Cover numbers depend only on the hypergraph, whereas AGM depends on the input factors.Source: §4.2 · pp. 11–12

4.3 Tree decomposition, acyclicity, and width-parameters

  • Tree decompositions use connected bags covering every hyperedge, and their width framework yields treewidth, generalized hypertree width, and fractional hypertree width via s, ρ, and ρ* respectively.α-acyclicity requires every bag to be a hyperedge, while adding a universal hyperedge motivates β-acyclicity.Source: §4.3 · p. 12

4.4 Vertex/variable ordering and its equivalence to tree decomposition

  • Elimination hypergraph sequences associate each vertex ordering with successive edge-union constructions, linking orderings to tree decompositions and induced g-width.A monotone-width lemma shows that hypergraph g-width equals the minimum induced g-width over vertex orderings.Source: §4.4 · pp. 13–14
  • β-acyclicity holds exactly when some ordering makes incident hyperedges nested for every vertex, and it can be verified in polynomial time.The ordering characterization also extends to treewidth, generalized hypertree width, and fractional hypertree width through induced-width bounds.Source: §4.4 · p. 14

5 THE InsideOut ALGORITHM

This section develops the InsideOut algorithm for general FAQ queries, including its elimination rules, output recovery, and factorized representations. It analyzes runtime through fractional FAQ-width and characterizes the selection of equivalent variable orderings using a precedence-poset framework.

5.1.1 Backtracking search.

  • OutsideIn evaluates FAQ-SS by backtracking over nonzero tuples, using join algorithms [2, 67, 69, 89], and runs in O(n·m·log N·AGMH(V)).It accumulates each tuple’s factor product into the corresponding free-variable entry; the method uses little extra space but may recompute subproblems.Source: §5.1.1 · p. 15

5.1.2 Dynamic programming with variable elimination. Ê

  • Variable elimination folds common factors using distributivity, repeatedly computing an intermediate factor for one bound variable and replacing its incident edges with a new hyperedge over the remaining scope.The resulting problem is another FAQ-SS instance on a modified multi-hypergraph, and the process continues until all specified variables are eliminated.Source: §5.1.2 · pp. 15–16

5.2.1 Introducing the indicator projections.

  • InsideOut uses indicator projections to avoid computing intermediate entries annihilated by factored-out sparse factors, solving the resulting FAQ-SS instance with OutsideIn.The projections participate instead of the original factors, and the required multiway join is computed directly with a worst-case optimal join algorithm rather than individual semijoins.Source: §5.2.1 · p. 16

5.2.2 The general case.

  • For general FAQ queries, semiring aggregates use the indicator-projection elimination strategy, whereas product aggregates remove the variable from incident factors by aggregating over its domain.Repeated elimination constructs a sequence of hypergraphs, with product-variable edges simply losing the eliminated vertex and other eliminations adding a new scope edge.Source: §5.2.2 · pp. 16–17
  • Idempotent product aggregates let InsideOut avoid powering intermediate factors and bypass the costly intermediate FAQ-SS computation, including factors with values in {0, 1}.For non-idempotent factors, passing through a product aggregate powers factors pointwise by |Dom(X_n)|, while idempotence permits factoring them out as in the semiring case.Source: §5.2.2 · pp. 17–18

5.2.3 Output representation.

  • After eliminating all bound variables, the remaining all-free FAQ can be evaluated with OutsideIn, but computing its factorized representation can improve runtime.The section defines the final instance on H_f and contrasts direct evaluation with first producing a factorized output.Source: §5.2.3 · p. 18
  • InsideOut recovers free-variable outputs by eliminating them first, computing intermediate factors, and using those factors to filter zero-output tuples before running OutsideIn.The recovery procedure is equivalent to the two phases of Yannakakis’s algorithm [90], and the implementation in LogicBlox follows this elimination/recovery method.Source: §5.2.3 · p. 19

5.3 Analysis

  • Theorem 5.5 bounds InsideOut’s runtime by the costs of variable elimination and final output reporting, with output reporting taking O(f · (f + m) · log ∥φ∥ · ∥φ∥) time.The analysis includes a data-independent O(n^2 · m) term for computing elimination structures and distinguishes product aggregates from other aggregates.Source: §5.3 · p. 20
  • For the example query, a standard ordering can require O(N^2 log N) = ˜O(N^2), whereas {0,1}-valued factors permit an equivalent ordering with runtime O(N).The improvement uses idempotence of multiplication on {0,1}-valued factors and the ordering (X5, X1, X2, X3, X4, X6).Source: §5.3 · pp. 21–22

5.4 Equivalent variable orderings

  • A φ-equivalent variable ordering places all free variables first and preserves the FAQ function for every permitted choice of input factors.Under a function-class promise F, equivalence requires preservation only for input factors belonging to F, such as {0,1}-valued functions.Source: §5.4 · p. 23

5.5 FAQ-width of a variable ordering

  • The best variable ordering minimizes the InsideOut runtime over EVO(φ), but the equivalence constraint makes this optimization harder than ordinary variable elimination.FAQ-width is introduced to characterize this ordering objective, while standard graphical-model, matrix, and constraint-satisfaction settings allow all variable orderings.Source: §5.5 · p. 23
  • Fractional FAQ-width depends on the chosen variable ordering, while input-factor projection sizes are generally instance-dependent, complicating direct runtime minimization.Different representations of the same FAQ query can therefore yield substantially different InsideOut runtimes.Source: §5.5 · pp. 23–25
  • InsideOut runs in time ˜O(N^faqw(σ) + ∥φ∥), with the hidden factor polynomial in query size and logarithmic in data size.This follows from Proposition 5.9 and the fractional FAQ-width definition.Source: §5.5 · p. 25
  • Equivalent orderings are characterized as the linear extensions LinEx(P) of a precedence poset P defined on the query’s expression tree.The expression tree and precedence poset can be constructed in polynomial time in query complexity.Source: §5.5 · p. 25
  • Every ordering in LinEx(P) is φ-equivalent, establishing the soundness of the precedence-poset characterization.This gives a structurally defined class of orderings that preserves the input FAQ query’s semantics.Source: §5.5 · p. 25
  • Component-wise equivalence preserves both EVO-membership and faqw, and every φ-equivalent ordering is component-wise equivalent to some ordering in LinEx(P).Thus, all equivalent orderings can be enumerated in exponential time through component-wise equivalence while preserving width.Source: §5.5 · p. 25
  • Every φ-equivalent ordering either lies in LinEx(P) or has the same faqw as an ordering there, and EVO-membership can be checked in polynomial time.The completeness result assumes that different variable aggregates do not commute.Source: §5.5 · pp. 25–26

6 CHARACTERIZING EQUIVALENT VARIABLE ORDERINGS

This section develops a precedence-poset and component-wise equivalence framework to characterize semantically equivalent variable orderings for FAQ queries and reduce FAQ-width optimization to linear extensions. It extends the construction to idempotent and general product aggregates, establishing soundness broadly while noting that completeness remains open for the general case.

6.1 FAQ with only semiring aggregates

  • Every linear extension of the expression-tree precedence poset is φ-equivalent, while every φ-equivalent ordering is component-wise equivalent to a linear extension and therefore has the same FAQ-width.Thus, EVO(φ) and the search for an ordering approximating faqw(φ) can be restricted to linear extensions of the precedence poset.Source: §6.1 · p. 26, §6.1.3 · p. 30

6.1.1 Expression tree and precedence poset

  • The expression tree is built by compartmentalizing variables according to connected components of the FAQ hypergraph, then compressing parent-child nodes with identical aggregate tags.The resulting tree induces a precedence poset in which ancestor variables precede descendants, while variables in the same node remain incomparable.Source: §6.1.1 · pp. 27, 29
  • For FAQ-SS instances, the compressed expression tree has depth at most one, with free variables at the root and remaining variables in its children.The construction begins with tagged variables, including a dummy free variable, and recursively processes connected components before removing the dummy variable.Source: §6.1.1 · p. 27

6.1.2 What makes two aggregates different?

  • Any two aggregates are mutually commutative if and only if they are identical, so distinct input aggregates are treated as noncommuting under the paper’s functional-identity assumption.Aggregates can nevertheless coincide accidentally on a restricted domain, such as min and × on {0,1}.Source: §6.1.2 · pp. 29–30

6.1.3 Soundness and completeness.

  • LinEx(P) can be a proper subset of EVO(φ), because factorization allows additional interleavings that do not change FAQ-width.In the example, LinEx(P) ⊊ EVO(φ), while the omitted orderings are irrelevant to computing faqw.Source: §6.1.3 · pp. 31–32
  • Constructing the compressed expression tree before selecting variables is essential, since a variable-wise precedence construction alone can exclude valid equivalent orderings.The example shows that selecting X5 first requires compression before determining the admissible first variable.Source: §6.1.3 · p. 32
  • Every φ-equivalent ordering places its first variable after the free variables in a child node of the expression-tree root, identifying all possible first choices.Lemma 6.9 is proved by constructing factors that distinguish an ordering violating this condition from an equivalent linear extension.Source: §6.1.3 · pp. 32–33
  • Component-wise equivalent orderings induce identical rooted tree decompositions and therefore have the same FAQ-width.The proof establishes this by induction over connected components and recursive deletion of the first variable.Source: §6.1.3 · p. 33
  • Theorem 6.12 establishes that EVO(φ) = CWE(LinEx(P)): an ordering is φ-equivalent exactly when it is component-wise equivalent to some linear extension of precedence poset P.Component-wise equivalence permits recursive interleavings across connected components while preserving equivalence and FAQ-width.Source: §6.1.3 · pp. 33–34
  • The completeness proof constructs a linear extension component by component that is CW-equivalent to any semantically equivalent variable ordering.For each connected component, an inductively obtained linear extension is combined after the first variable, yielding a global ordering in LinEx(P).Source: §6.1.3 · p. 34
  • Corollary 6.14 states that faqw(φ) equals the minimum FAQ-width over all linear extensions of the expression tree’s precedence poset.This removes redundant variable orderings from the search for an optimal ordering.Source: §6.1.3 · p. 35

6.2.1 Problem specification.

  • The generalized FAQ case allows input factors over idempotent elements D_I, includes aggregates not closed under D_I, and seeks orderings in EVO(φ, F(D_I)).The formulation includes aggregates closed under D_I and covers QCQ and #QCQ instances; EVO(φ, F(D_I)) is stronger than EVO(φ).Source: §6.2 · p. 35, §6.2.1 · pp. 35–36

6.2.2 Non-mutually-commutative aggregates vs. non-identical aggregates.

  • No two non-identical semiring aggregates commute under D_I, and a product aggregate does not commute with a semiring aggregate that is not closed under D_I.The latter case uses elements g_1,g_2 in D_I with g_1 ⊕ g_2 ≠ (g_1 ⊕ g_2)^2 to derive a contradiction.Source: §6.2.2 · p. 36
  • Proposition 6.18 provides D_I-valued functions φ_ij for aggregate pairs that are non-identical semiring aggregates or consist of one product and one non-product aggregate.These functions support distinguishing aggregate pairs through inputs whose ranges lie in D_I.Source: §6.2.2 · p. 37

6.2.3 Expression tree and precedence poset.

  • The expression tree is built by query extension, compartmentalization using extended components and dangling variables, and compression of adjacent nodes with the same tag.Query extension adds missing pairwise factors, compartmentalization recursively organizes tagged variables, and compression merges same-tag child nodes.Source: §6.2.3 · p. 38
  • When the first tag block has tag ⊗, compartmentalization yields at most one extended component with an empty dangling set, and final ⊗ nodes have at most one non-⊗ child.Compression also prevents an ⊗ node from having an ⊗ child.Source: §6.2.3 · p. 40
  • The tree can contain multiple copies of a product variable, but their distribution has structural properties that enable these copies to be handled.A product variable may occur in multiple tree nodes, unlike free and semiring variables.Source: §6.2.3 · p. 41
  • For product aggregates, no copy of a variable can be a strict ancestor of another copy, and later product variables cannot be ancestors of earlier ones.These restrictions rule out the ancestor pattern possible for semiring variables and support interpreting the expression-tree comparison relation as a partial order.Source: §6.2.3 · p. 42
  • The relation induced by ancestor precedence in the expression tree is a valid precedence poset on variables.This remains valid despite variables appearing multiple times in the expression tree.Source: §6.2.3 · p. 42
  • The poset places every semiring aggregate not closed under D_I before every product aggregate.This precedence follows from the query-extension construction, which makes each such semiring variable precede all product variables in the expression tree.Source: §6.2.3 · p. 43
  • Every linear extension of the precedence poset is φ-equivalent to the original FAQ expression.Soundness follows by factorizing conditional expressions across extended components and dangling sets, using closure and idempotence under D_I; compression preserves the argument because product variables play no role there.Source: §6.2.3 · pp. 43, 45
  • Every equivalent variable ordering obeys the same constraint, placing non-D_I-closed semiring variables before product variables.The completeness argument constructs an input-factor assignment that distinguishes an ordering violating this constraint.Source: §6.2.3 · pp. 45–46
  • The characterization relies on extended components, while dangling variables may be placed anywhere later in the ordering.The proof constructs compatible component orderings that preserve product-variable relative order and produce a linear extension componentwise-equivalent to the original ordering.Source: §6.2.3 · pp. 47–48
  • Componentwise-equivalent orderings remain valid elimination orderings and preserve fractional FAQ-width.Proposition 6.32 establishes π ∈ EVO(φ, F(D_I)) and faqw(σ) = faqw(π).Source: §6.2.3 · p. 47
  • Theorem 6.33 states that φ-equivalent orderings are exactly those componentwise-equivalent to a linear extension of the precedence poset P.Formally, EVO(φ, F(D_I)) = CWE(LinEx(P)).Source: §6.2.3 · p. 47

6.3 General FAQ query

  • General FAQ queries address non-idempotent product aggregates, a case with few practical examples that requires semantic rather than data-dependent idempotence.Semantic idempotence treats the product operator ⊗ as idempotent under D when a ⊗ a = a for every a ∈ D; this section focuses on the non-idempotent case.Source: §6.3 · p. 48
  • Extending every input factor with all product variables forces required precedence relations, such as x1 before x3, at the semantic level.The algorithm still runs on the original query rather than the extended query.Source: §6.3 · pp. 49–50
  • The expression tree and precedence poset are constructed from the extended query using compartmentalization, compression, and the precedence-poset definition.The extension is a semantic device for determining equivalent orderings, not a change to the query executed by InsideOut.Source: §6.3 · pp. 49–50
  • Because every extended factor contains all product variables, the semantic analysis no longer requires product idempotence or power-raising operations.The same analysis used earlier can therefore be applied to the extended query without the idempotence assumption.Source: §6.3 · p. 50
  • Every linear extension of the precedence poset is φ-equivalent to the original FAQ query.This is Theorem 6.37 for the general FAQ query construction.Source: §6.3 · p. 50
  • A rigorous completeness proof is omitted because it requires lengthy definitions and unnatural assumptions, leaving equality between EVO(φ) and CWE(LinEx(P)) as an open problem.The authors state that this general FAQ class lacks strong practical motivation for developing those proofs here.Source: §6.3 · p. 50

7 APPROXIMATING THE FAQ-WIDTH

This section develops polynomial-time approximation algorithms for FAQ-width, using fractional-hypertree-width approximations and expression-tree structure to construct variable orderings with controlled width. It also establishes tractability results for QCQ and #QCQ with bounded FAQ-width and relates FAQ-width to Chen–Dalmau’s prefix-graph width.

7 APPROXIMATING THE FAQ-WIDTH

  • FAQ-width equals fractional hypertree width for SumProd queries and queries with all variables free, implying that computing FAQ-width and an optimal FAQ-width tree decomposition are NP-hard.The section therefore targets polynomial-time approximation rather than exact optimization.Source: §7 · p. 50

7.1 FAQ with only semiring aggregates

  • The semiring-only analysis lower-bounds FAQ-width through the fractional hypertree widths of hypergraphs induced at expression-tree nodes, enabling the black-box approximation guarantee.These node-specific hypergraphs encode projections of residues contributed by child subtrees and intersecting hyperedges.Source: §7.1 · pp. 51–52
  • For semiring-only aggregates, an fhtw approximation with guarantee g and runtime t yields a φ-equivalent ordering σ with faqw(σ) ≤ faqw(φ) + g(faqw(φ)) in time |H| · t(|H|, faqw(φ)).The construction applies the black-box fhtw algorithm to hypergraphs associated with expression-tree nodes, then concatenates the resulting local orderings while respecting precedence.Source: §7.1 · p. 52

7.2 FAQ with an inner FAQ-formula closed under idempotent elements

  • For FAQ formulas with an inner formula closed under idempotent elements, the method distinguishes semiring and product nodes and modifies residue projections to exclude hyperedges intersecting semiring descendants.The resulting bounds apply to semiring nodes, where contributions from semiring descendants are summarized in the modified construction.Source: §7.2 · pp. 53–54
  • Theorem 7.5 extends the approximation-algorithm framework to FAQ queries with idempotent inner formulas, assuming an fhtw approximation with guarantee g and runtime t.The supplied passage states the theorem’s assumptions and setup but does not include its complete concluding bound.Source: §7.2 · p. 54
  • Theorem 7.5 constructs the final ordering as a linear extension of a precedence poset and guarantees faqw(σ) ≤ faqw(φ, D_I) + g(faqw(φ, D_I)).The construction uses tree decompositions for semiring-node hypergraphs, while product variables can be ordered arbitrarily because they do not affect FAQ-width.Source: §7.2 · pp. 54–55
  • The algorithm computes σ ∈ EVO(φ, D_I) with faqw(σ) = O(faqw^3(φ, D_I)) in time O(|H|^O(faqw^3(φ,D_I))).If faqw(φ, D_I) is bounded by a constant, the runtime becomes poly(|H|) = ˜O(1).Source: §7.2 · p. 55

7.2.1 Corollaries in Logic.

  • Bounded FAQ-width makes QCQ tractable, and #QCQ is tractable for quantified conjunctive queries whose FAQ-width is bounded.The QCQ result follows through the reduction from QCQ to FAQ, while the #QCQ corollary resolves an open question posed by Durand and Mengel [35].Source: §7.2.1 · pp. 55–56
  • FAQ-width is strictly stronger than Chen–Dalmau’s prefix-graph width: one family has bounded FAQ-width but unbounded prefix-graph width, with widths 2 versus n + 1 in the example.The result also implies Chen and Dalmau’s main positive result [25].Source: §7.2.1 · p. 56

8 INPUT AND OUTPUT REPRESENTATION

This section examines input and output representations for InsideOut, including oracle and compact encodings and corresponding representation-specific procedures. It characterizes tradeoffs among value queries, enumeration, preprocessing, and width under FAQ composition.

8.1 The factor oracle

  • InsideOut and OutsideIn extend beyond listing representations when factor oracles support conditional queries and product marginalization.The conditional-query assumption requires totally ordered domains and successor-style queries, while product marginalization returns an oracle on S−{i} with at most ||ψ_S|| ⊗-operations.Source: §8.1 · p. 57
  • Under these two oracle assumptions, Theorem 8.1 generalizes InsideOut’s prior runtime analysis to the more general factor-oracle model.The theorem bounds both the number of conditional queries and the total number of ⊕ operations using the notation of Theorem 5.5.Source: §8.1 · p. 57

8.2 Input representations parsimoniously reducible to FAQ

  • Truth tables and other succinct representations can be reduced to listing representations, but this reduction may require solving a more complicated composed FAQ.The discussed examples include GDNF, decision diagrams, factorized representations, DFTs, and ADDs.Source: §8.2 · p. 58

8.3 Input representations not parsimoniously reducible to FAQ

  • Compact SAT and #SAT encodings can be exponentially smaller than listing representations, so reducing them first is too costly and OutsideIn must be modified.The framework retains InsideOut as variable elimination while tailoring OutsideIn to compact encodings represented by box factors.Source: §8.3 · pp. 58–59
  • For SAT, #SAT, and box-cover problems, the framework explains existing algorithms through FAQ instances with box factors and the InsideOut/OutsideIn duality.Intermediate factors remain products of box factors; for β-acyclic hypergraphs, the supplied passages state tractability results for SAT/#SAT and linear-time solvability for box cover.Source: §8.3 · p. 59
  • For SAT, eliminating X_n applies Davis–Putnam resolution by combining every clause containing X_n with every clause containing ¯X_n.The resulting resolvents form a new SAT instance without X_n, avoiding enumeration of all 2^|U_n| assignments but potentially causing clause explosion.Source: §8.3 · p. 60
  • For β-acyclic CNF formulas, a nested elimination order prevents clause or box-factor explosion and makes SAT polynomial-time solvable [74].Nested clause sets form chains, so elimination does not increase the number of clauses.Source: §8.3 · p. 60
  • For #SAT and weighted #WSAT, clauses are represented as Boolean-valued factors, and variable elimination produces an equivalent instance over one fewer variable.#WSAT assigns each clause a nonnegative weight, with ordinary #SAT recovered when every clause weight is 0.Source: §8.3 · p. 60
  • A refined nested-order construction preserves β-acyclicity and keeps the eliminated #WSAT instance the same size, proving #SAT polynomial-time solvable for β-acyclic CNF.The construction ensures |C′_n| = |∂(X_n)| after eliminating X_n.Source: §8.3 · pp. 61–62

8.4 Output representation

  • InsideOut can modify its final stage to support multiple output representations, evaluated by preprocessing time, value-query time, and enumeration delay.The discussion assumes FAQ-SS with a single free variable and Boolean domain, and changes the step after eliminating X_n,…,X_{f+1}.Source: §8.4 · p. 62
  • The default listing representation uses preprocessing time ˜O(AGM(F)), constant value-query time, and constant enumeration delay after InsideOut elimination.OutsideIn reports the output in time ˜O(AGM(F)), with output size at most AGM(F).Source: §8.4 · p. 63
  • The ˜O(1)-delay representation supports ˜O(1) value queries and enumeration when intermediate factors are stored as BTree/trie structures.The alternative representation also generalizes factorized representation to FAQ representation.Source: §8.4 · p. 63
  • The ˜O(1)-delay representation is insufficient for future conditional or product marginalization queries posed in unknown variable orders.If future queries follow X_1,...,X_f, the intermediate factors suffice; message passing prepares calibrated bags for broader query orders, with tradeoffs left open.Source: §8.4 · p. 63
  • Message passing yields overall complexity ˜O(N^fhtw(H_f)) while calibrating bags for conditional queries along any GYO elimination order.InsideOut first eliminates X_i for i>f, then message passing runs on a tree decomposition of H_f.Source: §8.4 · p. 63

8.5 Composition of FAQ instances

  • Proposition 8.5 bounds the composed hypergraph using fhtw(H_0) multiplied by max over e in E_0 of ρ*(H_1^e), for every hypergraph H_0 and corresponding collection.The proof gives a better bound for specific hypergraphs.Source: §8.5 · p. 64
  • Even when fhtw(H_0)=1 and every component fhtw(H^1_e)=1, the composition can have fhtw(H_0∘H_1)≥n.The construction creates a clique K_n among the shared vertices, plus n spokes.Source: §8.5 · pp. 64–65
  • The construction reuses component tree-decomposition bags, then applies a greedy patchup phase to restore the running-intersection property, yielding a valid tree decomposition for H0 ◦ H1.Source: §8.5 · p. 65

9 CONCLUDING REMARKS … A.4 The set semiring

The concluding section and appendix highlight FAQ’s broad applicability across semiring-based inference, transforms, decoding, joins, and related computational tasks, while discussing practical implementation considerations for InsideOut. Together, they connect the framework to diverse problems through semiring-valued FAQ expressions and reductions.

9 CONCLUDING REMARKS

  • InsideOut-based implementations outperform existing commercial systems by at least an order of magnitude on selected graph-pattern queries and achieve orders-of-magnitude speedups over exporting data to R or Python.InsideOut was implemented in the LogicBlox database system and used to train a large class of machine-learning models inside the database.Source: §9 · pp. 65–66
  • Real-world InsideOut implementations must handle predicates such as a < b and a + b = c that have no size; assigning them infinite size can make AGM(Q) = N2 although |Q| ≤ N, or yield an infinite bound.Source: §9 · p. 66
  • Selecting an efficient variable ordering is also difficult because there are n! orderings, optimizer estimates are costly, and minimizing FAQ-width is NP-hard.The authors therefore use either the approximation algorithm from Section 7 or a greedy heuristic in practice.Source: §9 · p. 66

A MORE EXAMPLES OF PROBLEMS REDUCIBLE TO FAQ

  • FAQ captures problems across graphical-model inference, matrix multiplication, constraint satisfaction, quantified conjunctive queries, and other domains, with all reductions to the general multi-semiring FAQ presented as new.The examples begin by distinguishing FAQ-SS from the general FAQ over multiple semirings.Source: A MORE EXAMPLES OF PROBLEMS REDUCIBLE… · p. 70

A.1 The Boolean semiring

  • Under the Boolean semiring, satisfiability, k-colorability, Boolean and general conjunctive queries, natural joins, CSPs, and list recovery reduce to FAQ-SS.The examples also highlight that input encoding matters: SAT factors are clause-encoded, whereas BCQ factors use explicit tuple tables.Source: §A.1 · pp. 70–71

A.2 The sum-product semiring

  • Under the sum-product semiring, counting occurrences of fixed subgraphs such as triangles or k-cliques becomes an FAQ-SS computation over graph-edge factors.Induced-subgraph counting adds compactly represented inequality factors for non-edges.Source: §A.2 · p. 72
  • In the sum-product semiring, marginal and conditional distributions in probabilistic graphical models are special cases of FAQ-SS, while MAP queries use the max-product semiring.The passages also identify matrix-vector multiplication and the discrete Fourier transform as FAQ-SS instances, with the algorithm implying the Fast Fourier Transform.Source: §A.2 · p. 73

A.3 The max-product semiring

  • Maximum-likelihood decoding for binary linear codes is represented as a max-product FAQ-SS instance using channel factors and parity-check factors.The construction is equivalent to computing the most likely valid codeword probability under the code constraints.Source: §A.3 · p. 75

A.4 The set semiring

  • A natural join query is expressed over the set semiring by assigning each hypergraph edge a set-valued relation factor and evaluating a constant set-valued function.Each factor’s domain is the product of the domains of its variables, and the resulting FAQ output is the join result.Source: §A.4 · p. 75

A.5 Applications of the FAQ problem

This section shows that FAQ captures #CQ when queries are quantifier-free but requires extensions or alternative reductions for existential, universal, and counting quantified conjunctive queries. It gives reductions of QCQ and #QCQ to FAQ, including a later-used reduction where product aggregates universally quantified variables and input factors.

#CQ

  • #CQ reduces to FAQ-SS over the sum-product semiring for quantifier-free queries, but the straightforward mapping fails when existential quantifiers are present.The reduction maps true to 1 and false to 0.Source: §A.5 · p. 75

QCQ and #QCQ

  • QCQ cannot be reduced to FAQ-SS directly, while #QCQ—counting solutions to quantified conjunctive formulas—is harder still.QCQ contains both existential and universal quantifiers with a conjunction of atoms.Source: §A.5 · p. 76

QCQ – First Reduction

  • The first QCQ reduction represents quantified operators in FAQ, using max for the relevant quantified variables and atom-derived indicator factors.The section formulates the relation on free variables and defines each factor as an indicator of membership in the corresponding atom relation.Source: §A.5 · p. 76

QCQ – Second Reduction

  • The second QCQ reduction, used later in the paper, is notable because product aggregates both universally quantified variables and the input factors.It provides an alternative FAQ formulation of the relation on the free variables.Source: §A.5 · p. 76

#QCQ

  • #QCQ can likewise be reduced to FAQ by using a constant function together with atom-derived indicator factors to count tuples on the free variables.The construction parallels the preceding reductions for quantified conjunctive formulas.Source: §A.5 · p. 77

B REDUCTIONS FROM NON-SEMIRING TO SEMIRING

The section shows how non-semiring FAQ aggregates can be handled by mapping them to an extended commutative semiring, performing variable elimination there, and mapping results back when the required conditions hold. It illustrates the reduction with conditional averages, uniqueness quantification, and max-product, including a case where transfer back is unavailable.

Reduction framework

  • A two-way mapping to an extended commutative semiring lets FAQ inputs and computations be transferred to the new domain and results returned to the original domain.When the stated conditions hold, variable elimination can proceed as if the original structure were a commutative semiring.Source: B REDUCTIONS FROM NON-SEMIRING TO… · p. 77
  • If only conditions 1 and 2 hold, computations can proceed without the final transfer-back step, so factors and intermediate results remain in the extended domain.The original domain cannot be restored until all products in the extended semiring have been computed.Source: B REDUCTIONS FROM NON-SEMIRING TO… · p. 78

Example B.2 (Conditional average)

  • Conditional averaging becomes semiring-compatible by extending values to R × N, addressing the non-associativity of avg over R.The construction satisfies conditions 1, 2, and 3 and preserves the corresponding zero and one identities.Source: B REDUCTIONS FROM NON-SEMIRING TO… · p. 78

Example B.3 (Uniqueness quantification (∃!))

  • Uniqueness quantification cannot use XOR directly, but extending the domain to {0, 1, 2} yields a commutative-semiring reduction satisfying all three conditions.Binary unique reduces to XOR, whereas n-ary unique does not correspond to XOR for n>2.Source: B REDUCTIONS FROM NON-SEMIRING TO… · pp. 78–79

Example B.4 ((R, max, ×))

  • For (R, max, ×), extending the domain with NaN supplies the max identity but still fails distributivity, so the construction satisfies only conditions 1 and 2.The extended identities are 0 = (NaN, NaN) and 1 = (1, 1).Source: B REDUCTIONS FROM NON-SEMIRING TO… · p. 79

C TREE DECOMPOSITIONS AND VARIABLE ELIMINATION

This section establishes constructive links between tree decompositions and vertex orderings, including reduced decompositions, induced decompositions, and GYO elimination. These links characterize acyclicity and relate ordering-based widths to tree-decomposition widths.

Minimal tree decomposition

  • Reduced tree decompositions can be simplified by removing bags contained in neighboring bags, while preserving the decomposition and enabling inductive bounds on their size.A leaf bag in a reduced decomposition has a private vertex; removing that vertex and, when applicable, the bag, preserves reducedness for the smaller hypergraph.Source: C TREE DECOMPOSITIONS AND VARIABLE… · pp. 79–80

Tree decomposition from vertex ordering

  • A vertex ordering recursively induces a tree decomposition with at most n bags, whose bags are sets U_k and which is made non-redundant by reduction.The construction adds a bag U_n to a decomposition of the preceding hypergraph, then reduces the result; Proposition C.2 guarantees every final bag equals some U_k and is non-redundant.Source: C TREE DECOMPOSITIONS AND VARIABLE… · p. 80

GYO-elimination procedure

  • GYO elimination repeatedly removes contained bags and singly occurring vertices, and reversing the removed-vertex sequence yields an ordering whose induced fractional width is at most the decomposition’s width.The root bag may be chosen arbitrarily, so its vertices are eliminated last and appear first in the reversed ordering.Source: C TREE DECOMPOSITIONS AND VARIABLE… · p. 80

Vertex ordering from tree decomposition

  • A tree decomposition also induces a vertex ordering by recursively removing leaf bags’ private vertices; every U_k is contained in a bag, and the ordering is computable in polynomial time.The procedure first reduces and roots the decomposition, then appends each leaf bag’s private vertices after recursively processing the remaining tree.Source: C TREE DECOMPOSITIONS AND VARIABLE… · pp. 80–81

Acyclicity and widths

  • The constructions characterize α-acyclicity through orderings whose U_k sets fit within hyperedges and characterize β-acyclicity through orderings where every ∂_σ(v_k) is a chain.For α-acyclicity, the ordering-to-decomposition construction preserves hyperedge bags; for β-acyclicity, nest points yield the forward elimination order and a forbidden sequence contradicts the chain condition.Source: C TREE DECOMPOSITIONS AND VARIABLE… · pp. 81–82

D MISSING DETAILS FROM THE ANALYSIS OF InsideOut · E QUICK APPLICATIONS OF InsideOut · F MORE ON CHARACTERIZING EVO(휑) AND APPROXIMATING faqw(휑)

The applications show that InsideOut recovers efficient algorithms and familiar optimization procedures for matrix computations. Its runtime bounds include matrix-chain multiplication costs, FFT-related runtimes, and subquadratic Khatri–Rao multiplication.

E QUICK APPLICATIONS OF InsideOut

  • InsideOut’s optimal variable ordering for matrix-chain multiplication is exactly the optimal sequence of matrix multiplications, solvable by dynamic programming.The FAQ cost matches the usual matrix multiplication estimate at each elimination step.Source: E QUICK APPLICATIONS OF InsideOut · p. 83
  • InsideOut runs the DFT example in O(n log^4 n), a log^3 n factor slower than FFT’s O(n log n), while capturing FFT message passing as a special case.Preprocessing all required factors takes O(n log n), and the elimination itself also takes O(n log n).Source: E QUICK APPLICATIONS OF InsideOut · p. 83
  • InsideOut computes a circulant matrix-vector product in O(n log n) by chaining DFT, component-wise multiplication, and inverse DFT operations.The selected ordering corresponds to computing F · b, F · c, their component-wise product, and F−1 · u.Source: E QUICK APPLICATIONS OF InsideOut · p. 83
  • For the Kronecker product A = D ⊗ E, the fractional-cover analysis yields an overall runtime bound of O(n^3).The bound follows from the ordering Y1, Y0 and fractional covers for the intermediate sets and free variables.Source: E QUICK APPLICATIONS OF InsideOut · p. 83
  • For the column-wise product A = D ◦ E, suitable fractional covers in the stated variable ordering yield an overall runtime bound from expression (47).The construction covers the relevant elimination sets and the free variables using the displayed factors.Source: E QUICK APPLICATIONS OF InsideOut · p. 84
  • For the Khatri–Rao product, a straightforward edge cover gives only a quadratic runtime, but additional projected factors enable an O(n^5/3) InsideOut bound.The same runtime holds with the projections represented in truth-table form.Source: E QUICK APPLICATIONS OF InsideOut · p. 84

F.1 Qick applications of FAQ-SS without free variables (i.e. SumProd) · F.2 Variable ordering for FAQ with two blocks of semiring aggregates

FAQ-SS without free variables reduces to SumProd, where all variable orderings are equivalent and FAQ-width equals induced fractional edge-cover width, yielding applications to counting, graphical models, and joins. With two functionally different semiring aggregates, variable ordering becomes constrained by a precedence poset.

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

  • For FAQ-SS without free variables, all variable orderings are equivalent, every aggregate is a semiring aggregate, and faqw(σ) equals induced fractional edge-cover width.This special case connects directly to fractional hypertree width via Lemma 4.12.Source: §F.1 · p. 84
  • When fhtw(H) is bounded by a constant, Marx’s algorithm computes an ordering or decomposition with width O(fhtw^3(H)) in polynomial time.The algorithm runs in time O(|H|^O(fhtw^3(H))).Source: §F.1 · p. 84
  • Quantifier-free #CQ and probabilistic graphical-model partition functions run in ˜O(N^O(fhtw^3(H))) when fhtw(H) is bounded by a constant.The #CQ result is attributed to Theorem 1 from.Source: §F.1 · p. 85
  • For natural joins, InsideOut achieves ˜O(N^fhtw(H) + ∥φ∥) time, combining computation with the cost of reporting the output.The output size can exceed the width-based computation bound, so reporting must be accounted for explicitly.Source: §F.1 · pp. 85–86
  • A trie-like index ordered by the eliminated variable implicitly performs set-semiring marginalization, avoiding brute-force expansion over the output space.Reporting all output tuples takes O(n∥φ∥log N), corresponding to semi-join reductions related to Yannakakis’s algorithm [90].Source: §F.1 · p. 85

F.2 Variable ordering for FAQ with two blocks of semiring aggregates

  • This two-block setting motivates a precedence poset P = ([n], ⪯) over variables to characterize constraints on valid variable orderings.The section introduces the poset after emphasizing the subtleties caused by multiple variable aggregates.Source: §F.2 · p. 86, §F.2.1 · p. 86
  • With two variable-aggregate blocks, the aggregates may be functionally different and noncommutative, as in the #CQ reduction with Σ and max.The first block uses one semiring aggregate for variables in L, while the second uses another for variables outside L.Source: §F.2 · p. 86

F.2.1 The precedence poset.

The precedence poset orders variables in L before variables outside L within each connected component, and its linear extensions are sound and complete for finding equivalent variable orderings. The section then bounds FAQ-width using L-star size and fractional hypertree width, while showing these measures can diverge substantially.

F.2.1 The precedence poset.

  • The precedence poset requires u≺v for variables u∈L and v∉L in the same connected component, defining the candidate orderings LinEx(P).LinEx(P) denotes the set of linear extensions of the precedence poset.Source: §F.2.1 · p. 86
  • Every linear extension in LinEx(P) is φ-equivalent, so the poset is sound for identifying semantically valid variable orderings.This is established by Proposition F.6, including the case where the expression factorizes across connected components.Source: §F.2.1 · p. 86
  • Every φ-equivalent ordering has the same FAQ-width as some π∈LinEx(φ), so minimizing FAQ-width only requires searching linear extensions of the poset.This establishes completeness of the linear-extension characterization for the optimization problem.Source: §F.2.1 · p. 86
  • When ∅⊂L⊂[n], FAQ-width can be arbitrarily far from fractional hypertree width; for a star graph, fhtw(H)=1 while every φ-equivalent ordering places n last.The star graph is acyclic, yet the precedence constraints force its center variable n to be last when L=[n−1].Source: §F.2.1 · p. 87

F.2.2 Relation to L-star size.

  • The L-star size is defined as the maximum independence number α_E(U(C)) over connected components C of H−L, linking component-wise independence to the FAQ-width bound.The independence number is the largest subset containing no two vertices from the same hyperedge.Source: §F.2.1 · p. 87
  • Theorem F.13 gives faqw(φ) ≤ (1 + L-ss(H)) · fhtw(H), using a tree decomposition whose bags separate components of H−L and are amended with each component’s boundary set.The construction preserves the relevant decomposition structure and supports an L-prefixed elimination order.Source: §F.2.1 · pp. 88–89

F.2.3 Approximating … G.2 Truth table representation

The paper develops an approximation framework for FAQ-width that yields equivalent variable orderings with bounded overhead and tractability consequences for bounded-width queries. It also explains how factor representations support the required operations, contrasting ordered B-Trees with truth tables that are straightforward but wasteful for sparse factors.

F.2.3 Approximating

  • The contracted hypergraph H_L contains original edges within L and one interface edge U(C) for each connected component C of H−L, matching Chen and Mengel’s contraction.This construction captures how eliminating each component connects its neighbors in L.Source: §F.2.3 · p. 90
  • Theorem F.16 computes a φ-equivalent ordering σ in time |H|·t(|H|, faqw(φ)) with faqw(σ) ≤ faqw(φ) + g(faqw(φ)).The method combines decompositions for components of H−L with one for the contracted hypergraph H_L, then applies GYO elimination while eliminating L last.Source: §F.2.3 · p. 91
  • For bounded faqw(φ) ≤ c, Marx’s approximation yields a polynomial-time equivalent ordering with faqw(σ) = O(faqw^3(φ)).This leads to tractable FAQ evaluation and establishes tractability of #CQ when faqw(φ) is bounded.Source: §F.2.3 · p. 91
  • Bounded faqw(φ) is also necessary for #CQ tractability, assuming FPT ≠ W[1].The result follows from the relationship between FAQ-width and the structural conditions governing #CQ tractability.Source: §F.2.3 · p. 91

G.1 More on the factor oracle

  • The listing representation satisfies conditional queries and product marginalization when its B-Tree follows variable ordering σ.Ordered paths support conditional lookup by binary search, while marginalization multiplies leaves sharing a parent; preprocessing is essentially linear time, aside from indicator projections.Source: §G.1 · p. 92
  • All algorithmic queries respect σ, enabling essentially linear-time construction of B-Tree representations for the input factors.The ordering dependence is required for both conditional-query navigation and product marginalization.Source: §G.1 · p. 92

G.2 Truth table representation

  • Truth tables list factor parameters and values, as in dense matrix multiplication and textbook PGM inference, but are wasteful for sparse factors and convert to listings in linear time.The value may be implicit, as in the set semiring.Source: §G.2 · p. 92

G.3 Succinct Representation · G.4 Representations of sparse tables in PGMs

The section examines succinct representations of FAQ inputs, focusing on compact encodings and their efficient processing without full unpacking. It covers diverse structures, including GDNFs, decision diagrams, factorized databases, structured matrix-vector multiplication, and sparse tables in PGMs, along with alternatives for handling ADD conversion costs.

G.3 Succinct Representation

  • Succinct representations aim to reduce factor size while enabling efficient algorithms directly on the representation rather than after unpacking.The representations are treated as encodings of input factors as outputs of another FAQ or FAQ-SS instance.Source: §G.3 · p. 93
  • Decision diagrams generalize OBDDs, can preserve GDNF size up to constants, and may be exponentially smaller than any equivalent GDNF representation.The representation corresponds to labeled paths in a layered graph, while the effective computation remains an FAQ-SS instance.Source: §G.3 · p. 93
  • Factorized representations recursively combine partitions of variables through union and Cartesian-product nodes, with repeated subexpressions optionally shared as a DAG.GDNFs are a special case, and prior work shows that factorized input factors can yield factorized outputs with tight output-size bounds.Source: §G.3 · p. 94
  • The same FAQ algorithm supports sub-quadratic matrix-vector multiplication for structured matrices, with only the matrix representation and elimination order changing.The framework instantiates FAQ-SS formulations for DFT-related matrices, circulant matrices, and matrix products including Kronecker, Khatri-Rao, and Tracy-Singh products.Source: §G.3 · pp. 94–96

G.4 Representations of sparse tables in PGMs

  • In PGMs, sparse tables list only nonzero assignments, whereas ADDs represent factors as ordered-variable DAGs whose sinks carry values and whose internal nodes branch on bits.ADD evaluation follows the input assignment from the root to a sink, closely paralleling the decision diagrams described in Section G.3.Source: §G.4 · p. 96
  • Layering an arbitrary ADD requires an O(n) representation-size blowup by replacing long edges and sink connections with dummy paths.The construction inserts intermediate nodes for edges spanning multiple layers and adds a final layer for sink labels.Source: §G.4 · p. 96
  • When an ADD has s sinks, shared suffix paths reduce the conversion overhead to an additive O(sn + n^3), which is advantageous when the ADD is much larger than n and s.The O(sn) term accounts for sink paths, while O(n^3) bounds the number of distinct suffixes.Source: §G.4 · p. 97
  • Encoding an ADD directly as an FAQ instance causes only an O(1) representation-size blowup, but the resulting FAQ remains as large as the original ADD.Unlike the layered construction, this representation’s size depends on the full ADD rather than only n and the number of sinks s.Source: §G.4 · p. 97
  • Gogate and Domingos [40] provide message-passing algorithms for sparse-table and ADD representations, whereas this work targets exact computation of φ.The comparison concerns the algorithms’ computational focus rather than their representation formats.Source: §G.4 · p. 97
Loading 1504.04044v7…