-- Whither Outer?
  SELECT * FROM father OUTER UNION widgets;

The prolog semicolon is the syntax for the logical OR. Its usage in the language is rare, but this is not to say that the disjunction it represents in the language is rare. Multi-clause and multi-fact disjunction is Prolog’s preferred mechanism.

It was in trying to understand the meaning of this syntax in a query that I came across an opportunity to revisit SQL’s classic UNION operator – more specifically the strict requirement that two relations so unioned be “union compatible”. This led to a discovery of alternate universes where the SQL standard could have compelled the introduction of different flavors of UNION: namely the OUTER UNION and the CORRESPONDING UNION.

Prolog’s logical AND, represented as a comma, maps directly to the concept of a SQL JOIN. This is the multiplication operator and is equivalent to the multiplication of algebraic data types.

Prolog’s logical OR, represented as a semicolon, is simultaneously rare and common: rare because it seldom shows up in code or queries, and common in that programmers typing semicolon on the REPL are implicitly invoking OR (or UNION) to fetch the next row.

?- father(Parent,Child).
   Parent = tom, Child = bob
;  Parent = bob, Child = ann
;  Parent = bob, Child = pat.
?-

Prolog’s logical OR maps to the concept of a SQL UNION. This is the sum operator and is roughly equivalent to the sum of algebraic data types.

Let’s take a closer look at what is happening when we type in

?- father(Parent,Child).

at the Prolog REPL because it is this usage of the semicolon which will inspire us to ask what happens in different circumstances.

The Prolog engine satisfying this query has done a tree search to discover what values of Parent and Child would make this statement true. It discovers one row and tells you so:

   Parent = tom, Child = bob

but then it gives you the opportunity to get more rows by hitting the semicolon. This returns the next row (like a database cursor). Mashing semicolon on the keyboard will eventually return all rows that the Prolog engine could use to prove its case. But if you notice the similarity of the output to the results returned by a database query where the comma separates dimensions, and the semicolon separates rows, then you’ve already understood the point.

Running a SQL

select Parent,Child from father;

and getting all rows printed is equivalent to running the Prolog query and mashing the semicolon to completion.

So in one sense we already see how the semicolon acts like a UNION. The first row with a schema of Parent and Child is unioned to the next row with the exact same schema.

But what happens when we use the semicolon in the query itself:

?- father(Parent,Child) ; mother(Parent,Child).
   Parent = tom, Child = bob
;  Parent = bob, Child = ann
;  Parent = bob, Child = pat  % end of father rows
;  Parent = pam, Child = bob
;  Parent = theresa, Child = pat
;  Parent = theresa, Child = bob.   % end of mother rows

Here we really see the UNION shining because when we queried for father and or mother we used the same logical variables Parent and Child.

This is definitely equivalent to

select Parent,Child from father
  UNION ALL
select Parent,Child from mother;

Now, let’s try adding a third functor to the query separated by the semicolon:

?- father(Parent,Child) ; mother(Parent,Child); male(Child).
   Parent = tom, Child = bob
;  Parent = bob, Child = ann
;  Parent = bob, Child = pat
;  Parent = pam, Child = bob
;  Parent = theresa, Child = pat
;  Parent = theresa, Child = bob
;  Child = tom
;  Child = bob.

We can make sense of this in SQL too if we pad our columns with null:

select Parent,Child from father
  UNION ALL
select Parent,Child from mother;
  UNION ALL
select null as Parent,Child from male;

You can also see this null as the Greek letter omega (ω) in the screenshot of the diagram at the top of the page where Codd introduced the idea of OUTER UNION and used ω to pad the empty cells.

So why can’t we do that in SQL? Why do we have to pad the column ourselves instead of asking SQL to do it for us?

The answer is historical and unearths two separate but orthogonal semantics that SQL has enforced but are perfectly worthy of generalizing:

• How do we address our columns? In most SQLs this is only by ordinality
• What relations do we allow to be vertically concatenated? In most SQLs this is only those with the same number of dimensions

The answer to the first one allows us to imagine an alternate universe where we could UNION by column names instead of ordinality, i.e. match up two tables by their corresponding columns.

-- This is imaginary SQL
  SELECT * FROM father UNION CORRESPONDING mother;

-- this is the standard that
-- nobody actually implements:
-- SELECT * FROM father UNION CORRESPONDING select * from mother;

The answer to the second allows us to imagine an alternate universe where we could UNION without requiring the same schema, i.e. pad the non-matching columns as we concatenate any two rectangular shapes into a common schema.

-- This is imaginary SQL
  SELECT * FROM father OUTER UNION widgets;

While it was Prolog’s semicolon that first inspired me to generalize the union operator for delightql’s set operators , I was pleased to see that the issue had been debated in the land of the SQL standard’s committee.

Fun fact, the CORRESPONDING keyword is actually in the SQL standard and allows the UNION of corresponding columns but drops (not null-pads) the un-shared columns. It is in this way that these orthogonal concerns can sometimes intersect.

Only a few vendors implement the CORRESPONDING functionality and a different one, duckdb, has UNION BY NAME which does null-pad – exactly what was in Codd’s OUTER UNION proposal.

And another fun fact: there was an old SQL-92 artifact called the UNION JOIN which assumed no columns were corresponded by name or ordinality and padded all columns from both relations.

I love pushing at the edges of a technology and looking back at its history. That even Codd himself suggested a utility for a possible OUTER UNION is probably a revelation to some people – it was to me.

I cannot help but link to this web posting by Hugh Darwen who was there during the early years. Among other things he laments that our SQL UNION uses column ordinality and that it could have been based on the column names like in most other places in SQL.

In retrospect, it seems to me a bit strange that this was an open issue at all. Codd’s model required that every attribute value (in the tuples of a relation) be explicitly accessible. It also required that no significance be attached to any ordinal positions of attributes within a relation. In other words, every attribute must be referenceable, but not by its ordinal position. What options remain, if ordinal position is excluded? The ISBL team probably did not think their idea of using names to be very remarkable. The System R team decided instead to violate the model and use ordinal position anyway—a decision that, when I learned about it, I could put down only to careless study of the model or careless consideration of its implications.

Sample Prolog database for this post

% --- Facts ---
parent(tom, bob).
parent(pam, bob).
parent(bob, ann).
parent(bob, pat).
parent(theresa, pat).
parent(theresa, bob).

male(tom).
male(bob).
female(pam).
female(ann).
female(theresa).
female(pat).

% --- Rules ---
% X is the father of Y if X is a parent of Y and X is male.
father(X, Y) :-
    parent(X, Y),
    male(X).

% X is the mother of Y if X is a parent of Y and X is female.
mother(X, Y) :-
    parent(X, Y),
    female(X).