Prolog Cookbook

  1. Documenting, testing, and moduling
  2. Classical Logic
    1. Negation
      1. Not
      2. Difference
      3. Fill Values
      4. De Morgan's Law
    2. Conjunction
      1. And
      2. Intersection
      3. Inner Join
      4. Product
      5. Series
    3. Disjunction
      1. Or
      2. Union
      3. Outer Join
      4. Sum
      5. Parallel
    4. Implication
      1. Proofs
    5. Equivalence
  3. Automata
  4. Graph Traversal
    1. Depth First
    2. Breadth First
    3. Transitive Closures
  5. Route Finding
  6. Puzzle Solving


By Robert Laing

Once again, lets use Stanford University dean Jennifer Widom’s basic SQL examples from her college applications data as an illustration.

Which students applied for ‘CS’ and ‘EE’?

In what I’ve called copula notation, conjunction is written p ∧ q, which is a handy mnemonic that its set equivalent is P ∩ Q. That logic has a spiky version of set theory’s rounded symbol we’ll also encounter in disjunction and implication.


In the next section intersection we’ll do this the easy way with SQL’s INTERSECT operator:

SELECT sid FROM apply WHERE major = 'CS'
SELECT sid FROM apply WHERE major = 'EE'

Which produces the set {123, 345}. Since ‘EE’ is a subset of ‘CS’, ‘CS’ ∩ ‘EE’ = ‘EE’. That also means ‘EE’ ⇒ ‘CS’ as I’ll get to in implication.

For now, lets just use AND.

FROM apply AS a1, apply AS a2
WHERE a1.sid = a2.sid AND a1.major = 'CS' AND a2.major = 'EE'
ORDER BY a1.sid;

Subquery in WHERE clause

Another way of writing anded propositions is using IN in a WHERE subquery.

FROM apply
WHERE major = 'CS' 
AND sid IN (SELECT sid FROM apply WHERE major = 'EE')

For fans of Victorian syllogism, SQL allows = ANY(subquery) as a synonym for IN (subquery).

Subquery in FROM clause

One of the rules of relational algebra listed by Al Aho and Jeff Ullman is called selection splitting:

σA AND B(R) = σAB(R)) = σBA(R)).

In SQL that translates into Subqueries in the FROM clause.

FROM (SELECT sid FROM Apply WHERE major = 'CS') AS a1, Apply
WHERE a1.sid = Apply.sid AND major = 'EE';


In Prolog, this query can be written:

order_by([asc(SID)], distinct(SID, (apply(SID, _, 'CS', _), apply(SID, _, 'EE', _)))).

Which students applied for ‘CS’ and ‘history’?

?- apply(SID, _, 'CS', _), apply(SID, _, history, _).

Short answer, none, ie we get the empty set {}, which in Prolog equates to false and in SQL to NOT EXISTS.

This is a hint how to find all disjointed sets.

Which students applied for ‘CS’ and ’logic’?

?- apply(SID, _, 'CS', _), apply(SID, _, logic, _).

In this case B is the empty set since logic isn’t among the majors in the example database. Given the importance of logic in software coding, digital circuitry, modern life in general… it’s a bit alarming that the subject appears to have fallen out of modern schooling.

Anyways, this example is intended to show that attempting an intersection with an empty set is the set equivalent of multiplying by zero, ie A ∩ Ø = Ø, a reminder conjunction equates to product.

In the next section, I’ll show how AND is related to intersection.