I've put an introductory Prolog tut for SQL programmers on Swish

https://swish.swi-prolog.org/p/sql2prolog.swinb

I’ve translated the basic SQL select examples used by Stanford University’s database MooC in the Swish note above.

I’m hoping to get more advanced, making insertions and updates etc. But that’s it for now.

Any suggestions on improvements welcome.

To add my 2 cents …

Its very nice to see SQL and Prolog side-by-side …

But, so far the student will ask why go through the effort to use Prolog if SQL does it all – and SQL is much more pervasively used.

I would look out for examples that can’t be done with SQL, or are much more elegant in Prolog.

I think recursive (graph) structures are hard to handle in SQL but are a natural fit with Prolog.

Was expecting to hear the term Datalog ? This is also fun in SQL:

WITH RECURSIVE temp (n, fact) AS 
(SELECT 0, 1 -- Initial Subquery
  UNION ALL 
 SELECT n+1, (n+1)*fact FROM temp -- Recursive Subquery 
        WHERE n < 9)
SELECT * FROM temp;
2 Likes

Nice.

I didn’t know that SQL supports recursive calls.

I always thought that Datalog is an “extension” of SQL that supports recursion but no composite terms and functions – to avoid infinite recursions.

So, where does expressivity of SQL end and Prolog (and Datalog) continues …

However important differences between deductive databases and logic programming:

  • Order sensitivity and procedurality: In Prolog, program execution depends on the order of rules in the program and on the order of parts of rules; these properties are used by programmers to build efficient programs. In database languages (like SQL or Datalog), however, program execution is independent of the order of rules and facts.
  • Special predicates: In Prolog, programmers can directly influence the procedural evaluation of the program with special predicates such as the cut, this has no correspondence in deductive databases.
  • Function symbols: Logic Programming languages allow function symbols to build up complex symbols. This is not allowed in deductive databases.
  • Tuple-oriented processing: Deductive databases use set-oriented processing while logic programming languages concentrate on one tuple at a time.

https://en.wikipedia.org/wiki/Deductive_database

But you can relax some of the points. For example function symbols, you could also allow non-scalar columns in a deductive database system. And if you add some transaction scripting to SQL, you also get results that have a less logical direct reading.

I think this is the only item that relates to expressivity – indicating that Prolog can say/do more than SQL.

Btw, Conceptbase, a deductive database system, based on Prolog/Datalog, seems to have a notion of compositionality through parameterized combination of query classes.

I always thought that Datalog is an “extension” of SQL that supports recursion but no composite terms and functions – to avoid infinite recursions.

Datalog isn’t an extension of SQL, but rather a subset of Prolog. One of the issues I haven’t gone into is implementation, which is makes competing against open source projects like Postgresql (which has enormous commercial support from big banks) or commercial products like Oracle (which kidnapped Postgresql’s main open source competitor, MySQL, to kill it) fairly impossible.

Datalog strips stuff from Prolog which simply can’t be implemented in a system designed to handle enormous amounts of data, not just stuff small enough to fit into dynamic memory.

Anyways, I’m finding it very educational to revise my SQL basics using Prolog/Datalog. Will expand by tutorial tomorrow.

Yes. That’s why i put it into quote “extension” … i meant it, in the sense of providing capabilities that go beyond SQL’s ability to describe queries

Not the only item, there is for example also:

Any Datalog program P must satisfy the following safety conditions.

  • Each fact of P is ground.
  • Each variable which occurs in the head of a rule of P
    must also occur in the body of the same rule.

See also:

What You Always Wanted to Know About Datalog
Ceri et. al. - 1989
https://www.researchgate.net/publication/3296132

In pure Datalog, the negation sign ‘‘¬” is not allowed to appear.

In the old times researchers wrote Datalog¬ to indicate that negation is also allowed.

Datalog¬ covers SQL such as:

SELECT ProductID,
       ProductName
FROM   Products p
WHERE  NOT EXISTS (SELECT *
                   FROM   [Order Details] od
                   WHERE  p.ProductId = od.ProductId) 

And you can map it to Prolog negation as failure.

One can write this SQL statement in DES and see its translation to (an extension of) Datalog:

DES> /show_compilations on
DES> WITH RECURSIVE temp (n, fact) AS 
(SELECT 0, 1 -- Initial Subquery
  UNION ALL 
 SELECT n+1, (n+1)*fact FROM temp -- Recursive Subquery 
        WHERE n < 9)
SELECT * FROM temp;

Info: SQL statement compiled to:

answer(A,B) :-
  temp(0,1)
  /\
  (temp(C,D) :-
    temp(E,F),
    E<9,
    C=E+1,
    D=(E+1)*F)
  =>
  temp(A,B).

answer(temp.n:int,temp.fact:int) ->
{
  answer(0,1),
  answer(1,1),
  answer(2,2),
  answer(3,6),
  answer(4,24),
  answer(5,120),
  answer(6,720),
  answer(7,5040),
  answer(8,40320),
  answer(9,362880)
}
Info: 10 tuples computed.          

Curiously, this translation uses hypothetical reasoning for solving the CTE (Common Table Expression in SQL jargon for referring to the local view declaration). This translation was made for the sake of experimenting with this kind of reasoning, where the fact temp(0,1) and the rule temp(C,D) :- temp(E,F), E<9, C=E+1, D=(E+1)*F are assumed in order to solve the goal temp(A,B) (the symbol => is known as embedded implication in hypothetical Datalog). Note also that, since terms are not allowed, a goal such as C=E+1 in this particular system evaluates the arguments of the equality before unifying them.

The more expected translation of the original SQL statement is got from another (quasi) equivalent formulation:

DES> CREATE VIEW temp (n, fact) AS 
(SELECT 0, 1 -- Initial Subquery
  UNION ALL 
 SELECT n+1, (n+1)*fact FROM temp -- Recursive Subquery 
 WHERE n < 9);

Info: SQL statement compiled to:

temp(0,1).
temp(A,B) :-
  temp(C,D),
  C<9,
  A=C+1,
  B=(C+1)*D.

This SQL syntax for recursive queries seems (to me) more natural, though a view must be created for the self-reference. It is not supported in the standard.

We have proposed students to solve SQL puzzles for fun, and wrote a paper around this:
Experiencing Intuitionistic Logic Programming in SQL Puzzles

1 Like

I’ve just expanded it to work through union and intersection, and I’ve found the Prolog versions really nifty, and led me to some enlightenment on the relation between set and logic theory.

Union

select cName as name from College
union
select sName as name from Student;
college(Name, _, _) ; student(_, Name, _, _). 

Intersection

select sID from Apply where major = 'CS'
intersect
select sID from Apply where major = 'EE';
apply(SID, _, 'CS', _) , apply(SID, _, 'EE', _)

I recall reading a history of Augustus De Morgan which said what are commonly known as De Morgan’s laws didn’t originally apply to logic, but to set theory. (Furthermore, he never claimed to have thought of them first, but introduced them to the west by studying eastern mathematics).

What these illustrate is that A ∪ B can generally be replaced by A ∨ B, and A ∩ B by A ∧ B, which was news to me.

I think the formalization of set union in set theoretic terms shows the connection – if you had this in mind:

A ∪ B = {∀ t / t ∈ A ∨ t ∈ B}

I think what is left implicit in your code is the forall – SQL returns all tuples whereas in Prolog you ask to request them one by one.

DeMorgan would be ~(A v B) = ~A & ~B. But you might like this Book, used it costs only $6:

Unbenannt

https://www.amazon.com/Course-Database-Systems-Jeffrey-Ullman/dp/0138613370

This page is also of potential interest:

Projects

We have several complete CS145 Sample Projects available.

Materials from Second Edition Deleted in Third

  1. Object-Oriented Query Languages (old Sections 4.1, 9.1, 9.2, and 9.3).
  2. Recursive Datalog (old Section 10.3).

http://infolab.stanford.edu/~ullman/fcdb.html

To demonstrate DeMorgan you could use SQL MINUS.
You could for example demonstrate that (A \ (B u C)) = (A \ B) n (A \ C).
SQL MINUS like SQL NOT EXISTS requires Datalog¬.

Jennifer Widom gives the database courses I’m redoing in Prolog which my notes are based on. I’ve also found Jeffrey Ullman to be a brilliant teacher. I did his MooC on automata.

Good! Jeffrey Ullman had an older version of the book which dates back to 1982. It already explained logic reading of database queries back then.

LEFT OUTER JOINS are funny, I came up with a solution
that uses soft cut. Take this data:

enrolled(anna, 1993).
enrolled(bob, 1994).
enrolled(carla, 1993).

rector(1989, paul).
rector(1990, peter).
rector(1991, jack).
rector(1992, jill).
rector(1993, hector).
rector(1994, nestor).

And then you can query:

?- rector(Y,Z), (enrolled(X,Y) *-> true; X = null), write(Y-Z-X), nl, fail; true.
1989-paul-null
1990-peter-null
1991-jack-null
1992-jill-null
1993-hector-anna
1993-hector-carla
1994-nestor-bob
true.

But now we are into partial expressions and 3-valued logic, possibly to the dismay of peter ludeman. The data didn’t have any null value, but the outer join makes use of null values to build its result.

But please don’t just write the atom null there! :wink: One possible solution is to use [] for this, since it isn’t an atom but atomic. It still compares equal to itself, though, which is a problem.

You can use Datalog¬ instead of soft cut, it might also produce NULL values:

?- rector(Y,Z), (enrolled(X,Y); \+ enrolled(X,Y), X = null), 
    write(Y-Z-X), nl, fail; true.
1989-paul-null
1990-peter-null
1991-jack-null
1992-jill-null
1993-hector-anna
1993-hector-carla
1994-nestor-bob
true.

But full outer join gets nasty either way. Suggested value for null, the empty atom ‘’:

When to use NULL and when to use an empty string?

There is one DBMS namely Oracle which doesn’t allow to
choose it’s users between NULL and ‘’.
https://dba.stackexchange.com/a/138

Benefit, you are Oracle compatible.

Edit 23.02.2021:
BTW: SQL UNION can also produce null values, unless you have a SQL cursor that gives multiple different meta data. Here is an example, not that the impression emerges that NULL values are particular to Dalalog¬, pure Datalog might also be bugged with it:

SELECT "City", "Country", "Continent" from table1  
UNION  
SELECT "City", "Country", NULL AS "Continent" from table2 

https://stackoverflow.com/a/39766372/502187

There is a trick, take this example:

table1(a, b, c).               table2(a, b, d).
table1(e, [], f).              table2(e, [], g).
table1(h, i, j).               table2(h, i, k).
table1(l, [], m).              table2(l, x, n).
table1(o, y, p).               table2(o, [], q).

Now SQL wants me to compute:

SELECT Table1.Col1, Table1.Col2, Table1.Col3, Table2.Col4
FROM Table1 INNER JOIN Table2
ON Table1.Col1 = Table2.Col1 
AND Table1.Col2 = Table2.Col2

Col1:      Col2:     Col3:     Col4:
a          b         c         d
h          i         j         k

Prolog refuses somehow to do the right thing:

?- table1(X,Y,Z), table2(X,Y,T), write(X-Y-Z-T), nl, fail; true.
a-b-c-d
e-[]-f-g
h-i-j-k
true.

Well you can just try this, it is the Prolog equivalent to SQL join with NULL:

?- table1(X,Y,Z), table2(X,Y,T), Y\==[], write(X-Y-Z-T), nl, fail; true.
a-b-c-d
h-i-j-k
true.

This is because []=X and X=[] anyway fail for X an atom.
So you only need to filter []=[].
You might also try dif/2:

?- dif(Y,[]), table1(X,Y,Z), table2(X,Y,T), write(X-Y-Z-T), nl, fail; true.
a-b-c-d
h-i-j-k
true.