We have discussed the logical meaning of

two_hop(from, to) :-
    road(from, via),
    road(via, to).

Quick recap?

In computer science, a program can have several useful accounts of its meaning. So far we have used the logical, or model-theoretic, account of a CQ.

It tells us what the correct result must be. But as programmers, knowing the required output is only the first step. We also want to implement it.

First inspect what the logical account does not say. A valuation for two_hop has the form

{from -> a, via -> b, to -> c}.

Which variable does the logical semantics assign first?

Let

C1 = road(from, via)
C2 = road(via, to)

and recall that the instance contains

road("Logan", "Salt Lake City")
road("Salt Lake City", "Provo")
road("Logan", "Provo").

It contains no road whose source is "Provo".

The valuation

v = {
    from = "Logan",
    via  = "Salt Lake City",
    to   = "Provo"
}

satisfies \(C_1\land C_2\). Its restrictions are

and

They agree on via, and \(v_1\cup v_2=v\). How should we classify \(v_1\) relative to the local schema {from, via}, and relative to the full body schema {from, via, to}?

One successful \(v\) gives only local matches that extend to that full valuation. To collect every local match, for any sub-body \(C\) let

For example,

d = {from = "Logan", via = "Provo"}

belongs to \(\operatorname{Val}_I(C_1)\), but no tuple in \(\operatorname{Val}_I(C_2)\) assigns "Provo" to via. Must \(d\) extend to a valuation satisfying the full body?

At tuple level, the restrictions of a complete valuation agree on shared variables and recombine by union. Natural join lifts that operation to sets: it keeps compatible tuple pairs and emits their unions.

Forward, every valuation satisfying \(C_1\land C_2\) restricts uniquely to compatible members of \(\operatorname{Val}_I(C_1)\) and \(\operatorname{Val}_I(C_2)\). Conversely, compatible members have one well-defined union, and that union satisfies both sub-bodies. Is join merely an analogy for conjunction here?

What if \(C_1\) and \(C_2\) share no variables?

Use the concrete query

three_hop(from, to) :-
    road(from, x),
    road(x, y),
    road(y, to).

Let

and

Because natural join is binary, give two fully parenthesized expressions that combine all three atom relations.

Expand either expression using the natural-join definition. Both contain exactly the unions \(e_1\cup e_2\cup e_3\), where \(e_i\in E_i\) and the three tuples agree on every shared variable. Therefore

This is associativity. The compatible-pair condition is also symmetric in its two inputs, which gives commutativity. What changes between the two three_hop expressions?

This is the reason relational algebra is a useful bridge. Logic does not choose an order. The algebra does not choose one either, but its laws permit a compiler to choose parentheses while preserving meaning.

Both atoms read the same road relation, whose attributes are src and dst, but their variables need the schemas {from, via} and {via, to}. We relabel the input attributes for each occurrence. This operation is renaming:

E1 := δ[src→from, dst→via](road)
E2 := δ[src→via, dst→to](road).

A constant or repeated variable imposes a local condition within one atom:

road("Logan", to)
edge(x, x).

Should those equalities be enforced by joining two atom relations?

The one-relation filtering operation is called selection.

So shared variables across distinct atom relations cause joins; equalities inside one atom cause selections.

Now consider

edge_from_capital(a, b) :-
    edge(a, b),
    capital_city(a).

Let

Their schemas are {a, b} and {a}. What does joining with \(C\) add?

A join whose right input only filters existing tuples without adding attributes has a useful narrower form called semijoin.

Because the schema {a} of \(C\) is already contained in the schema {a, b} of \(E\),

Both expressions denote exactly the edges whose first endpoint is a capital city.

Return to two_hop. Its complete body-valuation relation has schema {from, via, to}. The separate result relation has schema {from, to}.

New answers accumulate there by set union. If the same answer is derived twice, should the destination contain it twice?

Then try

two_hop := two_hop ∪ (E1 ⋈ E2).

Union exposed the problem. Projection keeps the requested attributes, here from and to, while discarding via.

Now state the result and its accumulation.

This changes \(H\), not road. For a standalone CQ, \(H\) begins empty and remains separate from the input. The same union form will later accumulate rule consequences in Datalog.

Complete the two local atom translations now that projection is available.

The examples expose the general pattern. For an atom \(A=r(t_1,\ldots,t_k)\), select constants and equal repeated positions. Project one representative position for each distinct variable, then rename those representatives with the variable names. The resulting expression \(E_A\) denotes exactly \(\operatorname{Val}_I(A)\).

For three_hop, let \(E_1,E_2,E_3\) be the three atom expressions. The CQ body is one conjunction, but the algebra has no three-input join constructor. What must its syntax record?

Because each \(E_i\) denotes \(\operatorname{Val}_I(A_i)\), the conjunction-as- join law proves by induction on \(T\) that every \(J_T\) denotes the complete body-valuation relation. Projection then keeps the head variables. Thus every permitted tree \(T\) satisfies

for every permitted input instance \(I\).

What has the equivalence proof deliberately left open?