Data Definition Language (DDL)¶

The definition of SQL DDL is the set of features that create, modify, or delete schema entities.

Delightql’s DDL encompasses SQL’s DDL and extra features with no direct SQL mapping (higher-order predicates, ER-context rules). The thematic concern is reusability: definitions, tables, and data that can be authored, loaded, and referenced.

This section covers:

• Relational rules. Views, higher-order views, ER-context rules, and sigma predicates.
• Function rules. Reusable domain functions.
• Facts. Axiomatic ground data.
• Namespaces. Organization and visibility of all the above.

Basics¶

Assertion mode vs query mode. Delightql, like Prolog, distinguishes two programming modes:

• Query mode. Expressions entered into a REPL that execute immediately. This was the subject of the first book in this reference.
• Assertion mode. Files that contain definitions for later use.

The features in this DDL section are assertion-mode constructs.

Assertion mode has two general syntactic forms: rules and facts.

Rules¶

The general form of a rule is

  <HEAD>  <NECK>  <BODY>

  short_tracks(*)
    :- track(*), milliseconds < 60000

In the above example:

• short_tracks(*) is the HEAD
• :- is the NECK
• track(*), milliseconds < 60000 is the BODY. The body may use any DQL feature–the entire previous book applies here.

Facts¶

Facts are functor forms with grounded data.

parent("Abraham", "Isaac")

This looks like a query. The syntax is context dependent. In assertion mode, i.e. in a file with rules and definitions, this syntax defines extensional data – axiomatic truths with no derivation.

The Two Necks¶

The neck separates a rule’s head from its body. Delightql has two necks, each defining a different scope and extent:

The two neck operators

Extent vs Scope¶

There is a difference between when and where a rule definition is available. The terminology is known by the names extent and scope.

Scope refers to the spatial visibility of a definition. It asks where an abstraction – a name – is available for use.

Extent is temporal lifetime. It asks when an abstraction is available for use. In contrast to regular programming languages, extent matters more for databases where tables and views outlive a process.

The necks in delightql map to different types of scope and extent:

• Query-extent (:) – Exists only for the duration of one query. These are CTEs. These also have a scope limited by a query.
• Session-extent (:-) – Exists for the duration of the connection. These are temporary views, tables or inlinable definitions. Their scope is determined by namespacing – the subject of a later chapter.
• Permanent-extent – Persists after disconnection. These are tables and views.

Shadow Neck :¶

The shadow neck defines a momentary definition with limited scope. The definition exists only for the single query in which it appears:

short(name) : track(*), milliseconds < 60000
short(*)

A shadow-neck definition may shadow an existing table or view of the same name for the duration of the query. This scoping behavior is unique to the shadow neck.

Shadow-neck definitions are not DDL – they are reviewed here for syntactic similarity to rules.

Rule Neck (:-)¶

short_tracks(*) :- audio_tracks(*), milliseconds < 60000
audio_tracks(*) :- track(*), media_type_id != 3

The rule neck (:-) creates a definition that is equivalent to SQL’s CREATE TEMP VIEW. Delightql may choose to create temporary views to implement this abstraction, but may also choose to do expression rewriting.

Rules¶

The syntax of rules obey the general form:

  <HEAD>  <NECK>  <BODY>

In delightql these rules may be used for any of the following:

• Views
• Tables
• Higher-order views
• ER-contexts
• Sigma predicates
• Functions

All of these use the :- neck. The first five define relations; functions define the special subset of relations that are functions.

Arity and Naming¶

A rule’s arity is the number of arguments in its head.

inc:(x) :- x + 1        // arity 1
add:(x, y) :- x + y     // arity 2


contact(customer_id, email) :- customer(*) // arity 2
band(*) :- artist(*)  // arity determined by body

All definitions – functions, sigma predicates, higher-order rulesviews, tables, facts – must have the same fixed arity.

The following are forbidden:

add:(x) :- x + 1        // arity 1
add:(x, y) :- x + y     // arity 2

contact(customer_id, email) :- customer(*)
contact(customer_id, email, phone)  :- customer(*)

If you can write foo(*), all foo definitions must agree on arity. With argumentative heads, agreement is stricter: same arity AND same names at each position.

This rule is stricter than most languages where a name can be overloaded by arity. Delightql insists that there can only be one named entity per namespace and that that entity always have the same arity. The only place where this rule is relaxed is common expressions which can shadow tables, views, and functions.

Head Semantics¶

The head of a rule names the entity and declares what it exposes. How the head is written determines the output schema and how multi-clause entities combine.

Two Head Forms¶

Glob head¶

young(*)
  :- employee(*), birth_date > "1970-01-01"

The glob * passes through whatever the body produces. The entity inherits its schema from the body. This is the permissive form – the head makes no claim about column names or count.

Argumentative head¶

young(last_name, birth_date)
  :- employee(*), birth_date > "1970-01-01"

The head declares the entity’s output schema: exactly last_name and birth_date, in that order. Every clause must satisfy this contract – the body must produce columns with those names (among possibly others).

The body may be wider than the head. The head projects from the body by name, so wide source tables need not be narrowed in the body before the head can name the subset. If the body does not produce a column named in the head, then it is an error.

Ground Terms in the Head¶

A head position can hold a ground term (a literal) instead of a free variable (a column name).

bracket("old" as tag, last_name, first_name)
  :- employee(*), birth_date < "1960-01-01"

Ground terms in the head inject constants into the output and provide choice semantics for multi-clause disjunctive rules.

Multi-Clause Rules¶

bracket("old", last_name, first_name)
  :- employee(*), birth_date < "1960-01-01"
bracket("young", last_name, first_name)
  :- employee(*), birth_date > "1970-01-01"
bracket(title, last_name, first_name)
  :- employee(*)

Multi-headed rules with the exact same named and shaped head are called disjunctive rules. The disjunctive in disjunctive rules is a reference to the logical OR and manifests in different ways depending on the context:

• sum types in algebraic data types
• tagged unions and/or variants in many programming languages
• union in set theory (and therefore SQL)
• choice in grammar rules
• OR in logic

The meaning of multi-headed clauses is exactly UNION ALL.

Disjunctive Rules: Consistency of Head Forms¶

All clauses of the same entity must use the same head form – either all glob or all argumentative. Mixing is an error:

// OK: all glob
place(*) :- customer(*) |> (city, country)
place(*) :- employee(*) |> (city, country)

// OK: all argumentative
place(city, country) :- customer(*)
place(city, country) :- employee(*)

// ERROR: mixed head forms
place(*) :- customer(*) |> (city, country)
place(city, country) :- employee(*)

Disjunctive Rules: Union Semantics by head form¶

Glob heads and argumentative heads use the exact same union strategy. Both syntaxes must publish exactly the same heading: identical column names in identical order. The programmer must explicitly reconcile disagreement across multiple bodies.

Column naming with ground terms¶

Argumentative heads require strict agreement: every clause must have the same number of positions, and free variables at each position must use the same name across all clauses. If clause 1 has (name , age) and clause 2 has (age , name) then this is an error.

Ground terms (constants) are nameless – they do not contribute a column name for a position. Free variables provide names. The rules:

• If a position has free variables in one or more clauses, all those free variables must use the same name. Constants in other clauses are compatible (they provide a value but no name).
• Conflicting names at the same position is an error.

// OK: title names position 1; constants in other clauses are compatible
bracket("old", last_name, first_name)
  :- employee(*), birth_date < "1960-01-01"
bracket("young", last_name, first_name)
  :- employee(*), birth_date > "1970-01-01"
bracket(title, last_name, first_name)
  :- employee(*)

// ERROR: position 1 named title in one clause, city in another
bracket("old", last_name, first_name)
  :- employee(*), birth_date < "1960-01-01"
bracket(title, last_name, first_name)
  :- employee(*)
bracket(city, last_name, first_name)
  :- employee(*)

Higher-Order Rules¶

Higher-order rules are rules that accept tables or scalars as parameters – inputs that further instantiate a templated relation. SQL calls these table-valued functions; Prolog would call them higher-order predicates.

All higher-order rules return a table value. It is this specific quality that permits us calling this abstraction “higher-order” and not the fact that the inputs may be tables themselves.

A programmer can create their own higher-order rules and use them in all places where a table is allowed. With a certain kind of definition – one in which the final parameter is itself a table – a higher-order rule may also be used after a pipe. Given this definition:

clean_employees(T(*))(*) :-
  T(*)
    |> $(trim:())(last_name, first_name)
    |> $(date:())(birth_date, hire_date)

clean_employees can follow a pipe:

employee(*)
  |> clean_employees(*)

Higher-order rules are also called input-moded rules.

Definition Syntax¶

A higher-order rule has two sets of parentheses: the first for input parameters the second for output (and occasionally input – via unification) columns.

genre_track_count(T(*), G(*))(genre, track_count) :-
  T(*), G(*.(genre_id))
    |> %(G.name as genre ~> count:(*) as track_count)

In the above example, the parameters T(*) and G(*) are glob parameter functors and denote that two tables (or lower-order relations) are expected as inputs. The (*) in the parameter functor name signals to the compiler that the body will reference these tables’ columns by name.

The term higher-order rules is the standard usage throughout this reference, but an equally valid term is input-moded rules.

long_tracks(n, T(*), G(genre_id, genre))(genre, track_name) :-
  T(*), G(*.(genre_id)), milliseconds > $.n
    |> (genre, name as track_name)

The first set of parentheses, the ones closer to the name of the rule, should not be understood as a suite of dimensions that may be tables – although this is true – but as parameters that must be instantiated and passed in. In prolog, this sort of declaration is called a mode and is used to indicate which dimension needs to be instantiated vs which ones may be output only. In delightql input-moded rules require the parameters of the first parentheses to be input, and may allow the columns of the second set of parentheses to be input – though this is called unification and or grounding.

Direct Invocation¶

Tables can be passed in as parameter arguments. Given this definition:

genre_track_count(T(*), G(*))(genre, track_count) :-
  T(*), G(*.(genre_id))
    |> %(G.name as genre ~> count:(*) as track_count)

a call passes two tables:

genre_track_count(track(*), genre(*))(*)

The call site mirrors the definition head: each table parameter in this example is a full functor expression.

Because call-site arguments are relation expressions, they can compose:

genre_track_count(
  track(*, milliseconds > 300000),
  genre(*)
)(*)

Here the first argument is a filtered relation.

Piped Invocation¶

Pipes can be used on any higher-order predicate that takes a table-valued parameter:

clean_employees(T(*))(*) :-
  T(*)
    |> $(trim:())(last_name, first_name)
    |> $(date:())(birth_date, hire_date)

employee(*)
  |> clean_employees(*)

The piped relation fills the last parameter. The (*) after the rule name is the output schema.

Chaining is possible:

mask_phone(mask_value,T(*))(*) :-
  T(*) |> $$($.mask_value as phone)

employee_2024(*)
  |;| employee_2025(|> *(job_title as title, manager_id as reports_to))
  |> clean_employees(*)
  |> mask_phone("+1 (***) ***-****")(*)

Note. As with function pipes, the relation is piped into the last parameter of the higher-order predicate. If the higher-order predicate has multiple parameters, the other values must be set.

Multi-parameter piped invocation. When the piped relation is not the last parameter, use @ (the f-param placeholder) to mark where it goes – the same syntax as function pipes:

// Definition: table first, scalar second
tagged(T(*),label)(*) : T(*) |> +($.label as tag)

// Direct invocation (always works):
tagged(customer(*),"vip")(*)

// A `:` definition lasts one query, so it is restated:
tagged(T(*),label)(*) : T(*) |> +($.label as tag)

// Piped invocation with @:
customer(*) |> tagged(@,"vip")(*)

The @ tells the compiler which parameter receives the piped relation. Without @, the piped relation fills the last parameter by default – which fails when the last parameter is a scalar.

Parameters to Higher-order rules¶

Higher-order parameters come in five flavors, distinguished by syntax in the definition head:

The syntax alone tells the language what each parameter accepts. Capitalization is conventional – programmers may uppercase table parameters and lowercase scalars for readability, but the language does not require it.

Scalar Parameters¶

A bare identifier without parentheses in the head declares a scalar parameter. The body reads it as $.name: the sigil $. glued to the parameter’s name. A bare name in the body is always a column.

big_markets(T(*), total_floor, min_count)(*) :-
  T(*), total > $.total_floor,
    customer(*.(customer_id))
    |> %(country ~> count:(*) as invoice_count),
    invoice_count > $.min_count

big_markets(invoice(*), 10, 4)(*)

Parameters and columns do not compete¶

Because a parameter is always marked, a parameter and a column may share a name. Adding a column to an input can never redirect a reference to the parameter, and renaming a parameter never changes which column a bare name reads:

above(total, T(*))(*) : T(*), total > $.total
above(20, invoice(*))(*)        // invoices whose own Total column exceeds 20

A pipe changes which columns are in view, never what $.total reads:

h(total, T(*))(*) :-
  T(*) |> ((unit_price * quantity) as total) |> (total, $.total as supplied)

Here the final total is the column the previous stage created, and $.total is the parameter.

Every named parameter is read¶

A family must use every scalar parameter it names. A position counts as used when some clause reads it as $.name, or when some clause grounds it with a constant in its head. Otherwise the definition refuses where it is declared (semantic/ddl/head/unused_scalar):

h(total, T(*))(*) :- T(*), total > 20      // refused: `Total` here is a column, and
                                           // the parameter `Total` is read by no clause

Clause-local names¶

Scalar formal names are local to each clause. For example, h(k)(*) with body _(v @ $.k) and h(j)(*) with body _(v @ $.j + 100) bind the same argument position. Calling h(7)(*) returns 7 and 107 in either clause order. The same positional binding applies to query-local rules and effect rules. Family metadata labels this input argument 1; neither local name is the family’s parameter name. Public output-head agreement is unchanged.

Where $.name stands¶

$.name is a value. It stands wherever a value stands, including:

• a slot, where it constrains the column rather than binding one: T($.k, v);
• an argument forwarded to another rule: inner($.k, T)(*);
• a bound or an ordinal, which take the parameter’s literal actual: T(*), #< $.n and |$.n|.

It never names or addresses a column, so it cannot follow as, stand in a selector, or appear in a head.

Nested definitions¶

A definition written inside a higher-order body may read the enclosing rule’s parameters. $.name searches the enclosing higher-order clauses, nearest first. A nested higher-order rule’s own parameter of the same name shadows the outer one. Each invocation of the outer rule hands its nested definitions its own actuals:

outer(limit)(*) :-
    upto(s)(v) : _(v @ $.s)
    upto(s)(v) : upto($.s)(*), v < $.limit |> (v + 1 as v)
    upto(1)(*)

Value functions, contextual functions, truth rules and lambdas keep bare parameter names, and they do not interrupt this search: a nested value function may combine its own bare x with an enclosing $.limit. A $.name that no enclosing higher-order clause declares refuses where it is written (semantic/resolution/parameter).

Glob Parameter Functors¶

An glob parameter functor T(*) is structurally/duck typed: the body references columns by name, and any table that has those columns is accepted regardless of extra columns.

clean_employees(T(*))(*) :-
  T(*)
    |> $(trim:())(last_name, first_name)
    |> $(date:())(birth_date, hire_date)

The parameter T(*) accepts any table with last_name, first_name, birth_date, and hire_date columns.

Argumentative Parameter Functors¶

An argumentative paramter functor T(a, b) is positionally typed: the input must have exactly two columns, and they are renamed to a and b inside the body. The caller’s original column names are overwritten.

foo(T(label, value))(*) :-
  T(*), value > 10 |> (label)

The names label and value are column aliases available in the body. The definition simultaneously declares the arity (two columns) and provides names for positional access.

The advantage of the argumentative functor is in the calling convention, called scalar lifting. Because the definition declares a positional contract, a call site may pass bare scalars instead of a table:

foo("first", 12)(*)

The scalars are positionally matched to the declared columns label and value and lifted into a one-row table. This cascades to stacked notation:

foo("first", 2; "second", 20)(*)

which sugars explicit anonymous tables:

foo(_("first", 2; "second", 20))(*)

but still allows pipe invocation:

// genre_2025 is (name, genre_id): name binds label, genre_id binds value
genre_2025(*)
  |> foo(*)

Or explicit functor invocation:

foo(genre_2025(*))(*)

Scalar lifting requires a positional contract – a glob parameter functor cannot accept inline scalars because there is no declared arity to match against.

The & Rule¶

& is required only when using scalar lifting with an argumentative functor alongside other parameters.

When every table argument is passed as a functor expression, the parentheses disambiguate each argument. Commas separate parameters as usual – no & needed. & is the cost of the scalar-lifting shorthand: when bare scalars fill an argumentative functor, & marks where one argument ends and the next begins.

Higher-order Parameter Chart¶

The table is divided into two regions. In the top region, every table argument uses functor syntax – & is never needed. In the bottom region (scalar lifting), bare scalars fill argumentative functors and & marks the boundaries.

Functor syntax is always available and always unambiguous. Scalar lifting is an optional shorthand for inline data – use & when you use it, or wrap in _() to avoid it.

Sigma Rules¶

Sigma rules encapsulate reusable boolean logic:

is_high_value(amount) :- amount > 1000

track(*),
  +is_high_value(milliseconds / 1000),
  +like(name, "%Pt. 1")

Disjunctive Clauses

Multiple clauses with the same head are OR-ed together:

no_data("NA"; "N/A"; "UNKNOWN")

empty(column) :- null = column
empty(column) :- trim:(column) = ""
empty(column) :- +no_data(upper:(column))

customer(*),
  +empty(company),
  +empty(state)

SELECT *
FROM customer
WHERE (company IS NULL
       OR trim(company) = ''
       OR upper(company)
        IN ('NA', 'N/A', 'UNKNOWN'))
  AND (state IS NULL
       OR trim(state) = ''
       OR upper(state)
        IN ('NA', 'N/A', 'UNKNOWN'));

Requirements.

To create a sigma rule:

• The head is a relational functor with arguments
• The neck is :-
• The body consists of conjoined sigma predicates
• Each parameter must appear at least once in the body
• In disjunctive form, each clause must reference at least one parameter

Sigma predicates include:

• Infix comparisons: age < 20, last_name = 'Johnson'
• Functor predicates: +like(description, 'ipod%'), +between(Salary, 50000, 100000)
• in statements: state in ("MA"; "TX"; "CA")
• Existence tests: +other_table(...), \+other_table(...)

ER-Context Rules¶

ER-context rules allow a programmer to pre-define entity relationships via join conditions.

ER-context rules define the join relationships once. The & and && operators reference them concisely.

Defining Relationships¶

An ER-rule declares how two tables join. The head uses & between table names; the body is the join expression:

customer(*) & invoice(*) :-
  customer(*), invoice(*), customer.customer_id = invoice.customer_id

invoice(*) & invoice_line(*) :-
  invoice(*), invoice_line(*), invoice.invoice_id = invoice_line.invoice_id

invoice_line(*) & track(*) :-
  invoice_line(*), track(*), invoice_line.track_id = track.track_id

The & alone assigns this join to the default context ::normal.

Multiple Contexts¶

The same table pair can have different join semantics in different contexts:

customer(*) &(::support) employee(*) :-
  customer(*), employee(*), customer.support_rep_id = employee.employee_id

customer(*) &(::local) employee(*) :-
  customer(*), employee(*), customer.city = employee.city

The context name is a symbol, i.e. a :: followed by a valid identifier. The lack of a symbol means ::normal. The following are the same:

customer(*) & invoice(*)
customer(*) &(::normal) invoice(*)

Using Contexts¶

Calling the join mirrors the way in which the rule was defined:

customer(*) & invoice(*)

customer(*) &(::local) employee(*)

Direct Join (&)¶

The & operator performs a direct lookup in the written context, or ::normal when omitted. It does not search every context:

customer(*) & invoice(*)

Equivalent to:

customer(*), invoice(*), customer.customer_id = invoice.customer_id

Multiple & operators chain left to right. Each consecutive pair must have a defined ER-rule:

customer(*) & invoice(*) & invoice_line(*)

Compiles to:

customer(*), invoice(*), invoice_line(*),
  customer.customer_id = invoice.customer_id,
  invoice.invoice_id = invoice_line.invoice_id

Transitive Join (&&)¶

The && operator finds a path through the ER-graph:

customer(*) && track(*)

No direct customer(*)&track(*) rule exists, but the path does: customer -> invoice -> invoice_line -> track.

Ambiguity is an error. If multiple paths exist, the query fails:

employee(*) &(::sales) customer(*) :-
  employee(*), customer(*), employee.employee_id = customer.support_rep_id
customer(*) &(::sales) invoice(*) :-
  customer(*), invoice(*), customer.customer_id = invoice.customer_id
employee(*) &(::sales) invoice(*) :-   // creates a cycle
  employee(*), invoice(*), employee.city = invoice.billing_city

employee(*) &&(::sales) invoice(*)
// Error: Ambiguous: 2 paths from 'employee(*)' to 'invoice(*)':
//   employee(*) -> invoice(*)
//   employee(*) -> customer(*) -> invoice(*)

Recursion in Rules¶

Recursion in delightql emerges from self-reference. When a predicate’s definition includes a clause that references the predicate itself, the definition is recursive. When a common table expression includes a clause that references the CTE itself, the CTE is recursive. Both transpile to SQL’s WITH RECURSIVE construct.

This chapter covers the semantics of recursion in delightql, how it maps to SQL’s execution model, and the constraints that model imposes.

Two Forms of Recursion¶

Delightql supports recursion in two contexts:

Recursive rules are defined in assertion mode and persist as reusable predicates:

superior(employee, boss) :-
  employee(*), reports_to != null
    |> (employee_id as employee, reports_to as boss)
superior(employee, boss) :-
  employee(*) as e, superior(*) as s, e.reports_to = s.employee
    |> (e.employee_id as employee, s.boss)

Recursive CTEs are defined inline in query mode, scoped to a single query:

superior(*) : employee(*), reports_to != null |> (employee_id as employee, reports_to as boss)
superior(*) : employee(*) as e, superior(*) as s, e.reports_to = s.employee
    |> (e.employee_id as employee, s.boss)
superior(*)

Both forms transpile to WITH RECURSIVE. The choice depends on whether the recursive logic is reusable (rule) or ad-hoc (CTE).

A parameterized rule may be written in either place: in a rules file with :-, or in the query itself with : as a common higher-order expression. The two recurse identically; see Higher-Order Recursive Predicates below.

The Anatomy of Recursion¶

Every recursive definition has two components:

Base clauses provide initial rows without self-reference. These are SQL’s “anchor members”:

_(n @ 1) : counter                                 // literal base case
counter(*)

employee(*), title = "General Manager" : mgmt      // filtered base case
mgmt(*)

employee(*), reports_to != null                     // projected base case
    |> (reports_to as origin, employee_id as dest) : reachable
reachable(*)

Recursive clauses reference the predicate or CTE being defined. These are SQL’s “recursive members”:

_(n @ 1) : counter                                 // base case
counter(*), n < 100 |> (n + 1 as n) : counter
counter(*)

employee(*), title = "General Manager" : mgmt      // base case
mgmt(*) as m, employee(*) as o, o.reports_to = m.employee_id |> (o.*) : mgmt
mgmt(*)

employee(*), reports_to != null                     // base case
    |> (reports_to as origin, employee_id as dest) : reachable
reachable(*) as r, employee(*) as e, r.dest = e.reports_to
    |> (r.origin, e.employee_id as dest) : reachable
reachable(*)

Base clauses must precede recursive clauses in source order: names resolve strictly left to right, and a recursive clause reads a name the base clause establishes. In a recursive CTE the base clause creates the name, so writing the recursive clause first refuses as an unresolved name (“Table not found”). A rule, or a parameterized rule written in the query, declares its name in its head, so the name can see itself; there a self-reference before any base clause refuses as semantic/recursion/anchor_first.

Evaluation Model¶

SQL’s recursive CTEs evaluate using a working table algorithm:

1. Execute all base clauses; their results form the initial working table
2. Execute the recursive clause with the working table as input
3. The output becomes the new working table
4. Repeat until the working table is empty
5. Return the union of all iterations

This is bottom-up or co-recursive evaluation: starting from known facts it derives new facts and repeats until a fixed point is reached. It resembles dynamic programming more than classical recursion.

The critical implication: the recursive clause sees only the previous iteration’s rows, not the full accumulated result. This is why certain operations are prohibited – they would require access to rows that haven’t been computed yet or have already been consumed.

What Recursion Can Express¶

SQL’s recursive model handles a well-defined class of problems:

Hierarchical traversal – org charts, bill of materials, folder structures:

employee(*), reports_to = null |> (employee_id, last_name, 0 as depth) : tree
employee(*) as e, tree(*) as t, e.reports_to = t.employee_id
    |> (e.employee_id, e.last_name, t.depth + 1 as depth) : tree
tree(*)

Transitive closure – reachability, ancestry, dependency graphs:

employee(*), reports_to != null |> (reports_to as origin, employee_id as dest) : reachable
reachable(*) as r, employee(*) as e, r.dest = e.reports_to
    |> (r.origin, e.employee_id as dest) : reachable
reachable(*) |> %(*)  // deduplicate

Sequence generation – numeric ranges, date series, iteration:

_(d @ date:("2024-01-01")) : dates
dates(*), d < date:("2024-12-31")
    |> (date:(d, "+1 day") as d) : dates
dates(*)

Iterative computation – any algorithm expressible as “given previous state, compute next state”:

_(iter, x, target @ 0, 1.0, 2.0) : newton
newton(*), abs:((x * x) - target) > 0.0001, iter < 100
    |> (iter + 1 as iter, (x + (target / x)) / 2.0 as x, target) : newton
newton(*) |> %(target ~> (x as sqrt) <~ #(iter desc))

What Recursion Cannot Express¶

The working-table model imposes fundamental limitations. These are not arbitrary restrictions – they follow from the evaluation semantics.

No Aggregation in Recursive Clauses¶

Aggregation requires access to multiple rows. The recursive clause sees only the working table (previous iteration), not the full accumulated result.

// INVALID -- cannot aggregate within recursion
similar_artist(*), artist_id = 22    // Led Zeppelin
    |> (similar_id as artist_id, score as strength) : reach
reach(*) as r, similar_artist(*) as s, s.artist_id = r.artist_id, r.strength > 0.5
    |> (s.similar_id as artist_id, r.strength * s.score as strength) : reach  // seems ok?

// But this fails:
reach(*) as r, similar_artist(*) as s, s.artist_id = r.artist_id
    |> %(s.similar_id as artist_id ~> sum:(r.strength * s.score) as strength) : reach  // aggregation -- NOT ALLOWED
reach(*)

No Subqueries Referencing the Recursive Target¶

A subquery inside the recursive clause cannot reference the CTE being defined:

// INVALID -- subquery references 'paths'
employee(*), reports_to != null |> (reports_to as origin, employee_id as dest) : paths
employee(*) as e, paths(*) as p, e.reports_to = p.dest,
    \+ paths(*, e.employee_id = dest)  // "dest not already reached" -- NOT ALLOWED
    |> (p.origin, e.employee_id as dest) : paths
paths(*)

The subquery paths(*, ...) would need to see all accumulated rows, which aren’t available.

No Mutual Recursion¶

Two predicates cannot reference each other:

// INVALID -- mutual recursion
even(n) :- _(n @ 0)
even(n) :- odd(m) |> (m + 1 as n)
odd(n) :- even(m) |> (m + 1 as n)

SQL’s WITH RECURSIVE processes one CTE at a time. There’s no mechanism for two CTEs to co-evolve.

The refusal is semantic/recursion/mutual, and its message names the whole cycle (home.even -> home.odd -> home.even). A definition that returns to itself through any other definition — a rule that uses a view whose body uses the rule — refuses the same way.

Single Self-Reference¶

The recursive clause may reference the target exactly once:

// INVALID -- two self-references
employee(*), reports_to != null |> (reports_to as origin, employee_id as dest) : paths
paths(*) as p1, paths(*) as p2, p1.dest = p2.origin
    |> (p1.origin, p2.dest) : paths
paths(*)

This would require joining the working table against itself, which SQL doesn’t support in recursive CTEs.

Relations Only¶

Recursion is over relations. A value function that calls itself — with the same argument, a different one, or through other value functions — refuses as semantic/recursion/function-form. A sigma rule that cites itself, directly or through other sigma rules, refuses as semantic/recursion/truth-form, even with a base clause:

// INVALID -- a value function has no fixpoint to re-enter
fib:(n) :- fib:(n - 1) + fib:(n - 2)

Define the relation and ground the argument instead: fib(k, v) as a recursive relation, fib(5, v) to read one point.

Termination¶

Recursive CTEs terminate when the recursive clause produces no new rows. This happens when:

• A WHERE condition filters out all candidates
• A join finds no matches
• The depth limit (#) is reached
• The data is exhausted (finite traversal)

Ensuring termination:

For sequence generation, always include a bound:

_(n @ 1) : nums
nums(*), n < 1000 |> (n + 1 as n) : nums  // terminates at 1000
nums(*)

For graph traversal over potentially cyclic data, track visited nodes:

similar_artist(*)
    |> (artist_id as origin, similar_id as dest, :",{artist_id},{similar_id}," as visited) : paths
similar_artist(*) as e, paths(*) as p, p.dest = e.artist_id,
    \+like(p.visited, :"%,{e.similar_id},%")    // not already on the path
    |> (p.origin, e.similar_id as dest, :"{p.visited}{e.similar_id}," as visited) : paths
paths(*), origin = 22    // from Led Zeppelin: ,22,58,12, is not extended back to 22

For unknown depth, use # as a safety limit:

employee(*), reports_to = null |> (employee_id as id, 0 as depth) : tree
tree(*) as t, employee(*) as n, n.reports_to = t.id, # < 100
    |> (n.employee_id as id, t.depth + 1 as depth) : tree
tree(*)

UNION Badge¶

By default, delightql emits UNION ALL – duplicates across iterations are preserved. This is efficient and correct for most traversals.

For graph traversals that require the usage of UNION over UNION ALL for correctness use the UNION-BADGE where the badge % is postfixed to the name of the rule.

artist_edge(*) :-
  similar_artist(*)
    |> (artist_id as src, similar_id as dst)

artist_edge(*) :-
  similar_artist(*)
    |> (similar_id as src, artist_id as dst)

connected%(*) :-
  artist(*), name = "Led Zeppelin"
    |> (artist_id)

connected%(*) :-
  connected(*) as c,
    artist_edge(*) as e,
    c.artist_id = e.src
    |> (e.dst as artist_id)

This applies to CTEs as well:

// Construct an undirected artist graph.
similar_artist(*)
  |> (artist_id as src, similar_id as dst)
  : edge

similar_artist(*)
  |> (similar_id as src, artist_id as dst)
  : edge

// Begin at Led Zeppelin.
artist(*), name = "Led Zeppelin"
  |> (artist_id)
  : connected%

// Follow every edge. UNION prevents previously reached artists
// from returning to the top of the stack
connected(*) as c,
  edge(*) as e,
  c.artist_id = e.src
  |> (e.dst as artist_id)
  : connected%

// Display the connected component.
connected(*) as c,
  artist(*) as a,
  c.artist_id = a.artist_id
  |> (a.artist_id, a.name)
  |> #(artist_id)

A parameterized head wears the badge in the same place, after the name and before the parameter row, in a rules file or in the query:

connected_to%(root)(*) :-
  artist(*), name = $.root
    |> (artist_id)

connected_to%(root)(*) :-
  connected_to($.root)(*) as c,
    similar_artist(*) as s,
    c.artist_id = s.artist_id
    |> (s.similar_id as artist_id)

connected_to%(root)(*) :-
  connected_to($.root)(*) as c,
    similar_artist(*) as s,
    c.artist_id = s.similar_id
    |> (s.artist_id as artist_id)

connected_to("Gilberto Gil")(*) as c,
  artist(*) as a,
  c.artist_id = a.artist_id
  |> (a.artist_id, a.name)
  |> #(artist_id)

Each argument selects its own fixpoint, and the badge removes duplicates within that fixpoint only. When the argument comes from a caller’s rows, two caller rows with the same argument each receive the whole result.

Every clause of a definition wears the same badge. A mixed set refuses as semantic/recursion/mixed_badge. A badge on a definition that never references itself refuses as semantic/recursion/false_fixpoint: there is no fixpoint for it to describe. To remove duplicates from an ordinary definition, write |> %(*) in the body.

Higher-Order Recursive Predicates¶

Recursive rules can be parameterized, deferring the base case:

reports_to(boss)(employee_id, last_name) :- employee(*), last_name = $.boss
reports_to(boss)(employee_id, last_name) :-
    employee(*) as e,
    reports_to($.boss)(*) as r,
    e.reports_to = r.employee_id
    |> (e.employee_id, e.last_name)

Each invocation monomorphizes to a concrete WITH RECURSIVE:

reports_to("Edwards")(*)   // who reports to Edwards?
reports_to("Mitchell")(*)  // who reports to Mitchell?

The higher-order parameter boss is inlined into the anchor clause at query time. The recursive structure itself doesn’t change – only the starting point.

The argument selects one fixpoint, and it stays fixed while that fixpoint runs. The self-reference reports_to(boss)(*) passes the same argument, so it reads the rows found so far. A self-reference that changes an argument refuses as semantic/recursion/parameter-widening; state that changes from one step to the next belongs in the relation’s columns.

The same rule may be written in the query itself, as a common higher-order expression, with : in place of :-:

reports_to(boss)(employee_id, last_name) : employee(*), last_name = $.boss
reports_to(boss)(employee_id, last_name) :
    employee(*) as e,
    reports_to($.boss)(*) as r,
    e.reports_to = r.employee_id
    |> (e.employee_id, e.last_name)
reports_to("Edwards")(*)

It returns the same rows and refuses the same shapes as the rule, in every position: with a literal argument, with an argument read from the caller’s rows, and handed to another rule as a rule value.

Example: Mandelbrot Set¶

This example demonstrates sequence generation, computational iteration, and post-recursion aggregation working together:

_(x@-2.0)                                  : xaxis
xaxis(*), x < 1.2
 |> (x + 0.05 as x)                        : xaxis
_(y@-1.0)                                  : yaxis
yaxis(*), y < 1.0
 |> (y + 0.1 as y)                         : yaxis
sq:(x):
  x * x
xaxis(*), yaxis(*)
 |> (0 as iter,
     x as cx,
     y as cy,
     0.0 as x,
     0.0 as y)                             : m
m(*), (sq:(x) + sq:(y)) < 4.0,
  iter < 28
 |> (iter + 1 as iter,
     cx as cx,
     cy as cy,
     (sq:(x) - sq:(y)) + cx as x,
     ((2.0 * x) * y) + cy as y)            : m
m(*)
 |> %(cx,cy ~> max:(iter) as iter )        : m2
m2(*)
 |> %(cy
        ~>
      group_concat:(substr:(" .+*#", 1+min:(iter/7,4), 1), "") as t)
                                           : a
a(*)
 ~> group_concat:(rtrim:(t),char:(0x0a))

The query generates a coordinate grid, runs the escape-time algorithm via recursive iteration, then aggregates the results into ASCII art – all in a single delightql expression.

Delightql Recursive Limits¶

A true fixed-point engine – like those in Datalog systems – would maintain the full set of derived facts and allow each iteration to query against it. SQL chose a simpler model. The restrictions on aggregation, subqueries, and mutual recursion all follow from this choice.

Delightql inherits these limitations because it transpiles to SQL and the semantics remain bound by the target. Where SQL’s recursive CTEs fall short – self-similar tree construction, recursive aggregation, shortest-path computation – delightql falls short as well.

Facts¶

Facts are body-less rules that define ground data. In Prolog terms, they represent the extensional (axiomatic) portion of a program – truths asserted without derivation.

Standard Facts¶

The notation matches Prolog (minus the terminating period):

person(0, "Gusti", "Parlor", "[email protected]")
person(1, "Diane-marie", "McHenry", "[email protected]")
person(2, "Ced", "Mainds", "[email protected]")
person(3, "Bren", "Berndsen", "[email protected]")

Standard facts sharing the same functor name must be co-located – no other definitions may appear between them.

Stacked Facts¶

Define tabular data with headers:

staff(
  employee_id , first_name     , last_name
  -------------------
  0  , "Gusti"       , "Parlor" ;
  1  , "Diane-marie" , "McHenry" ;
  2  , "Ced"         , "Mainds"
)

The syntax mirrors anonymous tables, but anonymous tables are query-mode constructs (inline data) while stacked facts are assertion-mode constructs.

// Anonymous table (query mode)
_(first_name, last_name
  --------------
  "Gusti"       , "Parlor" ;
  "Diane-marie" , "McHenry"
)

// Stacked fact (assertion mode)
names(first_name, last_name
  --------------
  "Gusti"       , "Parlor" ;
  "Diane-marie" , "McHenry"
)

Default Implementation as Views¶

Delightql implements facts as views by default, not tables:

staff(
  employee_id , first_name     , last_name
  -------------------
  0  , "Gusti"       , "Parlor" ;
  1  , "Diane-marie" , "McHenry" ;
  2  , "Ced"         , "Mainds"
)

CREATE TEMP VIEW staff AS
  SELECT 0 AS employee_id, 'Gusti' AS first_name, 'Parlor' AS last_name
  UNION ALL SELECT 1, 'Diane-marie', 'McHenry'
  UNION ALL SELECT 2, 'Ced', 'Mainds';

This seems counterintuitive – facts are data, so why not tables? The justification: typical delightql files contain only a handful of facts (test fixtures, configuration, lookup tables). For small datasets, the difference between a view over literal values and a table with inserted rows is negligible. Views avoid the overhead of table creation and cleanup.

Sparse Stacked Facts¶

Stacked facts support the same sparse column syntax as anonymous tables. Mark optional columns with ? in the header, then use _(col @ val) fills in data rows:

config(
  key, value, description?, deprecated?
  --------------------------------------
  "timeout",  30 ;
  "retries",  3,   _(description @ "max retry count") ;
  "legacy",   1,   _(deprecated @ "true")
)

This is equivalent to the fully-expanded form:

config(
  key, value, description, deprecated
  ------------------------------------
  "timeout",  30,   null,                null ;
  "retries",  3,    "max retry count",   null ;
  "legacy",   1,    null,                "true"
)

Sparse columns reduce noise in metadata definitions and configuration facts where most rows only set a few optional properties.

Citation Rules¶

A citation is the shorthand invocation of a zero-argument value function: :greeting reads the function greeting, whether it was defined as greeting:() :- "hello" or as the paren-less greeting :- "hello". It is the same application as greeting:(); nothing distinguishes them after parsing.

esc :- char:(27)
hue :- 31
red:(s) :- :"{:esc}[{:hue}m{s}{:esc}[0m"

A citation composes wherever a value does — in arithmetic, in a template hole, as an argument. Qualified, the mark belongs to the leaf, after the namespace and its dot: ansi.:esc, the same function as ansi.esc:(). The mark never precedes the path: :ansi.esc is not a spelling.

A citation is a reference to a defined function and can alias another citation’s value; contrast the symbol ::name, which is a self-valued constant needing no definition.

Function Rules¶

Functions are relations with a functional dependency between input and output columns. Where a relation may have many outputs for a given input, a function has exactly one. Delightql supports several syntactic forms for defining functions, each suited to different use cases.

Stacked Notation (Named Case)¶

The stacked form defines functions as lookup tables with explicit input-output mappings:

title_kind(
  title          -> kind
  ------------------
  "IT Manager"   -> "tech";
  "IT Staff"     -> "tech";
  _              -> "other"
)

The -> separates inputs (left) from outputs (right). The header row names the columns; subsequent rows provide the mappings. The _ matches any input not explicitly listed.

Despite the visual similarity to anonymous table stacked notation, this is an assertion-mode construct – it defines a reusable function, not inline data.

As in anonymous tables, the dashed separator and @ are interchangeable, so a short mapping fits on one line:

region(country -> region @ "USA" -> "home"; "Canada" -> "home"; _ -> "abroad")

customer(*) |> (last_name, country, region:(country) as region)

A function is defined in one form only: stacked notation and rule clauses (region:(c) :- …) cannot be mixed for the same name.

Invocation:

employee(*) |> +(title_kind:(title) as kind)

SELECT *,
  CASE title
    WHEN 'IT Manager' THEN 'tech'
    WHEN 'IT Staff' THEN 'tech'
    ELSE 'other'
  END AS kind
FROM employee;

Multi-column inputs:

tax_rate(
  country, state -> rate
  --------------------------
  "USA", "CA"    -> 0.0725;
  "USA", "TX"    -> 0.0625;
  "Canada", "ON" -> 0.13;
  "Canada", "AB" -> 0.05;
  _              -> 0.0
)

invoice(*) |> +(tax_rate:(billing_country, billing_state) as tax)

Rule Form¶

For computed functions, use the rule form:

plus_two:(x) :- x + 2

invoice(*) |> +(plus_two:(total) as incremented)

SELECT *, total + 2 AS incremented FROM invoice;

The body is any domain expression. The function returns its evaluation.

Zero-Argument Functions and Citations¶

A function with no parameters is defined with an empty head or, as shorthand, with no parentheses at all. The two spellings define the same kind of value function:

greeting:() :- "hello"
tab :- char:(9)

Either is invoked as an ordinary application or, as shorthand, as a citation — the name marked with a leading ::

artist(*) |> +(greeting:() as g, :tab as sep)

The body is any domain expression, not only a literal. The usual arity and clause laws apply: greeting:("x") refuses, and defining greeting twice without guards refuses whichever spelling each definition used.

A qualified citation puts the mark on the leaf, where the application form puts its own mark: lib::text.:greeting invokes the same function as lib::text.greeting:(). :lib::text.greeting is not a spelling.

Disjunctive Clauses¶

Multiple clauses create conditional functions. Clauses are evaluated top-to-bottom; first match wins:

fizzbuzz:(n | (n % 15) = 0) :- "fizzbuzz"
fizzbuzz:(n | (n % 3) = 0)  :- "fizz"
fizzbuzz:(n | (n % 5) = 0)  :- "buzz"
fizzbuzz:(n)              :- n

The guard condition follows | in the head. If the guard fails, the next clause is tried.

_(n @ 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15) |> (fizzbuzz:(n) as result)

SELECT
  CASE
    WHEN n % 15 IS NOT DISTINCT FROM 0 THEN 'fizzbuzz'
    WHEN n % 3 IS NOT DISTINCT FROM 0 THEN 'fizz'
    WHEN n % 5 IS NOT DISTINCT FROM 0 THEN 'buzz'
    ELSE n
  END AS result
FROM (SELECT 1 AS n UNION ALL SELECT 2 UNION ALL SELECT 3
      UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6
      UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
      UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12
      UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15);