Skip to content

Recursive join

Repeatedly join relational query results to a relation to derive further rows from seeds, with duplicate and stopping rules determining whether a completed result is reached.

Version
v1 · 2026-10-07 · History
Domain-specific #
13995
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Relational Databases, Recursive Queries → Computer Science & Software Engineering

Core Idea

A recursive join is a relational query pattern in which seed rows start a result, and a recursive term repeatedly joins rows from a prior step to another relation to derive further rows. It can follow a reporting chain, expand an assembly into subparts, or perform another multi-step relational derivation. The defining move is not simply that a query refers to itself: the repeated step contains a join between recursive working rows and a relation. An arithmetic counter written with WITH RECURSIVE is recursive but has no such join.[1][2]

The result depends on what a row contains and how duplicates are treated. In PostgreSQL, UNION discards duplicate complete rows, whereas UNION ALL retains them. A query carrying depth, path, or quantity can produce distinct rows for repeated visits to the same underlying item. An unguarded cyclic query can continue producing rows indefinitely; merely spelling it as a recursive join does not give it a completed transitive closure. A depth cap can end execution while answering only a depth-bounded question.[1]

Structural Signature

  • Anchor rows. A nonrecursive term supplies the first rows. In the documented employee example it selects the top employee, identified by a null manager field; in the product example it selects parts directly included in the named product.[2][1]
  • Recursive working rows. Rows produced by a prior step become input to the next recursive evaluation. PostgreSQL describes working and intermediate tables; Microsoft describes successive Tᵢ result sets. This role is not necessarily the entire accumulated output at every step.[1][2]
  • Joined relation. A stored or otherwise defined relation supplies the matching tuples. The recursive term joins prior rows to it by an explicit relationship, such as employee-to-manager or subpart-to-parent. This relation is the internal Relation constituent asserted by the typed DAG.[1][2]
  • Derived row shape. The projection can carry a reached entity, a depth, a path, or a multiplied quantity. Those columns decide what counts as an identical result row; the operation is not universally a unique-node traversal.[1]
  • Duplicate and stopping discipline. A completed query needs its recursive term eventually to return no rows or an explicit bound or cycle rule to stop the derivation. The query remains a recursive-join expression if an unsafe cycle prevents that completion. UNION can suppress complete duplicate rows, but it need not suppress rows with changing depth or path values.[1][2]

What It Is Not

A recursive join is not every recursive CTE. PostgreSQL's n+1 example has a seed and a recursive term but no relational join. Nor is it a one-time self-join: a conventional join can link one generation to the next once, while this pattern feeds derived rows into another join step.[1]

It is not automatically transitive closure, deduplicated reachability, or guaranteed termination. A UNION ALL traversal may retain repeat rows; even UNION compares complete result rows, so a changing depth field can evade duplicate elimination on a cycle. A shortest-path-based formula for the number of rounds requires an especially narrow set-semantics traversal and does not describe the documented quantity-carrying parts example.[1]

Scope of Application

The pattern applies where a relational representation supplies links that must be followed for an unspecified or repeated number of steps. PostgreSQL documents a bill-of-materials query that multiplies quantities while expanding subparts. Microsoft documents an employee hierarchy query whose recursive member joins a prior DirectReports row to the employee table. These are unlike data and output shapes with the same seed, recursive-input, join, and derivation roles.[1][2]

The examples are database-vendor implementations, not proof that every SQL dialect accepts identical syntax, recursion limits, search order, or cycle controls. Their general query pattern is the abstraction; vendor behavior remains attributed to the relevant documentation.[1][2]

Clarity

Ask two different questions: “Does the expression contain a recursive join?” and “What complete result, if any, will it return?” The first is answered by the anchor, recursive input, and join relation. The second needs the row columns, duplicate policy, data cycles, and stopping rule. A cyclic UNION ALL expression can answer yes to the first and fail the second.[1]

Also distinguish a relationship row from a reached entity. In a parts query, two paths can contribute quantities to the same subpart; deleting those rows as if they were redundant unique-node visits would change the requested total. In an employee hierarchy, carrying Level gives a distinct output meaning from merely returning each employee key.[1][2]

Manages Complexity

A multi-level relation can contain many links, but the query can be understood through a short state transition: start with anchor rows; join current working rows to the relation; project new rows; apply the declared duplicate and stopping behavior; accumulate the result if the process ends. That decomposition exposes where a wrong answer or a runaway cycle can arise without requiring one to mentally unroll every level.[1][2]

It also keeps performance claims honest. A depth limit may bound one query, but it does not say whether the result is semantically complete. The decisive correctness checks are the join predicate, projected columns, duplicate semantics, and intended stopping condition.[1]

Abstract Reasoning

Given a candidate query, mark the anchor and the recursive term. In the latter, identify the recursive input and the relation joined to it. Trace one step by hand, then ask what would happen if an input row reappeared. If the output adds depth or path information, test a cycle with the whole output row rather than assuming a repeated node key will be discarded. This predicts whether a visited-key or explicit CYCLE guard is needed.[1]

To evaluate a claimed closure, check that the query did not merely stop at a requested depth. A bounded result may be useful, but it does not prove every reachable item was included. Conversely, when a finite set-style traversal genuinely suppresses previously seen result rows and exhausts the working table, a completed reachability result may be a fixed point. That is a successful-case property, not a condition for naming the join pattern.[1]

Knowledge Transfer

Within database work, the role map transfers between hierarchy and component expansion: anchor, recursive working rows, joined relation, output-row shape, duplicate policy, and stopping discipline. The two cited vendor examples can be compared at that level without pretending that an employee and a quantity-bearing part are the same data object.[1][2]

Graph traversal in a nonrelational program can be analogous, but a recursive join requires a relational operand and join semantics. The portable constituent already represented in the catalog is Relation, a tuple association with a membership rule. A broader idea of repeated derivation can be studied separately; the live Recursion, Iteration, and Fixed Point primes impose conditions that this potentially nonterminating query form does not satisfy in every instance.

Examples

PostgreSQL product subparts. Its documented included_parts query starts with parts directly included in our_product. The recursive member joins prior included parts to the parts relation where a parent part matches the prior subpart, multiplies quantities, and finally sums quantity by subpart. Mapped back: the directly included parts are anchors; included_parts supplies working rows; parts is the joined relation; the derived row carries subpart and multiplied quantity; UNION ALL preserves row multiplicity. The example demonstrates component expansion, not automatic unique-node closure or universal cycle safety.[1]

Microsoft employee hierarchy. Its example starts with the highest-ranking employee, whose ManagerID is null. Each recursive step joins MyEmployees.ManagerID to the prior DirectReports.EmployeeID and produces subordinates at the next Level. Mapped back: the top employee is the anchor; prior DirectReports rows are recursive input; MyEmployees supplies the joined manager relation; employee identifiers and level are the row shape; the demonstrated hierarchy ends when the recursive term returns no rows. The final sample SELECT filters its displayed rows by department or level zero; the recursive derivation is broader than that display filter. A malformed cycle could behave differently.[2]

Structural Tensions

Compact derivation versus explicit cycle semantics. A recursive CTE states a multi-level relational query without spelling out every level. That compactness can obscure whether a repeated entity is a duplicate row, a new path, or an infinite sequence of depths. Aggressive deduplication can lose meaningful paths or quantities; retaining everything without a guard can fail to terminate. Diagnostic: What is the intended unit of distinctness, and what exact event makes the recursive term stop?[1]

Completed closure versus bounded answer. A depth cap can make a risky query operationally bounded, but it may omit reachable results beyond that depth. Demanding unrestricted closure can be inappropriate when cycles or path enumeration produce unbounded rows. Diagnostic: Does the question ask for all reachable rows, all paths under a rule, or only rows within a declared depth? The answer decides which stopping and duplicate rule is correct.[1]

Relation constituent versus full query. The join cannot exist without a relation operand, yet the relation alone does not perform recursive derivation. Treating the parent as the whole query loses the anchor and repeated step; treating it as a mere neighboring database concept hides the necessary operand. Diagnostic: Which tuple association is actually being joined to the working rows, and what new rows does that join produce?[1][2]

Structural–Framed Character

Evaluative weight: the pattern itself is a query form, while judgments of completeness, efficiency, and usefulness depend on what result is wanted. Human-practice dependence: a query author chooses seed, join predicate, row columns, duplicate handling, and stopping rule; the stored relation does not make those choices. Institutional origin: database languages and implementations provide the syntax and evaluation machinery, with vendor differences visible in the sources. Vocabulary travel: “recursion” and “join” occur elsewhere, but SQL working rows, tuple association, and duplicate semantics do not automatically travel with those words. Import versus recognition: recognize this entry when a relational result is repeatedly joined to a relation; do not import it into an arithmetic recursion or generic graph walk without a relational join.[1][2]

Its character: structural within a database frame. The necessary relation operand belongs to the more portable live Relation; the named recursive-join query and its bag/set/stopping semantics remain specific to relational computation. Neither a successful fixed point nor a particular vendor syntax is universal to the named entry.

Structural Core vs. Domain Accent

The approved portable constituent is Relation: a specified tuple association is present as the joined operand in every instance. The larger query adds an anchor, repeated working rows, a join predicate, projected result columns, and declared duplicate and stopping behavior. This is a strict part-of relation with the parent inside the child, not a claim that a recursive join is itself a relation or a database.[1][2]

Remove the relation operand and there is no recursive join. Remove the relational query machinery and one may still describe recurrence or traversal abstractly, but that broader skeleton is not the named database operation. Its cross-domain reach has not been shown to meet a new-Prime test. Recursion, Iteration, and Fixed Point are related ideas in favorable completed cases, yet their live requirements of well-foundedness, progress, or convergence cannot be carried across an unguarded cyclic UNION ALL expression.[1]

This entry is part of Relation.

The one approved typed edge is strict composition/part_of to Relation, with parent-in-child direction. A joined tuple relation is necessary, independently meaningful, and internal to the recursive-join operation. The edge does not assert taxonomic subsumption or termination. Relational database provides a common operating environment, but a query pattern is not a kind of whole database. Relational Model describes a set-based framework, while SQL queries may retain bag duplicates; it is a nearby conceptual framework, not the asserted all-instance parent.[1]

The live Recursion, Iteration, and Fixed Point primes illuminate some successful executions, but their exact definitions cannot be used as strict parents of this query form merely because its name contains “recursive.” The PostgreSQL cycle counterexample is the test: with changing rows and no guard, the same join can continue without a completed fixed point or progress toward one.[1]

Relationships to Other Abstractions

Local relationship map for Recursive joinParents 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.Recursive joinDOMAINPrime abstraction: Relation — is part ofRelationPRIME

Current abstraction Recursive join Domain-specific

Parents (1) — more general patterns this builds on

  • Recursive join is part of Relation Prime

    A recursive join contains a relation as the operand repeatedly matched against recursively derived rows.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

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

Not to Be Confused With

Ordinary join: one evaluation combines rows from relations, with no recursively derived rows fed back into a new join. General recursive CTE: may derive arithmetic values without any join. Transitive closure: a completed reachability result under appropriate semantics; it can be an output of a suitable recursive join but is not guaranteed by every such expression. Query rewriting: replaces one query with an equivalent form, while a recursive join evaluates a repeated derivation. The classification test is the repeated join of recursive working rows to a relation, not the presence of a RECURSIVE keyword alone.[1][2]

References

[1] PostgreSQL Global Development Group. PostgreSQL 18 Documentation, 7.8 WITH Queries (Common Table Expressions). §§7.8.2 and 7.8.2.2. Anchor/recursive-term evaluation; UNION versus UNION ALL; product-parts example; cycle-detection example. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28

[2] Microsoft. Recursive queries using common table expressions (Transact-SQL). Last updated 2026-09-21. Structure, Pseudocode and Semantics, and employee-hierarchy example with code walkthrough. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o