Reactive and dataflow programs using SQLite — Part 2: Prolog as a database

In the last blog post we saw how Prolog deals with logical statements. These statements express simple truths, e.g. legs(chair, 4) simply states that a chair has four legs. There may also be a condition involved, e.g. language(File, python) :- extension(File, '.py') states that File is a Python program if its file extension is .py (not strictly correct, of course). We also saw a simplified version of how Prolog answers queries about these statements or givens, starting from the query itself and following backwards to facts.

Looking at logical predicates through a slightly different lens, an analogy to databases begins to emerge. The fact legs(chair, 4) can be viewed as stating that the tuple (chair, 4) belongs to the set of observations about the number of legs. A list of all such observations would now start to look very similar to a database table. In fact, let’s try this in sqlite.

CREATE TABLE legs (object TEXT, count INTEGER);
INSERT INTO legs VALUES ('chair', 4), ('table', 4), ('tripod', 3);
SELECT * FROM legs WHERE count = 4;

The output would be exactly the same as if we had ask Prolog legs(Object, 4), that is

object	count
chair	4
table	4

Likewise, if we compiled a list of our files and their extensions the result would be a table extension with columns like file and ext.

CREATE TABLE extension(file TEXT, ext TEXT);
INSERT INTO extension VALUES 
  ('README.txt', '.txt'),
  ('img.gif', '.gif'),
  ('main.py', '.py');

The clause language(File, python) :- extension(File, '.py') would then be equivalent to

CREATE VIEW language(file, lang) AS
  SELECT file, 'python' from extension WHERE ext = '.py';
SELECT * FROM language;

file	lang
main.py	python

Here I’ve used a view so the query results will always be updated and consistent with the extension table. We are not far from having a reactive system.

The main differences between a database like sqlite and Prolog are

1. In a DB, data flows forward from facts to conclusions while in Prolog the default mode of execution is working backwards from query and checking if and how it can be demonstrated using a subset of known facts. It would be less natural, though not impossible, in Prolog to retrieve additional answers to a query when new data is added, i.e. to react to new input.
2. Tables in a DB list objects satisfying a relation, no more or less, with all potentially side-effecting parts of the language handled by INSERT, UPDATE, etc. statements. In other words relations simply supply logic side of the language. Prolog predicates can also describe a relation, but they can also execute arbitrary code, commit or retract facts, and modify execution flow (like the cut predicate, which interrupts the search for further answers).

In the next blog post we will look at languages like Datalog that bridge these differences by bringing the Prolog’s syntax and focus on logic closer to the semantics of a relational database.