Skip to content

Yannakakis Algorithm for Acyclic Joins

Evaluate an alpha-acyclic relational join by propagating semijoins up and down a join tree to remove every dangling tuple, then joining or enumerating the reduced relations with input-plus-output cost for a fixed full query.

Version
v2 · 2026-09-06 · History
Domain-specific #
3131
Origin domain
computer science
Subdomain
database theory
Aliases
Yannakakis algorithm, Yannakakis's algorithm, Yannakakis’ algorithm

Core Idea

The Yannakakis algorithm for acyclic joins evaluates an alpha-acyclic natural-join or conjunctive query without allowing large intermediate joins to arise merely from a poor binary join order. It first uses a tree-shaped program of semijoins to delete every input tuple that cannot participate in any global answer, and only then constructs the answer from the reduced relations. For a fixed full acyclic query—one that returns all query variables—the resulting running time is proportional to input plus output size under the usual RAM/hash assumptions.

Scope of Application

The abstraction applies literally where a relational or conjunctive query has alpha-acyclic atom structure and its execution can exploit a join tree. Its family resemblance across systems is exact only while relation occurrences, compatibility projections, two-direction propagation, and final answer production survive.

Full acyclic natural joins. This is the clean center: all variables are returned, the two sweeps delete dangling tuples, and the reduced join can be emitted in input-plus-output time for a fixed query.

Clarity

The algorithm clarifies acyclic query evaluation by separating three questions that a generic “join the tables” instruction collapses. First is the structural question: does the query hypergraph admit a running-intersection join tree? Second is the support question: which individual input tuples have a compatible extension through every branch? Third is the construction question: how should the surviving compatible tuples be combined and emitted? GYO or another recognizer answers the first, two semijoin sweeps answer the second, and the final join answers the third.

Manages Complexity

Yannakakis controls intermediate-result explosion by paying for support before combination. A naive binary plan can join two relations into many tuples that a third relation later kills. The semijoin sweeps instead transmit only the existence of compatible witnesses, deleting unsupported base tuples without constructing their Cartesian combinations. Once full reduction is established, each partial combination produced along the final join can be charged to surviving input or actual output under the full-query assumptions.

Abstract Reasoning

The method supports a local-to-global consistency argument. If a decomposition has running intersection, an assignment supported across each adjacent separator can be extended by induction over subtrees. The algorithm operationalizes that proof: bottom-up semijoins establish subtree extension, top-down semijoins add compatibility with the complement, and the full-reduction invariant follows. The same reasoning explains why a cycle breaks the proof—there is no unique edge through which all information about a separated part must pass.

Knowledge Transfer

Within database theory, the role mapping travels directly:

  • query atom occurrence maps to a table alias, predicate occurrence, factor, or constraint relation;
  • join-tree node maps to the occurrence whose variable set labels one hyperedge;
  • tree separator maps to the shared attributes across an edge;
  • child-to-parent semijoin maps to a support message from one subquery toward the root;
  • parent-to-child semijoin maps to support from the complementary subquery;
  • dangling tuple maps to a row, factor assignment, or partial binding with no global extension;
  • full reduction maps to global support of every retained local tuple;
  • final join maps to witness construction, answer enumeration, or semiring combination.

Relationships to Other Abstractions

Local relationship map for Yannakakis Algorithm for Acyclic JoinsParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Yannakakis Algorithmfor Acyclic JoinsDOMAINDomain-specific abstraction: Relational Model — presupposesRelational ModelDOMAINDomain-specific abstraction: Tree (Graph Theory) — presupposesTree (GraphTheory)DOMAINPrime abstraction: Algorithm — is a kind ofAlgorithmPRIME

Current abstraction Yannakakis Algorithm for Acyclic Joins Domain-specific

Parents (3) — more general patterns this builds on

  • Yannakakis Algorithm for Acyclic Joins is a kind of Algorithm Prime

    prime:algorithm — proposed strict subsumption parent. Yannakakis has a finite input, effective ordered steps, termination, correctness condition, output, and resource bound.

  • Yannakakis Algorithm for Acyclic Joins presupposes Relational Model Domain-specific

    domain_specific:relational_model — proposed strict presupposition parent. Relations, natural join, projection, and semijoin are constitutive operations.

  • Yannakakis Algorithm for Acyclic Joins presupposes Tree (Graph Theory) Domain-specific

    domain_specific:tree_graph_theory — proposed strict presupposition parent. The join tree is literally a tree specialized by occurrence labels and running intersection; its rooting supplies the sweep organization.

Hierarchy paths (4) — routes to 4 parentless roots

Neighborhood in Abstraction Space

Yannakakis Algorithm for Acyclic Joins sits in a sparse region of the domain-specific corpus (74th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08